关键词: 生产配送联合调度, 多回程车辆路径, 柔性作业车间, 文化基因算法

Abstract: With an increasingly fierce market competition, manufacturing enterprises are facing great pressure to survive. In order to shorten the order delivery cycle and improve customer satisfaction, manufacturing enterprises begin to directly deliver the finished products to the customers or the front warehouse after the production. This new mode puts forward higher requirements for the collaboration between production scheduling and logistics delivery. However, in the real world, managers often make a production scheduling plan first, and then formulate a delivery scheduling plan based on the production plan. This independent and separated optimization method cannot effectively coordinate production scheduling and logistics distribution, resulting in meeting customer response time requirements at a higher cost, or reducing costs at the expense of violating customer response time constraints, which cannot realize the original intention of the new mode.
Motivated by the collaborative production and delivery service of a household appliance manufacturer, an integrated production and delivery scheduling problem is studied. The household appliance production workshop studied in this paper is a typical flexible job shop, but there is no research on the integrated optimization of flexible job shop production scheduling and delivery routing. At the same time, the existing literature hardly considers the multi-trip vehicle routing problem in delivery. Considering flexible job shop scheduling, multi-vehicle delivery scheduling and multi-trip vehicle routing, a mixed integer programming model is developed to minimize the total cost including order completion time cost and delivery distance cost. This model is a typical NP-hard problem. Small-sized instances can be directly solved by calling a commercial solver, while large-sized instances are difficult to be solved to optimal by a solver.
In order to solve large-sized instances, an improved memetic algorithm (IMA) framework is adopted with a new designed chromosome coding according to the characteristics of the problem. IMA improves search efficiency by introducing the idea of local search into the mutation operator of the Genetic Algorithm. The local search procedures are used to educate the offspring so that they have a large amount of professional knowledge. A new parent selection method based on the Softmax function is proposed, which not only ensures that the parents of the previous iteration is better and the solution declines faster, but also ensures the parents of the later iteration to be more diverse, so that the algorithm can jump out of the local optimum. The proposed IMA also includes two crossover operators and four education operators. The algorithm evaluates the quality and diversity of chromosomes through fitness and biased fitness function, and adopts a survivor selection method that considers the contribution of diversity, which can effectively balance the exploration and exploitation of the algorithm. Finally, a three-step local search is designed to fine-tune the optimal individual to improve the quality of the optimal solution and speed up the convergence of the algorithm.
The numerical experiments show that when the number of orders and machines is greater than 5, the Gurobi solver cannot find the global optimal solution within an acceptable time, while the proposed IMA can find the optimal or very close to optimal solution for small-sized instances within 10 seconds. For large-sized instances, the proposed IMA shows better performance than the classical genetic algorithm and the three algorithms that remove the improved operator, indicating that the improved operator designed in this paper has a certain effect. So, the performance of the algorithm and the effectiveness of the improved operator are also verified. On the other hand, integrated scheduling is more effective than separated scheduling in both small-sized and large-sized instances. In scenarios where there are many distinct customer nodes, long-distance delivery, and more emphasis on time objectives, the advantages of integrated scheduling are more obvious.
This research provides theoretical guidance for the decision of integrated production and delivery scheduling. Some uncertain factors, such as dynamic arrival of orders and uncertain transportation time affected by congestion, can be taken into account in future research to update the scheduling decision in real time and solve the dynamic integrated scheduling problem. It is also possible to study the integrated optimization of networked production planning for multi-workshop production and trunk distribution planning.

Key words: integrated production and delivery scheduling, multi-trip vehicle routing, flexible job shop, memetic algorithm