On polynomial solvability of two multiprocessor scheduling problems

Autor:	Alexander G. Tarnowski, Eberhard Girlich
Rok vydání:	1999
Předmět:	Rate-monotonic scheduling Mathematical optimization Cutting stock problem General Mathematics Dynamic priority scheduling Management Science and Operations Research Greedy algorithm Time complexity Software Fair-share scheduling Multiprocessor scheduling Mathematics Scheduling (computing)
Zdroj:	Mathematical Methods of Operations Research. 50:27-51
ISSN:	1432-5217 1432-2994
DOI:	10.1007/pl00020925
Popis:	We discuss a new approach for solving multiprocessor scheduling problems by using and improving results for guillotine pallet loading problem. We introduce a new class of schedules by analogy with the guillotine restriction for cutting stock problem and show that many well-known algorithms from classical scheduling theory construct schedules only from this class. We also consider two multiprocessor scheduling problems and prove that they can be solved in polynomial time.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::71612cab0f2a21a2507e036ed82dbd8d https://doi.org/10.1007/pl00020925 Zobrazit plný text záznamu Plný text ve formátu PDF