# Parallel Machine Production and Transportation Operations’ Scheduling with Tight Time Windows

Authors: Yang Jiang; Tong He; Jie Xiong; Xin Wu; Yao Chen
Journal: Complexity
 (2020)

---

## Abstract

This study addresses a parallel machine production and transportation operations’ scheduling problem with a tight time window associated with the transfer and delivery process. The orders located at the parallel machines need to be delivered to customers by train. Each order must be processed within a limited completion time in order for the product to be matched with the optimal trip to its destination within the delivery period. A mathematical analysis method is used to reveal the impact of tight time windows on the scheduling of production and transportation operations. The order transfer redundancy time and order transfer waiting time are employed to reflect the impact scheduling of production on the transfer process. The order delivery redundancy time and order delivery waiting time are used to describe delivery operations. The goal is to maximize the coordination level of order transfer and delivery, which are reflected in the order transfer time and the order delivery time, respectively. Additionally, a simulated annealing algorithm using the column generation technique was developed to solve this problem. The results show that the use of the system coordination model in this method obviously improves the number of successful transfers and deliveries.


---

## Body

## 1. Introduction

Made-to-order or time-sensitive goods are a hot topic that has been addressed by many researchers (Shu et al. [1] and Federgruen et al. [2]), and completed orders are usually required to be delivered to customers within tight time windows. It is believed that benefits are anticipated for integrating production scheduling with transportation operations [3–5]. The sharing of manufacturing resources means that raw materials and semifinished products located at different suppliers and customers are transferred widely and frequently [6, 7].The scheduling of parallel batch production adding transportation operations should integrate tight time windows associated with rail transport plans to ensure that time-sensitive orders are met. The integrated scheduling problem features several special characteristics. Compared with a normal distribution system design problem, the time-critical aspect means that the longest lead-time from a production line to any accessible trip’s destination is subject to time-deadline restrictions that limit the order completion time. Furthermore, the orders should be transferred onto the selected trips within tight time windows imposed by the rail transport plan (Goossens et al. [8] and Fu et al. [9]). The challenges of rail time windows for time-sensitive products can be inferred according to Kang et al. [10] and Wu et al. [11]. Meanwhile, a trip can ship multiple orders to multiple destinations along the same railway line, which enriches the diversity of production schedules and trip selection (Diaz-Madronero et al. [12] and Cao et al. [13]).With the development of off-site production businesses, it is increasingly urgent to coordinate the activities of both production and transportation operations to facilitate the dispatch and receipt of goods. The contributions of this paper are summarized as follows. First, a mathematical formula is developed to describe the relationships between the order transfer redundancy time (OTR), order transfer waiting time (OTW), order delivery redundancy time (ODR), and order delivery waiting time (ODW). The comprehensive formula can be used to improve the connecting relationship between the production line and trains. Meanwhile, the formula is also used to distinguish between the last feasible connecting train and the nonlast ones and to judge whether the feasible connecting trains will be missed. Moreover, a parallel machine production and distribution model is proposed to optimize transfer and delivery considering tight time windows. The complexity of the problem is based primarily on the use of a large set of discrete variables. A simulated annealing algorithm combined with a column generation approach (SACG) is designed to address the numerical testing network model. The results of the numerical example show that the quantitative performances of the delivery timeliness improved by the connecting quality (OT) are much better than those from the view of the delivery time window (OD).In the remainder of this study, we first address some synergetic indexes first to measure the effect of tight time windows on production and transportation operations in Sections3.1 and 3.2. A mathematical method is employed to reveal the relationships between OTR and OTW, and a similar scenario analysis approach is also applied to ODR and ODW for transportation operations. Section 3.3 develops a coordination scheduling model of parallel machine production and transportation operations to maximize the coordination level of order transfer and delivery, which reflects OT and OD. A simulated annealing algorithm using the column generation technique was developed, and we conduct a case study in Section 4. Finally, we conclude this study in Section 5 with discussions on possible extensions.


## 2. Literature Review

Research on the integration of scheduling models of production and distribution, which is known as integrated production-distribution planning or scheduling, has been relatively recent and includes studies such as Pundoor and Chen [5], Pornsing et al. [14], Zhong and Jiang [15], Russel et al. [16], Kishimoto et al. [17], and Ma et al. [18]. Many made-to-order or time-sensitive products are often needed to be delivered to their customers in time-critical modes in which tasks must be executed within a tight time frame. Most extant studies consider only the determination of location decisions or production scheduling through the application of mixed-integer programming (MIP) models (Chen [3]). Their objective functions are to minimize the total operating cost, service time, or budget input [19–27]. These models are subjected to production capacity, fleet size, job processing, or batching constraints, e.g., Cheng et al. [28], Devapriya et al. [29], and Noroozi et al. [30]. For example, Hajiaghaei-Keshteli et al. [21] formulated a mathematical model to study the production and transportation system and capacity and the cost of rail transportation, which were the focus of their article. Jiang et al. [31] applied a scenario analysis method to establish performance measures to minimize the total waiting time. One of the tasks of this paper is to handle tight time windows and limit the deadline-dependent lead time within a given time window. The time deadlines in the transfer and delivery process that are imposed to guarantee on-time delivery have an impact on parallel batch scheduling and transfer trip selection. In particular, parallel batch scheduling complicates the model construction and solution.Parallel batch scheduling problems under the influence of rail timetables are the focus of our research. In previous studies related to production and distribution system design problems, trucks and planes were used to serve customers as an important transport mode, and mathematical models were proposed to optimize the production and road and air transportation coordination problem (Chang and Lee [20], Chen and Vairaktarakis [4], Zhong and Jiang [15], Moons et al. [32], Wang and Cheng [33], Xuan [34], Zhong et al. [35], Seyedhosseini and Ghoreyshi [36], Gong et al. [37], Zandieh and Molla-Alizadeh-Zavardehi [38], and Delavar et al. [39]). For instance, an integrated production and distribution scheduling problem was considered by Devapriya et al. [29], and in this research, the trucks’ routes and fleet size are the important decisions to be made. Azadian et al. [40] researched the order contract producing problem from a manager’s perspective and proposed an integrated scheduling model on the coordination of production and transportation planning. It is not difficult to see that this class of problems employed a vehicle routing problem to satisfy its delivery shipments. The coordination between production and rail transportation in an operational time dimension is one of the less focused-upon aspects and is our major task and focus. The mode of railway transportation is quite different from that of air transportation in transport plans and rolling stock (Pemberton [41]; Ho and Leung [38]). The distribution system design integrates the knowledge of path selection, and the time window caused by the rail timetable makes our focus more novel and interesting. To the best of our knowledge, few studies have investigated these topics in the context of railway timetables.In conclusion, our method not only takes relevant accessibility into account but also takes delivery timeliness as a time window constraint into account. Of course, this approach is common in other articles. However, more importantly, not only delivery timeliness (customer service levels at the individual order level) is guaranteed by the tight delivery time window but a comprehensive formula is also introduced to measure delivery timeliness or customer service levels at the individual order level. The comprehensive formula can be used to distinguish between the last feasible connecting train and the nonlast ones and to judge whether the feasible connecting trains will be missed. Meanwhile, the formula is employed to improve the connecting relationship between the production line and trains. This formula is summarized in the scenario analysis introduced in our research.


## 3. Integrated Scheduling Coordination Model

### 3.1. Order Transfer Redundant Time and Order Transfer Waiting Time

The OTR describes whether the transfer relationship can be established successfully. If OTR is equal to or greater than 0, it means that the transfer can be carried out, as shown in scenarios (a) and (b) in Figure1. However, the order may miss all the feasible trips to its destination when OTR is less than 0, as shown in scenario (c) in Figure 1.Figure 1
Three different relationships between the order completion time and feasible trip departure time.The OTW is the waiting time for orderi when it transfers from the production line l to its selected connecting trip l′. As shown in Figure 1, the OTW is forced to be Mwhen order i misses all the feasible trips, where Mrepresents an infinite value.The OTR and OTW can be calculated by the following equation:(1)tsill′r=tsl′D−tsilA−tsll′Tra,tsill′w=yil′⋅tsl′D′−tsilA−tsll'Tra+1−yil′⋅M.Furthermore, some interconnections between OTR and OTW can be found in Figure1. Based on the three different relationships between the order completion time and feasible trip departure time, OT is introduced in equation (2). In each scenario, two timelines are included: production and transportation. To facilitate modeling, θ is a fixed value that represents the penalty value for missing feasible connecting trips.(2)tsill′h=tsill′r−tsill′w=tsl′D−tsl′D′≥0, whentsill′r−tsill′w≥0,tsill′r−tsill′w=−θ,whentsl′D−tsilA+tsll′Tra<0.


### 3.2. Order Delivery Redundant Time and Order Delivery Waiting Time

The ODR is a measure of delivery success. If the ODR is greater than 0, the delivery is successful, as shown in scenarios (a) and (b) of Figure2. However, the order may violate the tight time window when the ODR is less than 0, as shown in scenario (c) of Figure 2.Figure 2
Three different relationships between the order arrival time and the tight time window.The ODW is the waiting time for orderi before the delivery is allowed by the tight time window. As shown in Figure 2, the ODW is forced to be Mwhen order i violates the tight time window, where Mrepresents an infinite value.The ODR and ODW are formulated in the following equation:(3)teil′r=teiend−yil′⋅teil′A−tel′Tra−1−yil′⋅M,teil′w=maxteibeg−yil′⋅teil′A−tel′Tra+1−yil′⋅M,0+M⋅maxyil′⋅teil′A−teiend−1−yil′⋅M,0.Similarly, some interconnections between the ODR and ODW can be found in Figure2. Based on the three different relationships of the selected trip arrival time and the tight time window, OD is introduced in equation (4). In each scenario, two timelines are included: production and transportation. To facilitate modeling, α, μ, and δ are fixed values that present the penalty values for violating the tight time window and δ≫α.(4)teil′d=teil′r−teil′w=−α,whenyil′⋅teil′A+tel′Tra<teibeg,teil′r−teil′w=μ,whenteibeg<yil′⋅teil′A+tel′Tra<teiend,teil′r−teil′w=−δ,whenyil′⋅teil′A+tel′Tra>teiend.


### 3.3. Model Formulation

The objective function includes two aspects. On the one hand, our research aims to maximize OTR and ODR. This means that the improvement of transfer success and delivery success is a measure of scheduling. On the other hand, minimizing OTW and ODW is a measure of system cooperative efficiency. Therefore, the objective function is to maximize OT and OD as follows, wheretsill′h and teil′d are expressed in equations (2) and (4), respectively:(5)MaxT=∑s∈S∑i∈I∑l∈L∑l′∈L′tsill′h+∑ei∈E∑l′∈L′teil′d.(1)
For any production linel∈L, if i and j are processed continuously, then the order completion time is formulated in (6); if iis the first order on l, then see equation (7).(6)tsjlA+piQi=tsilA,when∑jk∑i≠jkrjil=1,∀l∈L,(7)tsilA=piQi,when∑jk∑i≠jkrjil=0,∀l∈L.(2)
Constraints imposed by integer programming:(8)∑l∑i∑j≠irijl=1,rijl=0,1,∀i,j∈I,l∈L=1,yil′=0,1,∀i∈I,l′∈L′.(3)
The total number of processing steps should not exceed the capacity of each production line.(9)∑l∈L∑i∈Iyil⋅Qi≤Capl∀l.


## 3.1. Order Transfer Redundant Time and Order Transfer Waiting Time

The OTR describes whether the transfer relationship can be established successfully. If OTR is equal to or greater than 0, it means that the transfer can be carried out, as shown in scenarios (a) and (b) in Figure1. However, the order may miss all the feasible trips to its destination when OTR is less than 0, as shown in scenario (c) in Figure 1.Figure 1
Three different relationships between the order completion time and feasible trip departure time.The OTW is the waiting time for orderi when it transfers from the production line l to its selected connecting trip l′. As shown in Figure 1, the OTW is forced to be Mwhen order i misses all the feasible trips, where Mrepresents an infinite value.The OTR and OTW can be calculated by the following equation:(1)tsill′r=tsl′D−tsilA−tsll′Tra,tsill′w=yil′⋅tsl′D′−tsilA−tsll'Tra+1−yil′⋅M.Furthermore, some interconnections between OTR and OTW can be found in Figure1. Based on the three different relationships between the order completion time and feasible trip departure time, OT is introduced in equation (2). In each scenario, two timelines are included: production and transportation. To facilitate modeling, θ is a fixed value that represents the penalty value for missing feasible connecting trips.(2)tsill′h=tsill′r−tsill′w=tsl′D−tsl′D′≥0, whentsill′r−tsill′w≥0,tsill′r−tsill′w=−θ,whentsl′D−tsilA+tsll′Tra<0.


## 3.2. Order Delivery Redundant Time and Order Delivery Waiting Time

The ODR is a measure of delivery success. If the ODR is greater than 0, the delivery is successful, as shown in scenarios (a) and (b) of Figure2. However, the order may violate the tight time window when the ODR is less than 0, as shown in scenario (c) of Figure 2.Figure 2
Three different relationships between the order arrival time and the tight time window.The ODW is the waiting time for orderi before the delivery is allowed by the tight time window. As shown in Figure 2, the ODW is forced to be Mwhen order i violates the tight time window, where Mrepresents an infinite value.The ODR and ODW are formulated in the following equation:(3)teil′r=teiend−yil′⋅teil′A−tel′Tra−1−yil′⋅M,teil′w=maxteibeg−yil′⋅teil′A−tel′Tra+1−yil′⋅M,0+M⋅maxyil′⋅teil′A−teiend−1−yil′⋅M,0.Similarly, some interconnections between the ODR and ODW can be found in Figure2. Based on the three different relationships of the selected trip arrival time and the tight time window, OD is introduced in equation (4). In each scenario, two timelines are included: production and transportation. To facilitate modeling, α, μ, and δ are fixed values that present the penalty values for violating the tight time window and δ≫α.(4)teil′d=teil′r−teil′w=−α,whenyil′⋅teil′A+tel′Tra<teibeg,teil′r−teil′w=μ,whenteibeg<yil′⋅teil′A+tel′Tra<teiend,teil′r−teil′w=−δ,whenyil′⋅teil′A+tel′Tra>teiend.


## 3.3. Model Formulation

The objective function includes two aspects. On the one hand, our research aims to maximize OTR and ODR. This means that the improvement of transfer success and delivery success is a measure of scheduling. On the other hand, minimizing OTW and ODW is a measure of system cooperative efficiency. Therefore, the objective function is to maximize OT and OD as follows, wheretsill′h and teil′d are expressed in equations (2) and (4), respectively:(5)MaxT=∑s∈S∑i∈I∑l∈L∑l′∈L′tsill′h+∑ei∈E∑l′∈L′teil′d.(1)
For any production linel∈L, if i and j are processed continuously, then the order completion time is formulated in (6); if iis the first order on l, then see equation (7).(6)tsjlA+piQi=tsilA,when∑jk∑i≠jkrjil=1,∀l∈L,(7)tsilA=piQi,when∑jk∑i≠jkrjil=0,∀l∈L.(2)
Constraints imposed by integer programming:(8)∑l∑i∑j≠irijl=1,rijl=0,1,∀i,j∈I,l∈L=1,yil′=0,1,∀i∈I,l′∈L′.(3)
The total number of processing steps should not exceed the capacity of each production line.(9)∑l∈L∑i∈Iyil⋅Qi≤Capl∀l.


## 4. Solution Algorithm and Case Study

### 4.1. Simulated Annealing Embedded in the Column Generation Approach

Integration problems such as production-distribution and location-routing problems belong to the NP-hard class, so it is difficult to solve them with exact algorithms (Perl and Daskin [42]). Heuristic approaches have become a more feasible algorithm (Nagy and Salhi [43]). For example, Jiang et al. [31] used a genetic algorithm to handle supply chain management with a single machine and transportation scheduling problem. Additionally, the simulated annealing algorithm [44] and cross-entropy method [11] are effective and have been applied to solve this kind of problem.Simulated annealing (SA) has been proven by many researchers to be an effective method for solving combinatorial optimization problems. Its efficiency and effectiveness in solving a variety of real-world issues, e.g., SA combined with local search for solving vehicle routing problems with time windows (Lin et al. [45]), flow path and location problems (Hamzeei et al. [46]), timetabling problems (Daduna and Vo [47]), network design optimization (Friesz et al. [48]), and distribution center problems (Wei and Zhou. [49]), have been proven. Meanwhile, Ahin and Türkbey [50] presented that the approximate Pareto optimal sets we have found include almost all the previously obtained results and many more approximate Pareto optimal solutions. The results indicated that SA can determine the best solution most times. Therefore, we have a reason to believe that our proposed algorithm is effective and can be applied to solve our problem.Column generation (CG) is an effective method to solve large-scale linear programming problems, especially for large-scale models. The CG technique has been widely used to solve a variety of real-world issues, e.g., crew scheduling (Soumis [51]), production scheduling (Chen and Powell [52]), vehicle routing (Skitt and Levary [53]), air transport (Liang et al. [54]), and issues in the medical and health-related industries (Wang et al. [55]). The detailed branch and price flow chart is shown in Figure 3. In our problem, CG is employed to obtain the parallel batch scheduling solution. The framework of the developed SACG in our research is shown in Figure 4.Figure 3
The branch and price process.Figure 4
The framework of the developed SACG.The encoding style of solutions in Figure5 is a matrix representation. As shown, rows indicate the production line set, and the columns indicate the order set. We used blank cells to fill in some rows since the number of orders in each production line may not be equal. Each order cell must be covered in a certain production line, and the number of cells is equal to the total number of orders.Figure 5
The encoding style and solution expression.After generating an initial solution, replacing moves are performed to search the alternative set. When a dropping move is called, it tries to select the trip. However, due to the condition of the production schedule, it may fail to find a transfer trip or deliver successfully, which may cause the infeasibility of transfer or delivery. The cooling function defines the temperatureTi for each step of the algorithm i. It has a strong impact on the success of the SA algorithm. In the proposed algorithm, the linear strategy for updating the temperature is selected.(10)Ti=Initial_Temperature−i×Cooling_Rate,where Ti represents the temperature at iteration i and Cooling_Rate and Initial_Temperature are the specified constant value and the initial temperature, respectively.Last, in the proposed algorithm, the number of iterations and the number of reduced temperatures with no improvement are used as stopping criteria.


### 4.2. Numerical Test

Figure6 is an example network including multiple production lines, six railway stations, ten orders, and eight railway trips. The starting point of all trips is considered as the location of the production facility. The timetable of all trips is shown in Table 1. The second column indicates the departure time of each trip. Nonzero elements in columns 3 to 8 of Table 1 characterize the path of each trip, and each element indicates the arrival time of the trip at the corresponding station. If the path of a trip covers the destination of an order and the order completion time is before the trip departs, it is a feasible solution that the order selects the trip.Figure 6
Illustration of a sample network.Table 1
Timetable of the sample network.
Train lineDeparture time123456113.5——5—7.5—21.5—4.5————323—4.5——642.54.5—5.5—8—535——6.5——63.54.5—6.5—7.5—74—5.5————84.55.5——7——


#### 4.2.1. Network Solution

We test the model and SACG algorithm on a personal computer with Intel Core i5, 2.60 GHz CPU, and 4 GB RAM. We set the initial temperature to 500, the descent rate to 0.95, and the terminal condition to 0.1. Letθ=100, α=10, μ=10, and δ=100. The cost of the parallel production line is defined as 0 at first, and it will be deeply discussed in the subsequent analysis. The SACG can solve the model in a very short time, and the detailed results are shown in Table 2. The OTW, tsill′w, is the key indicator to measure the production success connection. It shows that 100% of orders achieve successful transfer in the sample network. Meanwhile, ODW is used to judge whether the delivery is successful. From Table 2, we can see that orders 1 and 6 fail to deliver. We obtain the same performance as the experiment in Jiang et al. [31], and the number of successful deliveries is 8. The success rate of order transfer is much better than that in Jiang et al. [31].Table 2
Solution for the sample network.
Processing time/quality0.1/10.3/10.4/20.1/30.1/50.1/30.4/10.2/10.2/10.2/4Delivery time window[1, 7][1, 10][1, 9][1, 10][1, 8][1, 5][1, 6][1, 6][1, 8][1, 4]Production scheduling and train allocated610973142851√√√2√√3√√√45√√678tsill′r2.92.62.82.52.02.72.82.60.13.2tsill′w0.40.10.31.00.50.20.30.10.10.7teil′r−1.51.55.02.50.5−10.50.51.00teil′w0000000000


#### 4.2.2. Algorithm Performance

The iteration trace of SACG is shown in Figure7. It can be seen that the genetic algorithm finds the optimal solution in a very short time. The iteration becomes stable after 10 iterations, and the optimal solution with the objective function is −99.5. The detailed results are presented in the first row of Table 3. Compared with the solution given in [31], the optimized solution we found decreases the total cost by nearly 50%.Figure 7
Iteration trace of SACG.Table 3
Same results for operation scheduling using different algorithms.
MethodSuccessful connectionsSuccessful deliveriesObjective functionOT (tsill′h)OD (teil′d)Parallel production linesSA108–99.520.5–1203GA108–99.520.5–1203We adopt a genetic algorithm to solve the numerical network again and compare the performance with SA. The results of all algorithms are similar, and the correctness of the algorithm is verified (Table3).Two major algorithm parameters related to iteration times are tested here, and the results are shown in Table4. Different combinations of T0 and qare used to solve the problem. The results show that when we set a larger initial temperature (T0) and a larger descent rate (q), the optimal result can be improved to a certain extent. When T0 = 0 or q = 0, the SACG algorithm cannot work.Table 4
Different objective values corresponding to varying SA parameters.
T0\q00.750.80.850.90.9500000001000–102–102.5–99.5–99.5–99.52000–101.5–99.5–99.5–99.5–99.55000–99.5–99.5–99.5–99.5–99.5


#### 4.2.3. Comparison of Different Goals

To verify the proposed model (Max OT + OD), we compare the other two objectives, i.e., Max OT and Max OD. The experiment is completed under the same conditions and with the same data. Table5 lists the details of the results.Table 5
Results of different objectives.
ObjectiveSuccessful transfersSuccessful deliveriesObjective functionMax OT107–210Max OD88–104.5Max (OT + OD)108–99.5There are ten successful transfers and seven successful deliveries when maximizing OT. Meanwhile, maximizing OD can obtain eight successful transfers and eight successful deliveries. Compared with Max OT and Max OD, Max (OT + OD) achieves an obvious improvement in the objective function.


#### 4.2.4. Analysis of Related Parameters

In this section, we test the influence of relevant parameters on the scheduling model. First, we set the parallel production line cost as –∞ and the capacity of each parallel production line as ∞. The result shows that only one production line is needed. The function value is –209, the number of successful transfers is 9, and the number of successful deliveries is 8. We obtained the same optimal solutions as in [31]. Second, we keep other conditions unchanged and test the sensitivity of capacity values when the parallel production line cost is 0. The details are shown in Table 6, and the trend draws the conclusion that the number of successful transfers is 10, and the number of successful deliveries is 8. We can seek some explanation from equation (3). Taking order 1 as an example, regardless of whether the order selects any trip, the earliest arrival time at its destination is 4.5. The earliest arrival time including the transit time is larger than its delivery time window upper bound. Therefore, variations in the capacity only change the number of parallel production lines and have no effect on delivery success. However, as the capacity gradually increases, the number of parallel production lines will stabilize at a certain value.Table 6
Variation with respect to the production line capacity.
Capacity4681015201000 (Inf)Parallel production lines6544333Objective function–99.5–99.5–99.5–99.5–99.5–99.5–99.5Successful connections10101010101010Successful deliveries8888888In addition, we also tested the effect of the cost change on the function value, and the function value also changes when the cost increases gradually. However, almost the same conclusion is always reached: in the sample system, the number of successful transfers is 10, and the number of successful deliveries is 8. The detailed results are shown in Table7.Table 7
Changes in objective function values under different costs.
Production line cost0–10–20–30–40–50–60–70–80–90–100Production line32222222222Objective function–100–122–141–161–182–203–221–242–262–281–301Successful connections1010101010101010101010Successful deliveries88888888888


## 4.1. Simulated Annealing Embedded in the Column Generation Approach

Integration problems such as production-distribution and location-routing problems belong to the NP-hard class, so it is difficult to solve them with exact algorithms (Perl and Daskin [42]). Heuristic approaches have become a more feasible algorithm (Nagy and Salhi [43]). For example, Jiang et al. [31] used a genetic algorithm to handle supply chain management with a single machine and transportation scheduling problem. Additionally, the simulated annealing algorithm [44] and cross-entropy method [11] are effective and have been applied to solve this kind of problem.Simulated annealing (SA) has been proven by many researchers to be an effective method for solving combinatorial optimization problems. Its efficiency and effectiveness in solving a variety of real-world issues, e.g., SA combined with local search for solving vehicle routing problems with time windows (Lin et al. [45]), flow path and location problems (Hamzeei et al. [46]), timetabling problems (Daduna and Vo [47]), network design optimization (Friesz et al. [48]), and distribution center problems (Wei and Zhou. [49]), have been proven. Meanwhile, Ahin and Türkbey [50] presented that the approximate Pareto optimal sets we have found include almost all the previously obtained results and many more approximate Pareto optimal solutions. The results indicated that SA can determine the best solution most times. Therefore, we have a reason to believe that our proposed algorithm is effective and can be applied to solve our problem.Column generation (CG) is an effective method to solve large-scale linear programming problems, especially for large-scale models. The CG technique has been widely used to solve a variety of real-world issues, e.g., crew scheduling (Soumis [51]), production scheduling (Chen and Powell [52]), vehicle routing (Skitt and Levary [53]), air transport (Liang et al. [54]), and issues in the medical and health-related industries (Wang et al. [55]). The detailed branch and price flow chart is shown in Figure 3. In our problem, CG is employed to obtain the parallel batch scheduling solution. The framework of the developed SACG in our research is shown in Figure 4.Figure 3
The branch and price process.Figure 4
The framework of the developed SACG.The encoding style of solutions in Figure5 is a matrix representation. As shown, rows indicate the production line set, and the columns indicate the order set. We used blank cells to fill in some rows since the number of orders in each production line may not be equal. Each order cell must be covered in a certain production line, and the number of cells is equal to the total number of orders.Figure 5
The encoding style and solution expression.After generating an initial solution, replacing moves are performed to search the alternative set. When a dropping move is called, it tries to select the trip. However, due to the condition of the production schedule, it may fail to find a transfer trip or deliver successfully, which may cause the infeasibility of transfer or delivery. The cooling function defines the temperatureTi for each step of the algorithm i. It has a strong impact on the success of the SA algorithm. In the proposed algorithm, the linear strategy for updating the temperature is selected.(10)Ti=Initial_Temperature−i×Cooling_Rate,where Ti represents the temperature at iteration i and Cooling_Rate and Initial_Temperature are the specified constant value and the initial temperature, respectively.Last, in the proposed algorithm, the number of iterations and the number of reduced temperatures with no improvement are used as stopping criteria.


## 4.2. Numerical Test

Figure6 is an example network including multiple production lines, six railway stations, ten orders, and eight railway trips. The starting point of all trips is considered as the location of the production facility. The timetable of all trips is shown in Table 1. The second column indicates the departure time of each trip. Nonzero elements in columns 3 to 8 of Table 1 characterize the path of each trip, and each element indicates the arrival time of the trip at the corresponding station. If the path of a trip covers the destination of an order and the order completion time is before the trip departs, it is a feasible solution that the order selects the trip.Figure 6
Illustration of a sample network.Table 1
Timetable of the sample network.
Train lineDeparture time123456113.5——5—7.5—21.5—4.5————323—4.5——642.54.5—5.5—8—535——6.5——63.54.5—6.5—7.5—74—5.5————84.55.5——7——


### 4.2.1. Network Solution

We test the model and SACG algorithm on a personal computer with Intel Core i5, 2.60 GHz CPU, and 4 GB RAM. We set the initial temperature to 500, the descent rate to 0.95, and the terminal condition to 0.1. Letθ=100, α=10, μ=10, and δ=100. The cost of the parallel production line is defined as 0 at first, and it will be deeply discussed in the subsequent analysis. The SACG can solve the model in a very short time, and the detailed results are shown in Table 2. The OTW, tsill′w, is the key indicator to measure the production success connection. It shows that 100% of orders achieve successful transfer in the sample network. Meanwhile, ODW is used to judge whether the delivery is successful. From Table 2, we can see that orders 1 and 6 fail to deliver. We obtain the same performance as the experiment in Jiang et al. [31], and the number of successful deliveries is 8. The success rate of order transfer is much better than that in Jiang et al. [31].Table 2
Solution for the sample network.
Processing time/quality0.1/10.3/10.4/20.1/30.1/50.1/30.4/10.2/10.2/10.2/4Delivery time window[1, 7][1, 10][1, 9][1, 10][1, 8][1, 5][1, 6][1, 6][1, 8][1, 4]Production scheduling and train allocated610973142851√√√2√√3√√√45√√678tsill′r2.92.62.82.52.02.72.82.60.13.2tsill′w0.40.10.31.00.50.20.30.10.10.7teil′r−1.51.55.02.50.5−10.50.51.00teil′w0000000000


### 4.2.2. Algorithm Performance

The iteration trace of SACG is shown in Figure7. It can be seen that the genetic algorithm finds the optimal solution in a very short time. The iteration becomes stable after 10 iterations, and the optimal solution with the objective function is −99.5. The detailed results are presented in the first row of Table 3. Compared with the solution given in [31], the optimized solution we found decreases the total cost by nearly 50%.Figure 7
Iteration trace of SACG.Table 3
Same results for operation scheduling using different algorithms.
MethodSuccessful connectionsSuccessful deliveriesObjective functionOT (tsill′h)OD (teil′d)Parallel production linesSA108–99.520.5–1203GA108–99.520.5–1203We adopt a genetic algorithm to solve the numerical network again and compare the performance with SA. The results of all algorithms are similar, and the correctness of the algorithm is verified (Table3).Two major algorithm parameters related to iteration times are tested here, and the results are shown in Table4. Different combinations of T0 and qare used to solve the problem. The results show that when we set a larger initial temperature (T0) and a larger descent rate (q), the optimal result can be improved to a certain extent. When T0 = 0 or q = 0, the SACG algorithm cannot work.Table 4
Different objective values corresponding to varying SA parameters.
T0\q00.750.80.850.90.9500000001000–102–102.5–99.5–99.5–99.52000–101.5–99.5–99.5–99.5–99.55000–99.5–99.5–99.5–99.5–99.5


### 4.2.3. Comparison of Different Goals

To verify the proposed model (Max OT + OD), we compare the other two objectives, i.e., Max OT and Max OD. The experiment is completed under the same conditions and with the same data. Table5 lists the details of the results.Table 5
Results of different objectives.
ObjectiveSuccessful transfersSuccessful deliveriesObjective functionMax OT107–210Max OD88–104.5Max (OT + OD)108–99.5There are ten successful transfers and seven successful deliveries when maximizing OT. Meanwhile, maximizing OD can obtain eight successful transfers and eight successful deliveries. Compared with Max OT and Max OD, Max (OT + OD) achieves an obvious improvement in the objective function.


### 4.2.4. Analysis of Related Parameters

In this section, we test the influence of relevant parameters on the scheduling model. First, we set the parallel production line cost as –∞ and the capacity of each parallel production line as ∞. The result shows that only one production line is needed. The function value is –209, the number of successful transfers is 9, and the number of successful deliveries is 8. We obtained the same optimal solutions as in [31]. Second, we keep other conditions unchanged and test the sensitivity of capacity values when the parallel production line cost is 0. The details are shown in Table 6, and the trend draws the conclusion that the number of successful transfers is 10, and the number of successful deliveries is 8. We can seek some explanation from equation (3). Taking order 1 as an example, regardless of whether the order selects any trip, the earliest arrival time at its destination is 4.5. The earliest arrival time including the transit time is larger than its delivery time window upper bound. Therefore, variations in the capacity only change the number of parallel production lines and have no effect on delivery success. However, as the capacity gradually increases, the number of parallel production lines will stabilize at a certain value.Table 6
Variation with respect to the production line capacity.
Capacity4681015201000 (Inf)Parallel production lines6544333Objective function–99.5–99.5–99.5–99.5–99.5–99.5–99.5Successful connections10101010101010Successful deliveries8888888In addition, we also tested the effect of the cost change on the function value, and the function value also changes when the cost increases gradually. However, almost the same conclusion is always reached: in the sample system, the number of successful transfers is 10, and the number of successful deliveries is 8. The detailed results are shown in Table7.Table 7
Changes in objective function values under different costs.
Production line cost0–10–20–30–40–50–60–70–80–90–100Production line32222222222Objective function–100–122–141–161–182–203–221–242–262–281–301Successful connections1010101010101010101010Successful deliveries88888888888


## 4.2.1. Network Solution

We test the model and SACG algorithm on a personal computer with Intel Core i5, 2.60 GHz CPU, and 4 GB RAM. We set the initial temperature to 500, the descent rate to 0.95, and the terminal condition to 0.1. Letθ=100, α=10, μ=10, and δ=100. The cost of the parallel production line is defined as 0 at first, and it will be deeply discussed in the subsequent analysis. The SACG can solve the model in a very short time, and the detailed results are shown in Table 2. The OTW, tsill′w, is the key indicator to measure the production success connection. It shows that 100% of orders achieve successful transfer in the sample network. Meanwhile, ODW is used to judge whether the delivery is successful. From Table 2, we can see that orders 1 and 6 fail to deliver. We obtain the same performance as the experiment in Jiang et al. [31], and the number of successful deliveries is 8. The success rate of order transfer is much better than that in Jiang et al. [31].Table 2
Solution for the sample network.
Processing time/quality0.1/10.3/10.4/20.1/30.1/50.1/30.4/10.2/10.2/10.2/4Delivery time window[1, 7][1, 10][1, 9][1, 10][1, 8][1, 5][1, 6][1, 6][1, 8][1, 4]Production scheduling and train allocated610973142851√√√2√√3√√√45√√678tsill′r2.92.62.82.52.02.72.82.60.13.2tsill′w0.40.10.31.00.50.20.30.10.10.7teil′r−1.51.55.02.50.5−10.50.51.00teil′w0000000000


## 4.2.2. Algorithm Performance

The iteration trace of SACG is shown in Figure7. It can be seen that the genetic algorithm finds the optimal solution in a very short time. The iteration becomes stable after 10 iterations, and the optimal solution with the objective function is −99.5. The detailed results are presented in the first row of Table 3. Compared with the solution given in [31], the optimized solution we found decreases the total cost by nearly 50%.Figure 7
Iteration trace of SACG.Table 3
Same results for operation scheduling using different algorithms.
MethodSuccessful connectionsSuccessful deliveriesObjective functionOT (tsill′h)OD (teil′d)Parallel production linesSA108–99.520.5–1203GA108–99.520.5–1203We adopt a genetic algorithm to solve the numerical network again and compare the performance with SA. The results of all algorithms are similar, and the correctness of the algorithm is verified (Table3).Two major algorithm parameters related to iteration times are tested here, and the results are shown in Table4. Different combinations of T0 and qare used to solve the problem. The results show that when we set a larger initial temperature (T0) and a larger descent rate (q), the optimal result can be improved to a certain extent. When T0 = 0 or q = 0, the SACG algorithm cannot work.Table 4
Different objective values corresponding to varying SA parameters.
T0\q00.750.80.850.90.9500000001000–102–102.5–99.5–99.5–99.52000–101.5–99.5–99.5–99.5–99.55000–99.5–99.5–99.5–99.5–99.5


## 4.2.3. Comparison of Different Goals

To verify the proposed model (Max OT + OD), we compare the other two objectives, i.e., Max OT and Max OD. The experiment is completed under the same conditions and with the same data. Table5 lists the details of the results.Table 5
Results of different objectives.
ObjectiveSuccessful transfersSuccessful deliveriesObjective functionMax OT107–210Max OD88–104.5Max (OT + OD)108–99.5There are ten successful transfers and seven successful deliveries when maximizing OT. Meanwhile, maximizing OD can obtain eight successful transfers and eight successful deliveries. Compared with Max OT and Max OD, Max (OT + OD) achieves an obvious improvement in the objective function.


## 4.2.4. Analysis of Related Parameters

In this section, we test the influence of relevant parameters on the scheduling model. First, we set the parallel production line cost as –∞ and the capacity of each parallel production line as ∞. The result shows that only one production line is needed. The function value is –209, the number of successful transfers is 9, and the number of successful deliveries is 8. We obtained the same optimal solutions as in [31]. Second, we keep other conditions unchanged and test the sensitivity of capacity values when the parallel production line cost is 0. The details are shown in Table 6, and the trend draws the conclusion that the number of successful transfers is 10, and the number of successful deliveries is 8. We can seek some explanation from equation (3). Taking order 1 as an example, regardless of whether the order selects any trip, the earliest arrival time at its destination is 4.5. The earliest arrival time including the transit time is larger than its delivery time window upper bound. Therefore, variations in the capacity only change the number of parallel production lines and have no effect on delivery success. However, as the capacity gradually increases, the number of parallel production lines will stabilize at a certain value.Table 6
Variation with respect to the production line capacity.
Capacity4681015201000 (Inf)Parallel production lines6544333Objective function–99.5–99.5–99.5–99.5–99.5–99.5–99.5Successful connections10101010101010Successful deliveries8888888In addition, we also tested the effect of the cost change on the function value, and the function value also changes when the cost increases gradually. However, almost the same conclusion is always reached: in the sample system, the number of successful transfers is 10, and the number of successful deliveries is 8. The detailed results are shown in Table7.Table 7
Changes in objective function values under different costs.
Production line cost0–10–20–30–40–50–60–70–80–90–100Production line32222222222Objective function–100–122–141–161–182–203–221–242–262–281–301Successful connections1010101010101010101010Successful deliveries88888888888


## 5. Conclusions

Many studies focus on production allocation, but few pay attention to the coordination and scheduling of orders and transportation in a time-critical mode. This paper focuses on the parallel batch scheduling of production and transportation with respect to synergy in the time dimension. We adopt a scenario analysis method to reveal some internal mechanisms in the transfer and delivery process. Several interconnections between OTR and OTW in the transfer process are found, and OT is introduced based on these findings. Similarly, ODR and ODW in the delivery process are commonly expressed by OD. A column-generation-based simulated annealing algorithm is proposed to solve the problem. Compared with Max OT and Max OD, Max (OT + OD) achieves an obvious improvement in the objective function. Meanwhile, the results of our research are compared with those of similar studies, and the model and algorithm are proven to be workable.Our research can be further expanded. In practice, due to some unexpected situations, train schedules may change, so it would be worth studying how to formulate strategies to eliminate any negative effects of such changes.



---

*Source: 1381340-2020-10-10.xml*