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

Flow Shop Scheduling with Deteriorating Processing Time and Chains Constraint

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

The two - machine flow shop scheduling problem is considered with Linear processing time and chains constraint in order to minimize the make - span. Under the simple linear deteriorating, nonnegative start and stop lag deteriorating rates are introduced so as to combine jobs and construct eomposlte jobs satisfying precedence relations. Finally, the optimal polynomial algorithm for the two - machine flow shop scheduling problem with chains constraint is given.