Solving parallel machines job-shop scheduling problems by an adaptive algorithm

Abstract

A parallel machines job-shop problem is a generalisation of a job-shop problem to the case when there are identical machines of the same type. Job-shop problems encountered in a flexible manufacturing system, train timetabling, production planning and in other real-life scheduling systems. This paper presents an adaptive algorithm with a learning stage for solving the parallel machines job-shop problem. A learning stage tends to produce knowledge about a benchmark of priority dispatching rules allowing a scheduler to improve the quality of a schedule which may be useful for a similar scheduling problem. Once trained on solving sample problems (usually with small sizes), the adaptive algorithm is able to solve similar job-shop problems with larger size better than heuristics used as a benchmark at the learning stage. For using an adaptive algorithm with a learning stage, a job-shop problem is modelled via a weighted mixed graph with a conflict resolution strategy used for finding an appropriate schedule. We show how to generalise the mixed graph model for solving parallel machines job-shop problem. The proposed adaptive algorithm is tested on benchmark instances.

Keywords:

• flexible job-shop
• identical machines
• adaptive algorithm
• learning

Acknowledgements

The authors would like to thank the anonymous referees for their useful suggestions and comments on the early version of the paper.