带有维修活动和工件可拒绝的单机排序问题  

Due-window scheduling problems with rejection jobs and maintenance

作　　者：陈东[1] 赵传立[1] 

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

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

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

摘　　要：讨论了带有交货期、维修活动和工件可拒绝的单机排序问题,这一问题是将所有的工件分成2个集合,分别是被接受的工件集和被拒绝的工件集。规定每个被接受的工件都有一个待定的交货期,且所有工件的交货期的大小相同。如果工件在交货期内完工,则不产生任何费用,否则工件提前或延误,会产生相应的提前或延误的费用。而对于拒绝工件而言,它的费用只与工件有关。维修活动需要在一个固定的时间长度内完成,排在维修活动之后的工件的加工时间将会减少。这类问题的总费用是2个工件集的费用之和,目标函数是确定被接受工件的最优排序,极小化接受工件和拒绝工件的总费用,该问题在多项式时间可解,在今后的应用中能发挥作用。The authors consider a single machine scheduling with job rejection,due-window and maintenance activity.The scheduling problem is given by partitioning the jobs into a set of accepted and a set of rejected jobs.Every accepted job has an undetermined due-window,but the size of all due-window is identical.There is no cost where the job is completed during the due-window,but there is cost where the job is completed prior or after the due-window.The cost of the rejected jobs depend on the rejected jobs.The maintenance activity requires a constant time,and after that the processing time of the job will be reduced.The cost of this problem is the sum of two sets jobs.The objective is to determine the optimal sequence of accepted jobs and minimize a total costs including accepted jobs and rejection jobs.Consequently,the problem can be shown to be solved in polynomial time.

关 键 词：排序 单机 维修活动 交货期 拒绝工件 

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