在NDP约束条件下考虑带退化效应的单机在线调度

doi:10.15960/j.cnki.issn.1007-6093.2026.01.012

Abstract

Abstract: 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.

Key words: NDP constraint, deterioration, single machine, online scheduling, maximum weighted completion time

CLC Number:

O223

MENG Lanmeng, MA Ran, ZHANG Yuzhong. Single-machine online scheduling with NDP constraint and deterioration[J]. Operations Research Transactions, 2026, 30(1): 179-187.

References

[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.

Single-machine online scheduling with NDP constraint and deterioration

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	CHEN Rongjun, LIU Yongcai, HUANG He, TANG Guochun. Dynamic programming algorithms for single machine supply chain scheduling [J]. Operations Research Transactions, 2026, 30(1): 171-178.
[2]	Kaiyuan JIN, Feifeng ZHENG, Ming LIU. Online scheduling model of batch processing machine considering order types and setup time [J]. Operations Research Transactions, 2025, 29(4): 231-240.
[3]	Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect [J]. Operations Research Transactions, 2025, 29(1): 19-30.
[4]	Wenjie LI, Zhihui DU, Menglong SU. Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times [J]. Operations Research Transactions, 2024, 28(4): 18-28.
[5]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[6]	Qiiong WU, Changjun WANG. Production capacity sharing bargaining based on Lagrangian relaxation [J]. Operations Research Transactions, 2024, 28(2): 93-102.
[7]	Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.
[8]	Wenjie LI, Yujing LI, Hailing LIU. Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable [J]. Operations Research Transactions, 2022, 26(2): 55-63.
[9]	Yinling WANG, Xin HAN, Xinxin SHAO. Online single machine scheduling problem with transportation [J]. Operations Research Transactions, 2022, 26(1): 125-133.
[10]	Chen XU, Yinfeng XU, Feifeng ZHENG. Multitasking scheduling considering part jobs uninterrupted assignment [J]. Operations Research Transactions, 2021, 25(4): 91-100.
[11]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[12]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[13]	MIN Xiao, ZHU Junlei, LIU Jing. An online algorithm for hierarchical scheduling on two identical machines with rejection [J]. Operations Research Transactions, 2018, 22(3): 117-124.
[14]	MIAO Cuixia, MENG Fanxiao. Two-machine flow-shop scheduling with deterioration and rejection [J]. Operations Research Transactions, 2017, 21(2): 66-72.
[15]	FAN Jing, LU Xiwen. Supply chain scheduling problem under simple linear deterioration on a single-machine with an unavailability constraint [J]. Operations Research Transactions, 2016, 20(4): 69-76.