A genetic-search-guided greedy algorithm for multi-resource shop scheduling with resource flexibility

Abstract

The Multi-Resource Job-Shop Problem with resource Flexibility (MJSPF) provides a framework for realistic modeling of a wide range of problems encountered in manufacturing systems. The problem is a generalization of the classical job shop problem. Each operation may require a combination of more than one resource and there may be several feasible resource combinations for each operation. The scheduling problem consists in both assigning resources to operations and sequencing operations on the selected resources in order to minimize the makespan. In this paper, a polynomial algorithm for solving a special case with two jobs is proposed, and the concept of a combined job is introduced. Building on these results, a greedy heuristic that considers jobs sequentially according to a given job sequence is proposed for scheduling any number of jobs. The greedy heuristic is guided by a genetic algorithm in order to identify effective job sequences. Computational results on benchmark instances for special cases of the MJSPF show that the general method is competitive with respect to the best known heuristic approaches dedicated to these special cases.

Keywords:

• Multi-purpose machine job shop
• resource flexibility
• multiprocessor
• multiple machine
• geometric approach
• greedy heuristic
• genetic algorithms

Acknowledgment

The authors are grateful to two anonymous referees and the associate editor for their constructive comments and suggestions, which helped to improve the presentation of the paper.