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

Key:

- Free Content

- New Content

- Subscribed Content

- Free Trial Content

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: 10.1007/s10845-005-5514-0

Affiliations: 1: Email: grabadi@odu.edu

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$47.00 plus tax Refund Policy