带有退化维护活动和工件可拒绝的非同类机排序问题  

Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection

作　　者：高洁 邹娟[1] 隋玉康 张玉忠 GAO Jie;ZOU Juan;SUI Yukang;ZHANG Yuzhong(School of Mathematical Sciences,Qufu Normal University,Qufu 273165,Shandong,China;Institute of Operation Research,Qufu Normal University,Rizhao 276826,Shandong,China)

机构地区：[1]曲阜师范大学数学科学学院,山东曲阜273165 [2]曲阜师范大学运筹学研究院,山东日照276826

出　　处：《运筹学学报》2023年第3期137-149,共13页Operations Research Transactions

基　　金：国家自然科学基金(No.12271295)。

摘　　要：本文研究了带有退化维护活动和工件可拒绝的非同类机排序问题。每台机器至多执行一次退化维护活动,退化维护活动的维护时长是其开始时刻的线性非减函数。工件或者被加工并支付生产成本,或者被拒绝并支付拒绝成本。目标是确定每台机器上退化维护活动的位置与所有接受工件的加工顺序使所有接受工件的排序指标、生产成本及所有拒绝工件的拒绝惩罚之和达到最小。当排序指标为最大完工时间时,我们给出一个最坏性能比为2的近似算法。当排序指标为总完工时间、机器总负载及完工时间的总绝对偏差时,我们指出这三个问题都是在多项式时间内可解的。We study unrelated parallel-machine scheduling problems with deteriorating maintenance activities and job rejection.Each machine has at most one deteriorating maintenance activity throughout the scheduling horizon.The duration of the maintenance activity increases linearly with its starting time.Each job is either processed and it incurs a production cost,or is rejected with a penalty cost.The objective is to find the position of the maintenance activity of each machine and the sequence of the accepted jobs such that the scheduling cost of all accepted jobs plus the total cost of rejecting and processing jobs is minimized.When the scheduling cost is the makespan,we provide an approximation algorithm with worst-case ratio of 2.When the scheduling costs are the total completion time,the total machine load and the total absolute deviation of completion times,we show that the three versions of the scheduling problem can be optimally solved in polynomial time.

关 键 词：排序 非同类机 退化维护活动 近似算法 

分 类 号：O221.7[理学—运筹学与控制论]