具有退化工件和老化效应的单机可拒绝排序问题  

Single-machine Scheduling with Deteriorating Jobs,Aging Effect and Rejection

作　　者：刘春来[1] 王建军[1] LIU Chun-lai WANG Jian-jun(Institute of Systems Engineering, Dalian University of Technology, Dalian 116023, China)

机构地区：[1]大连理工大学管理与经济学部,辽宁大连116023

出　　处：《运筹与管理》2017年第6期95-101,共7页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71271039;70902033);新世纪优秀人才支持计划资助项目(NCET-13-0082);国家创新研究群体科学基金资助项目(71421001)

摘　　要：研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加工的效率;机器进行维修活动后将恢复到初始状态,老化效应也将重新开始。目标是确定拒绝哪些工件、何时进行维修活动以及接受工件集中工件的次序,以便极小化接受加工工件的最大完工时间与拒绝加工工件总处罚费用的和。证明得到了所研究的问题是NP-难解的,并给出了解决问题的一个全多项式时间近似方案(FPTAS)算法。This paper studies a single-machine scheduling with deteriorating jobs and aging effect under rejection, that is, the actual processing time of a job is the function of its starting time and the position scheduled. At the same time, the producer can reject some jobs by paying the rejection penalty. During the whole processing, the optional maintenance activity is scheduled in order to improve the efficiency. After the maintenance activity, the machine will restore the initial condition; the aging effect will also restart. The objective is to determine which jobs are rejected, when to arrange the maintenance activity and the sequence of the accepted jobs so that the sum of the makespan of the accepted jobs and total rejection penalty of the rejected jobs is minimized. We firstly prove the problem is NP-hard in the strong sense, and then a fully polynomial time approximation scheme is presented.

关 键 词：单机排序 拒绝 维修活动 FPTAS 

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