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

摘要： 为了缩短订单交付周期、提高顾客满意度,制造企业正在向“工厂下线直发”的模式转型,成品从工厂下生产线后,直接发送到客户或前置仓。这一模式对生产调度和物流配送之间协同提出了更高的要求。为了解决这一问题,考虑柔性作业车间生产调度、多车配送调度和多回程车辆路径规划,以最小化总成本为目标,建立了混合整数规划模型。该模型是典型的NP-hard问题,小规模算例可以直接调用商用优化器进行求解,大规模算例难以采用精确算法进行求解。因此,基于文化基因算法框架,针对问题特征设计了染色体编码和多种改进算子。数值实验表明,联合调度比分解调度更有效,且验证了算法的性能和改进算子的有效性。在不重复客户节点较多、远距离配送以及时间目标权重较高的场景中,联合调度的优势更为显著。研究为生产—配送联合调度决策提供了理论指导。

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