关键词: 分布式混合流水车间, 车辆路径, 分布估计算法, 自适应大邻域搜索, Q学习

Abstract: With the development of global economic integration, manufacturing enterprises have to improve customer service levels from the perspective of the overall supply chain. Production and distribution are two important decisions for make-to-order (MTO) manufacturers. These two decisions are generally made in a sequential manner, in which production schedules are firstly generated by the production department and the transportation routes are subsequently provided by the logistics department. The lack of joint optimization of production scheduling and distribution may increase the operation cost but decrease the customer satisfaction, especially in time-intensive industries, such as newspapers, perishable products, and fashion garments, etc. In addition, to further enhance cost competitiveness and market responsiveness, distributed manufacturing has become a general trend for large manufacturing enterprises because of its higher production profits, lower management risks, and faster manufacturing cycles. Therefore, the coordination of production and distribution among distributed factories has recently attracted an increasing attention in both manufacturing industries and academic community.
This paper focuses on a coordinated distributed hybrid flow shop scheduling and vehicle routing problem (CDHFSVRP) for minimizing the sum of transportation cost and delay cost. A search of available literature shows that no research efforts have been devoted to addressing the CDHFSVRP. The CDHFSVRP consists of two combinatorial optimization problems, namely the distributed hybrid flow shop scheduling problem in the production stage and the vehicle routing problem in the distribution stage. To address the CDHFSVRP, four types of decisions have to be made, namely factory allocation, determination of job processing sequence on machines, vehicle allocation, and distribution route selection. Considering the NP-hardness of the CDHFSVRP, a hybrid algorithm (EDA-ALNS-DQ) that integrates a distribution estimation algorithm (EDA) and an adaptive large neighborhood search (ALNS) is presented to generate coordinated schedules. In this algorithm, EDA firstly employs the probabilistic models to generate populations, and then ALNS with six types of destroy operators and three types of repair operators further improves some good solutions. Although the traditional ALNS applies the well-known roulette wheel selection method to determine the operators, it will be difficult to identify an appropriate operator when most of the considered operators provide similar performance. To enhance the local search performance of ALNS, Q-learning is adopted to exploit the knowledge of solution space and accordingly select the operators based on the reward matrix.
To evaluate the performance of the proposed hybrid algorithm, two sets of test problems are randomly generated based on the previous study of ULLRICH’s. All the compared algorithms are coded with C++ and run on a PC with Intel CoreTM i5-1035G1 CPU 1.00GHz processor. EDA-ALNS-DQ is firstly compared with CPLEX on a set of 18 small-sized problems. Both CPLEX and EDA-ALNS-DQ reach the optimal results of 13 problems, and EDA-ALNS-DQ spends much shorter CPU time. For the other 5 problems, CPLEX fails to obtain the optimal solutions in a predefined computation time, whereas EDA-ALNS-DQ is capable of offering better solutions, each of which is equal or less than the upper bound of CPLEX. Furthermore, EDA-ALNS-DQ is evaluated on a set of 27 large-sized problems, and it statistically performs better than some competitive scheduling algorithms, namely traditional EDA, ALNS, and EDA-ALNS. EDA-ALNS is the same as the proposed EDA-ALNS-DQ, except for determining the destroy and repair operators using the traditional well-known roulette wheel selection method. As a novel meta-heuristic, EDA-ALNS-DQ is capable of making a good balance of search exploration and exploitation, and therefore provides a promising approach to integrating distributed hybrid flow shop scheduling and vehicle routing.
The proposed EDA-ALNS-DQ is expected to help operation managers of manufacturers to make better decisions on the coordination of production and distribution among distributed factories. Future research may focus on integrated production and distribution in more realistic industrial environments, such as the consideration of more complicated production environments, uncertain transportation time, and multiple types of transportation modes, etc. Another potential research area is to develop more effective heuristics or meta-heuristics to deal with the CDHFSVRP.

Key words: distributed hybrid flow shop, vehicle routing, estimation of distribution algorithm, adaptive large neighbourhood search, Q-learning