In this paper, we consider the online scheduling problem on a single machine to minimize the weighted makespan. In this problem, all jobs arrive over time and they are allowed to be restarted only once. For the general case when the processing times of all jobs are arbitrary, we show that there is no online algorithm with a competitive ratio of less than 2, which matches the lower bound of the problem without restart. That is, only one restart for all jobs is invalid for improving the competitive ratio in the general case. For the special case when all jobs have the same processing time, we present the best possible online algorithm with a competitive ratio of 1.4656, which improves the competitive ratio of $ \frac{1+\sqrt{5}}{2}\approx1.618 $ for the problem without restart.
Citation: Xiaoxiao Liang, Lingfa Lu, Xueke Sun, Xue Yu, Lili Zuo. Online scheduling on a single machine with one restart for all jobs to minimize the weighted makespan[J]. AIMS Mathematics, 2024, 9(1): 2518-2529. doi: 10.3934/math.2024124
In this paper, we consider the online scheduling problem on a single machine to minimize the weighted makespan. In this problem, all jobs arrive over time and they are allowed to be restarted only once. For the general case when the processing times of all jobs are arbitrary, we show that there is no online algorithm with a competitive ratio of less than 2, which matches the lower bound of the problem without restart. That is, only one restart for all jobs is invalid for improving the competitive ratio in the general case. For the special case when all jobs have the same processing time, we present the best possible online algorithm with a competitive ratio of 1.4656, which improves the competitive ratio of $ \frac{1+\sqrt{5}}{2}\approx1.618 $ for the problem without restart.
| [1] |
M. V. D. Akker, H. Hoogeveen, N. Vakhania, Restarts can help in the on-line minimization of the maximum delivery time on a single machine, J. Scheduling, 3 (2000), 333–341. https://doi.org/10.1002/1099-1425(200011/12)3:6<333::AID-JOS53>3.0.CO;2-8 doi: 10.1002/1099-1425(200011/12)3:6<333::AID-JOS53>3.0.CO;2-8
|
| [2] |
H. Hoogeveen, C. N. Potts, G. J. Woeginger, On-line scheduling on a single machine: Maximizing the number of early jobs, Oper. Res. Lett., 27 (2000), 193–197. https://doi.org/10.1016/S0167-6377(00)00061-4 doi: 10.1016/S0167-6377(00)00061-4
|
| [3] |
R. Y. Fu, J. Tian, J. J. Yuan, C. He, On-line scheduling on a batch machine to minimize makespan with limited restarts, Oper. Res. Lett., 36 (2008), 255–258. https://doi.org/10.1016/j.orl.2007.07.001 doi: 10.1016/j.orl.2007.07.001
|
| [4] |
H. L. Liu, J. J. Yuan, Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart, Theor. Comput. Sci., 543 (2014), 24–36. https://doi.org/10.1016/j.tcs.2014.05.021 doi: 10.1016/j.tcs.2014.05.021
|
| [5] |
H. L. Liu, X. W. Lu, Online scheduling on a parallel batch machine with delivery times and limited restarts, J. Oper. Res. Soc. China, 10 (2022), 113–131. https://doi.org/10.1007/s40305-021-00356-7 doi: 10.1007/s40305-021-00356-7
|
| [6] |
R. Y. Fu, T. Ji, J. J. Yuan, Y. X. Lin, Online scheduling in a parallel batch processing system to minimize makespan using restarts, Theor. Comput. Sci., 374 (2007), 196–202. https://doi.org/10.1016/j.tcs.2006.12.040 doi: 10.1016/j.tcs.2006.12.040
|
| [7] |
J. J. Yuan, R. Y. Fu, C. T. Ng, T. C. E. Cheng, A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan, J. Scheduling, 14 (2011), 361–369. https://doi.org/10.1007/s10951-010-0172-2 doi: 10.1007/s10951-010-0172-2
|
| [8] |
R. Y. Fu, T. C. E. Cheng, C. T. Ng, J. J. Yuan, Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan, Inform. Process. Lett., 110 (2010), 444–450. https://doi.org/10.1016/j.ipl.2010.04.008 doi: 10.1016/j.ipl.2010.04.008
|
| [9] |
J. Tian, R. Y. Fu, J. J. Yuan, Online over time scheduling on parallel-batch machines: A survey, J. Oper. Res. Soc. China, 2 (2014), 445–454. https://doi.org/10.1007/s40305-014-0060-0 doi: 10.1007/s40305-014-0060-0
|
| [10] |
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
|
| [11] |
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
|
| [12] | L. F. Lu, L. Q. Zhang, J. W. Ou, Single machine scheduling with rejection to minimize the weighted makespan, In: Algorithmic Aspects in Information and Management, AAIM 2021, Lecture Notes in Computer Science, Springer, Cham, 13153 (2021), 96–110. https://doi.org/10.1007/978-3-030-93176-6_9 |
| [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] | R. Q. Sun, On the parameterized tractability of single machine scheduling with rejection to minimize the weighted makespan, In: Theoretical Computer Science, NCTCS 2022, Communications in Computer and Information Science, Springer, Singapore, 1693 (2022), 236–247. https://doi.org/10.1007/978-981-19-8152-4_17 |
| [15] |
H. Nouinou, T. Arbaoui, A. Yalaoui, Minimising total weighted completion time for semi-online single machine scheduling with known arrivals and bounded processing times, Int. J. Prod. Res., 2023, 1–14. https://doi.org/10.1080/00207543.2023.2217294 doi: 10.1080/00207543.2023.2217294
|
Xiaoxiao Liang, Lingfa Lu, Xueke Sun, Xue Yu, Lili Zuo. Online scheduling on a single machine with one restart for all jobs to minimize the weighted makespan[J]. AIMS Mathematics, 2024, 9(1): 2518-2529. doi: 10.3934/math.2024124
DownLoad: