Optimal on-line algorithms for single-machine scheduling

Autor:	Han Hoogeveen, Arjen P. A. Vestjens
Rok vydání:	1996
Předmět:	Rate-monotonic scheduling Earliest deadline first scheduling Mathematical optimization Single-machine scheduling Open-shop scheduling Least slack time scheduling Computer science Flow shop scheduling Dynamic priority scheduling Algorithm Multiprocessor scheduling
Zdroj:	Integer Programming and Combinatorial Optimization ISBN: 9783540613107 IPCO
DOI:	10.1007/3-540-61310-2_30
Popis:	We consider single-machine on-line scheduling problems where jobs arrive over time. A set of independent jobs has to be scheduled on the machine, where preemption is not allowed and the number of jobs is unknown in advance. Each job becomes available at its release date, which is not known in advance, and its characteristics, e.g., processing requirement, become known at its arrival. We deal with two problems: minimizing total completion time and minimizing the maximum time by which all jobs have been delivered. For both problems we propose and analyze an on-line algorithm based on the following idea: As soon as the machine becomes available for processing, choose an available job with highest priority, and schedule it if its processing requirement is not too large. Otherwise, postpone the start of this job for a while. We prove that our algorithms have performance bound 2 and (√5 + 1)/2, respectively, and we show that for both problems there cannot exist an on-line algorithm with a better performance guarantee.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::71ceea9543feb2b2a85ae98580fdc640 https://doi.org/10.1007/3-540-61310-2_30 Zobrazit plný text záznamu