• search hit 6 of 13
Back to Result List

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

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.