具有学习效应的间歇批生产的单机排序问题  

Single-machine Scheduling Problems with Learning Effects in Intermittent Batch Production

作　　者：杨明明[1] 张淑娟[1] 韩翔凌[1] 

机构地区：[1]曲阜师范大学管理学院,山东日照276826

出　　处：《重庆师范大学学报（自然科学版）》2011年第3期4-9,共6页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.10671108);山东省自然科学基金(No.Y2005A04)

摘　　要：本文研究了目标函数为总完工时间,具有Dejong学习效应和遗忘效应的间歇批生产的单机排序问题。考虑了批与批之间没有学习效应的传递、有部分学习效应的传递和有总的学习效应传递3种模型。首先,在批与批之间没有学习效应传递的模型中,给出了复杂性为O(nlogn)的最优算法。其次,在批与批之间有部分学习效应传递的情形下,对批在机器上的加工次序问题,通过引入0-1变量,把每一批看作一个工件,将其转化为指派问题。并进一步给出了复杂性为O(nlogn+m3)的多项式时间算法。最后,在批与批之间有总的学习效应传递的情形下,证明了每一批中的工件按SPT序排列可使每一批的完工时间达到最小,并对所有批中的工件个数都相等这一特殊情形,给出了复杂性为O(nlogn+m3)的多项式时间算法。In this paper,we study single-machine scheduling problems with Dejong＇s learning and forgetting effects in intermittent batch production.We consider the models of no transmission,partial transmission and total transmission of the Dejong＇s learning effects from batch to batch.The objective of scheduling problems is to minimize the total completion time.Firstly,in the model of no transmission from batch to batch,we provide the polynomial-time optimal algorithm,the complexity is O（nlog n）.In addition,in the model of partial transmission from batch to batch,for the problem of batch sequence on the machine,we introduce 0-1 variable,and the problem can be formulated as an assignment problem.As we all know,an assignment problem exists in the polynomial algorithm,and the complexity of the polynomial algorithm is O（m3）.Further,we give the polynomial-time optimal algorithm,the complexity is O（nlog n＋m3）.Finally,we show that SPT-sequence is the optimal sequence for the jobs within each batch,and present the polynomial time algorithm for the special case that the job numbers of all batches are equal in the problem with the total transmission mod-nomial time algorithm for the special case that the job numbers of all batches are equal in the problem with the total transmission models,and the complexity of the algorithm is O（nlog n＋m3）.

关 键 词：排序 学习效应 单机排序 间歇批生产 

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