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

作者：Defersha Fantahun M; Chen Mingyuan^*

来源：International Journal of Advanced Manufacturing Technology, 2010, 49(1-4): 263-279.

DOI：10.1007/s00170-009-2388-x

• Flexible job-shop scheduling
• Sequence dependent setups
• Attached/detached setup
• Time lag
• Machine release date
• Genetic algorithm
• Parallel computing

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.

• 出版日期2010-7