Scheduling on Uniform Nonsimultaneous Parallel Machines

Autor:	Donald K. Friesen, Liliana Grigoriu
Rok vydání:	2017
Předmět:	Mathematical optimization 021103 operations research 010201 computation theory & mathematics Computer science General problem 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Completion time 01 natural sciences Scheduling (computing)
Zdroj:	Operations Research Proceedings 2016 ISBN: 9783319557014 OR
Popis:	We consider the problem of scheduling on uniform processors which may not start processing at the same time with the purpose of minimizing the maximum completion time. We provide a variant of the MULTIFIT algorithm which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two processors. Experimental results suggest that our algorithm is a viable option for addressing this problem in practice.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6b72300cd193f00f44243b5718f2b28c https://doi.org/10.1007/978-3-319-55702-1_62 Zobrazit plný text záznamu