|
|||||
|
|
On-line scheduling of unit time jobs with rejection: minimizing the total completion time |
|
| Authors: | Leah Epstein John Noga Gerhard J. Woeginger |
| Affiliation: | a School of Computer and Media Sciences, The Interdisciplinary Center, P.O. Box 167, 46150, Herzliya, Israel;b Department of Computer Science, California State University, 18111 Nordhoff Street, Northridge, CA 91330-8295, USA;c Department of Mathematics, University of Twente, P.O. Box 217, 7500 AE, Enschede, The Netherlands;d Institut für Mathematik, Technische Universität Graz, Steyrergasse 30, A-8010, Graz, Austria |
| 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. |
| Keywords: | Scheduling On-line algorithm Competitive analysis Worst-case bounds |
| 本文献已被 ScienceDirect 等数据库收录！ | |