带有安装时间与维修活动的单机排序问题  

Single-machine scheduling problemswith setup time and maintenanceactivitie

作　　者：赵玉芳[1] 葛秋利 ZHAO Yufang;GE Qiuli(College of Mathematic and Systems Science,Shenyang Normal University,Shenyang 110034,China)

机构地区：[1]沈阳师范大学数学与系统科学学院,沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2018年第5期402-409,共8页Journal of Shenyang Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(11171050)

摘　　要：考虑带有安装时间与维修活动的单机排序问题。每个工件都有自己的交货期窗口,工件在交货期窗口之前或之后完成都会产生费用。工件在加工之前需要安装时间,安装时间为加工时间的线性函数。维修活动使工件的加工时间缩短,并且维修活动的长度可以通过资源分配减少,考虑维修活动的2种情况:维修活动的长度与已完成工件的加工时间有关;维修活动的长度与维修的位置有关。在维修活动的2种情况下,根据维修活动的不同位置分类讨论,目标是找到交货期窗口的大小和位置,以及带有资源的维修的位置,使得提前费用、延误费用、交货期窗口的位置和长度产生的费用与资源的费用之和最小。证明了该问题在多项式时间内是可解的。Consider the single-machine scheduling problems with setup time and maintenance active.Every job has its own due-window,and the job will generate cost before or after the due-window.Thejob needs setup time before processing,and the setup time is a linear function of processing time.Maintenance active reduces processing time of the job,moreover the length of maintenance activity can be reduced by resource amount allocated,two models associated with maintenance activity are considered,in which the length of maintenance is time-dependent or position-dependent.In both cases of maintenance active,classified according to different locations of maintenance active,the objectiveis to find the size and location of the due-window,the position of maintenance as well as resource amount allocated to it,and minimize a total cost function based on earliness,tardiness,due-window location,due-window size,and resources cost.Prove that the problems are all solvable in polynomial time.

关 键 词：单机排序 维修 交货期窗口 安装时间 多项式算法 

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