On-line scheduling of unit time jobs with rejection: Minimizing the total completion time

On-line scheduling of unit time jobs with rejection: Minimizing the total completion time

0.00 Avg rating0 Votes
Article ID: iaor20031412
Country: Netherlands
Volume: 30
Issue: 6
Start Page Number: 415
End Page Number: 420
Publication Date: Dec 2002
Journal: Operations Research Letters
Authors: , ,
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 1/2(2 + √(3)) ≈ 1.86602. Moreover, we prove that there does not exist an on-line algorithm with competitive ratio better than 1.63784.

Reviews

Required fields are marked *. Your email address will not be published.