Deterministic machine scheduling with release times and sequence-dependent setups using random-insertion heuristics

Autor:	Fernando González-Solano, Milton Soto-Ferrari, Jairo R. Montoya-Torres
Rok vydání:	2012
Předmět:	Organizational Behavior and Human Resource Management Mathematical optimization Machine scheduling Sequence dependent Job shop scheduling Computer science Management Science and Operations Research Completion time Heuristics Randomness Scheduling (computing)
Zdroj:	International Journal of Advanced Operations Management. 4:4
ISSN:	1758-9398 1758-938X
DOI:	10.1504/ijaom.2012.045889
Popis:	This paper considers the problem of scheduling a set of jobs on both a single machine and identical parallel machines settings with the objective of minimising the maximum completion time of all jobs (makespan). Jobs are subject to release dates and there are sequence-dependent setup times. Since this problem is known to be strongly NP-hard even for the single machine case, this paper proposes heuristic algorithms to solve it. Algorithm uses the advantages of random-variate generators as a strategy for the generation of various execution sequences, and then selects the best of such schedules. Experiments are performed using random-generated data from taken literature. Results show that the heuristics perform very well compared against the optimal solution, and requiring short computational time.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6379019f7a794140e4015b082100e843 https://doi.org/10.1504/ijaom.2012.045889 Zobrazit plný text záznamu