Memetic algorithms for the job shop scheduling problem with operators

作者：Mencia Raul; Sierra Maria R; Mencia Carlos; Varela Ramiro^*

来源：Applied Soft Computing, 2015, 34: 94-105.

DOI：10.1016/j.asoc.2015.05.004

• Metaheuristics
• Scheduling with operators
• Local search
• Memetic algorithm

The job-shop scheduling problem with operators (JSO) is an extension of the classic job-shop problem in which an operation must be assisted by one of a limited set of human operators, so it models many real life situations. In this paper we tackle the JSO by means of memetic algorithms with the objective of minimizing the makespan. We define and analyze a neighborhood structure which is then exploited in local search and tabu search algorithms. These algorithms are combined with a conventional genetic algorithm to improve a fraction of the chromosomes in each generation. We also consider two different schedule builders for chromosome decoding. All these elements are combined to obtain memetic algorithms which are evaluated over an extensive set of instances. The results of the experimental study show that they reach high quality solutions in very short time, comparing favorably with the state-of-the-art methods.

• 出版日期2015-9