本文研究工件处理在无延迟加工(NDP) 约束条件下具有退化效应的在线生产调度问题。工件是以时间在线的方式到达, 同时要求被不可中断地加工, 其加工时间的模型是$p_{j}=a+b_{j}t$ ($a>0$), 目标是极小化最大加权完工时间。针对此问题, 首先利用对手法证明出下界为$1+b_{\max}$, 然后设计出一个竞争比为$2+b_{\max}$ 的在线算法, 最后对于该模型进行数据模拟以验证在线算法的有效性和正确性。
This paper studies the single machine online production scheduling with non-delayed processing (NDP) constraint as well as deterioration. Jobs arriving over time on-line are processed non-preemptive on machine. The model of job processing time is $p_{j}=a+b_{j}t (a>0$). Its objective is to minimize the maximum weighted completion time. Firstly, we derive the lower bound of the considered problem is $1+b_{\max}$ by means of adversary method. Then we design a online algorithm with the competitive ratio of $2+b_{\max}$. Moreover, these online models are simulated to verify the effectiveness and correctness of online algorithm.
[1] Mor B, Mosheiov G. Minimizing total load on parallel machines with linear deterioration [J]. Optimization Letters, 2020, 14(3): 771-779.
[2] Atsmony M, Mosheiov G. Minimizing total completion time with linear deterioration: A new lower bound [J]. Computers & Industrial Engineering, 2022, 163: 107867.
[3] Jiang T H, Zhu H Q, Liu L, et al. Energy-conscious flexible job shop scheduling problem considering transportation time and deterioration effect simultaneously [J]. Sustainable Computing: Informatics and Systems, 2022, 35: 100680.
[4] Chen R B, Yuan J J. Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices [J]. 4OR-A Quarterly Journal of Operations Research, 2020, 18(2): 177-196.
[5] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: A survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.
[6] Gupta J N D, Gupta S K. Single facility scheduling with nonlinear processing times [J]. Computers & Industrial Engineering, 1988, 14(4): 387-393.
[7] Mosheiov G. Scheduling jobs under simple linear deterioration [J]. Computers Operations Research, 1994, 21(6): 653-659.
[8] Liu M, Zheng F F, Wang S J, et al. Optimal algorithms for online single machine scheduling with deteriorating jobs [J]. Theoretical Computer Science, 2012, 445: 75-81.
[9] Ma R, Tao J P, Yuan J J. Online scheduling with linear deteriorating jobs to minimize the total weighted completion time [J]. Applied Mathematics and Computation, 2016, 273: 570-583.
[10] Cheng T C E, Ding Q, Lin B M T. A concise survey of scheduling with time-depent processing times [J]. European Journal of Operational Research, 2004, 152(1): 1-13.
[11] Wang J B, Cheng T C E. Scheduling problems with the effects of deterioration and learning [J]. Asia-Pacific Journal of Operational Research, 2007, 24(2): 245-261.
[12] Li W J, Yuan J J. Single-machine online scheduling of jobs with non-delayed processing constraint [J]. Journal of Combinatorial Optimization, 2021, 41(4): 830-843.
[13] Li W J, Liu H L. Online NDP-constraint scheduling of jobs with delivery times or weights [J]. Optimization Letters, 2023, 17: 591-612.
[14] Li W J. A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time [J]. Asia-Pacific Journal of Operational Research, 2015, 32(4): 1550030.
[15] Chai X, Lu L F, Li W H, et al. Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time [J]. Asia-Pacific Journal of Operational Research, 2018, 35(6): 1850048.
[16] Li W H, Chai X. Online scheduling on bounded batch machines to minimize the maximum weighted completion time [J]. Journal of the Operations Research Society of China, 2018, 6(3): 455-465.
[17] Yuan J J, Ng C T, Cheng T C E. Scheduling with release dates and preemption to minimize multiple max-form objective functions [J]. European Journal of Operational Research, 2020, 280(3): 860-875.
[18] Chai X, Li W H, Zhu Y J. Online scheduling to minimize maximum weighted flow-time on a bounded parallel-batch machine [J]. Annals of Operations Research, 2021, 298(1): 79-93.
[19] 臧西杰，李士生，王曦峰，最小化最大加权完工时间重新排序研究[J，系统科学与数学，2017， 37(11):2293-2300.
北大中文核心期刊