Title: Simulated annealing and genetic algorithm for unrelated parallel machine scheduling considering set-up times

Authors: Dong-Won Kim, Dong-Gil Na, Wooseung Jang, F. Frank Chen

Addresses: Department of Industrial and Information Systems Engineering, Chonbuk National University, Jeonju 561-756, Korea. ' Postal Technology Research Center, Electronics and Telecommunications Research Institute, Daejeon 305-700, Korea. ' Department of Industrial and Manufacturing Systems Engineering, University of Missouri, Columbia, MO 65211, USA. ' Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA 24061, USA

Abstract: This paper presents the comparative use of Simulated Annealing (SA) and Genetic Algorithm (GA) in a scheduling problem of unrelated parallel machines with set-up times. The problem accounts for allotting batched work parts to the unrelated parallel machines, where each batch is composed of a fixed number of identical jobs. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor set-up times are required between two subsequent batches, depending on the batch sequence but yet independent of machines. The objective of the problem is to minimise the Total Weighted Tardiness (TWT) for the unrelated parallel machine scheduling. SA and GA algorithms are proposed to obtain near-optimal solutions of the problem. The performance of proposed heuristics is compared through computational experiments with real data from dicing operations of a compound semiconductor manufacturing facility.

Keywords: scheduling; production planning; meta-heuristics; simulated annealing; genetic algorithms; distributed manufacturing; unrelated parallel machines.

DOI: 10.1504/IJCAT.2006.010078

International Journal of Computer Applications in Technology, 2006 Vol.26 No.1/2, pp.28 - 36

Published online: 16 Jun 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article