Title

A Simulated Annealing Algorithm For The Unrelated Parallel Machine Scheduling Problem

Keywords

Integer program; Scheduling; Setup times; Simulated annealing; Unrelated parallel machines

Abstract

The problem addressed in this paper is scheduling jobs on unrelated parallel machines with sequence-dependent setup times to minimize the maximum completion time (i.e., the makespan). This problem is NP-hard even without including setup times. Adding sequence-dependent setup times adds another dimension of complexity to the problem and obtaining optimal solutions becomes very difficult especially for large problems. In this paper a Simulated Annealing (SA) algorithm is applied to the problem at hand to reach near-optimum solution. The effectiveness of the Simulated Annealing algorithm is measured by comparing the quality of its solutions to optimal solutions for small problems. The results show that the SA efficiently obtained optimal solutions for all test problems.

Publication Date

12-1-2002

Publication Title

Robotics, Automation, Control and Manufacturing: Trends, Principles and Applications - Proceedings of the 5th Biannual World Automation Congress, WAC 2002, ISORA 2002, ISIAC 2002 and ISOMA 2002

Volume

14

Number of Pages

115-120

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

38949160036 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/38949160036

This document is currently not available here.

Share

COinS