Applying 'Peeling Onion' approach for competitive analysis in online scheduling with rejection
| Autor: | Ran Ma, Sainan Guo |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
050210 logistics & transportation
Mathematical optimization 021103 operations research Information Systems and Management General Computer Science Job shop scheduling Competitive analysis Computer science 05 social sciences 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Scheduling (computing) Online optimization Modeling and Simulation 0502 economics and business Online algorithm Time complexity |
| Zdroj: | European Journal of Operational Research. 290:57-67 |
| ISSN: | 0377-2217 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect