Free Access

Online Single-Processor Scheduling with an Unexpected Breakdown

Sainan Guo

School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, P. R. China

E-mail Address: athenagsn@163.com

Search for more papers by this author

Yannan Chen

School of Mathematical Sciences, South China Normal University, Guangzhou 510631, P. R. China

E-mail Address: ynchen@scnu.edu.cn

Search for more papers by this author

Yaping Mao

Department of Mathematics and Statistics, Qinghai Normal University, Xining 810008, Qinghai, P. R. China

Academy of Plateau Science and Sustainability, Xining 810008, Qinghai, P. R. China

E-mail Address: maoyaping@ymail.com

Search for more papers by this author

, and

Xiaoyan Zhang

School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, P. R. China

E-mail Address: zhangxiaoyan@njnu.edu.cn

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0217595923500057Cited by:0 (Source: Crossref)

Abstract

In this paper, we consider two single-processor online scheduling problems with an unexpected breakdown. Speaking specifically, there is a group of nonresumable jobs being processed on the single processor. Note that the breakdown will emerge on the processor suddenly, which signifies that its beginning time and its length are unknown in advance. In this study, we are interested in scheduling the jobs so as to minimize the maximum weighted completion time. Most noticeably, when all jobs respect an agreeable condition, i.e., for each two jobs $J_{a}$ and $J_{b}$ , $w_{a} \geq w_{b}$ means that $p_{a} \geq p_{b}$ , we design an optimal online algorithm. In addition, for the general version, we propose an online algorithm with a competitive ratio of at most 2.

Keywords:

References

Chai, X, LF Lu WH Li and LQ Zhang (2018). Best-possible online algorithms for single machine scheduling to minimize the maximum weighted completion time. Asia-Pacific Journal of Operational Research, 35(6), 1850048.1–1850048.11. Link, Web of Science, Google Scholar
Chen, C, P Penna and YF Xu (2020). Online scheduling of jobs with favorite machines. Computers & Operations Research, 116, 104868. Crossref, Web of Science, Google Scholar
Chau, V, SZ Feng and NK Thắng (2021). Competitive algorithms for demand response management in a smart grid. Journal of Scheduling, 1–8. Web of Science, Google Scholar
Cordone, R and P Hosteins (2019). A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization. Computers & Operations Research, 102, 130–140. Crossref, Web of Science, Google Scholar
Correa, JR and MR Wagner (2009). LP-based online scheduling: From single to parallel machines. Mathematical Programming, 119, 109–136. Crossref, Web of Science, Google Scholar
Croce, FD, R Tadei P Baracco and RD Tullio (1993). On minimizing the weighted sum of quadratic completion times on a single machine. In Proc. IEEE Int. Conf. Robotics and Automation, pp. 816–820. IEEE. Crossref, Google Scholar
Feng, Q and JJ Yuan (2007). NP-hardness of a multicriteria scheduling on two families of jobs. Or Transactions, 11, 121–126. Google Scholar
Fiat, A and GJ Woeginger (1998). Competitive analysis of algorithms. In Developments from a June Seminar on Online Algorithms: The State of the Art. Berlin: Springer. Crossref, Google Scholar
Graham, RL, EL Lawler JK Lenstra and AHG Rinnooy Kan (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326. Crossref, Google Scholar
Huo, YM, B Reznichenko and HR Zhao (2014). Minimizing total weighted completion time with an unexpected machine unavailable interval. Journal of Scheduling, 17(2), 161–172. Crossref, Web of Science, Google Scholar
Kacem, I and H Kellerer (2016). Semi-online scheduling on a single machine with unexpected breakdown. Theoretical Computer Science, 646, 40–48. Crossref, Web of Science, Google Scholar
Lee, K, FF Zheng and ML Pinedo (2019). Online scheduling of ordered flow shops. European Journal of Operational Research, 272, 50–60. Crossref, Web of Science, Google Scholar
Li, WJ (2015). A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time. Asia-Pacific Journal of Operational Research, 32(4), 1550030. Link, Web of Science, Google Scholar
Liu, PH, C Wang and XW Lu (2019). A note on minimizing total weighted completion time with an unexpected machine unavailable interval. Journal of Scheduling, 22, 255–262. Crossref, Web of Science, Google Scholar
Ma, R and SN Guo (2021). Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection. European Journal of Operational Research, 290(1), 57–67. Crossref, Web of Science, Google Scholar
Ma, Y, CB Chu and CR Zuo (2010). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 58(2), 199–211. Crossref, Web of Science, Google Scholar
Schmidt, G (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121(1), 1–15. Crossref, Web of Science, Google Scholar
Tang, LX, F Li and ZL Chen (2019). Integrated scheduling of production and two-stage delivery of make-to-order products: Offline and online algorithms. Informs Journal on Computing, 31(3), 493–514. Crossref, Web of Science, Google Scholar
Zhang, A, XT Qi and GH Li (2020). Machine scheduling with soft precedence constraints. European Journal of Operational Research, 282(2), 491–505. Crossref, Web of Science, Google Scholar
Zhao, L and X Han (2022). Decomposition-based scheduling for parallel real-time tasks on multiprocessors. Computers & Electrical Engineering, 97, 107644. Crossref, Web of Science, Google Scholar