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