Flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints

Abstract

The purpose of this research is to solve flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints in the operations. We first formulate the problem as a Mixed-Integer Linear Program (MILP). The MILP can be used to compute optimal solutions for small-sized problems. We also developed a heuristic algorithm that can obtain a good solution for the problem regardless of its size. Moreover, we have developed a representation and schedule builder that always produces a legal and feasible solution for the problem, and developed genetic and tabu search algorithms based on the proposed schedule builder. The results of the computational experiments show that the developed meta-heuristics are very effective.

Keywords:

• flexible job-shop scheduling
• ‘AND’/‘OR’ precedence constraints
• heuristic
• genetic algorithm
• Tabu search

Acknowledgements

The authors are grateful to the careful and constructive reviews from three anonymous referees. This work was supported by the Grant of the Korean Ministry of Education, Science and Technology (The Regional Core Research Program/Institute of Logistics Information Technology).