A Genetic Algorithm for a Two-Machine Flowshop with a Limited Waiting Time Constraint and Sequence-Dependent Setup Times

Abstract EN

This study considers a two-machine flowshop with a limited waiting time constraint between the two machines and sequence-dependent setup times on the second machine.

These characteristics are motivated from semiconductor manufacturing systems.

The objective of this scheduling problem is to minimize the total tardiness.

In this study, a mixed-integer linear programming formulation was provided to define the problem mathematically and used to find optimal solutions using a mathematical programming solver, CPLEX.

As CPLEX required a significantly long computation time because this problem is known to be NP-complete, a genetic algorithm was proposed to solve the problem within a short computation time.

Computational experiments were performed to evaluate the performance of the proposed algorithm and the suggested GA outperformed the other heuristics considered in the study.