Comparative Study of Heuristic Algorithms for Parallel Machine Scheduling with Sequence-Dependent Setups and Release Times

Published in: Engineering for a Smarter Planet: Innovation, ITC, and Computational Tools for Sustainable Development: Proceedings of the 9th Latin American and Caribbean Conference for Engineering and Technology
Date of Conference: August 3-5, 2011
Location of Conference: Medellin, Colombia
Authors: Vanessa Patricia Manotas Niño
Elyn Lizeth Solano Charris
Jairo Rafael Montoya Torres
Refereed Paper: #80

Abstract

This paper considers the application of heuristic algorithms to analyze the results obtained for the parallel machine scheduling problem with release times and sequence-dependent setups times. Since this problem is known to be strongly NP-hard for the case of minimizing the makespan, we resolved it with different heuristics and their performance is compared with a solution obtained using a lower bound. Such heuristics are based on either dispatching rules or random schedule generation strategies. Computational experiments are performed using random-generated data taken from the literature. Our results show that the heuristics perform very well compared against the lower bound, and requiring short computational time.