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

Aparallel 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. Alearning 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.