Single-machine scheduling with preventive periodic maintenance and resumable jobs in remanufacturing system  

预防性周期维护下考虑可中断工件的再制造单机调度(英文)

作　　者：刘碧玉[1,2] 陈伟达[1] 

机构地区：[1]东南大学经济管理学院,南京211189 [2]安徽工业大学管理科学与工程学院,马鞍山243000

出　　处：《Journal of Southeast University(English Edition)》2012年第3期349-353,共5页东南大学学报（英文版）

基　　金：The National Natural Science Foundation of China (No.70971022,71271054);the Scientific Research Innovation Project for College Graduates in Jiangsu Province(No.CXLX_0157);the Scientific Research Foundation of the Education Department of Anhui Province(No.2011sk123)

摘　　要：A single-machine scheduling with preventive periodic maintenance activities in a remanufacturing system including resumable and non-resumable jobs is studied.The objective is to find a schedule to minimize the makespan and an LPT-LS algorithm is proposed.Non-resumable jobs are first scheduled in a machine by the longest processing time（LPT） rule,and then resumable jobs are scheduled by the list scheduling（LS） rule.And the worst-case ratios of this algorithm in three different cases in terms of the value of the total processing time of the resumable jobs（denoted as S2） are discussed.When S2 is longer than the spare time of the machine after the non-resumable jobs are assigned by the LPT rule,it is equal to 1.When S2 falls in between the spare time of the machine by the LPT rule and the optimal schedule rule,it is less than 2.When S2 is less than the spare time of the machine by the optimal schedule rule,it is less than 2.Finally,numerical examples are presented for verification.研究预防性周期维护策略下再制造系统中可中断和不可中断2类工件的单机调度问题.以最小化完工时间为目标,提出了LPT-LS算法,该算法首先按LPT(longest processing time)规则安排不可中断工件,然后按LS(list scheduling)规则安排可中断工件.并根据可中断工件的总加工时间(记为S2)分3种情况证明了该算法的最坏情况比,结论如下:当S2大于按LPT规则安排不可中断工件后机器的空闲时间时,最坏情况比为1;当S2介于分别按LPT规则和OPT(最优排序)规则安排不可中断工件后机器的空闲时间之间时,最坏情况比小于2;当S2小于按OPT规则安排不可中断工件后机器的空闲时间时,最坏情况比小于2.最后通过算例验证了结论的正确性.

关 键 词：single-machine scheduling preventive periodic maintenance resumable jobs LPT-LS algorithm 

分 类 号：F273[经济管理—企业管理]