Abstract
We consider on-line scheduling of unit time jobs on a single machine with job-dependent penalties. The jobs arrive on-line (one by one) and can be either accepted and scheduled, or be rejected at the cost of a penalty. The objective is to minimize the total completion time of the accepted jobs plus the sum of the penalties of the rejected jobs.
We give an on-line algorithm for this problem with competitive ratio . Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.
| Original language | English |
|---|---|
| Pages (from-to) | 415-420 |
| Journal | Operations research letters |
| Volume | 30 |
| Issue number | 6 |
| DOIs | |
| Publication status | Published - 2002 |
Keywords
- IR-74863
- On-line algorithm
- Scheduling
- Worst-case bounds
- METIS-208618
- Competitive Analysis
Fingerprint Dive into the research topics of 'On-line scheduling of unit time jobs with rejection: Minimizing the total completion time'. Together they form a unique fingerprint.
Cite this
Epstein, L., Noga, J., & Woeginger, G. (2002). On-line scheduling of unit time jobs with rejection: Minimizing the total completion time. Operations research letters, 30(6), 415-420. https://doi.org/10.1016/S0167-6377(02)00160-8