A parallel genetic algorithm for a flexible job-shop scheduling problem with sequence dependent setups

The flexible job-shop scheduling problem is an extension of the classical job-shop scheduling problem by allowing an operation to be assigned to one of a set of eligible machines during scheduling. Thus, the problem is to simultaneously assign each operation to a machine (routing problem), prioritiz...

Full description

Saved in:
Bibliographic Details
Published in:International journal of advanced manufacturing technology 2010-07, Vol.49 (1-4), p.263-279
Main Authors: Defersha, Fantahun M., Chen, Mingyuan
Format: Article
Language:English
Subjects:
CAE) and Design
Completion time
Computer-Aided Engineering (CAD
Engineering
Genetic algorithms
Industrial and Production Engineering
Job shop scheduling
Job shops
Mathematical models
Mechanical Engineering
Media Management
Original Article
Production scheduling
Sequences
Sequential scheduling
Time dependence
Time lag
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 flexible job-shop scheduling problem is an extension of the classical job-shop scheduling problem by allowing an operation to be assigned to one of a set of eligible machines during scheduling. Thus, the problem is to simultaneously assign each operation to a machine (routing problem), prioritize the operations on the machines (sequencing problem), and determine their starting times. The minimization of the maximal completion time of all operations is a widely used objective function in solving this problem. This paper presents a mathematical model for a flexible job-shop scheduling problem incorporating sequence-dependent setup time, attached or detached setup time, machine release dates, and time lag requirements. In order to efficiently solve the developed model, we propose a parallel genetic algorithm that runs on a parallel computing platform. Numerical examples show that parallel computing can greatly improve the computational performance of the algorithm.
ISSN:0268-3768
1433-3015
DOI:10.1007/s00170-009-2388-x