A Semi-Online Algorithm for Single Machine Scheduling with Rejection

Sainan Guo (), Ran Ma, Yuzhong Zhang () and Baoqiang Fan ()
Additional contact information
Sainan Guo: School of Mathematics and Information Science, Henan Polytechnic University, Jiaozuo 454000, P. R. China
Ran Ma: School of Management Engineering, Qingdao University of Technology, Qingdao 266525, P. R. China
Yuzhong Zhang: Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, P. R. China
Baoqiang Fan: Department of Mathematics and Information, Ludong University, Yantai 264025, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 05, 1-21

Abstract: In this paper, a single-machine semi-online scheduling problem with rejection is addressed. In this model, “semi-online” implies that pmax pmin ≤ γ, where pmax and pmin are the maximum processing time and the minimum one among all jobs, respectively, γ ≥ 1. In this setting, each job arrives online over time, and rejection is allowable. Our goal is minimizing the total penalty cost of rejected jobs plus the total completion time of processed jobs. The seminal result of this study is that we offer an algorithm with competitive ratio 1 + 1+γ(γ−1)−1 γ, which matches the result of the problem without rejection.

Keywords: Semi-online scheduling; rejection; single machine; total completion time (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595921400030
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:38:y:2021:i:05:n:s0217595921400030

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595921400030

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