# A Mathematical Model for Multiworkshop IPPS Problem in Batch Production

Authors: Li Ba; Yan Li; Mingshun Yang; Xueliang Wu; Yong Liu; Xinqin Gao; Zhihong Miao
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Integrated Process Planning and Scheduling (IPPS) problem is an important issue in production scheduling. Actually, there exit many factors affecting scheduling results. Many types of workpieces are commonly manufactured in batch production. Moreover, due to differences among process methods, all processes of a workpiece may not be performed in the same workshop or even in the same factory. For making IPPS problem more in line with practical manufacturing, this paper addresses an IPPS problem with batches and limited vehicles (BV-IPPS). An equal batch splitting strategy is adopted. A model for BV-IPPS problem is established. Makespan is the objective to be minimized. For solving the complex problem, a particle swarm optimization (PSO) with a multilayer encoding structure is proposed. Each module of the algorithm is designed. Finally, case studies have been conducted to validate the model and algorithm.


---

## Body

## 1. Introduction

Process planning and production scheduling are two indispensable subsystems in manufacturing systems. In traditional manufacturing, they are performed independently in series. A process planning subsystem determines the process route for each workpiece, and a scheduling subsystem allocates manufacturing resources according to the results from the process planning subsystem [1–3]. The independent and serial running mode of the two subsystems may lead to unrealistic process routes, uneven resource utilization, and bottlenecks in scheduling [1–3]. Integration of the two subsystems is an effective method to eliminate conflicts of resources, shorten finishing times of workpieces, and improve machine utilization [1–3]. The integration of process planning with scheduling is important for the development of manufacturing systems.Integrated process planning and scheduling (IPPS) problem is a significant issue in the field of production scheduling. Existing research focusing on IPPS problems has typically considered only process stages. Few studies have considered batches in the IPPS problem even though many workpieces are processed in batch production. Batch splitting problem has been a significant issue in real production environments [4, 5]. Furthermore, there are some cases in which all processes cannot be accomplished in the same workshop due to their different processing characteristics. Because machines may be located in different workshops, transportation between them must be considered in scheduling which will influence the finishing time of the workpieces.Batch splitting problem involves splitting lot numbers and splitting lot sizes for each workpiece. In fixed batch splitting, the lot numbers of all workpieces are constant, and the lot sizes of all sublots of a workpiece are equal. Equal batch splitting is typically used in production scheduling problems [4, 6]. The lot size of each sublot of a workpiece is equal, but the lot numbers of different types of workpieces are not equal (the lot number of each workpiece can be changed). Therefore, equal batch splitting is more flexible than fixed batch splitting. Equal batch splitting is adopted in this paper because fixed batch splitting may cause an imbalance between machine and load.In conclusion, batch and transportation are simultaneously considered so that the IPPS problem better aligns with the real production environment. An IPPS problem considering equal batch splitting and limited vehicles (BV-IPPS) is proposed. The mathematical model of BV-IPPS is established to minimize the makespan. Given the complexity of the problem, a particle swarm optimization (PSO) is designed with a multilayer encoding structure. Finally, the model and algorithm are proven through a case study.This paper initially provides a brief literature review related to IPPS problem in Section2. A mathematical model for the problem is proposed in Section 3. A PSO with a multilayer encoding structure is designed in Section 4. The computational results are analysed in Section 5. Finally, the conclusions are provided in Section 6.


## 2. Literature Review

The basic IPPS problem can be defined as follows [7]: “Given a set of n parts that are to be processed on m machines with operations including alternative manufacturing resources, select suitable manufacturing resources and sequences of operations to determine a schedule in which the precedence constraints among operations can be satisfied and the corresponding objectives can be achieved.”Researchers began studying IPPS problem in the 1980s [8]. Chryssolouris et al. [9] proposed an approach to integrate process planning and scheduling. An increasing number of studies have focused on the IPPS problem in recent years.Phanden et al. [1] determined that considering process planning and scheduling separately may cause many problems and limitations. They introduced three common approaches for integrating process planning and scheduling. Potential avenues for future IPPS work are discussed at the end of the paper.(  1) Integrated Approaches. Saygin and Kilic [10] proposed a framework for integrating process planning and scheduling that consisted of machine tool selection, process plan selection, scheduling, and rescheduling modules. The framework was validated using many samples. Phanden et al. [11] established a makespan-targeted IPPS model composed of a process route selection module, scheduling module, analysis module, and process route modification module. A genetic algorithm (GA) was designed to solve the model. The availability of the model and algorithm was proven by a case study. Manupati et al. [12] proposed a mobile agent-based approach for integrating process planning and scheduling. A mathematical model for a biobjective IPPS problem with consideration of transportation was established. The approach was proven through many examples.(  2) Improvements to Algorithms. Petrović et al. [3] proposed a hybrid algorithm based on PSO and chaos theory. The advantages of the hybrid algorithm have been proven through many benchmarks by comparisons with other approaches. Xia et al. [13] proposed a dynamic IPPS problem with consideration of machine breakdown and new job arrival. A model for the problem was established. A hybrid GA with variable neighbourhood search was designed to solve the problem. Zhang and Wong [14] proposed a GA framework and integrated ant colony optimization (ACO) into the framework for solving IPPS problem. Lian et al. [15] proposed an imperialist competitive algorithm (ICA) to solve IPPS problem. Lian et al. [16] proposed a mathematical model for process planning problem with an objective of total cost minimization. An ICA was designed to solve the problem. Shao et al. [17] established an IPPS model with two objectives. Makespan and machine utilization are objectives which will be optimized. A modified genetic algorithm-based approach was designed for solving the problem. Li et al. [18] proposed an evolutionary algorithm-based approach for solving IPPS problem. Guo et al. [7] presented an advanced PSO approach to solve the IPPS problem. The advantages of PSO were proven by comparison with other intelligent algorithms. Seker et al. [19] proposed a hybrid heuristic algorithm based on a GA and artificial neural network (ANN) to solve IPPS problem.(  3) Other Research on IPPS Problem. Zhang et al. [20] established an IPPS model with the total energy consumption as the objective. A genetic algorithm-based approach was proposed to solve the problem. Haddadzade et al. [2] proposed an IPPS problem that considered stochastic processing time. The Dijkstra algorithm and Monte Carlo sampling method were used to create examples, and a hybrid algorithm based on simulated annealing and tabu search was designed to solve the problem. Kis [21] proposed a particular job-shop scheduling problem in a chemical production environment. The process routes were directed acyclic graphs and consisted of several alternative subgraphs. A tabu search and GA were proposed to solve the problem. Li and McMahon [22] proposed a multiobjective IPPS problem. The target to be optimized was obtained by combining multiple objectives through linear weighting. A simulated annealing algorithm (SAA) was proposed to solve the problem. Moon and Seo [23] considered transportation in IPPS problem with the makespan as the objective, and an evolution algorithm was proposed to solve the problem.Many existing studies on IPPS problem only involve the process stage; few consider batching, which may cause the IPPS problem to unrealistic. In real production, many workpieces are processed in batches. Batch splitting problem is a significant issue in real production environments [4, 5]. Furthermore, all processes may not able to be processed in the same workshop due to different process types. Transportation is another factor that must be considered in real production environments. References [12, 23] considered transport in an IPPS problem but did not consider the amounts and locations of transports, which may cause the methodology to not fit real production environments.Recently, several studies have focused on production scheduling problems considering batch splitting. For example, batching has been considered in a job-shop scheduling problem (JSP) [4, 24], flow-shop scheduling problem (FSP) [25, 26], and parallel machine scheduling problem [27]. Research on production scheduling problems considering batch splitting has mainly focused on JSP and FSP. As manufacturing technology has improved over time, normal machine tools now coexist with numerically controlled machine tools and machining centres in many workshops [28]; however, because different machines have similar functions, multiple process routes are designed for the same workpiece to fully utilize different machines [1–3]. Designing multiple process routes for a workpiece is of great significance for improving the flexibility of scheduling and reducing resource conflicts [1–3]. IPPS problem involves parallel machines and alternative process routes simultaneously. Compared to JSP and FSP, IPPS problem has a larger solution space and is more complex. The scheduling result of IPPS problem is more in line with real production situations. IPPS problem has been identified as NP-hard [19].Based on the above literature, this paper proposes an IPPS problem considering equal batch splitting and limited vehicles with the makespan as the objective to be minimized. A model for the problem is built, and a PSO with a multilayer encoding structure is proposed. Finally, the model and algorithm are validated through a case study.


## 3. BV-IPPS Problem Formulation

### 3.1. Problem Description

There are different workpieces that must be processed in a factory. The batches of different workpieces are different. Each workpiece can be processed through more than one process route, and each process can be processed by more than one machine. There are several vehicles for transporting workpieces. Under these conditions, the makespan is regarded as an objective. An optimal solution is obtained by selecting the process routes, machines, vehicles and sorting process sequences for each workpiece.A simple example is shown to illustrate BV-IPPS problem. An order involves two types of jobs:J1 and J2. A lot of J1 and J2 will be processed. J1 is not divided. J2 is divided into two sublots: JS21 and JS22. There are six machines: M1–M6. There are two workshops: W1 and W2. M1, M2 and M3 belong to W1. M4, M5 and M6 belong to W2. There are four process methods: P1, P2, P3 and P4. M1 is able to complete P1. M2 and M3 are able to complete P2. M4 and M5 are able to complete P3. M6 is able to complete P4. There are three process routes: R1(P1-P2-P3-P4), R2(P1-P2-P4) and R3(P2-P3-P4). R1 is designed for J1. R2 and R3 are designed for J2. There are three vehicles for transmitting jobs: V1, V2 and V3. Assuming R1 is used for J1, R2 is used for JS21, and R3 is used for JS22. Processing flow of a scheduling solution is shown as Figure 1.Figure 1
Processing flow of a scheduling solution.


### 3.2. BV-IPPS Model

Based on the above descriptions, a BV-IPPS model is proposed. The following parameters are defined to establish the model for the problem:n: Number of workpieces;m: Number of machines;t: Number of vehicles;w: Number of workshops;p: Number of process routes;Ji: Workpiece i, i∈[1,n];JSil: lth sublot of Ji, l∈[1,bci];Rk: Process route k, k∈[1,p];Mj: Machine j, j∈[1,m];Vr: Vehicle r, r∈[1,t];Wg: Workshop g, g∈[1,w];psk: Number of processes of Rk;bi: Lot size of Ji;bci: Lot number of Ji;bsil: Lot size of JSil;WMj: Workshop in which Mj is located;WRr: Current workshop in which Vr is located;TMSj: Earliest time at which Mj can be used;TJSil: Earliest time at which JSil can be processed;TSJilkvj: Rk is chosen for JSil. The starting time of the vth process of Rk, which is processed on Mj, v∈[1,psk];TMJilkvj: Rk is chosen for JSil. The process time of the vth process per one piece of Ji, which is processed on Mj;TFJilkvj: Rk is chosen for JSil. The completion time of the vth process of Rk, which is processed on Mj;TFFJil: Completion time of JSil;TRFrg′g″: Transport time of Vr, which travels from Wg′ to Wg″, g′∈[1,w], g″∈[1,w];TRSr: Earliest time at which Vr can be used;RJPilk: Boolean value. If Rk is chosen for JSil, the value is 1; otherwise, it is 0;RPMkvj: Boolean value. If the vth process of Rk is processed on Mj, the value is 1; otherwise, it is 0;RMWjg: Boolean value. If Mj is located in Wg, the value is 1; otherwise, it is 0.Based on the above parameters, the makespan is the target to be minimized. The objective function is established as:(1)min⁡max⁡TFFJili∈1,n,l∈1,bci.The following constraints are considered in the model:(1)
The sum of the lot sizes of each sublot of a workpiece is equal to the total lot size of the workpiece.(2)∑l=1bcibsil=bi(2)
One machine can only process one process of a sublot of a workpiece at a time.If from timet,(3)RJPilk·RPMkv′j=1then during time slott,t+TMJilkv′j·bsil, (4)∑v=1pskRJPilk·RPMkvj=1v′∈1,psk.(3)
One process cannot be processed by more than one machine.If from timet,(5)RJPilk·RPMkvj′=1then during time slot[t,t+TMJilkvj′·bsil],(6)∑j=1mRJPilk·RPMkvj=1j′∈1,m.(4)
Assume thatRJPilk·RPMkv″j′=1, RMWj′g′=1, RJPilk·RPMkv″-1j″=1, and RMWj″g″=1. Then, the v″-1 th process of JSil is completed. ∀r′:(7)max⁡TRSr′+TRFr′WRr′g″,TJSil+TRFr′g″g′=min⁡max⁡TRSr+TRFrWRrg″,TJSil+TRFrg″g′Then,(8)TSJilkv″j′=max⁡max⁡TRSr′+TRFr′WRr′g″,TJSil+TRFr′g″g′,TMSj′Based on constraint(4), WRr′, TRSr′, TFJilkv″j′, TJSil and TMSj′ are updated by the following formulas:(9)WRr′=g′(10)TRSr′=max⁡TRSr′+TRFr′WRr′g″,TJSil+TRFr′g″g′(11)TFJilkv″j′=TSJilkv″j′+TMJilkv″j′·bsil(12)TMSj′=TSJilkv″j′+TMJilkv″j′·bsil(13)TJSil=TSJilkv″j′+TMJilkv″j′·bsilIfv″=psk, then(14)TFFJil=TSJilkv″j′+TMJilkv″j′·bsilv″∈2,psk,r′∈1,tFormula (2) ensures that each batch of a workpiece is correct. The relationships between processes and machines are constrained through formulas (3)–(6) to ensure the rationality of the manufacturing process. If a process of a sublot of the workpiece and the front of the process are performed in different workshops, a vehicle for transporting the sublot of the workpiece is determined by formula (7). The starting time of each process is calculated by formula (8). Several parameters are calculated based on formula (8). The vehicles’ locations are updated based on formula (9). The vehicles’ earliest free time are updated by formula (10). The completion time for each process is calculated by formula (11). The machines’ earliest free time is updated by formula (12). The earliest starting time of each sublot of the workpiece is updated by formula (13). The final completion time of each sublot of workpiece is calculated by formula (14).


## 3.1. Problem Description

There are different workpieces that must be processed in a factory. The batches of different workpieces are different. Each workpiece can be processed through more than one process route, and each process can be processed by more than one machine. There are several vehicles for transporting workpieces. Under these conditions, the makespan is regarded as an objective. An optimal solution is obtained by selecting the process routes, machines, vehicles and sorting process sequences for each workpiece.A simple example is shown to illustrate BV-IPPS problem. An order involves two types of jobs:J1 and J2. A lot of J1 and J2 will be processed. J1 is not divided. J2 is divided into two sublots: JS21 and JS22. There are six machines: M1–M6. There are two workshops: W1 and W2. M1, M2 and M3 belong to W1. M4, M5 and M6 belong to W2. There are four process methods: P1, P2, P3 and P4. M1 is able to complete P1. M2 and M3 are able to complete P2. M4 and M5 are able to complete P3. M6 is able to complete P4. There are three process routes: R1(P1-P2-P3-P4), R2(P1-P2-P4) and R3(P2-P3-P4). R1 is designed for J1. R2 and R3 are designed for J2. There are three vehicles for transmitting jobs: V1, V2 and V3. Assuming R1 is used for J1, R2 is used for JS21, and R3 is used for JS22. Processing flow of a scheduling solution is shown as Figure 1.Figure 1
Processing flow of a scheduling solution.


## 3.2. BV-IPPS Model

Based on the above descriptions, a BV-IPPS model is proposed. The following parameters are defined to establish the model for the problem:n: Number of workpieces;m: Number of machines;t: Number of vehicles;w: Number of workshops;p: Number of process routes;Ji: Workpiece i, i∈[1,n];JSil: lth sublot of Ji, l∈[1,bci];Rk: Process route k, k∈[1,p];Mj: Machine j, j∈[1,m];Vr: Vehicle r, r∈[1,t];Wg: Workshop g, g∈[1,w];psk: Number of processes of Rk;bi: Lot size of Ji;bci: Lot number of Ji;bsil: Lot size of JSil;WMj: Workshop in which Mj is located;WRr: Current workshop in which Vr is located;TMSj: Earliest time at which Mj can be used;TJSil: Earliest time at which JSil can be processed;TSJilkvj: Rk is chosen for JSil. The starting time of the vth process of Rk, which is processed on Mj, v∈[1,psk];TMJilkvj: Rk is chosen for JSil. The process time of the vth process per one piece of Ji, which is processed on Mj;TFJilkvj: Rk is chosen for JSil. The completion time of the vth process of Rk, which is processed on Mj;TFFJil: Completion time of JSil;TRFrg′g″: Transport time of Vr, which travels from Wg′ to Wg″, g′∈[1,w], g″∈[1,w];TRSr: Earliest time at which Vr can be used;RJPilk: Boolean value. If Rk is chosen for JSil, the value is 1; otherwise, it is 0;RPMkvj: Boolean value. If the vth process of Rk is processed on Mj, the value is 1; otherwise, it is 0;RMWjg: Boolean value. If Mj is located in Wg, the value is 1; otherwise, it is 0.Based on the above parameters, the makespan is the target to be minimized. The objective function is established as:(1)min⁡max⁡TFFJili∈1,n,l∈1,bci.The following constraints are considered in the model:(1)
The sum of the lot sizes of each sublot of a workpiece is equal to the total lot size of the workpiece.(2)∑l=1bcibsil=bi(2)
One machine can only process one process of a sublot of a workpiece at a time.If from timet,(3)RJPilk·RPMkv′j=1then during time slott,t+TMJilkv′j·bsil, (4)∑v=1pskRJPilk·RPMkvj=1v′∈1,psk.(3)
One process cannot be processed by more than one machine.If from timet,(5)RJPilk·RPMkvj′=1then during time slot[t,t+TMJilkvj′·bsil],(6)∑j=1mRJPilk·RPMkvj=1j′∈1,m.(4)
Assume thatRJPilk·RPMkv″j′=1, RMWj′g′=1, RJPilk·RPMkv″-1j″=1, and RMWj″g″=1. Then, the v″-1 th process of JSil is completed. ∀r′:(7)max⁡TRSr′+TRFr′WRr′g″,TJSil+TRFr′g″g′=min⁡max⁡TRSr+TRFrWRrg″,TJSil+TRFrg″g′Then,(8)TSJilkv″j′=max⁡max⁡TRSr′+TRFr′WRr′g″,TJSil+TRFr′g″g′,TMSj′Based on constraint(4), WRr′, TRSr′, TFJilkv″j′, TJSil and TMSj′ are updated by the following formulas:(9)WRr′=g′(10)TRSr′=max⁡TRSr′+TRFr′WRr′g″,TJSil+TRFr′g″g′(11)TFJilkv″j′=TSJilkv″j′+TMJilkv″j′·bsil(12)TMSj′=TSJilkv″j′+TMJilkv″j′·bsil(13)TJSil=TSJilkv″j′+TMJilkv″j′·bsilIfv″=psk, then(14)TFFJil=TSJilkv″j′+TMJilkv″j′·bsilv″∈2,psk,r′∈1,tFormula (2) ensures that each batch of a workpiece is correct. The relationships between processes and machines are constrained through formulas (3)–(6) to ensure the rationality of the manufacturing process. If a process of a sublot of the workpiece and the front of the process are performed in different workshops, a vehicle for transporting the sublot of the workpiece is determined by formula (7). The starting time of each process is calculated by formula (8). Several parameters are calculated based on formula (8). The vehicles’ locations are updated based on formula (9). The vehicles’ earliest free time are updated by formula (10). The completion time for each process is calculated by formula (11). The machines’ earliest free time is updated by formula (12). The earliest starting time of each sublot of the workpiece is updated by formula (13). The final completion time of each sublot of workpiece is calculated by formula (14).


## 4. PSO with a Multilayer Encoding Structure

Based on the description and modelling of the problem, the BV-IPPS problem is an NP-hard problem. PSO was proposed by Kennedy and Eberhart in 1995 [29] and was formerly used to solve continuous optimization problems. Hitherto, researchers have attempted to improve PSO to solve discrete NP-hard problems. Considering the complexity and discreteness of BV-IPPS problems, this study proposes a PSO to solve the BV-IPPS problem. Each module of the algorithm is introduced below. A flowchart of the PSO with a seven-layer encoding structure for the BV-IPPS problem is proposed at the end of this section.


### 4.1. Solution Representation

A seven-layer encoding structure is proposed to construct solutions. The structure consists of seven layers: the workpiece, sublot of the workpiece, batch, machine, workshop, process time and process route. An example of the encoding structure of BV-IPPS is provided in Table1.Table 1
Sample coding of BV-IPPS.
Ji Code of the workpiece 2 1 2 1 2 2 1 2 JSil Code of the sublot of the workpiece 21 11 22 11 21 22 11 21 bsil Lot size of each sublot of the workpiece 26 70 34 70 26 34 70 26 Mj Code of the machine 4 2 1 4 3 1 1 2 Wg Code of the workshop 2 1 1 2 2 1 1 1 TMJilkvj Process time per one piece of the workpiece 0.8 0.9 0.7 1.3 1 0.6 1.1 0.7 Rk Code of the process route 3 2 1 2 3 1 2 3In Table1, for example, the codes on the first column mean that R3 is adopted for JS21. Because code “21” first appears in the layer of the sublot of the workpiece, it represents the first process of JS21. There are 26 pieces of JS21 that will be processed. M4 is chosen to complete this process. The process time is 0.8 per workpiece. M4 is located in W2, and so on.Vehicles are not contained in the solution representation. In this study, vehicles are scheduled dynamically by constraint(4) in Section 4. An order of vehicles is generated after scheduling. For example, order [2113] means that V2 is used first, then V1 is used for transportation, and so on.


### 4.2. Updating

Individuals are updated with the current global optimal individual or their own best solutions of history based on a probability. A precedence preserving order-based crossover (POX) [30] operator is used for updating. Individuals are still feasible after updating by using the POX operator. Assuming that workpiece J3 will be updated, an example of a POX operator for the BV-IPPS problem is shown in Figure 2. Steps of Figure 2 are shown as follows.Figure 2
Example of POX for BV-IPPS.( 1 ) The columns which contain J3 are cleared in F1. Then, the temporary F1 is generated.( 2 ) Each column of global optimal individual is traversed orderly. The columns which contain J3 are taken.( 3 ) Each column of J3 is inserted into the blank columns of temporary F1. If the number of blank columns of temporary F1 is less than the number of columns of J3, the rest of columns of J3 are inserted in the end of temporary F1. The new F1 is generated.


### 4.3. Mutating

The process sequences and machines are mutated separately. Swapping is used to mutate the process sequence. Two locations are generated randomly. The two columns of data in the locations are exchanged. This may lead to an unfeasible solution after swapping. The new solution will be corrected after swapping. For machine mutating, a location is generated randomly. Then, the code of the machine in the location is changed randomly.Assuming that the fifth and ninth columns will be swapped, swapping and correction are shown in Figure3. Steps of Figure 3 are shown as follows.Figure 3
Example of swapping and correction.( 1 ) The fifth and ninth columns are swapped. Then, the temporary F1 is generated.( 2 ) Since there is an invalid column which contains JS31 in temporary F1, the columns which contain JS31 are cleared. Then, the temporary F1′ is generated.( 3 ) Each column of F1 is traversed orderly. The columns which contain JS31 are taken.( 4 ) Each column of JS31 is inserted into the blank columns of temporary F1′. The new F1 is generated.Assuming that the machine of the third column will be mutated,M3, M4 and M6 can be used to process the first process of JS32. M3 belongs to W1. M4 and M6 belong to W2. An example of changing for a machine is shown in Figure 4. Steps of Figure 4 are shown as follows.Figure 4
Example of changing for a machine.( 1 ) A machine is selected randomly for replacing M6 at the third column. In Figure 4, M6 is replaced by M4.( 2 ) Process time and workshop of the third column are updated. The new F1 is generated.


### 4.4. Parameters and Flowchart of PSO with a Seven-Layer Encoding Structure

The parameters of PSO with a seven-layer encoding structure areM, D, Alpha, Beta, Pm, Ps and Pa, which are defined as follows:M: Population size, controlling the number of individuals in the population.D: Iteration, controlling the number of iterations in the algorithm.Alpha: Probability with which controlling individuals are updated with the global optimal individual, decimals in the(0,1) interval.Beta: Probability with which controlling individuals are updated with their best solution of history, decimals in the(0,1) interval. In this paper, Beta = 1-Alpha.Pm: Mutation probability of individuals, decimals in the (0,1) interval.Ps: Mutation probability of the process sequence of an individual, decimals in the (0,1) interval.Pa: Mutation probability of the machines of an individual, decimals in the (0,1) interval.Based on the above description, a flowchart of PSO with a seven-layer encoding structure for BV-IPPS is shown in Figure5.Figure 5
Flowchart of PSO with a seven-layer encoding structure for BV-IPPS.


## 4.1. Solution Representation

A seven-layer encoding structure is proposed to construct solutions. The structure consists of seven layers: the workpiece, sublot of the workpiece, batch, machine, workshop, process time and process route. An example of the encoding structure of BV-IPPS is provided in Table1.Table 1
Sample coding of BV-IPPS.
Ji Code of the workpiece 2 1 2 1 2 2 1 2 JSil Code of the sublot of the workpiece 21 11 22 11 21 22 11 21 bsil Lot size of each sublot of the workpiece 26 70 34 70 26 34 70 26 Mj Code of the machine 4 2 1 4 3 1 1 2 Wg Code of the workshop 2 1 1 2 2 1 1 1 TMJilkvj Process time per one piece of the workpiece 0.8 0.9 0.7 1.3 1 0.6 1.1 0.7 Rk Code of the process route 3 2 1 2 3 1 2 3In Table1, for example, the codes on the first column mean that R3 is adopted for JS21. Because code “21” first appears in the layer of the sublot of the workpiece, it represents the first process of JS21. There are 26 pieces of JS21 that will be processed. M4 is chosen to complete this process. The process time is 0.8 per workpiece. M4 is located in W2, and so on.Vehicles are not contained in the solution representation. In this study, vehicles are scheduled dynamically by constraint(4) in Section 4. An order of vehicles is generated after scheduling. For example, order [2113] means that V2 is used first, then V1 is used for transportation, and so on.


## 4.2. Updating

Individuals are updated with the current global optimal individual or their own best solutions of history based on a probability. A precedence preserving order-based crossover (POX) [30] operator is used for updating. Individuals are still feasible after updating by using the POX operator. Assuming that workpiece J3 will be updated, an example of a POX operator for the BV-IPPS problem is shown in Figure 2. Steps of Figure 2 are shown as follows.Figure 2
Example of POX for BV-IPPS.( 1 ) The columns which contain J3 are cleared in F1. Then, the temporary F1 is generated.( 2 ) Each column of global optimal individual is traversed orderly. The columns which contain J3 are taken.( 3 ) Each column of J3 is inserted into the blank columns of temporary F1. If the number of blank columns of temporary F1 is less than the number of columns of J3, the rest of columns of J3 are inserted in the end of temporary F1. The new F1 is generated.


## 4.3. Mutating

The process sequences and machines are mutated separately. Swapping is used to mutate the process sequence. Two locations are generated randomly. The two columns of data in the locations are exchanged. This may lead to an unfeasible solution after swapping. The new solution will be corrected after swapping. For machine mutating, a location is generated randomly. Then, the code of the machine in the location is changed randomly.Assuming that the fifth and ninth columns will be swapped, swapping and correction are shown in Figure3. Steps of Figure 3 are shown as follows.Figure 3
Example of swapping and correction.( 1 ) The fifth and ninth columns are swapped. Then, the temporary F1 is generated.( 2 ) Since there is an invalid column which contains JS31 in temporary F1, the columns which contain JS31 are cleared. Then, the temporary F1′ is generated.( 3 ) Each column of F1 is traversed orderly. The columns which contain JS31 are taken.( 4 ) Each column of JS31 is inserted into the blank columns of temporary F1′. The new F1 is generated.Assuming that the machine of the third column will be mutated,M3, M4 and M6 can be used to process the first process of JS32. M3 belongs to W1. M4 and M6 belong to W2. An example of changing for a machine is shown in Figure 4. Steps of Figure 4 are shown as follows.Figure 4
Example of changing for a machine.( 1 ) A machine is selected randomly for replacing M6 at the third column. In Figure 4, M6 is replaced by M4.( 2 ) Process time and workshop of the third column are updated. The new F1 is generated.


## 4.4. Parameters and Flowchart of PSO with a Seven-Layer Encoding Structure

The parameters of PSO with a seven-layer encoding structure areM, D, Alpha, Beta, Pm, Ps and Pa, which are defined as follows:M: Population size, controlling the number of individuals in the population.D: Iteration, controlling the number of iterations in the algorithm.Alpha: Probability with which controlling individuals are updated with the global optimal individual, decimals in the(0,1) interval.Beta: Probability with which controlling individuals are updated with their best solution of history, decimals in the(0,1) interval. In this paper, Beta = 1-Alpha.Pm: Mutation probability of individuals, decimals in the (0,1) interval.Ps: Mutation probability of the process sequence of an individual, decimals in the (0,1) interval.Pa: Mutation probability of the machines of an individual, decimals in the (0,1) interval.Based on the above description, a flowchart of PSO with a seven-layer encoding structure for BV-IPPS is shown in Figure5.Figure 5
Flowchart of PSO with a seven-layer encoding structure for BV-IPPS.


## 5. Experimental Results and Analyses

### 5.1. Experiment  1: Batch and Transport

A lathe manufacturer receives an order. Several shaft parts must be processed. The minimum length of the shaft parts is 300 mm. The maximum length of the shaft parts is 900 mm. There are five types of shaft parts:J1–J5. The batch of each shaft part is 20, 10, 10, 30, and 20. There are six machines: M1–M6. There are three workshops: W1–W3. M1 and M2 are located in W1, M3 and M4 are located in W2, and M5 and M6 are located in W3. There are six vehicles: V1–V6. There are six process methods: P1–P6. There are thirteen process routes: R1–R13. V1, V2, J1 and J2 are located in W1 at time zero, V3, V4, J3 and J4 are located in W2 at time zero, and V5, V6 and J5 are located in W3 at time zero. The makespan is the objective to be minimized. PSO is used to solve the BV-IPPS problem. The process routes of each workpiece are provided in Tables 2–6. The transport time between workshops is provided in Table 7. The process time and transport time are specified in minutes.Table 2
Process routes ofJ1.
Process route 1 2 3 Process method 1 4 5 1 3 6 2 3 5 6  Machine 3 4 6 2 5 6 3 5 3 4 6 1 4 2 3 1 3 5 1 4 3 5 2 3 Process time 1.2 1 1.4 0.7 0.8 1.1 0.9 0.7 1.2 1 1.4 1.2 1 1 1.1 1.2 1.3 1.4 0.8 0.7 1 0.8 0.7 0.8Table 3
Process routes ofJ2.
Process route 4 5 Process method 2 5 6 1 4  Machine 1 3 5 3 5 2 3 3 4 6 2 5 6 Process time 1.2 0.9 1 1 0.8 0.7 1.1 1.2 1.4 0.9 1.1 0.8 0.7Table 4
Process routes ofJ3.
Process route 6 7 Process method 1 3 4 5 2 4 6  Machine 3 4 6 1 4 2 5 6 3 5 1 3 5 2 5 6 2 3 Process time 0.8 1.2 1.1 1.1 0.8 1 0.8 1.2 0.6 0.9 1 1.3 0.8 1 0.8 0.9 0.9 1.2Table 5
Process routes ofJ4.
Process route 8 9 10 Process method 1 5 6 2 4 5 6 3 4 5  Machine 3 4 6 3 5 2 3 1 3 5 2 5 6 3 5 2 3 1 4 2 5 6 3 5 Process time 1.1 0.8 1.1 0.7 0.9 0.8 0.6 1.2 1.1 1.3 1 0.9 1.1 1.2 0.8 0.6 0.8 1.2 0.9 0.7 1 1 0.6 0.9Table 6
Process routes ofJ5.
Process route 11 12 13 Process method 1 2 3 4 1 3 5 6 3 4 5 6  Machine 3 4 6 1 3 5 1 4 2 5 6 3 4 6 1 4 3 5 2 3 1 4 2 5 6 3 5 2 3 Process time 0.9 1 0.8 1 1 1.2 0.8 0.7 0.9 1 0.7 0.9 1 0.8 1 0.8 1.1 0.8 0.7 1 1 1.3 1.2 1 0.7 1.1 0.8 1 0.9Table 7
Transport time between workshops.
W 1 W 2 W 3 W 1 0 7 13 W 2 7 0 9 W 3 13 9 0


#### 5.1.1. Assumptions

(1)
All machines are idle at time zero; (2)
Workpieces are processed according to the process sequence; (3)
Waiting periods between processes are allowed; (4)
Machines will never break down.


#### 5.1.2. Results and Analyses

In this study, parameters of PSO are set:D=300, M=500, Alpha = 0.5, Beta = 0.5, Pm=0.1, Ps=0.5, and Pa=0.5. Equal batch splitting is adopted, and the maximum lot number is four. The C# programming language is used to create the algorithm. The runtime is 75 seconds (CPU: 2.6 GHz, dual-core, RAM: 3 GB). The best solution is shown in Table 8. The makespan of the best solution is 66 min. The curve of the makespan of the optimal solution in each iteration is shown in Figure 6. The Gantt chart of the best solution is shown in Figure 7.Table 8
Best solution.
J i 4 1 4 1 5 4 3 5 1 5 4 5 2 2 J S i l 43 11 42 12 51 43 31 51 11 51 41 52 21 21 B S i l 10 10 10 10 10 10 10 10 10 10 10 10 10 10 M j 4 4 3 4 3 2 5 3 2 4 1 6 6 6 W g 2 2 2 2 2 1 3 2 1 2 1 3 3 3 T M J i l k v j 0.9 1 1.1 1 0.9 0.7 0.8 1 0.7 0.7 1.2 0.8 0.9 0.7 R k 10 1 8 2 11 10 7 11 1 11 10 11 5 5 V r -- 1 -- 2 5 1 3 -- 2 -- 4 -- 4 --  J i 3 5 4 1 4 5 3 1 5 1 4 5 4 4 J S i l 31 52 43 11 42 52 31 12 52 12 41 51 41 42 B S i l 10 10 10 10 10 10 10 10 10 10 10 10 10 10 M j 5 1 3 3 5 1 2 1 2 2 5 6 3 3 W g 3 1 2 2 3 1 1 1 1 1 3 3 2 2 T M J i l k v j 0.8 1 0.6 0.9 0.9 0.8 0.9 1.2 0.9 1 1 0.7 0.6 0.6 R k 7 11 10 1 8 11 7 2 11 2 10 11 10 8 V r -- 6 1 2 5 -- 3 4 -- -- 6 1 5 6Figure 6
Curve of the makespan of the optimal solution in each iteration.Figure 7
Gantt chart of the best solution by adopting equal batch splitting and setting the maximum lot number equal to four.The best solution within the vehicles is shown in Table8; for example, the first and second processes of JS43 are not carried out in the same workshop. V1 is selected to transfer JS43 from W2 to W1 according to formula (7). In another example, the third and fourth processes of JS52 are both performed in W1. Thus, a vehicle is not needed between these two processes.(  1) Batch. For the above problem, if workpieces are processed without considering batch splitting, the makespan is 82 min, which is longer than 66 min. The Gantt chart of the best solution without considering batch splitting is shown in Figure 8. Machines will work for prolonged periods of time. If batch splitting is adopted, each sublot of the workpieces can be processed concurrently. Therefore, the completion time of each sublot of the workpieces is shorter.Figure 8
Gantt chart of the best solution without considering batch splitting.(  2) Limited Vehicles. Figure 7 shows that vehicles and machines are scheduled simultaneously. With regard to the transport time of an empty vehicle, V4 is used to transfer JS12 when the first process of JS12 has been completed. In the twentieth minute, V4 is not in workshop W2. However, M4 is located in workshop W2, which is used to process the first process of JS12. Therefore, V4 must travel to W2 first. Thus, the transport time of empty vehicle V4 is generated. Then, JS12 is transferred by V4 from workshop W2 to W1. The amounts and locations of vehicles are considered in the IPPS problem simultaneously in this paper. The result is more realistic for determining the real scheduling solution than the best solution obtained by solving the basic IPPS problem.


### 5.2. Experiment  2: Equal Batch Splitting and Fixed Batch Splitting

To make the comparisons between the two batch splitting strategies more distinct, transport factors will be ignored in experiment 2, which involves two different scale samples. The assumptions are the same as those in experiment 1. As space is limited, several important parameters of the samples are provided in Table9. The algorithm parameters are provided in Table 10.Table 9
Two samples of Experiment  2.
(a) Parameters of Sample  1 b 1 b 2 b 3 b 4 b 5 n m t w p VRN VRT 20 10 10 30 20 5 6 6 3 13 2–4 0.6–1.4  (b) Parameters of Sample  2 b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 10 n m t w p VRN VRT 40 10 10 30 40 20 10 30 40 20 10 10 10 5 20 3–5 0.5–2.0Table 10
Algorithm parameters of the two samples.
Algorithm parameters for Sample  1 Algorithm parameters for Sample  2 D M Alpha Beta P m P s P a D M Alpha Beta P m P s P a 300 500 0.5 0.5 0.1 0.5 0.5 400 800 0.5 0.5 0.1 0.5 0.5In Table9, “VRN” represents the value range of the number of procedures of each process route and “VRT” represents the process time range of each process.Two samples are calculated 100 times for each batch splitting strategy. The results of the different batch splitting strategies are provided in Table11.Table 11
Results of the different batch splitting strategies.
(a) Results of Sample1 Batch splitting strategy Equal Fixed Fixed Fixed Not splitting Number of lots Max = 4 4 3 2 - Makespan of the best solution(m) 47.7 48.2 48.6 50 64  (b) Results of Sample2 Batch splitting strategy Equal Fixed Fixed Fixed Fixed Not splitting Number of lots Max = 5 5 4 3 2 - Makespan of the best solution(m) 143.1 165.2 153.9 143.3 142 164(  1) Sample  1. The makespan obtained by adopting equal batch splitting and setting the maximum lot number equal to four is better than other results obtained by adopting fixed batch splitting in sample 1. The lot number and batch of each workpiece are constant values in fixed batch splitting. This may lead to an imbalance between the machine and load. The lot number of each workpiece can be changed in equal batch splitting. Thus, equal batch splitting is more flexible than fixed batch splitting. The result obtained by adopting equal batch splitting is superior to that obtained with fixed batch splitting.(  2) Sample  2. The makespan obtained by adopting equal batch splitting and setting the maximum lot number equal to five is not the best makespan of all batch splitting strategies in sample 2. Sample  2 is a large-scale problem. Each workpiece can be divided into five types of lot numbers. The number of batch division results obtained by adopting equal batch splitting in sample 2 is 9536 (510/45) times the number of batch division results obtained by adopting equal batch splitting in sample 1. Therefore, it is more difficult to achieve a smaller makespan by adopting the equal batch splitting strategy due to large-scale problems.


## 5.1. Experiment  1: Batch and Transport

A lathe manufacturer receives an order. Several shaft parts must be processed. The minimum length of the shaft parts is 300 mm. The maximum length of the shaft parts is 900 mm. There are five types of shaft parts:J1–J5. The batch of each shaft part is 20, 10, 10, 30, and 20. There are six machines: M1–M6. There are three workshops: W1–W3. M1 and M2 are located in W1, M3 and M4 are located in W2, and M5 and M6 are located in W3. There are six vehicles: V1–V6. There are six process methods: P1–P6. There are thirteen process routes: R1–R13. V1, V2, J1 and J2 are located in W1 at time zero, V3, V4, J3 and J4 are located in W2 at time zero, and V5, V6 and J5 are located in W3 at time zero. The makespan is the objective to be minimized. PSO is used to solve the BV-IPPS problem. The process routes of each workpiece are provided in Tables 2–6. The transport time between workshops is provided in Table 7. The process time and transport time are specified in minutes.Table 2
Process routes ofJ1.
Process route 1 2 3 Process method 1 4 5 1 3 6 2 3 5 6  Machine 3 4 6 2 5 6 3 5 3 4 6 1 4 2 3 1 3 5 1 4 3 5 2 3 Process time 1.2 1 1.4 0.7 0.8 1.1 0.9 0.7 1.2 1 1.4 1.2 1 1 1.1 1.2 1.3 1.4 0.8 0.7 1 0.8 0.7 0.8Table 3
Process routes ofJ2.
Process route 4 5 Process method 2 5 6 1 4  Machine 1 3 5 3 5 2 3 3 4 6 2 5 6 Process time 1.2 0.9 1 1 0.8 0.7 1.1 1.2 1.4 0.9 1.1 0.8 0.7Table 4
Process routes ofJ3.
Process route 6 7 Process method 1 3 4 5 2 4 6  Machine 3 4 6 1 4 2 5 6 3 5 1 3 5 2 5 6 2 3 Process time 0.8 1.2 1.1 1.1 0.8 1 0.8 1.2 0.6 0.9 1 1.3 0.8 1 0.8 0.9 0.9 1.2Table 5
Process routes ofJ4.
Process route 8 9 10 Process method 1 5 6 2 4 5 6 3 4 5  Machine 3 4 6 3 5 2 3 1 3 5 2 5 6 3 5 2 3 1 4 2 5 6 3 5 Process time 1.1 0.8 1.1 0.7 0.9 0.8 0.6 1.2 1.1 1.3 1 0.9 1.1 1.2 0.8 0.6 0.8 1.2 0.9 0.7 1 1 0.6 0.9Table 6
Process routes ofJ5.
Process route 11 12 13 Process method 1 2 3 4 1 3 5 6 3 4 5 6  Machine 3 4 6 1 3 5 1 4 2 5 6 3 4 6 1 4 3 5 2 3 1 4 2 5 6 3 5 2 3 Process time 0.9 1 0.8 1 1 1.2 0.8 0.7 0.9 1 0.7 0.9 1 0.8 1 0.8 1.1 0.8 0.7 1 1 1.3 1.2 1 0.7 1.1 0.8 1 0.9Table 7
Transport time between workshops.
W 1 W 2 W 3 W 1 0 7 13 W 2 7 0 9 W 3 13 9 0


### 5.1.1. Assumptions

(1)
All machines are idle at time zero; (2)
Workpieces are processed according to the process sequence; (3)
Waiting periods between processes are allowed; (4)
Machines will never break down.


### 5.1.2. Results and Analyses

In this study, parameters of PSO are set:D=300, M=500, Alpha = 0.5, Beta = 0.5, Pm=0.1, Ps=0.5, and Pa=0.5. Equal batch splitting is adopted, and the maximum lot number is four. The C# programming language is used to create the algorithm. The runtime is 75 seconds (CPU: 2.6 GHz, dual-core, RAM: 3 GB). The best solution is shown in Table 8. The makespan of the best solution is 66 min. The curve of the makespan of the optimal solution in each iteration is shown in Figure 6. The Gantt chart of the best solution is shown in Figure 7.Table 8
Best solution.
J i 4 1 4 1 5 4 3 5 1 5 4 5 2 2 J S i l 43 11 42 12 51 43 31 51 11 51 41 52 21 21 B S i l 10 10 10 10 10 10 10 10 10 10 10 10 10 10 M j 4 4 3 4 3 2 5 3 2 4 1 6 6 6 W g 2 2 2 2 2 1 3 2 1 2 1 3 3 3 T M J i l k v j 0.9 1 1.1 1 0.9 0.7 0.8 1 0.7 0.7 1.2 0.8 0.9 0.7 R k 10 1 8 2 11 10 7 11 1 11 10 11 5 5 V r -- 1 -- 2 5 1 3 -- 2 -- 4 -- 4 --  J i 3 5 4 1 4 5 3 1 5 1 4 5 4 4 J S i l 31 52 43 11 42 52 31 12 52 12 41 51 41 42 B S i l 10 10 10 10 10 10 10 10 10 10 10 10 10 10 M j 5 1 3 3 5 1 2 1 2 2 5 6 3 3 W g 3 1 2 2 3 1 1 1 1 1 3 3 2 2 T M J i l k v j 0.8 1 0.6 0.9 0.9 0.8 0.9 1.2 0.9 1 1 0.7 0.6 0.6 R k 7 11 10 1 8 11 7 2 11 2 10 11 10 8 V r -- 6 1 2 5 -- 3 4 -- -- 6 1 5 6Figure 6
Curve of the makespan of the optimal solution in each iteration.Figure 7
Gantt chart of the best solution by adopting equal batch splitting and setting the maximum lot number equal to four.The best solution within the vehicles is shown in Table8; for example, the first and second processes of JS43 are not carried out in the same workshop. V1 is selected to transfer JS43 from W2 to W1 according to formula (7). In another example, the third and fourth processes of JS52 are both performed in W1. Thus, a vehicle is not needed between these two processes.(  1) Batch. For the above problem, if workpieces are processed without considering batch splitting, the makespan is 82 min, which is longer than 66 min. The Gantt chart of the best solution without considering batch splitting is shown in Figure 8. Machines will work for prolonged periods of time. If batch splitting is adopted, each sublot of the workpieces can be processed concurrently. Therefore, the completion time of each sublot of the workpieces is shorter.Figure 8
Gantt chart of the best solution without considering batch splitting.(  2) Limited Vehicles. Figure 7 shows that vehicles and machines are scheduled simultaneously. With regard to the transport time of an empty vehicle, V4 is used to transfer JS12 when the first process of JS12 has been completed. In the twentieth minute, V4 is not in workshop W2. However, M4 is located in workshop W2, which is used to process the first process of JS12. Therefore, V4 must travel to W2 first. Thus, the transport time of empty vehicle V4 is generated. Then, JS12 is transferred by V4 from workshop W2 to W1. The amounts and locations of vehicles are considered in the IPPS problem simultaneously in this paper. The result is more realistic for determining the real scheduling solution than the best solution obtained by solving the basic IPPS problem.


## 5.1.1. Assumptions

(1)
All machines are idle at time zero; (2)
Workpieces are processed according to the process sequence; (3)
Waiting periods between processes are allowed; (4)
Machines will never break down.


## 5.1.2. Results and Analyses

In this study, parameters of PSO are set:D=300, M=500, Alpha = 0.5, Beta = 0.5, Pm=0.1, Ps=0.5, and Pa=0.5. Equal batch splitting is adopted, and the maximum lot number is four. The C# programming language is used to create the algorithm. The runtime is 75 seconds (CPU: 2.6 GHz, dual-core, RAM: 3 GB). The best solution is shown in Table 8. The makespan of the best solution is 66 min. The curve of the makespan of the optimal solution in each iteration is shown in Figure 6. The Gantt chart of the best solution is shown in Figure 7.Table 8
Best solution.
J i 4 1 4 1 5 4 3 5 1 5 4 5 2 2 J S i l 43 11 42 12 51 43 31 51 11 51 41 52 21 21 B S i l 10 10 10 10 10 10 10 10 10 10 10 10 10 10 M j 4 4 3 4 3 2 5 3 2 4 1 6 6 6 W g 2 2 2 2 2 1 3 2 1 2 1 3 3 3 T M J i l k v j 0.9 1 1.1 1 0.9 0.7 0.8 1 0.7 0.7 1.2 0.8 0.9 0.7 R k 10 1 8 2 11 10 7 11 1 11 10 11 5 5 V r -- 1 -- 2 5 1 3 -- 2 -- 4 -- 4 --  J i 3 5 4 1 4 5 3 1 5 1 4 5 4 4 J S i l 31 52 43 11 42 52 31 12 52 12 41 51 41 42 B S i l 10 10 10 10 10 10 10 10 10 10 10 10 10 10 M j 5 1 3 3 5 1 2 1 2 2 5 6 3 3 W g 3 1 2 2 3 1 1 1 1 1 3 3 2 2 T M J i l k v j 0.8 1 0.6 0.9 0.9 0.8 0.9 1.2 0.9 1 1 0.7 0.6 0.6 R k 7 11 10 1 8 11 7 2 11 2 10 11 10 8 V r -- 6 1 2 5 -- 3 4 -- -- 6 1 5 6Figure 6
Curve of the makespan of the optimal solution in each iteration.Figure 7
Gantt chart of the best solution by adopting equal batch splitting and setting the maximum lot number equal to four.The best solution within the vehicles is shown in Table8; for example, the first and second processes of JS43 are not carried out in the same workshop. V1 is selected to transfer JS43 from W2 to W1 according to formula (7). In another example, the third and fourth processes of JS52 are both performed in W1. Thus, a vehicle is not needed between these two processes.(  1) Batch. For the above problem, if workpieces are processed without considering batch splitting, the makespan is 82 min, which is longer than 66 min. The Gantt chart of the best solution without considering batch splitting is shown in Figure 8. Machines will work for prolonged periods of time. If batch splitting is adopted, each sublot of the workpieces can be processed concurrently. Therefore, the completion time of each sublot of the workpieces is shorter.Figure 8
Gantt chart of the best solution without considering batch splitting.(  2) Limited Vehicles. Figure 7 shows that vehicles and machines are scheduled simultaneously. With regard to the transport time of an empty vehicle, V4 is used to transfer JS12 when the first process of JS12 has been completed. In the twentieth minute, V4 is not in workshop W2. However, M4 is located in workshop W2, which is used to process the first process of JS12. Therefore, V4 must travel to W2 first. Thus, the transport time of empty vehicle V4 is generated. Then, JS12 is transferred by V4 from workshop W2 to W1. The amounts and locations of vehicles are considered in the IPPS problem simultaneously in this paper. The result is more realistic for determining the real scheduling solution than the best solution obtained by solving the basic IPPS problem.


## 5.2. Experiment  2: Equal Batch Splitting and Fixed Batch Splitting

To make the comparisons between the two batch splitting strategies more distinct, transport factors will be ignored in experiment 2, which involves two different scale samples. The assumptions are the same as those in experiment 1. As space is limited, several important parameters of the samples are provided in Table9. The algorithm parameters are provided in Table 10.Table 9
Two samples of Experiment  2.
(a) Parameters of Sample  1 b 1 b 2 b 3 b 4 b 5 n m t w p VRN VRT 20 10 10 30 20 5 6 6 3 13 2–4 0.6–1.4  (b) Parameters of Sample  2 b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 b 10 n m t w p VRN VRT 40 10 10 30 40 20 10 30 40 20 10 10 10 5 20 3–5 0.5–2.0Table 10
Algorithm parameters of the two samples.
Algorithm parameters for Sample  1 Algorithm parameters for Sample  2 D M Alpha Beta P m P s P a D M Alpha Beta P m P s P a 300 500 0.5 0.5 0.1 0.5 0.5 400 800 0.5 0.5 0.1 0.5 0.5In Table9, “VRN” represents the value range of the number of procedures of each process route and “VRT” represents the process time range of each process.Two samples are calculated 100 times for each batch splitting strategy. The results of the different batch splitting strategies are provided in Table11.Table 11
Results of the different batch splitting strategies.
(a) Results of Sample1 Batch splitting strategy Equal Fixed Fixed Fixed Not splitting Number of lots Max = 4 4 3 2 - Makespan of the best solution(m) 47.7 48.2 48.6 50 64  (b) Results of Sample2 Batch splitting strategy Equal Fixed Fixed Fixed Fixed Not splitting Number of lots Max = 5 5 4 3 2 - Makespan of the best solution(m) 143.1 165.2 153.9 143.3 142 164(  1) Sample  1. The makespan obtained by adopting equal batch splitting and setting the maximum lot number equal to four is better than other results obtained by adopting fixed batch splitting in sample 1. The lot number and batch of each workpiece are constant values in fixed batch splitting. This may lead to an imbalance between the machine and load. The lot number of each workpiece can be changed in equal batch splitting. Thus, equal batch splitting is more flexible than fixed batch splitting. The result obtained by adopting equal batch splitting is superior to that obtained with fixed batch splitting.(  2) Sample  2. The makespan obtained by adopting equal batch splitting and setting the maximum lot number equal to five is not the best makespan of all batch splitting strategies in sample 2. Sample  2 is a large-scale problem. Each workpiece can be divided into five types of lot numbers. The number of batch division results obtained by adopting equal batch splitting in sample 2 is 9536 (510/45) times the number of batch division results obtained by adopting equal batch splitting in sample 1. Therefore, it is more difficult to achieve a smaller makespan by adopting the equal batch splitting strategy due to large-scale problems.


## 6. Conclusions

In this paper, main works are summarised as follows.( 1 ) This study considered batches and transportation in the IPPS problem simultaneously. The equal batch splitting strategy is used to split the batch of each workpiece. A BV-IPPS problem considering equal batch splitting and a limited number of vehicles is proposed. The makespan is taken as the objective to be minimized, and a mathematical model for the BV-IPPS problem is established.( 2 ) Due to the complexity and discreteness of the BV-IPPS problem, a PSO within a multilayer encoding structure is proposed to solve the problem. Each module of the algorithm is designed, and a flowchart of the algorithm is given.( 3 ) The above model and algorithm are validated experimentally. The results show that the makespan obtained by adopting an equal batch splitting strategy in the BV-IPPS problem is superior to that obtained with no splitting. Additionally, transportation is considered in the IPPS problem. The best solution obtained by scheduling vehicles and machines simultaneously is more feasible for determining the real scheduling solution than the best solution obtained by scheduling machines only.Additionally, some future works will be carried on.( 1 ) The result obtained using the equal splitting batch strategy in the BV-IPPS problem is better than that obtained with the fix splitting batch strategy. However, according to the experimental results, due to the larger search space in the larger-scale samples, it may be more difficult to find a better solution with the equal splitting batch strategy. In future research, we will focus on improving the algorithm. Specifically, more advanced algorithms will be developed to address large-scale BV-IPPS problems.( 2 ) BV-IPPS problem is a static scheduling problem in this paper. In order to make IPPS problem more in line with practical manufacturing environment, some dynamic factors will be considered in IPPS problem. For example, new job inserting, job cancelling or machine breakdown will be considered.



---

*Source: 7948693-2018-03-20.xml*