链约束下加工时间恶化的Flow Shop排序问题

摘要

讨论作业具有线性加工时间,作业间具有链约束的两台处理机流水作业排序问题,目标函数为极小化完工时间.在作业加工时间简单线性恶化下,提出作业的非负开始和停止延迟恶化率,构造了满足约束条件的复合作业.在此基础上,给出作业间具有平行链约束的两台处理机流水作业排序问题的最优多项式算法.