Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times

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

Full description

Saved in:
Bibliographic Details
Published in:Journal of intelligent manufacturing 2006-02, Vol.17 (1), p.85-97
Main Authors: Rabadi, Ghaith, Moraga, Reinaldo J., Al-Salem, Ameer
Format: Article
Language:English
Subjects:
Algorithms
Engineering
Heuristic
Heuristic methods
Job shops
Linear programming
Literature reviews
Manufacturing
Preempting
Production controls
Schedules
Scheduling
Setup times
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. [PUBLICATION ABSTRACT]
ISSN:0956-5515
1572-8145
DOI:10.1007/s10845-005-5514-0