带时间延迟的极小化总完工时间的单机排序问题

研究工件带有两道工序的单台机排序问题。在该问题中，工件的第一道工序先于第二道工序加工，并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间，目标是极小化所有工件的总完土时间。文章考虑所有工件相同且两道工序的加工时间均为单位时间的情形。通过引入忌一连续加工的概念和分析最优解的性质，根据延迟时间的大小，分别设计了两个算法并证明了算法所得的排序为最优排序。

Single Machine Sequencing Problem of Minimization of Total Completion Time with Time Delay

This paper studies the sequencing problem of single machine with its workpieces having two processes. In this problem, the first process of workpieces is implemented earlier than the second one and the commencement time of the second one and the completion time of the first one should at least have a certain time interval, called as delay time. The objective is to minimize the total completion time of all workpieces. This paper considers situations when all workpieces are the same and the processing time of two processes is unit time, respectively designs two algorithms according to the delay time by introducing the concept of k-continuous process and analyzing the property of optimal solution and proves that the se- quencing obtained by the algorithm is the optimal sequencing.