强制工期相等的双机流水车间排序问题

讨论了强制工期相等的n个工件在双机流水车间的加工.在允许机器空闲的条件下,寻找一个工件排序,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会不可行排序.先讨论问题的可行性,如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后,给出一个多项式时间算法,在预排序列的基础上,通过调整最先加工的工件来获得最优排序.

Double Machines Flow Workshop Scheduling with Identical Deadline

In the paper, the problem that n jobs are processed with same deadline in double machines flow shop was discussed. Under the condition of permission the idle insert, a job sequence was determined, which minimize the maximum earliness. Since tardy jobs are prohibited, it is possible that there is no feasible sequence for the problem. Firstly, the feasibility of the sequence was considered. If it is feasible, a sequence used as pre-detennined sequence is founded, and an algorithm to calculate the starting times of job as late as possible was developed. Secondly, based on the pre-determined sequence, a polynomial time algorithm was proposed and optimality was achieved through adjusting the first processing job.