Online nonpreemptive scheduling of equal-length jobs on two identical machines

Autor:	Michael H. Goldwasser, Mark Pedigo
Rok vydání:	2008
Předmět:	Mathematical optimization Mathematics (miscellaneous) Competitive analysis Deterministic algorithm Computer science Distributed computing Release date Admission control Upper and lower bounds Multiprocessor scheduling Scheduling (computing)
Zdroj:	ACM Transactions on Algorithms. 5:1-18
ISSN:	1549-6333 1549-6325
DOI:	10.1145/1435375.1435377
Popis:	We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j | Σ Ū j . The problem is known to be polynomially solvable in an offline setting. In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::5ab1a1819249327d2c9fb0bd81c52304 https://doi.org/10.1145/1435375.1435377 Zobrazit plný text záznamu