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

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

作　　者：胡觉亮[1] 王焕男 蒋义伟[1] 

机构地区：[1]浙江理工大学理学院,杭州310018

出　　处：《浙江理工大学学报（自然科学版）》2014年第1期83-87,共5页Journal of Zhejiang Sci-Tech University(Natural Sciences)

基　　金：国家自然科学基金(11001242;11071220)

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

关 键 词：单台机 时间延迟 总完工时间 算法设计与分析 最优排序 

分 类 号：O233[理学—运筹学与控制论]