Sage Journals: Discover world-class research

Abstract

The integration of process planning and scheduling is important for an efficient utilization of manufacturing resources. However, the focus of existing works is mainly on deterministic constraints of jobs. This article proposes a novel memetic algorithm for the integrated process planning and scheduling problem with processing time uncertainty based on processing time scenarios. First, a mathematical model for the stochastic integrated process planning and scheduling problem based on the network graph is established. Due to the nonlinearity in the model and the complexity of the problem, a memetic algorithm is then suggested for this problem. A novel local search (variable neighborhood search) algorithm is incorporated into the memetic algorithm. Two effective neighborhood structures are employed in the variable neighborhood search algorithm to improve the overall performance of the population. Furthermore, for the uncertainty in processing times, a set of scenarios have been generated to evaluate each individual. Finally, two performance measures—the expected performance measure and the worst-case deviation measure—are introduced and compared. In the experimental studies, the proposed memetic algorithm is tested on typical benchmark instances. Computational results show that the expected makespan measure performs better than the worst-case deviation measure and the proposed method exhibits high performance especially for large-scale instances. In addition, the results obtained by the proposed memetic algorithm are more satisfactory than those obtained by the algorithm that considers deterministic processing times only.

Keywords

Integrated process planning and scheduling memetic algorithm undetermined processing time

Introduction

Process planning and scheduling are two important functions in a manufacturing system.^1,2 In tradition, the two functions are split each other: the scheduling procedure is performed after the process plan of each job is determined. This is a simple paradigm of many real production processes. However, this paradigm ignores the inherent relationship between process planning and scheduling. The integration of the two functions can truly bring significant improvements in reducing scheduling conflicts, lead time, human intervention, and so on.³

Three approaches are mainly adopted in addressing the integrated process planning and scheduling (IPPS) problem: the mixed integer linear programming (MILP)-based approach, the meta-heuristic-based approach, and the agent-based method. Existing MILP models investigated by some researchers are based on the assumption that all the available process plans are prepared in advance. A successful model is suggested⁴ among a variety of research articles. However, as revealed in that article, their model is efficient for small-scale instances only, and the quality of the algorithm deteriorates in solving medium- or large-scale instances. Similar models can also be found in existing literatures.^3,5 The meta-heuristic-based approaches have garnered tremendous attention and have been adopted widely for the IPPS problem. For instance, Shao et al.⁶ developed a modified genetic algorithm to address the problem. A novel imperialist competitive algorithm⁷ was considered to address the IPPS problem. In addition, the agent-based method, a kind of artificial intelligence, is also a practical method to deal with the IPPS problem and a representative research⁸ has been presented. Moreover, the rescheduling strategy considering machine breakdown was also studied.⁹

In literatures mentioned above, processing times are deterministic. However, a manufacturing system in the real world is often subject to many sources of uncertainty. One source of uncertainty lies in the processing time of an operation which may fluctuate within a certain range. Therefore, a predefined schedule may usually be affected¹⁰ and subsequent processing programs may also be put off because scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic model will perform poorly when evaluated relative to actual processing times.¹¹ Chance-constrained programming approaches have been considered in some research articles regarding uncertain processing times.^12–14 For instance, Elyasi and Salmasi¹⁴ give detailed descriptions on applying the chance-constrained programming method in solving stochastic scheduling problems. On the other hand, some articles consider fuzzy processing times within a meta-heuristic framework;^15–17 applications of meta-heuristic algorithms bring convenience to solve uncertain constraint problems. Besides, Horng et al.¹⁸ recommended an evolutionary algorithm called evolutionary strategy in ordinal optimization, (ESOO) for solving the stochastic job shop scheduling problem (SJSSP); they show that their method can obtain promising results. Artificial intelligence-based methods have also been covered. For example, Azadeh et al.¹⁹ suggested an artificial neural network (ANN)-based method where the ANN is adopted to select the optimal dispatching rule for each machine in a job shop with stochastic processing times. Recently, Wang and Choi²⁰ presented a novel decomposition-based holonic approach (DBHA) for minimizing the makespan of a flexible flow shop with stochastic processing times.

To our knowledge, there are two kinds of methods to deal with scheduling problems with undetermined parameters: reactive scheduling and proactive scheduling (also preventive scheduling).²¹ For reactive scheduling, an original schedule is obtained in a deterministic manner. Whenever there are unexpected events, it handles uncertainty by generating updated schedules in time. Due to the short-sighted nature in reactive scheduling, the global optimality is not guaranteed. In proactive scheduling, the system never regenerates any updated schedules during the schedule’s implementation stage because the generated schedule in proactive paradigm is capable to hedge against uncertainty.

Although novel methods in dealing with uncertainty have been suggested, such as Petri nets²² and chance-constrained programming,²³ meta-heuristic-based approaches in addressing the stochastic IPPS problem have seldom been reported. In this article, we focus on the IPPS problem with uncertain processing times using proactive scheduling paradigm to guarantee the global optimality. The objective is to minimize the total completion time (makespan). We deduce a novel mathematical model for the stochastic IPPS problem. Due to the complexity of the problem, a memetic algorithm (MA) is developed to address this problem while fluctuations in processing times are captured by a set of processing time scenarios. We consider two measures, the expected makespan measure²⁴ and the worst-case deviation measure,²⁵ respectively, in individual evaluation in MA. Experimental results show that the proposed MA can generate satisfactory schedules to cope with fluctuations in processing times.

The rest of the article is structured as follows. The next section gives the description of the IPPS problem and the mathematical model. In section “Robust scheduling models,” the two performance measures will be introduced. Section “The MA” presents the details of the proposed MA. Computational results with discussions will be reported in section “Experiments with discussions.” The last section gives conclusions.

The IPPS problem with mathematical modeling

Problem description

The IPPS problem can be defined as follows:²⁶ given a set of n parts (jobs) to be processed on m machines with operations including alternative manufacturing resources, select the suitable manufacturing resources and sequence the operations so as to determine a schedule in which the precedence constraints among operations can be satisfied and the corresponding objectives can be achieved. In short, this problem can be regarded as “job shop scheduling problems with routing and process plan flexibility.”⁴ Jobs to be processed in the IPPS problem are described by network graphs as illustrated in Figure 1(a).

Figure 1.

Network graph representations: a) a network graph representation of a job, b-c) two combinations of the network graph in a) and d) an example of generating combinations from a network graph with two OR nodes.

In a network graph, the starting node and the ending node are two dummy nodes. A process plan for a job begins at the starting node and ends at the ending node. In an operation node, the operation number with its alternative machines and corresponding processing times are specified. For operation 6 in Figure 1(a), it can be processed by machine 1 or 5 with processing times 42 or 38. An arc coming from node A to node B implies that operation B should follow operation A directly or indirectly. Moreover, if a bifurcation is marked with “OR” (called an OR node), this means that one and only one OR link path of the two should be traversed. In other cases, the two link paths of a bifurcation should be traversed. For the network of the job in Figure 1(a), feasible paths (9-10-11) and (12-13) are two OR link paths. Two possible process plans in Figure 1(a) are (7→1→8→4→2→12→3→5→13→6→14) and (1→2→3→4→5→6→7→8→12→13→14).

In classical (flexible) job shop scheduling problems (FJSP), the number of operations belonging to a certain job is predefined, and each operation should be processed by a machine. More importantly, each job has a fixed operation sequence (e.g. O₁→O₂→O₃→…). This implies that operation O_i +₁ should be scheduled after O_i and before O_i +₂ in any case. However, the IPPS problem is a more flexible problem because the precedence relationship of some operations is not fixed (e.g. there is no precedence relationship between operations 2 and 4 in Figure 1(a)). Moreover, some operations may not be selected if an OR link path is not selected.

Mathematical modeling

Our MILP model is developed based on network graphs instead of pre-generated process plans. The term “(operation) combination” is very important in modeling this problem. By judging the corresponding OR nodes in a network graph, a job’s operation combination can be formed by picking several operations (not all the operations in a network graph) without taking operation precedence relationships into account. For instance, the job in Figure 1(a) has only two operation combinations as shown in Figure 1(b) and (c), respectively: combination (1-8, 12-14) and combination (1-11, 14). These two combinations can be judged by the OR node in Figure 1(a). Furthermore, additional operation nodes should be added if there are more than one OR nodes. In Figure 1(d), there are four combinations, where operations 2′, 3′, 4′, 5′, 8′, and 9′ are newly added. The newly added operations have the same precedence relationships and available machines together with processing times as the original operations. The proposed model is based on some basic assumptions as follows:

Jobs and machine tools are independent and available at time zero.

Job preemption is not allowed, and each machine can handle only one job at a time. Different operations of one job cannot be processed simultaneously.

Once a job is finished, it will be immediately transferred to another machine with transportation time neglected.

Setup time of an operation is included in the processing time.

Processing times of operations are not deterministic.

We first establish a model using deterministic processing times; then, the robust mathematical model will be presented based on the deterministic version.

Objective : min C_{max}

(1)

\sum_{h \in K_{i}} Y_{ih} = 1, \forall i

(2)

\sum_{k \in M_{ij}} \sum_{f = 1}^{f_{k}} X_{ijkf} = 1, \forall i, j \in n_{i} \ RE S_{i}

(3)

\sum_{k \in M_{ij}} \sum_{f = 1}^{f_{k}} X_{ijkf} = Y_{ih}, \forall i, j \in R_{ih}, h \in K_{i}

(4)

\sum_{i = 1}^{n} \sum_{j \in n_{i} \ RE S_{i}} X_{ijkf} ⩽ 1, \forall k, f \in [1, f_{k}]

(5)

\sum_{i = 1}^{n} \sum_{j \in R_{i h}} X_{i j k f} ⩽ Y_{i h}, \forall k, f \in [1, f_{k}], h \in K_{i}

(6)

\begin{matrix} S_{ij'} ⩾ S_{ij} + X_{ijkf} p_{ijk} - A (2 - X_{ijkf} - X_{ij' k' f'}), \\ \forall i, j, j' \in n_{i}, j \neq j', k \in M_{ij}, k' \in M_{ij'}, \\ V_{ijj'} = 1, f \in [1, f_{k}], f' \in [1, f_{k'}] \end{matrix}

(7)

B_{k, f + 1} ⩾ B_{k, f} + \sum_{i = 1}^{n} \sum_{j \in n_{i}} X_{i j k f} p_{i j k}, \forall k, f \in [1, f_{k}]

(8)

B_{k, f} ⩾ S_{i j} - A (1 - X_{i j k f}), \forall i, j \in n_{i}, k \in M_{i j}, f \in [1, f_{k}]

(9)

B_{k, f} ⩽ S_{i j} + A (1 - X_{i j k f}), \forall i, j \in n_{i}, k \in M_{i j}, f \in [1, f_{k}]

(10)

\sum_{i = 1}^{n} \sum_{j \in n_{i}} X_{i j k f} ⩾ \sum_{i = 1}^{n} \sum_{j \in n_{i}} X_{i j k, f + 1}, \forall k, f \in [1, f_{k})

(11)

Z_{i j j^{'}} + Z_{i j^{'} j} = 1, \forall i, j, j^{'} \in n_{i}, j \neq j^{'}, V_{i j j^{'}} + V_{i j^{'} j} = 0

(12)

\begin{array}{l} S_{i j^{'}} - S_{i j} ⩾ \sum_{k \in M_{i j}} \sum_{f = 1}^{f_{k}} X_{i j k f} p_{i j k} - A (1 - Z_{i j j^{'}}), \\ \forall i, j, j^{'} \in n_{i}, j \neq j^{'}, V_{i j j^{'}} + V_{i j^{'} j} = 0 \end{array}

(13)

C_{\max} ⩾ S_{i j} + \sum_{k \in M_{i j}} \sum_{f = 1}^{f_{k}} X_{i j k f} p_{i j k}, \forall i, j \in n_{i}

(14)

Constraint set (2) specifies that only one combination should be chosen for each job. Constraint sets (3) and (4) state that each selected operation of each job can be only assigned one and only one position on an available machine. Constraint sets (5) and (6) make sure that each position on each machine can handle at most one operation. Constraint set (7) schedules two operations of the same job; the two operations have a sequence relation. Constraint set (8) means that the starting time of a subsequent position on one machine should not be earlier than the completion time of the previous one. Constraint sets (9) and (10) couple machine starting times and job starting times. Constraint set (11) requires every operation on one machine to be arranged with the front to back order. Constraint sets (12) and (13) schedule two operations that have no precedence relationship. Finally, constraint set (14) determines the makespan of the schedule. Constraint sets (2–14) above are about deterministic case; in considering undetermined processing times, the following constraints should be added based on the conception of robust scheduling and the robust optimization approach.^27,28 We consider the bounded and symmetric uncertainty in modeling the stochastic IPPS problem.

Bounded and symmetric uncertainty

In this paradigm, a “true” value $\tilde{a}$ of a parameter (a processing time in this article) is distributed around its nominal value (mean value) a randomly and symmetrically: $\tilde{a} = (1 + ε ξ) a$ . In the equation, $ξ$ is a random variable distributed in the interval [−1, 1], and $ε$ is a given uncertainty level. In other words, a “true” parameter may fluctuate within the interval $[(1 - ε) a, (1 + ε) a]$ . In the proposed mathematical model, additional four constraint sets (15), (16), (17), and (18) should be added. Thus, constraint sets (1–14, 15, 16, 17, and 18) constitute the whole robust mathematical model for the stochastic IPPS problem

\begin{matrix} S_{ij} - S_{ij'} + X_{ijkf} p_{ijk} - A (2 - X_{ijkf} - X_{ij' k' f'}) \\ + ε [Ω p_{ijk} X_{ijkf}] ⩽ δ, \\ \forall i, j, j' \in n_{i}, j \neq j', k \in M_{ij}, k' \in M_{ij'}, \\ V_{ijj'} = 1, f \in [1, f_{k}], f' \in [1, f_{k'}] \end{matrix}

(15)

\begin{array}{l} B_{k f} - B_{k, f + 1} + \sum_{i = 1}^{n} \sum_{j \in n_{i}} X_{i j k f} p_{i j k} + ε [Ω \sqrt{\sum_{i = 1}^{n} \sum_{j \in n_{i}} X_{i j k f} p_{i j k}^{2}}] \\ ⩽ δ, \forall k, f \in [1, f_{k}] \end{array}

(16)

\begin{matrix} \sum_{k \in M_{ij}} \sum_{f = 1}^{f_{k}} X_{ijkf} p_{ijk} + ε [Ω \sqrt{\sum_{k \in M_{ij}} \sum_{f = 1}^{f_{k}} X_{ijkf} p_{ijk}^{2}}] \\ - A (1 - Z_{ijj'}) - S_{ij'} + S_{ij} ⩽ δ, \\ \forall i, j, j' \in n_{i}, j \neq j', V_{ijj'} + V_{ij' j} = 0 \end{matrix}

(17)

\begin{array}{l} S_{i j} - C_{\max} + \sum_{k \in M_{i j}} \sum_{f = 1}^{f_{k}} X_{i j k f} p_{i j k} + \\ ε [Ω \sqrt{\sum_{k \in M_{i j}} \sum_{f = 1}^{f_{k}} X_{i j k f} p_{i j k}^{2}}] ⩽ δ, \forall i, j \in n_{i} \end{array}

(18)

In constraint sets (15, 16, 17, and 18), $δ$ is a given infeasibility tolerance and $Ω$ is a positive parameter with $κ = \exp {- Ω^{2} / 2}$ , where $κ$ is a probability: the probability of violation of the constraint is at most $κ$ . Although the proposed model can be realized in a commercial solver such as GAMS/Cplex, initial attempts tell us this method is entirely infeasible for a real-life instance because the central processing unit (CPU) time is not acceptable at all due to the complexity of the problem. In particular, constraint sets (15, 16, 17, and 18) are nonlinear (a convex mixed integer nonlinear programming (MINLP) problem). Therefore, we develop an MA to address the problem.

Robust scheduling models

The idea behind the method that deals with uncertain processing times in this article is to determine a schedule whose performance is more satisfactory than a schedule without considering robustness with potential realizations of processing times to hedge against the prevailing processing time uncertainty. The performance measure of interest is makespan. Two measures that consider the system performance over all potential realizations of job processing times are adopted and compared. One measure of schedule robustness is about the expected performance and the other focuses on the worst-case deviation over all scenarios.

The uncertain processing time can be described through a set of scenarios Λ, and each scenario $λ \in Λ$ represents a unique set of processing times for each job on each machine. In addition, let $P^{λ} = {p_{ijk}^{λ} : i = 1, 2, \dots, n, j = 1, 2, \dots, | n_{i} |, k = 1, 2, \dots, m}$ denote the vector of processing times associated with scenario λ. Let Ω represent the set of all feasible schedules and $σ_{λ}^{*} \in Ω$ be the optimal schedule with scenario λ. Let $φ (σ, P^{λ})$ denote the makespan of schedule $σ \in Ω$ given scenario λ and $ρ (λ)$ denote the probability of scenario λ. The objective of the model with expected performance measure (called the ECM model) can be described as follows

min_{σ \in Ω} EC (σ) = \sum_{λ \in Λ} ρ (λ) \times φ (σ, P^{λ})

(19)

Thus, the optimal expected performance can be denoted as $E C^{*} = min_{σ \in Ω} EC (σ)$ . The model ECM expresses the pursuit of an excellent performance under a statistical significance. The worst-case deviation model (called the WCM model),²⁵ which pays close attention to the worst performance over all scenarios, can be stated as follows

min_{σ \in Ω} WC (σ) = max_{λ \in Λ} φ (σ, P^{λ})

(20)

The optimal worst performance can be denoted as $W C^{*} = min_{σ \in Ω} WC (σ)$ .

The MA

Encoding and decoding

The chromosome structure is illustrated in Figure 2. In our problem, a chromosome consists of a scheduling string, some process plan strings, and corresponding operation strings. The scheduling string adopts an operation-based coding scheme.²⁹ It is a permutation of job numbers with each job number appearing exactly $| N O_{il} |$ times, where $N O_{il}$ denotes the set of operations that belong to the l-th process plan of job i. An outstanding feature of this permutation is that it ensures the feasibility of an individual in decoding process. The length of the scheduling string equals the sum of the maximum possible number of operations of each job $(\sum {| N O_{il} |}_{max})$ . If the number of the operations of a process plan is less than the maximum possible one of that job $(| N O_{il} | < {| N O_{il} |}_{max})$ , $(\sum ({| N O_{il} |}_{max} - | N O_{il} |))$ randomly selected positions in the scheduling string should be filled with “0”s to avoid any infeasibility. In Figure 2, the actual numbers of operations for the three jobs are three, two, and three, respectively. We assume that the length of the scheduling string is 9 $(\sum {| N O_{il} |}_{max} = 3 + 3 + 3)$ . Thus, a position in the scheduling string should be filled with a “0” because the process plan of the second job has only two operations in this case $(| N O_{il} | < {| N O_{il} |}_{max})$ . The operation string contains the information of a process plan of a job. In an individual, there are a total of n operation strings with each string containing $| N O_{il} |$ operations. As illustrated in Figure 2, every position in an operation string represents an operation. Two numbers in a pair of parentheses in each position represent the operation number and the selected machine, respectively. The permutation of operations in an operation string should be feasible, and this can be realized by the binary tree method.³⁰ The number in a process plan string indicates which combination (mentioned in section “Mathematical modeling”) is selected for that job.

Figure 2.

The coding scheme.

The active scheduling procedure³¹ summarized as follows is adopted in the decoding process.

Step 1: For each number in the scheduling string, determine the corresponding job and operation if the number is not equal to 0: if the number $i (i \neq 0)$ in the scheduling string appears exactly l times, it means the operation in the l-th position of the operation string of job i is selected. For convenience, we denote this operation as $O_{ij}$ .

Step 2: Find out the operation $O_{ij}$ by locating this operation in the operation string.

Step 3: Assign this operation on the predefined machine $m_{k}$ .

Step 3.1: Check whether there is a time slot on $m_{k}$ .

Step 3.2: If there is a time slot and $max {c_{i, j - 1}, t_{s}} + p_{ijk} ⩽ t_{e}$ , insert the operation in this time slot and go to Step 1 for next operation. Otherwise, check the next slot on the same machine till all the time slots are checked (t_s and t_e represent the starting time and the ending time of a time slot, respectively; c_ij, is the completion time of $O_{ij}$ ).

Step 3.3: If there is no available time slot, append the operation at the end of the machine with the starting time $max {c_{i, j - 1}, t_{k}}$ (t_k is the last operation’s completion time on machine k at present).

Step 4: Go to Step 1 for next operation till the operations are all scheduled.

Genetic operators

Figure 3 illustrates the crossover procedure. Position-based crossover method is adopted. Randomly select some jobs and exchange the operation strings together with corresponding process plan strings of the selected jobs in two individuals; other operation strings and process plan strings in both individuals are kept still. Then, two empty scheduling strings O1, O2 are initialized. The genes in parent 1, which reflect the unselected jobs, are passed on to the same positions as in the offspring 1 (O1). These genes are removed from parent 2 (P2), and the remaining elements are copied into the undetermined positions in O1 in the same order as they appear in P2. A repairing procedure is adopted to resolve the illegitimacy; it deletes redundant symbols or adds necessary symbols after checking the actual number of operations of each selected job. Figure 3(a) gives an example. Last two jobs are selected, and a “0” is filled in a position in offspring 2 (O2) to avoid infeasibility.

Figure 3.

Crossover operators: a) the first crossover operator and b) the second crossover operator.

Different with the case in job shop scheduling problem (JSP) or FJSP where the processing sequence is fixed; in the IPPS problem, the same operation combination of a job can have different permutations. Our proposed chromosome structure allows the MA to take this advantage by performing the second crossover operator as shown in Figure 3(b). An order crossover (OX)-based one-point crossover is performed between two operation strings for the same job in two individuals. The two jobs in both individuals should have the same number in the process plan strings (they have the same operation combination). Two new feasible operation stings are generated with new feasible permutations.

For the selection operator, a simple tournament selection is adopted. The mutation procedure is performed by changing a machine for an operation and swapping two numbers in two different positions in the scheduling string.

Local search algorithm

Embedding local search methods into a meta-heuristic algorithm is a highly respected way.³² In our algorithm, we employ the variable neighborhood search (VNS) algorithm to improve the population’s overall performance. In VNS, two neighborhood structures are adopted. A neighborhood structure combines the special knowledge of a certain problem to facilitate an effective and slight perturbation in an individual. These two adopted neighborhood structures have been successfully applied to the FJSP. The first one is the N5 neighborhood structure.³³ It is famous for its high cost performance because only swapping the first and (or) last two operations in a critical block is performed. The second one is proposed by Mastrolilli and Gambardella³⁴ (referred to as Nopt neighborhood structure); it tries to remove an operation that is on a critical path to another machine to break the critical path.

VNS tries to optimize an individual using one neighborhood structure continuously till there is no further improvement. Then, it jumps to the second neighborhood. If the individual is improved by the second neighborhood, it goes back to the first neighborhood to repeat the above process. Otherwise, the VNS algorithm is terminated. The procedure of the proposed MA is presented in Figure 4. The parameters Ns, Np, and N in Figure 4 denote the number of scenarios, individuals, and iterations, respectively.

Figure 4.

The flowchart of the proposed memetic algorithm.

Experiments with discussion

To study the effect of the two performance measures and obtain robust schedules, we adopt the well-known benchmark instances proposed by Kim et al.³⁵ The bounded and symmetric uncertainty paradigm is considered in our experiments. In this paradigm, the actual processing time of an operation is distributed around its mean value randomly and symmetrically. We consider two types of fluctuations in processing times: small fluctuation and large fluctuation. The two types of fluctuations are controlled by the tightness factor β. Furthermore, we assume that the actual processing time of an operation ${\tilde{p}}_{ijk}$ is uniformly distributed within the range $[(1 - β) p_{ijk}, (1 + β) p_{ijk}]$ . For the small fluctuation case, the value of β is 0.15 while β takes the value 0.5 for the large fluctuation case. Fifty scenarios are generated by sampling in the range $[(1 - β) p_{ijk}, (1 + β) p_{ijk}]$ . For evaluating and verifying the variation of makespan values of the resultant robust schedule schemes, 100 additional scenarios are prepared. The computational results presented in this section result from all the 100 scenarios.

In the proposed MA, 400 individuals are employed and the algorithm terminates after 400 iterations. In addition, the crossover probability is set to 0.7. The whole algorithm is programmed in C++ language; all the experiments are carried out on a PC with an Intel i5-3470 3.2 GHz CPU and 4 GB of memory.

As mentioned above, two measures of schedule robustness, namely the expected performance and the worst-case deviation, are adopted and compared. Tables 1 and 2 present the nominal makespan values, the maximum makespan values, the minimum makespan values, and the mean makespan values of the 24 benchmark instances with the ECM model (the expected performance measure) and the WCM model (the worst-case deviation measure), respectively.

Table 1.

Computational results using the expected performance measure.

Instances	Number of jobs	β = 0.15				β = 0.5
Instances	Number of jobs	Nominal makespan	Best makespan	Worst makespan	Mean makespan	Nominal makespan	Best makespan	Worst makespan	Mean makespan
1	6	427	402.6	447.6	427.0	429	370.3	509.2	431.9
2	6	343	320.7	361.5	342.1	343	305.8	408.1	352.0
3	6	347	329.4	365.9	346.0	347	323.6	431.6	363.9
4	6	306	288.9	321.6	305.5	306	252.6	362.7	307.7
5	6	319	305.0	340.8	319.5	319	293.1	397.6	337.4
6	6	427	402.6	447.6	427.0	427	379.4	501.7	434.3
7	6	372	352.0	397.9	373.1	372	330.7	445.3	386.4
8	6	343	325.6	361.5	342.7	343	301.2	412.7	361.6
9	6	427	402.6	447.6	427.0	428	371.9	498.4	427.6
10	9	427	406.8	447.6	427.3	434	378.7	511.6	439.4
11	9	347	335.3	364.5	349.1	347	340.4	431.6	379.6
12	9	323	306.1	344.2	324.2	326	303.5	403.3	349.5
13	9	428	407.7	450.2	428.3	430	412.4	552.6	459.3
14	9	376	359.2	399.4	377.4	374	368.6	451.5	408.9
15	9	427	402.6	447.6	427.2	435	380.2	522.9	442.8
16	12	427	402.6	450.9	428.7	442	400.1	542.3	466.3
17	12	380	373.6	410.1	388.7	383	366.1	460.6	420.7
18	12	335	328.3	362.6	340.0	333	325.3	414.8	366.1
19	12	430	413.6	448.6	430.9	455	416.8	536.4	478.7
20	12	392	386.1	427.8	402.3	378	375.6	463.9	423.5
21	12	427	405.5	447.6	427.3	434	407.7	507.8	451.5
22	15	444	433.9	474.9	452.0	449	449.7	554.4	504.1
23	15	412	397.8	444.7	414.6	422	427.2	515.9	472.3
24	18	459	449.6	484.1	467.5	474	494.1	566.2	527.8

Table 2.

Computational results using the worst-case deviation measure.

Instances	Number of jobs	β = 0.15				β = 0.5
Instances	Number of jobs	Nominal makespan	Best makespan	Worst makespan	Mean makespan	Nominal makespan	Best makespan	Worst makespan	Mean makespan
1	6	430	408.4	451.8	430.3	431	374.7	502.9	438.6
2	6	343	326.2	361.5	344.2	358	309.0	412.6	371.2
3	6	347	334.3	365.9	348.6	356	326.2	430.6	384.5
4	6	307	289.9	322.5	307.2	310	280.1	379.6	319.6
5	6	319	305.0	337.5	321.5	325	294.2	417.8	343.1
6	6	430	412.4	451.8	431.8	433	415.3	520.7	460.7
7	6	372	353.2	397.9	374.3	374	354.3	452.6	403.3
8	6	350	331.5	374.2	350.7	350	307.7	416.4	375.0
9	6	430	409.7	451.8	430.4	442	380.3	517.3	448.4
10	9	428	408.8	451.4	431.0	430	403.7	515.7	452.3
11	9	357	346.8	378.0	363.8	360	343.4	447.5	394.5
12	9	326	312.0	346.5	328.3	329	314.8	420.6	358.0
13	9	429	415.0	449.4	432.3	443	435.0	543.1	484.1
14	9	376	365.3	402.1	381.1	384	376.1	481.6	431.8
15	9	430	411.1	451.8	431.3	433	386.8	498.6	445.5
16	12	429	417.7	451.7	433.0	440	411.6	518.7	472.3
17	12	401	397.7	422.6	410.0	383	388.6	468.4	434.0
18	12	341	330.4	362.1	346.2	342	352.0	446.6	389.9
19	12	433	424.0	455.6	440.6	443	424.0	536.9	491.9
20	12	397	391.2	424.8	407.0	401	415.1	502.4	455.2
21	12	427	420.1	449.5	432.8	437	428.1	530.6	471.2
22	15	447	443.8	471.8	456.6	456	459.3	577.0	512.0
23	15	417	411.7	441.4	424.9	431	453.3	546.5	494.6
24	18	483	476.0	511.3	493.2	518	526.9	632.7	571.8

As presented in both Tables 1 and 2, the makespan values of 100 scenarios fall within the ranges around corresponding mean makespan values. For the small fluctuation case (β = 0.15) in both tables, it seems that the average makespan values of 100 scenarios do not deviate much from corresponding nominal makespan values. For the large fluctuation case (β = 0.5), however, the average makespan values of large-scale instances in both tables deviate largely from the corresponding nominal makespan values. The reason behind this is that large fluctuations in processing times lead to more elusive situations in determining the makespan. Moreover, it can be perceived from both tables that the nominal makespan values in the large fluctuation case (β = 0.5) are generally larger than the ones in the small fluctuation case (β = 0.15). This stems from the selection procedure in the proposed MA because the selection operator in our algorithm is guided by the expected performance measure or the worst-case deviation measure instead of the nominal makespan measure.

Figures 5 and 6 give two Gantt charts with the same scheduling scheme of the first instance with nominal and actual processing times, respectively. An instance in Kim’s benchmark is constructed with several jobs taken from all the 18 jobs. There are six jobs (jobs 1–3 and jobs 10–12) in the first instance. Corresponding job IDs are given in both Gantt charts for all the six jobs (note that six job IDs in both Gantt charts are 1, 2, 3, 10, 11, and 12, and jobs are marked with different colors). It can be seen that the permutation of operations on the same machine and the sequence of operations belonging to the same job remain unchanged although the processing times are different in the two cases. The makespan 417.1 in Figure 6 is shorter than the nominal version (427). However, in some cases, it may be larger than the nominal one.

Figure 5.

The Gantt chart of the first instance with nominal processing times.

Figure 6.

The Gantt chart of the first instance with actual processing times.

Figure 7 shows the boxplots of small-scale, medium-scale, and large-scale instances (represented by instance 1, instance 12, and instance 24) in both the small and large fluctuation cases. According to Figure 7 and Tables 1 and 2, the ECM model that adopts expected performance measure is better than the WCM model that adopts worst-case deviation measure. More importantly, the ECM model shows especial talent in capturing a robust schedule for large-scale instances.

Figure 7.

The boxplots of instances 1, 12, and 24: a-b) the boxplots of instance 1 in small and large fluctuation cases respectively, c-d) the boxplots of instance 12 in small and large fluctuation cases respectively and e-f) the boxplots of instance 24 in small and large fluctuation cases respectively.

In the following, visual comparisons are given between different schedules that generated with and without considering robustness to show the advantage of the proposed scenario-based MA. Using the same instances as above (instances 1, 12, and 24), we plot the boxplots as shown in Figure 8. It can be seen from Figure 8 that the medians of the makespan values with the ECM model are all less than those of the schedules that consider deterministic processing times only. An extreme case is depicted in Figure 8(e): the worst makespan value in 100 scenarios using the ECM model is even better than the best makespan value of the schedule that considers deterministic processing times only.

Figure 8.

Comparisons between the schedules with and without considering robustness: a-b) the boxplots of instance 1 in small and large fluctuation cases respectively, c-d) the boxplots of instance 12 in small and large fluctuation cases respectively and e-f) the boxplots of instance 24 in small and large fluctuation cases respectively.

Conclusion

In this article, we establish a mathematical model for the stochastic IPPS problem. Due to the complexity of the problem, we suggest a VNS-based MA to address the IPPS problem with fluctuations in processing times to adjust to real-world situations. Effective neighborhood structures are employed in VNS and the uncertainty in processing times is captured by a set of scenarios. The proposed MA is tested on typical benchmark instances to evaluate its performance with two performance measures. Computational results show that the expected makespan measure performs better than the worst-case deviation measure and the proposed method exhibits high performance in large-scale instances.

Footnotes

Appendix 1 Acknowledgements

The authors express their special appreciation to all authors in “References” section due to their support for the article. The authors also thank the anonymous referees for their insightful and valuable suggestions and comments to improve this article.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

This research is supported by the Funds for International Cooperation and Exchange of the National Natural Science Foundation of China (Grant No. 51561125002), National Natural Science Foundation of China (Grant Nos 51275190, 51405075 and 51575211), and the Fundamental Research Funds for the Central Universities (HUST: 2014TS038).

References

Haddadzade

Razfar

Zarandi

MHF

. Multipart setup planning through integration of process planning and scheduling. Proc IMechE, Part B: J Engineering Manufacture. Epub ahead of print 20 February 2015. DOI: 10.1177/0954405414565138.

Dai

Tang

. Energy-aware integrated process planning and scheduling for job shops. Proc IMechE, Part B: J Engineering Manufacture. Epub ahead of print 29 October 2014. DOI: 10.1177/0954405414553069.

Tan

Khoshnevis

A linearized polynomial mixed integer programming model for the integration of process planning and scheduling. J Intell Manuf 2004; 15(5): 593–605.

Özgüven

Özbakır

Yavuz

Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Appl Math Model 2010; 34(6): 1539–1548.

Gao

Shao

. Mathematical modeling and evolutionary algorithm-based approach for integrated process planning and scheduling. Comput Oper Res 2010; 37(4): 656–667.

Shao

Gao

. Integration of process planning and scheduling—a modified genetic algorithm-based approach. Comput Oper Res 2009; 36(6): 2082–2096.

Lian

Zhang

Gao

. Integrated process planning and scheduling using an imperialist competitive algorithm. Int J Prod Res 2012; 50(15): 4326–4343.

Wong

Zhang

Wang

. Integrated process planning and scheduling—multi-agent system with two-stage ant colony optimisation algorithm. Int J Prod Res 2012; 50(21): 6188–6201.

Wang

Zhang

Fuh

JYH

. Job rescheduling by exploring the solution space of process planning for machine breakdown/arrival problems. Proc IMechE, Part B: J Engineering Manufacture 2011; 225(2): 282–296.

10.

Pan

Qiao

. A novel algorithm for wafer sojourn time analysis of single-arm cluster tools with wafer residency time constraints and activity time variation. IEEE Sys Man Cybern 2015; 45(5): 805–818.

11.

Kouvelis

Daniels

Vairaktarakis

Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Trans 2000; 32(5): 421–432.

12.

Özcan

Balancing stochastic two-sided assembly lines: a chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm. Eur J Oper Res 2010; 205(1): 81–97.

13.

Ağpak

Gökçen

A chance-constrained approach to stochastic line balancing problem. Eur J Oper Res 2007; 180(3): 1098–1115.

14.

Elyasi

Salmasi

Stochastic scheduling with minimizing the number of tardy jobs using chance constrained programming. Math Comput Model 2013; 57(5–6): 1154–1164.

15.

J-Q

Pan

Q-K.

Chemical-reaction optimization for solving fuzzy job-shop scheduling problem with flexible maintenance activities. Int J Prod Econ 2013; 145(1): 4–17.

16.

Wang

Zhou

. A hybrid artificial bee colony algorithm for the fuzzy flexible job-shop scheduling problem. Int J Prod Res 2013; 51(12): 3593–3608.

17.

Wang

. An effective estimation of distribution algorithm for the flexible job-shop scheduling problem with fuzzy processing time. Int J Prod Res 2013; 51(12): 3778–3793.

18.

Horng

S-C

Lin

S-S

Yang

F-Y.

Evolutionary algorithm for stochastic job shop scheduling with random processing time. Expert Syst Appl 2012; 39(3): 3603–3610.

19.

Azadeh

Negahban

Moghaddam

A hybrid computer simulation-artificial neural network algorithm for optimisation of dispatching rule selection in stochastic job shop scheduling problems. Int J Prod Res 2011; 50(2): 551–566.

20.

Wang

Choi

SH.

A holonic approach to flexible flow shop scheduling under stochastic processing times. Comput Oper Res 2014; 43: 157–168.

21.

Ierapetritou

Process scheduling under uncertainty: review and challenges. Comput Chem Eng 2008; 32(4–5): 715–727.

22.

Liu

Zeng

Duan

. E-net modeling and analysis of emergency response processes constrained by resources and uncertain durations. IEEE Sys Man Cybern 2015; 45(1): 84–96.

23.

Tian

Zhou

Chu

A chance constrained programming approach to determine the optimal disassembly sequence. IEEE T Autom Sci Eng 2013; 10(4): 1004–1013.

24.

Pinedo

Minimizing the expected makespan in stochastic flow shops. Oper Res 1982; 30(1): 148–162.

25.

Daniels

Kouvelis

Robust scheduling to hedge against processing time uncertainty in single-stage production. Manage Sci 1995; 41(2): 363–376.

26.

Guo

Mileham

. Applications of particle swarm optimisation in integrated process planning and scheduling. Rob Cim: Int Manuf 2009; 25(2): 280–288.

27.

Janak

Lin

Floudas

. A new robust optimization approach for scheduling under uncertainty: II. Uncertainty with known probability distribution. Comput Chem Eng 2007; 31(3): 171–195.

28.

Lin

Janak

Floudas

. A new robust optimization approach for scheduling under uncertainty: I. Bounded uncertainty. Comput Chem Eng 2004; 28(6–7): 1069–1085.

29.

Bierwirth

A generalized permutation approach to job shop scheduling with genetic algorithms. Or Spektrum 1995; 17(2–3): 87–92.

30.

Tseng

HE.

Guided genetic algorithms for solving a larger constraint assembly problem. Int J Prod Res 2006; 44(3): 601–625.

31.

Bierwirth

Mattfeld

DC.

Production scheduling and rescheduling with genetic algorithms. Evol Comput 1999; 7(1): 1–17.

32.

Xie

Zhang

Shao

. An effective hybrid teaching–learning-based optimization algorithm for permutation flow shop scheduling problem. Adv Eng Softw 2014; 77: 35–47.

33.

Nowicki

Smutnicki

A fast taboo search algorithm for the job shop problem. Manage Sci 1996; 42(6): 797–813.

34.

Mastrolilli

Gambardella

Effective neighborhood functions for the flexible job shop problem. J Sched 1996; 3(1): 3–20.

35.

Kim

Park

A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Comput Oper Res 2003; 30(8): 1151–1171.

Mathematical modeling and a memetic algorithm for the integration of process planning and scheduling considering uncertain processing times

Abstract

Keywords

Introduction

The IPPS problem with mathematical modeling

Problem description

Mathematical modeling

Bounded and symmetric uncertainty

Robust scheduling models

The MA

Encoding and decoding

Genetic operators

Local search algorithm

Experiments with discussion

Conclusion

Footnotes

Appendix 1

Acknowledgements

Declaration of conflicting interests

Funding

References