带有退化、拒绝和不可用区间的恒速机排序

作     者：赵玉芳 富晓双 田野 ZHAO Yufang;FU Xiaoshuang;TIAN Ye

作者机构：沈阳师范大学数学与系统科学学院沈阳110034 北京市第五中学通州校区北京101100 

出 版 物：《沈阳师范大学学报（自然科学版）》 (Journal of Shenyang Normal University:Natural Science Edition)

年 卷 期：2021年第39卷第3期

页      面：224-229页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：辽宁省教育厅科学研究经费项目(LFW202001) 

主　　题：排序 恒速机 退化 拒绝 不可用区间 

摘      要：考虑带有退化工件、拒绝和不可用区间的2台恒速机排序问题,其中一台机器上带有一段固定的不可用区间。该问题以实际生产环境为背景来研究机器的工件调度问题。在此模型中,每个工件的实际加工时间与它的基本加工时间、退化率和开始加工时间有关,工件的实际加工时间是其开始加工时间的线性递增函数,工件可以被拒绝,被拒绝的工件需要支付惩罚成本,在不可用区间内,机器无法加工工件。目标是极小化接受工件的最大完工时间与被拒绝工件的总拒绝惩罚之和。对于这个NP-难问题,在不可用区间前、后及另一台机器上,工件按{aj/bj}不减顺序排列可以得到最优解,通过过程划分的方法,提出了一个完全多项式时间近似策略(FPTAS),最后确定了其时间复杂性为O(n^(6)L^(4)/ε^(3))。