A hybrid algorithm considering continuous transportation for flexible job shop scheduling problem with finite transportation resources

Traditional flexible job shop scheduling ignores transportation or considers production and transportation separately. With factory digitalization and the widespread use of automated guided vehicles (AGVs), the isolated scheduling of production and transportation is no longer sufficient to meet increased productivity demands. Thus, integrated scheduling has become an inevitable option. Previous research has not sufficiently explored the domain knowledge of flexible job shop scheduling problem with finite transportation resources (FJSP-T), and thus the optimal solution cannot be found in an acceptable time using meta-heuristic algorithms. This paper explores FJSP-T to enhance the efficiency of the entire production system, and the objective is to minimize the makespan. The transportation situations of FJSP-T are analyzed, and it has been identified that the key to solving the problem is considering continuous transportation of AGVs. Further, the active decoding method and the initialization method considering continuous transportation are designed. A hybrid algorithm (HA) is proposed, which incorporates local search into the genetic algorithm, and various neighborhood structures for local search are designed. Finally, the superiority of the active decoding method is proved experimentally, and the algorithm performance is tested on two sets of famous benchmark instances (including 67 instances). Compared with other state-of-the-art reported algorithms, the proposed method obtains the new best solutions for 6 instances, and all solutions are not lower than previous results. Meanwhile, the computational time is only a few seconds. As a result, the proposed HA has significantly improved in solving FJSP-T regardless of the solution accuracy and the computational time.