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

Authors: Jairo R. Montoya-Torres; Fernando González-Solano; Milton Soto-Ferrari

Addresses: Escuela Internacional de Ciencias Económicas y Administrativas, Universidad de La Sabana, km 7 autopista norte de Bogotá D.C, Chía (Cundinamarca), Colombia. ' Departamento de Ingeniería Industrial, Universidad del Norte, km 5 vía Puerto Colombia, Barranquilla, Colombia. ' Departamento de Ingeniería Industrial, Universidad del Norte, km 5 vía Puerto Colombia, Barranquilla, Colombia

Abstract: 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.

Keywords: single machine scheduling; parallel machine scheduling; sequence-dependent setup times; heuristics; randomness; release times; random-insertion heuristics; makespan.

DOI: 10.1504/IJAOM.2012.045889

International Journal of Advanced Operations Management, 2012 Vol.4 No.1/2, pp.4 - 26

Published online: 11 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article