New heuristics and integer programming formulations for scheduling divisible load tasks

Autor:	Elbio Renato Torres Abib, Celso C. Ribeiro
Rok vydání:	2009
Předmět:	Mathematical optimization Exact algorithm Linear programming Job shop scheduling Computer science Special case Heuristics Integer programming Upper and lower bounds Scheduling (computing)
Zdroj:	CISched
DOI:	10.1109/scis.2009.4927015
Popis:	Divisible load applications occur in many fields of science and engineering. They can be parallelized in a master-worker fashion, but they pose several scheduling challenges. We propose single-round and multi-round integer programming formulations for scheduling divisible load applications with minimum makespan. An innovative linear-time exact algorithm improving the complexity of the best known algorithm to date is described for the special case in which the processor activation order is known beforehand. This algorithm is embedded within a greedy-with-feedback heuristic for finding good solutions for single-round problems. Numerical results illustrate the speed and the effectiveness of the proposed heuristic.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::5e0042bba5e9e0bd7a75507d1056810d https://doi.org/10.1109/scis.2009.4927015 Zobrazit plný text záznamu