On-line single-machine scheduling to minimize the weighted makespan under (dis)agreeability conditions

Bingbing Fan; Lingfa Lu; Zhan Shi; Bingbing Fan; Lingfa Lu; Zhan Shi

doi:10.3934/jimo.2026145

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 8: 4138-4150. doi: 10.3934/jimo.2026145

Previous Article Next Article

Theory article Special Issues

On-line single-machine scheduling to minimize the weighted makespan under (dis)agreeability conditions

School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P.R. China

Received: 08 May 2026 Revised: 24 June 2026 Accepted: 13 July 2026 Published: 29 July 2026
90B35

In this paper, we considered the on-line single-machine scheduling with the objective of minimizing the weighted makespan. For the general case, a lower bound of $ 2 $ and two on-line algorithms with the best-possible competitive ratio of 2 were provided in the literature. We considered eight special cases in which all jobs had the agreeability or disagreeability condition on jobs' parameters. For each special case, we provided a lower bound and a corresponding on-line algorithm with the best-possible competitive ratio which matched the given lower bound.
- on-line scheduling,
- single-machine scheduling,
- weighted makespan,
- (dis)agreeability conditions,
- competitive ratio
Citation: Bingbing Fan, Lingfa Lu, Zhan Shi. On-line single-machine scheduling to minimize the weighted makespan under (dis)agreeability conditions[J]. Journal of Industrial and Management Optimization, 2026, 22(8): 4138-4150. doi: 10.3934/jimo.2026145

Related Papers:

Abstract

In this paper, we considered the on-line single-machine scheduling with the objective of minimizing the weighted makespan. For the general case, a lower bound of $ 2 $ and two on-line algorithms with the best-possible competitive ratio of 2 were provided in the literature. We considered eight special cases in which all jobs had the agreeability or disagreeability condition on jobs' parameters. For each special case, we provided a lower bound and a corresponding on-line algorithm with the best-possible competitive ratio which matched the given lower bound.

References

[1]	W. J. Li, A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time, Asia-Pac. J. Oper. Res., 32 (2015), 1550030. https://doi.org/10.1142/S021759591550030X doi: 10.1142/S021759591550030X
[2]	X. Chai, L. F. Lu, W. H. Li, L. Q. Zhang, Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time, Asia-Pac. J. Oper. Res., 35 (2018), 1850048. https://doi.org/10.1142/S0217595918500483 doi: 10.1142/S0217595918500483
[3]	A. Amouzandeh, R. van Stee, Improved online scheduling with restarts on a single machine, Theory Comput. Syst., 70 (2026), 10. https://doi.org/10.1007/s00224-026-10267-w doi: 10.1007/s00224-026-10267-w
[4]	O. Braun, F. Chung, R. L. Graham, Lower bounds for online scheduling on four processors, J. Sched., 28 (2025), 529–544. https://doi.org/10.1007/s10951-025-00843-2 doi: 10.1007/s10951-025-00843-2
[5]	Z. L. Chen, Online integrated production and distribution scheduling: review and extensions, INFORMS J. Comput., 37 (2025), 360–380. https://doi.org/10.1287/ijoc.2022.0305 doi: 10.1287/ijoc.2022.0305
[6]	C. Escribe, M. Hu, R. Levi, Competitive algorithms for the online minimum peak job scheduling, Oper. Res., 73 (2025), 408–423. https://doi.org/10.1287/opre.2021.0080 doi: 10.1287/opre.2021.0080
[7]	Y. J. Qu, J. Tian, R. Y. Fu, K. J. Ge, A best possible online algorithm for single-machine scheduling with non-delayed processing constraint and bounded delivery times, J. Oper. Res. Soc. China, 14 (2026), 489–501. https://doi.org/10.1007/s40305-024-00541-4 doi: 10.1007/s40305-024-00541-4
[8]	J. M. Yang, Z. Y. Tan, Online scheduling with rejection revisited, Inform. and Comput., 310 (2026), 105442. https://doi.org/10.1016/j.ic.2026.105442 doi: 10.1016/j.ic.2026.105442
[9]	H. Zhang, L. F. Lu, J. J. Yuan, Online scheduling on an unbounded parallel-batch machine to minimize the weighted makespan, J. Comb. Optim., 49 (2025), 6. https://doi.org/10.1007/s10878-024-01242-7 doi: 10.1007/s10878-024-01242-7
[10]	L. Q. Zhang, L. F. Lu, X. K. Sun, L. L. Zuo, On-Line Single Machine Scheduling of Unit Time Jobs with Rejection: Minimizing the Maximum Quadratic Completion Time, Asia-Pacific J. Oper. Res., 42 (2025), 2550009. https://doi.org/10.1142/S0217595925500095 doi: 10.1142/S0217595925500095
[11]	Q. Feng, J. J. Yuan, NP-hardness of a multicriteria scheduling on two families of jobs, OR Transactions, 114 (2007), 121–126. https://doi.org/10.15960/j.cnki.issn.1007-6093.2007.04.001 doi: 10.15960/j.cnki.issn.1007-6093.2007.04.001
[12]	Q. Q. Nong, T. C. E. Cheng, C. T. Ng, Two-agent scheduling to minimize the total cost, European J. Oper. Res., 215 (2011), 39–44. https://doi.org/10.1016/j.ejor.2011.05.041 doi: 10.1016/j.ejor.2011.05.041
[13]	W. H. Li, X. Chai, Online scheduling on bounded batch machines to minimize the maximum weighted completion time, J. Oper. Res. Soc. China, 6 (2018), 455–465. https://doi.org/10.1007/s40305-017-0179-x doi: 10.1007/s40305-017-0179-x
[14]	W. J. Li, J. J. Yuan, Single-machine online scheduling of jobs with non-delayed processing constraint, J. Comb. Optim., 41 (2021), 830–843. https://doi.org/10.1007/s10878-021-00722-4 doi: 10.1007/s10878-021-00722-4
[15]	W. J. Li, H. L. Liu, Online NDP-constraint scheduling of jobs with delivery times or weights, Optim. Lett., 17 (2023), 591–612. https://doi.org/10.1007/s11590-022-01889-3 doi: 10.1007/s11590-022-01889-3
[16]	L. F. Lu, L. L. Zuo, L. Q. Zhang, J. W. Ou, Order acceptance and scheduling with weighted makespan, 4OR, 23 (2025), 247–267. https://doi.org/10.1007/s10288-025-00586-y doi: 10.1007/s10288-025-00586-y
[17]	F. F. Zheng, N. Li, M. Liu, Y. Xu, Single machine lot scheduling to minimize maximum weighted completion time, J. Comb. Optim., 50 (2025), 1. https://doi.org/10.1007/s10878-025-01327-x doi: 10.1007/s10878-025-01327-x
[18]	X. X. Liang, L. F. Lu, X. K. Sun, X. Yu, L. L. Zuo, Online scheduling on a single machine with one restart for all jobs to minimize the weighted makespan, AIMS Math., 9 (2024), 2518–2529. https://doi.org/10.3934/math.2024124 doi: 10.3934/math.2024124

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)