On-Line Single Machine Scheduling of Unit Time Jobs with Rejection: Minimizing the Maximum Quadratic Completion Time

Liqi Zhang (), Lingfa Lu, Xueke Sun () and Lili Zuo ()
Additional contact information
Liqi Zhang: College of Information and Management Science, Henan Agricultural University, Zhengzhou, Henan 450003, P. R. China
Lingfa Lu: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Xueke Sun: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China
Lili Zuo: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan 450001, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2025, vol. 42, issue 05, 1-10

Abstract: In this paper, we consider the on-line single machine scheduling of unit time jobs with rejection. All jobs arrive on-line over a list (one by one). For each arriving job, the on-line algorithm must decide immediately to accept or reject it. The objective is to minimize the maximum quadratic completion time of accepted jobs plus the total rejection cost of rejected jobs. For this problem, we show that 1.7299 is a lower bound on the competitive ratio and present a simple greedy algorithm with the competitive ratio 2. Furthermore, we also provide a modified greedy algorithm with a better competitive ratio 1 + 3 2 ≈ 1.86602.

Keywords: Scheduling with rejection; the maximum quadratic completion time; on-line algorithm; competitive ratio (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595925500095
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:42:y:2025:i:05:n:s0217595925500095

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595925500095

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 ().