Schedules with a single preemption on uniform parallel machines

Autor:	Alan Soper, Vitaly A. Strusevich
Jazyk:	angličtina
Rok vydání:	2018
Předmět:	Mathematical optimization Schedule Job shop scheduling Applied Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Preemption Discrete Mathematics and Combinatorics QA Measure (mathematics) Time complexity Mathematics
ISSN:	0166-218X
Popis:	For a scheduling problem to minimize the makespan on parallel machines, we consider schedules with at most one preemption. We show that in the case of two uniform machines the problem is solvable in polynomial time. For m ≥ 3 uniform parallel machines, we measure the quality of a single preemption as the worst-case ratio of the makespan of an optimal schedule with at most one preemption over the makespan of an optimal preemptive schedule. We show that the global bound on such a ratio is 2 − 2 ∕ m .
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eb89e96416c087e1bb9edaa2ccc0e191 Zobrazit plný text záznamu Full Text from ScienceDirect