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.
Download full text files
Additional Services
| 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 |
