Short Note on Scheduling on a Single Machine with one Non-availability Period
Please always quote using this URN:urn:nbn:de:0296-matheon-5392
- We consider scheduling on a single machine with one non-availability period to minimize the weighted sum of completion times. We provide a preemptive algorithm with an approximation ratio arbitrarily close to the Golden Ratio,~$(1+\sqrt{5})/2+\eps$, which improves on a previously best known~$2$-approximation. The non-preemptive version of the same algorithm yields a~$(2+\eps)$-approximation.
Author: | Nicole Megow, Jose Verschae |
---|---|
URN: | urn:nbn:de:0296-matheon-5392 |
Referee: | Rolf H. Möhring |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2009/05/01 |
Release Date: | 2009/05/01 |
Institute: | Technische Universität Berlin |
Preprint Number: | 533 |