Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times

Authors: Rabadi, Ghaith; Moraga, Reinaldo; Al-Salem, Ameer

Source: Journal of Intelligent Manufacturing, Volume 17, Number 1, February 2006 , pp. 85-97(13)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

The problem addressed in this paper is the non-preemptive unrelated parallel machine scheduling problem with the objective of minimizing the makespan. Machine-dependent and job sequence-dependent setup times are considered, all jobs are available at time zero, and all times are deterministic. This is a NP-hard problem and in this paper, optimal solutions are found for small problems only. For larger problems, a new meta-heuristic, Meta-RaPS, is introduced and its performance is evaluated by comparing its solutions to the solutions of an existing heuristic for the same problem. The results show that Meta-RaPS found all optimal solutions for the small problems and outperformed the solutions obtained by the existing heuristic for larger problems.

Keywords: Scheduling; unrelated parallel machine; setup times; heuristics; Meta-RaPS

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10845-005-5514-0

Affiliations: 1: Email: grabadi@odu.edu

Publication date: 2006-02-01