Matheuristic co-evolutionary algorithm for solving the integrated processing and transportation scheduling problem with processing-transportation composite robots

Abstract

Abstract With the rapid development of robotic technology, a new type of robot, the processing-transportation composite robot (PTCR), has been widely applied in manufacturing systems. It has multiple functions, such as transferring jobs between machines and processing tasks, thereby greatly enhancing production flexibility. Hence, this study investigates the integrated processing and transportation scheduling problem with PTCRs (IPTS-PTCRs) in a job shop environment to minimise the makespan. A mixed-integer linear programming (MILP) model is first designed to define this complex problem. Then, a hybrid algorithm incorporating mathematical programming and a collaborative evolutionary mechanism is designed to solve the model, named the matheuristic co-evolutionary algorithm (MCEA). This algorithm combines multiple heuristics with a random method, resulting in a two-stage collaborative initialisation that generates a high-quality and diverse initial population. A novel collaborative evolutionary mechanism is incorporated into the crossover and mutation operators to enhance interactions between sub-populations. A novel local search based on adaptive decomposed MILP is developed to conduct an in-depth exploration of the best solution. Finally, multiple sets of experiments are conducted to validate the effectiveness of the proposed MILP model and MCEA. The experimental results show that the MILP model can obtain optimal solutions for small-scale instances. The improved components enhance the average performance of the MCEA by 44.1%. The proposed MCEA outperforms five state-of-the-art algorithms in terms of numerical analysis, statistical testing, differential comparison, and stability evaluation.