MILP Modeling and Optimization of Three-Stage Flexible Job Shop Scheduling Problem with Assembly and AGV Transportation

Abstract

The flexible job shop scheduling problem (FJSP) is commonly encountered in practical manufacturing environments. A product is typically built by assembling multiple jobs during actual manufacturing. AGVs are normally used to transport the jobs from the processing shop to the assembly shop, where they are assembled. Therefore, studying the integrated scheduling problem with its processing, transportation, and assembly stages is extremely beneficial and significant. This research studies the three-stage flexible job shop scheduling problem with assembly and AGV transportation (FJSP-T-A), which includes processing jobs, transporting them via AGVs, and assembling them. A mixed integer linear programming (MILP) model is established to obtain optimal solutions. As the MILP model is challenging for solving large-scale problems, a novel co-evolutionary algorithm (NCEA) with two different decoding methods is proposed. In NCEA, a restart operation is developed to improve the diversity of the population, and a multiple crossover strategy is designed to improve the quality of individuals. The validity of the MILP model is proven by analyzing its complexity. The effectiveness of the restart operator, multiple crossovers, and the proposed algorithm is demonstrated by calculating and analyzing the RPI values of each algorithm's results within the time limit and performing a paired t-test on the average values of each algorithm at the 95% confidence level. This paper studies FJSP-T-A by minimizing the makespan for the first time, and presents a MILP model and an NCEA with two different decoding methods.