Applying “Peeling Onion” approach for competitive analysis in online scheduling with rejection

Ran Ma and Sainan Guo

European Journal of Operational Research, 2021, vol. 290, issue 1, 57-67

Abstract: In this study, we consider the classical online scheduling problem with rejection on identical parallel machines. In particular, a series of independent jobs arriving online over time will be scheduled on the identical machines with the flexibility of rejection, which implies that each job is either rejected with a penalty cost or accepted and scheduled on one of the identical machines. In addition, the knowledge of each job Jj, including the processing time pj, release date rj, and penalty cost ej, is disclosed upon arrival of this job. Our goal is to minimize the total completion time of the accepted jobs plus the total penalty cost of the rejected jobs. For this problem, we provide a deterministic polynomial time online algorithm named as Delayed Shortest Processing Time with Rejection, shortly as DSPTR. For the sake of analyzing the competitive ratio of DSPTR, we introduce an interesting and efficient approach entitled as “Peeling Onion”. By means of “Peeling Onion”, we demonstrate that DSPTR is a 2-competitive online algorithm and the bound is tight. We believe that the introduction of the analysis approach “Peeling Onion” could also be applied to other online optimization problems and yield a new perspective on competitive analysis in general.

Keywords: Scheduling; Online algorithm; Competitive ratio; Parallel machines; Rejection (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720307001
Full text for ScienceDirect subscribers only

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:eee:ejores:v:290:y:2021:i:1:p:57-67

DOI: 10.1016/j.ejor.2020.08.009

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().