Memetic algorithms for the job shop scheduling problem with operators

• New neighborhood structures for the job shop scheduling problem with operators (JSO) are proposed and analyzed.
• A new memetic algorithm is proposed for the JSO that incorporates the neighborhood structures in the local search procedure.
• An experimental study was conducted showing that the memetic algorithm compares favorably with the state-of-the-art.

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.

Figure optionsDownload as PowerPoint slide