Online Single-Processor Scheduling with an Unexpected Breakdown

Sainan Guo (), Yannan Chen (), Yaping Mao and Xiaoyan Zhang
Additional contact information
Sainan Guo: School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, P. R. China
Yannan Chen: School of Mathematical Sciences, South China Normal University, Guangzhou 510631, P. R. China
Yaping Mao: Department of Mathematics and Statistics, Qinghai Normal University, Xining 810008, Qinghai, P. R. China4Academy of Plateau Science and Sustainability, Xining 810008, Qinghai, P. R. China
Xiaoyan Zhang: School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2024, vol. 41, issue 01, 1-15

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 Ja and Jb, wa ≥ wb means that pa ≥ pb, 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: Scheduling; online algorithm; single processor; unexpected breakdown (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595923500057
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:41:y:2024:i:01:n:s0217595923500057

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595923500057

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().