A Self-Adaptive Memetic Algorithm for Distributed Job Shop Scheduling Problem

Abstract

Distributed scheduling has become a common manufacturing mode, and the distributed job scheduling problem (DJSP) has attracted more manufacturers and researchers in the field of operation research. For the distributed scheduling problem, it emphasizes the flexibility of factory assignment and determines the sequence of operation related to each machine in related factories. In this paper, a mixed-integer linear programming model for the DJSP is formulated to be optimized by an SMA. Also in this paper, a self-adaptive memetic algorithm (SMA) is proposed to obtain a near-optimal solution in a limited time for the DJSP. To strengthen the effectiveness of the SMA, an independent encoding is designed with jobs assigned to factories and the sequence of operation. In the proposed algorithm, various local search strategies related to the critical path in the critical factory are designed to enhance the quality of the solution. Moreover, the self-adaptive scheme for solution improvement is formulated to reduce the search time and avoid prematurity effectively. To demonstrate the performance of the proposed algorithm, numerical experiments are carried out on 120 different instances extended from the well-known job shop scheduling benchmarks. The proposed SMA has updated 30 instance records in 120 instances and it has obtained the 91 best records in 120 instances. According to the comparison, an SMA is a more effective algorithm that could update several records of benchmarks.

Keywords

• distributed job shop scheduling problem
• self-adaptive memetic algorithm
• makespan
• chromosome representation