带强制工期的双机开放车间排序问题

Two Machines Open Shop Scheduling with Identical Deadline

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

This paper discusses the problem in which n jobs with common deadline have to be processed on two machines open shop considering the idle insert.The objective is to find a job sequence and determine jobs＇ starting times so as to minimize the maximum earliness.Since tardy jobs are prohibited,it＇s possible that there is no feasible sequence for the problem.We consider the feasibility primarily.If the problem is feasible,we first pre-determine a sequence and develop an algorithm to compute jobs＇ starting times to make jobs process as late as possible.Then,a polynomial time algorithm is developed to achieve optimality through adjusting the first processing job on the two machines based on the pre-determined sequence.