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

摘要

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