# A Robust Two-Machine Flow-Shop Scheduling Model with Scenario-Dependent Processing Times

Authors: Chia-Lun Hsu; Win-Chin Lin; Lini Duan; Jan-Ray Liao; Chin-Chia Wu; Juin-Han Chen
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

In many scheduling studies, researchers consider the processing times of jobs as constant numbers. This assumption sometimes is at odds with practical manufacturing process due to several sources of uncertainties arising from real-life situations. Examples are the changing working environments, machine breakdowns, tool quality variations and unavailability, and so on. In light of the phenomenon of scenario-dependent processing times existing in many applications, this paper proposes to incorporate scenario-dependent processing times into a two-machine flow-shop environment with the objective of minimizing the total completion time. The problem under consideration is never explored. To solve it, we first derive a lower bound and two optimality properties to enhance the searching efficiency of a branch-and-bound method. Then, we propose 12 simple heuristics and their corresponding counterparts improved by a pairwise interchange method. Furthermore, we set proposed 12 simple heuristics as the 12 initial seeds to design 12 variants of a cloud theory-based simulated annealing (CSA) algorithm. Finally, we conduct simulations and report the performances of the proposed branch-and-bound method, the 12 heuristics, and the 12 variants of CSA algorithm.


---

## Body

## 1. Introduction

In classical scheduling models, the processing times of jobs are often assumed to be constant numbers, but in practice it can be met with a lot of uncertainty occurrences such as the working environment changes, machine breakdowns, tool quality variations and unavailability, worker performance instabilities, and some external complex factors. Furthermore, the phenomenon of scenario-dependent processing times has not been addressed in the area of scheduling problems until recently [1, 2]. Motivated by these uncertainty reasons, in this study we address scenario-dependent processing times into a two-machine flow-shop setting and find a robust measurement which minimizes the maximum total completion time over all scenarios. This problem is certainly NP-hard because the same problem without the scenario-dependent processing times is nondeterministic polynomial-time hardness (or NP-hard) (see Gonzalez and Sahni [3]).Many studies on literature consider that most processing times are often estimated based on statistical data and find that the variation of the data can be very big and the underlying distributions come from the data which could be inaccurate. Therefore, researchers consider the worst-case performance measurement to be more important than the average error performance. When any one of two probable scenarios occurs, Kouvelis and Yu [4] suggested adopting a robust approach to overcome the worst case. For details of different scenarios of job processing times, readers may refer to Aissi et al. [5], Aloulou and Della Croce [6], De Farias et al. [7], Kasperski and Zielinski [8], Yang and Yu [9], and so on.Regarding the studies on the completion time on the two-machine flow-shop scheduling problem without the scenario-dependent processing times, Kohler and Steiglitz [10] proposed some heuristics for finding near-optimal solutions. Following the NP-hard result by Gonzalez and Sahni [3], Cadambi and Sathe [11], Pan and Wu [12], Wang et al. [13], and Della Croce et al. [14] utilized a branch-and-bound method incorporating several superior properties for exact solutions in turn. Following up two related studies, some complexity and approximation results for special cases of this problem are presented by Hoogeveen and Kawaguchi [15] while the lower bound based on Lagrangian relaxation was improved by Della Croce et al. [16]. For more flow shops with more than two machines, readers may refer to Gupta et al. [17], Xiang et al. [18], Allahverdi and Aldowaisan [19], Chung et al. [20], Rajendran and Ziegler [21], Zhang et al. [22], Tasgetiren et al. [23], Gao et al. [24], Shivakumar and Amudha [25], Dong et al. [26, 27], and Marichelvam et al. [28].Meanwhile, simulated annealing (SA), proposed by Kirkpatrick et al. [29], has been widely and successfully used to solve many discrete combinatorial problems. However, there are some drawbacks in this method. For example, the temperature is discrete and unchangeable in the annealing course from implementation aspect. This point cannot be fit to the requirement of continuous decrease in temperature in actual physical annealing processes. Second point is that it is easy to accept deteriorating solution with high temperature and it does not converge quickly. Third point is that it is hard to escape from local minimum trap with low temperature and has low searching accuracy. To overcome the disadvantages, Lv et al. [30] gave a theoretical discussion of a cloud theory-based simulated annealing algorithm (CSA) and showed that CSA is superior to SA in terms of convergence speed, searching ability, and robustness. Following that, Torabzadeh and Zandieh [31] applied CSA to solve the two-stage assembly flow-shop problems on m-machine environment to minimize a weighted sum of makespan and mean completion time. They further compared CSA and SA and showed that CSA performed better than SA did. For more applications of the CSA algorithm, readers may refer to Geng et al. [32] for a SVR-based load forecasting model, to Pourvaziri and Pierreval [33] for a dynamic facility layout problem based on open queuing network, and to We et al. [34] for a two-stage assembly scheduling problem with learning consideration.In light of these observations, in this study, we will consider a robust two-machine flow-shop scheduling problem with scenario-dependent processing times and the goal is to minimize the total completion time of jobs. In the same problem setting but under the case where jobs processing times are constant, the literature shows that this problem is NP-hard for the adopted goal. The main contributions of this study are as follows. (1) The authors addressed a robust two-machine flow-shop scheduling problem with scenario-dependent processing times. (2) The authors derived two new dominant properties and two lower bounds to be embedded in a branch-and-bound method for finding optimal solutions efficiently. (3) The authors proposed 12 simple heuristics and their corresponding counterparts improved by a pairwise interchange method. (4) The authors design 12 variants of a CSA algorithm.The rest of this study is organized as follows. In Section2, we introduce notations and problem formulation. In Section 3, we derive a lower bound and two dominant properties to be used in a branch-and-bound method. In Section 4, we propose 12 simple heuristics and their corresponding improved counterparts by a pairwise interchange process and 12 variants of CSA algorithm. In Section 5, we tune the parameters of CSA algorithm, and in Section 6, we conduct simulation studies to evaluate the performances of all the proposed methods.


## 2. Notations and Problem Description

The adopted notations for this study are listed as follows:n: number of jobs.J1,J2,…,Jn: n job codes{M1, M2}: two machine codesσ1,σ2: job schedulesδ, δ′: k determined job schedule and n − k undetermined job schedule[ ]: scheduled job positions: scenario, where s = 1, 2ajs,bjs: scenario-s processing times of job Jj on M1, M2t1s, t2s: the starting time on M1 and M2Cijsσ: the completion time of job Jj on machine i under scenario s for the job schedule σTi: the initial temperature in CSATf: the final temperature in CSAλ: the annealing index with 0<λ<1 in CSANr: the number of improvements in CSAThe studied two-machine flow-shop scheduling problem with two scenarios (or states) is described as follows. There aren jobs, each consisting of two operations with processing times ajs,bjs, j=1,2,…,n, for scenario s, s=1,2, on machines M1 and M2, respectively. There are precedence constraints between the operations, i.e., each job is first processed on M1 and then on M2. Additionally, no machine can process more than one job at a time and a job cannot be interrupted once the processing starts; no idle time can be allowed on machine M1. As the value of our objective function is scenario-dependent, the robustness criterion of this study is the absolute robustness [4, 6], which is to find a schedule minimizing minσ∈Πmaxs=1,2∑j=1nC2jsσ, where Π is the set of all possible permutations of jobs.


## 3. Methodology

Given the fact that the same problem without scenario-dependent version is NP-hard (see Gonzalez and Sahni [3]), the branch-and-bound approach is commonly and widely used for an optimal-solution technical tool. Besides, deriving a good lower bound of the partial schedule is very important in the branch-and-bound (B&B) method. In what follows, we build a lower bound based on the idea of Ignall and Schrage [35]. Let σ=δ,δ′ be a schedule where the order of the first k jobs in the subschedule δ has been determined and the remaining (n − k) jobs in another subschedule δ′ have not been determined, where l = n − k. According to the definition, the completion times for the (k + 1)th job, say Ji from unscheduled set δ′, and the (k + 2)th job, say Jj from unscheduled set δ′, on machines M1 and M2 for scenario s in a schedule σ=δ,δ′ are given as follows:(1)C1isσ=∑v∈δavsσ+ais=t1s+ais,C1jsσ=∑v∈δavsσ+ais+ajs=t1s+ais+ajs,C2isσ=maxC1isσ,t2s+bis,C2jsσ=maxC2isσ,C1jsσ+bjs.In general,(2)C2k+1sσ=maxt2sσ,t1s+ak+1s+bk+1s>t2s+bk+1s,C2k+2sσ=maxC2k+1sσ,t1s+ak+1s+ak+2s+bk+2s≥t2s+bk+1s+bk+2s.In a similar way, we have(3)C2k+lsσ≥t2s+bk+1s+⋯+bk+ls.Therefore, we have the following inequality fors = 1, 2.(4)∑i=1nC2isσ≥∑i=1kC2isσ+n−kt2s+∑i=k+1nn−i+1bis,s=1,2.On the other hand, we have(5)C2k+1sσ=maxt2s,t1s+ak+1s+bk+1s≥t1s+ak+1s+bk+1s,C2k+2sσ=maxC2k+1sσ,t1s+ak+1s+ak+2s+bk+2s≥t1s+ak+1s+ak+2s+bk+2s.In a similar way, we have(6)C2k+lsσ≥t1s+ak+1s+⋯+ak+n1s+bk+ls.Therefore, we have the following inequality fors = 1, 2.(7)∑i=1nC2isσ≥∑i=1kC2isσ+n−kt1s+∑i=k+1nn−i+1ais+∑i=k+1nbis,s=1,2.According to equations (4) and (7), we have(8)maxs=1,2∑i=1nC2isσ≥12∑s=1,2∑i=1kC2isσ+n−kt2s+∑i=k+1nn−i+1bis,maxs=1,2∑i=1nC2isσ≥12∑s=1,2∑i=1kC2isσ+n−kt1s+∑i=k+1nn−i+1ais+∑i=k+1nbis.Therefore, we have the following lower bound:(9)maxs=1,2∑i=1nC2isσ≥max12∑s=1,2∑i=1kC2isσ+n−kt1s+∑i=k+1nn−i+1ais+∑i=k+1nbis,12∑s=1,2∑i=1kC2isσ+n−kt2s+∑i=k+1nn−i+1bis.That is,(10)lower bound=max12∑s=1,2∑i=1kC2isσ+n−kt1s+∑i=k+1nn−i+1ais+∑i=k+1nbis,12∑s=1,2∑i=1kC2isσ+n−kt2s+∑i=k+1nn−i+1bis,where ak+1s≤⋯≤ak+ls and bk+1s≤⋯≤bk+ls are nondecreasing orders of ak+1s,…,ak+ls and bk+1s,…,bk+ls for jobs in the partial schedule δ′, s = 1, 2.In what follows, we also derive two more properties used in our proposed branch-and-bound method. The first one is based on the idea of Cadambi and Sathe [11]. To further explain the details of Property 1, we let σ1=δ,i,j,δ′ and σ2=δ,j,i,δ′ denote two schedules in which δ and δ′, respectively, are partial sequences. To show that σ1 is no worse than σ2, the following condition suffices:(11)maxC2i1σ1+C2j1σ1,C2i2σ1+C2j2σ1≤maxC2j1σ2+C2i1σ2,C2j2σ2+C2i2σ2,C2jsσ1≤C2isσ2,s=1,2.Property 1.
Ifais<ajs and bis=bjs, s = 1, 2, then σ1 is no worse than σ2.Proof.
To show thatσ1 is no worse than σ2, the following condition suffices:(12)maxs=1,2C2isσ2+C2jsσ2≥maxs=1,2C2isσ1+C2jsσ1.
From the definition of completion time of a job, the following equations hold. Fors = 1, 2,(13)C1isσ1=∑v∈δavsσ1+ais=t1s+ais,(14)C1jsσ1=t1s+ais+ajs=C1isσ2,(15)C2isσ1=maxC1isσ1,t2s+bis,(16)C2jsσ1=maxC2isσ1,C1jsσ1+bjs,(17)C1jsσ2=t1s+ajs,(18)C2jsσ2=maxC1jsσ2,t2s+bjs,(19)C2isσ2=maxC2jsσ2,C1isσ2+bis.
Using successively definition (18), definition (17), assumptions, definition (13), and definition (15), we have(20)C2jsσ2=maxC1jsσ2,t2s+bjs≥C2isσ1=maxt1s+ais,t2s+bis=maxC1isσ1,t2s+bis=C2isσ1.
Using successively definition (19), inequality (20), equality (14), assumptions, and definition (16), we have(21)C2isσ2=maxC2jsσ2,C1isσ2+bis≥maxC2isσ1,C1isσ2+bis=maxC2isσ1,C1jsσ1+bjs=C2jsσ1.
From (20) and (21), we have maxs=1,2C2isσ2+C2jsσ2≥maxs=1,2C2isσ1+C2jsσ1.Property 2.
Ifais<ajs, t1s+ajs<t2s, bis<bjs, and t1s+ais+ajs<t2s+bis, s = 1, 2, then σ1 is no worse than σ2.Proof.
This proof can be obtained similarly to the proof of Property1.
Note that in general, a sequenceσ1 of jobs is said to be no worse than another sequence σ2 if Fσ1=maxs=1,2∑i=1nC2isσ1≤Fσ2. Properties 1 and 2 are two special cases.


## 4. Some Heuristics and Some Variants of the CSA

In light of the scenario-dependent processing time factor, we consider a two-stage method to solve this problem. It is well known that the Johnson rule can be applied to minimize the makespan criterion for the two-machine flow shop. Thus, we adopt several different variants of the combinations of the scenario-dependent processing times to be applied on Johnson rule to find initial seeds. Even though it is not the best one for the total completion time criterion, a good seed can be obtained. Following that, we improve these seeds by a pairwise interchange method and reset these seeds in CSAs, respectively.In the researchers’ communities, Johnson’s rule [36] has been commonly utilized to solve the makespan minimization problem on 2-machine flow-shop setting. However, one can observe that it could not yield the optimal schedule for this model when the scenario-dependent processing times are present. The main idea of Johnson’s rule is based on “There exists an optimal sequence in which job Ji is scheduled before job Jj if minai,bj≤minaj,bi holds.” Furthermore, to explore the performance of this rule, 12 simple heuristics and their corresponding improved ones by a pairwise interchange process are provided in the following. The details of the steps for the 12 heuristics in stage one are described as follows.For stage 1, the following 12 heuristic algorithms are based on the Johnson rule [36]. Furthermore, to obtain a high quality of approximate solutions, we consider the solutions found from these 12 heuristics as 12 seeds to be improved by a pairwise interchange process and to be seeds used in a cloud theory-based simulated annealing (CSA) algorithm, respectively. The summary of 12 proposed initial heuristics, their corresponding 12 (pairwise) improved counterparts, and 12 variants of the CSA algorithm is as follows.According the thoughts of Johnson’s rule, we propose the 12 heuristics as H1, H2, …, and H12 as follows.H1 heuristic(1)
Letai∗=maxai1,ai2 be the processing time for job Ji on machine 1 and bi∗=maxbi1,bi2 be the processing time for job Ji on machine 2, i = 1, 2, …, n(2)
Letvi=signai∗−bi∗/minai∗,bi∗, i = 1, 2, …, n(3)
Order jobs in nondecreasing value ofvi, i = 1,…, n} and output the final schedule σ1 and its value of the objective functionRegarding the H2 heuristic and H3 heuristic, in step 1, we replace ai∗=maxai1,ai2,bi∗=maxbi1,bi2 by ai∗=minai1,ai2, bi∗=minbi1,bi2, and by ai∗=ai1+ai2/2, bi∗=bi1+bi2/2, respectively, while steps 2–5 are the same as those of H1 method. Regarding H4, H5, and H6 methods, for each θ, we reset ai∗=θ⋅maxai1,ai2 as the processing time for job Ji on machine 1 and bi∗=1−θ⋅maxbi1,bi2 as the processing time for job Ji on machine 2, keeping the same steps 2–5 as those in H1. We then record H4, H5, and H6 for θ=0.25,0.5,0.75. In a similar way, we record H7 to H9 for the cases ai∗=β⋅minai1,ai2 and bi∗=1−β⋅minbi1,bi2, for β=0.25,0.5,0.75, and record H10 to H12 for the cases ai∗=γai1+ai2/2 and bi∗=1−γbi1+bi2/2, for γ=0.25,0.5,0.75.For stage 2, we consider embedding a pairwise interchange improvement method to each heuristic Hi to increase the efficiency of finding better solutions,i = 1, 2, …, 12. They are simply recorded as H1+PI,H2+PI,…,H12+PI.The problem under study is NP-hard because the same problem without scenario-dependent processing times is NP-hard. In order to quickly find good quality of near-optimal solutions and save CPU time, for stage 3, we utilize the cloud theory-based simulated annealing (CSA) algorithm proposed by Torabzadeh and Zandieh [31]. Furthermore, we also adopt solutions yielded from 12 heuristics at the first stage to be 12 seeds in CSA algorithm. Some important parameters in CSA such as the initial temperature (Ti), final temperature (Tf), the number of improvement repetitions (Nr), and the annealing index (λ) need to be explored and tuned. The descriptions of 12 variants of CSA algorithm are summarized as follows (Algorithm 1).Algorithm 1: The details of 12 variants of CSA.
Input: 12 initials of σ1,σ2,…,σ12 and values of parameters TiTf, λ, Nr(1)Doi = 1, 12(2) for eachσi(3) LetT = Ti(4)Do while {T > Tf}(5) LetHe = T, En = T, u0 = 1 − T, En′=maxEn+He−1/3q,δ,where 0 <q < 1, and 0 < δ < 10−8.(6) LetT′=En′⋅−2lnu0(7)Do while {j < Nr}.(8) Choosep and q integers randomly with 1≤p,q≤n(9) Interchange thepth position and qth position in σi to generate another new schedule σt.(10) Compute the value of the objective function forσt, obj (σt).(11) If obj(σt) < obj(σi), then replace σi by σt; otherwise, replace σi by σtifω < exp−d/T′, where σ is a random number between (0, 1) and d=objσt−objσi/objσi.(12)j = j + 1(13)End do(14)T=T×λj(15)End do(16)Output the final schedule CSA_σi,(17)End do(18)Output the final 12 schedules CSA_σ1,CSA_σ2,…,CSA_σ12Besides the above developments, our proposed branch-and-bound algorithm adopts the depth first policy in the branching tree and assigns jobs in a forward manner starting from the first place to the last place [34, 37]. In the branching nodes, we determine if the node should be cut by using Property 1 and Property 2. We compute its lower bound for the active node and find its objective function for the complete node. We adopt the best solution among the proposed heuristics as an upper bound. Once a complete node is done, we update the upper bound when a complete node is generated.


## 5. Tuning the Parameters

Before performing intensive computational simulation experiments, there are four initial parameters in a CSA algorithm that need to be tuned, such as the initial temperature (Ti), final temperature (Tf), the number of improvement repetitions (Nr), and the annealing index (λ). According to the experience from some preliminary simulations, final temperature (Tf) is set at 10−8. An experiment of one factor at a time was run to tune the parameters in the order of Ti, Nr, and λ. On these computer experiments, the size of jobs was set at n = 10, the processing times ajs,bjs followed a uniform distribution over integers 1 to 20, Nr was set as 10, and λ was set as 0.98. For each parameter combination, 100 problem instances were generated, the mean of the objective function was computed, and the B&B method was also run to obtain the optimal value of the objective function. The average error percentage (AEP) was recorded. The formula of AEP is AEP = 100∗ × [(Oj − O∗)/O∗] [%], where Oj is the final objective value outputted from each of heuristics or algorithms and O∗ is from the B&B method. We tested Ti at 0.9, 0.99, 0.1, 0.01, 10−3, 10−4, and 10−5. As shown in Figure 1, as Ti=0.9, the mean of AEP has the minimum, 0.0257.Figure 1
The AEP of differentTi values.Second, the parameter Nr increases from 1 to 25, and other parameters were fixed at Ti=0.9 and λ = 0.98. As shown in Figure 2, as Nr = 20, the mean AEP has a minimum of 0.18%.Figure 2
The AEP of differentNr values.Third, the parameterλ was chosen at values of 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.91, 0.92, 0.93, 0.94, 0.95, 0.96, 0.97, 0.98, and 0.99. As shown in Figure 3, as λ = 0.99, the mean AEP reaches a minimum value of 0.16%.Figure 3
The AEP of differentλ values.According to the parameter tuning results, the parameters were set finally as follows:Ti at 0.9, Nr at 20, λ at 0.99, and Tf at 10−8, respectively, for the later computational experiments.


## 6. Simulation Studies

Intensive computational simulation experiments were carried out to evaluate the performances of the branch-and-bound method and the efficacy of the 12 heuristics and 12 variants of the CSA algorithm (recorded as 12 CSA_Hs). The heuristics and algorithms were coded by FORTRAN (Compaq visual Fortran 6.6 version). The experiments were executed on a PC with an Intel Xeon CPU E5-1620 3.60 GHz, RAM 4.00 GB, and in Windows 7 OS with 32 bits. For small size of jobs (n = 8, 9, 10, 12), the mean AEPs of 12 heuristics and 12 variants of the CSA algorithm were recorded; for large size of jobs (n = 150, 150, 200), the mean RPDs were reported, where RPD was calculated as RPD = 100 × [(Oj − O∗)/O∗] [%], in which Oj is the final objective value yielded from each of heuristics or algorithms and O∗ is the best among the 12 heuristics and 12 algorithms.The job processing times were generated using several different uniform distributions by Kouveils et al. [2]. The integer processing times of ajs,bjs on machine Mi follows a 10⋅βi⋅U0,1+40⋅α⋅βi+1 discrete uniformly distribution, where α takes values of 0.2, 0.6, and 1.0 and (β1,β2) takes values of, say, type T1 = (1.0, 1.0), type T2 = (1.2, 1.0), and type T3 = (1.0, 1.2). There are nine combinations of α and types of (β1,β2). For each parameter combination, 100 problem instances were generated.The results found from the B&B method are listed in Table1. As can be seen from Table 1, as n = 12, the number of nodes in the B&B method will exceed 108. The number of nodes and CPU processing times will also increase as the number of jobs n and alpha increases.Table 1
The results obtained from the branch-and-bound method.
nβ1β2αNodeCPU timeFSMeanMaxMeanMax81.01.00.23,601.7128,9800.010.111000.62,467.7927,0520.010.091001.02,578.2727,2650.010.091001.21.00.23,609.4828,9680.010.111000.63,540.3828,7700.010.091001.04,025.8328,9720.020.091001.01.20.22,456.5526,8130.010.091000.62,182.4223,9810.010.081001.01,477.5715,7260.010.0610091.01.00.216,721.47195,1550.080.831000.617,317.86240,6730.091.081001.017,927.18231,5930.090.941001.21.00.223,905.57194,0720.120.801000.626,148.99260,6570.121.051001.041,122.48260,6550.191.231001.01.20.26,823.80113,5580.040.471000.612,606.71158,8540.060.621001.014,495.86227,8850.070.92100101.01.00.2127,492.361,791,1450.688.521000.696,467.991,449,9460.537.161001.0124,604.261,736,0810.668.241001.21.00.2169,486.431,703,8050.898.241000.6243,752.912,023,6411.249.751001.0210,469.411,712,3851.068.111001.01.20.282,160.681,324,8510.416.321000.6110,516.601,875,3740.548.801001.058,701.331,513,0220.296.90100121.01.00.23,755,562.1762,436,48327.88439.35980.63,274,146.0855,548,98224.46392.19991.02,832,541.9259,238,96320.91416.35971.21.00.23,949,093.8872,245,92229.29506.82930.65,902,111.5991,075,14941.62613.26931.06,079,569.1883,141,56642.73557.81951.01.20.23,069,396.1286,360,81421.14562.121000.63,423,781.2864,285,64423.61433.17981.03,795,927.4293,999,41925.85593.71100Mean1,041,910.8819,043,9677.35127.6599.25The simulation results of the small size of jobs are shown in Tables2 and 3 for 12 Hi + PIs and 12 CSA_Hs. The AEPs of the CSA_Hs algorithm are much less than the Hi + PIs. The comparison results of the Hi + PIs and the CSA_Hs are further shown in Figure 4. In light of the boxplots in Figure 4, the performances of the group CSA_Hs are better than those of the group Hi + PIs in the mean and variance of AEP, i.e., the CSA_Hs are more accurate and stable.Table 2
The AEPs of 12 heuristics, Hi + PIs.
nβ1β2αH1 + PIH2 + PIH3 + PIH4 + PIH5 + PIH6 + PIH7 + PIH8 + PIH9 + PIH10 + PIH11 + PIH12 + PIFSAEPAEPAEPAEPAEPAEPAEPAEPAEPAEPAEPAEP81.01.00.20.881.070.710.880.861.250.871.091.370.850.841.131000.60.440.480.420.360.430.580.500.480.620.420.410.561001.00.270.310.280.260.270.410.210.280.420.200.250.401001.21.00.20.600.790.700.500.580.800.540.670.780.430.640.801000.60.260.270.270.180.250.310.190.290.270.160.290.291001.00.130.130.130.090.120.110.070.130.130.070.130.151001.01.20.21.221.211.111.111.111.411.011.121.331.061.181.301000.60.420.420.360.320.420.760.470.440.610.390.380.621001.00.260.240.270.250.270.410.280.260.270.240.270.3510091.01.00.21.081.221.110.940.921.461.111.241.440.730.911.311000.60.480.590.500.410.430.720.480.580.710.390.550.711001.00.310.330.310.310.310.340.320.350.380.280.310.401001.21.00.20.740.840.760.520.700.870.560.820.790.470.660.781000.60.240.260.250.150.250.250.140.270.280.130.260.241001.00.110.110.110.090.110.110.080.100.110.080.100.091001.01.20.21.331.311.181.031.291.361.251.241.351.121.151.361000.60.370.400.360.430.350.500.410.340.490.400.370.471001.00.260.280.290.300.270.380.300.270.300.250.280.32100101.01.00.21.111.321.120.961.131.381.111.211.291.011.221.371000.60.520.610.520.480.550.730.520.610.600.480.510.631001.00.350.390.340.280.330.390.320.340.460.290.310.431001.21.00.20.810.910.810.540.770.880.710.950.950.550.770.931000.60.200.200.190.150.200.230.180.210.210.120.210.221001.00.110.130.130.090.120.120.090.130.140.080.130.131001.01.20.21.321.351.431.311.361.441.121.211.471.281.371.441000.60.450.460.450.480.460.630.500.460.570.400.440.561001.00.260.290.280.260.270.330.240.270.310.290.270.37100121.01.00.21.281.341.371.131.281.591.211.411.571.181.281.54980.60.620.660.610.540.570.720.610.730.680.550.670.708991.00.410.500.440.330.400.500.430.510.550.370.480.47971.21.00.21.031.110.910.740.861.220.741.051.120.680.931.08930.60.260.250.270.240.240.270.210.270.270.190.280.27931.00.180.150.160.130.180.190.130.150.150.100.160.16951.01.20.21.391.381.451.351.341.681.351.411.661.461.331.461000.60.390.360.420.440.420.570.360.360.540.440.400.60981.00.250.230.240.240.240.300.230.230.310.280.250.32100Mean0.570.610.560.490.550.700.520.600.680.490.560.6699.25Table 3
The AEP of 12 CSA_Hs.
nβ1β2αCSA_H1CSA _H2CSA _H3CSA _H4CSA _H5CSA _H6CSA _H7CSA _H8CSA _H9CSA _H10CSA _H11CSA _H12FSAEPAEPAEPAEPAEPAEPAEPAEPAEPAEPAEPAEP81.01.00.20.0040.0000.0000.0030.0020.0020.0020.0000.0020.0080.0020.0051000.60.0010.0020.0000.0000.0010.0020.0010.0020.0010.0020.0020.0011001.00.0010.0000.0010.0010.0000.0000.0020.0000.0000.0000.0000.0001001.21.00.20.0050.0030.0000.0030.0000.0000.0000.0010.0020.0020.0020.0001000.60.0000.0000.0000.0000.0000.0010.0000.0000.0000.0010.0000.0001001.00.0000.0000.0000.0000.0000.0000.0000.0000.0000.0000.0000.0001001.01.20.20.0050.0000.0060.0050.0050.0000.0030.0000.0020.0030.0000.0021000.60.0000.0010.0010.0020.0010.0010.0010.0000.0010.0020.0000.0001001.00.0000.0000.0000.0000.0000.0000.0010.0000.0010.0000.0000.00010091.01.00.20.0070.0080.0060.0110.0060.0010.0070.0060.0070.0120.0170.0011000.60.0070.0040.0050.0050.0040.0060.0030.0110.0020.0100.0000.0061001.00.0020.0000.0030.0020.0020.0020.0020.0030.0050.0040.0020.0021001.21.00.20.0020.0050.0020.0020.0060.0010.0060.0110.0060.0010.0100.0061000.60.0020.0000.0000.0020.0010.0010.0010.0010.0020.0020.0000.0021001.00.0010.0000.0000.0000.0000.0000.0010.0000.0000.0000.0000.0011001.01.20.20.0030.0060.0070.0100.0110.0040.0100.0080.0140.0080.0080.0081000.60.0000.0000.0030.0020.0030.0010.0020.0020.0030.0010.0020.0021001.00.0020.0010.0000.0000.0010.0000.0010.0020.0000.0020.0010.001100101.01.00.20.0260.0180.0220.0180.0290.0230.0150.0330.0170.0290.0300.0291000.60.0100.0110.0180.0150.0100.0090.0150.0190.0150.0220.0060.0101001.00.0070.0090.0080.0030.0130.0110.0070.0050.0070.0100.0070.0091001.21.00.20.0120.0080.0210.0100.0150.0110.0160.0220.0090.0140.0080.0131000.60.0030.0020.0010.0040.0010.0030.0030.0030.0030.0030.0010.0041001.00.0020.0030.0030.0010.0020.0010.0030.0010.0020.0010.0030.0021001.01.20.20.0270.0270.0120.0280.0240.0270.0200.0170.0230.0250.0260.0241000.60.0080.0070.0040.0060.0090.0030.0070.0050.0080.0060.0020.0031001.00.0030.0040.0020.0020.0040.0040.0020.0040.0040.0020.0030.004100121.01.00.20.0820.0930.0650.0690.0680.0630.0990.0830.0590.0830.0810.090980.60.0490.0370.0290.0320.0320.0410.0350.0480.0340.0410.0400.047991.00.0200.0140.0240.0200.0200.0170.0310.0170.0220.0190.0210.024971.21.00.20.0500.0440.0550.0370.0370.0410.0500.0630.0470.0490.0480.037930.60.0080.0090.0120.0100.0110.0120.0120.0150.0110.0130.0120.007931.00.0060.0040.0040.0060.0040.0050.0050.0030.0050.0050.0040.005951.01.20.20.0610.0530.0550.0280.0590.0480.0540.0620.0480.0610.0490.0431000.60.0150.0150.0120.0070.0210.0100.0210.0120.0090.0120.0140.010981.00.0080.0070.0060.0080.0070.0060.0100.0050.0060.0050.0060.008100Mean0.0120.0110.0110.0100.0110.0100.0120.0130.0110.0130.0110.01199.25Figure 4
The boxplots of 12 heuristics and 12 CSA-Hs algorithms (smalln).In regard to the performances of 12 heuristics and 12 CSA_Hs, Tables4 and 5 demonstrate the simulation numerical results.Table 4
The RPD of 12 Hi + PI.
nβ1β2αH1 + PIH2 + PIH3 + PIH4 + PIH5 + PIH6 + PIH7 + PIH8 + PIH9 + PIH10 + PIH11 + PIH12 + PIRPDRPDRPDRPDRPDRPDRPDRPDRPDRPDRPDRPD1001.01.00.21.411.241.431.011.361.431.161.280.991.011.391.170.60.660.580.670.460.650.640.530.570.440.480.650.551.00.410.360.430.280.410.410.360.360.290.300.400.351.21.00.20.680.950.700.730.641.031.070.960.970.610.660.970.60.310.340.330.300.300.340.440.340.330.260.330.341.00.200.200.200.180.200.200.270.200.200.160.200.201.01.20.21.291.191.241.091.261.531.121.220.991.061.221.250.60.370.390.360.370.360.560.370.390.340.360.360.411.00.240.250.240.240.240.360.250.250.210.240.240.261501.01.00.21.291.111.300.811.291.261.051.080.700.851.251.000.60.560.480.570.340.550.570.440.470.320.360.540.461.00.370.320.380.230.360.370.280.320.210.250.360.301.21.00.20.550.770.580.640.510.900.970.790.840.450.540.850.60.280.300.290.280.270.300.440.300.290.230.290.291.00.200.200.200.190.200.200.290.200.200.140.200.201.01.20.21.161.041.150.881.121.460.971.010.810.911.101.130.60.350.360.330.330.340.540.340.360.290.330.330.421.00.220.230.220.220.220.350.230.230.180.220.220.252001.01.00.21.180.991.160.671.141.200.900.980.620.731.140.960.60.520.430.540.310.500.530.390.440.270.330.510.411.00.320.260.330.190.320.320.260.280.160.200.310.251.21.00.20.450.700.490.600.420.800.900.710.770.370.440.740.60.270.300.290.290.260.300.450.310.300.220.290.291.00.200.200.200.190.200.190.290.200.200.130.200.201.01.20.21.070.981.020.811.001.420.870.980.730.810.951.060.60.340.340.320.320.330.540.330.340.260.320.320.391.00.210.220.210.210.210.340.210.210.170.210.200.24Mean0.560.550.560.450.540.670.560.550.450.430.540.55Table 5
The RPD of 12 CSA_Hs.
nβ1β2αCSA_H1CSA _H2CSA _H3CSA _H4CSA _H5CSA _H6CSA _H7CSA _H8CSA _H9CSA _H10CSA _H11CSA _H12RPDRPDRPDRPDRPDRPDRPDRPDRPDRPDRPDRPD1001.01.00.20.120.110.110.130.120.120.100.110.120.130.130.110.60.050.050.050.050.050.050.060.050.050.050.050.051.00.030.030.030.030.030.030.040.040.030.040.030.031.21.00.20.050.040.050.050.050.050.050.050.050.050.050.050.60.020.020.010.010.020.010.020.010.020.010.010.021.00.010.010.010.010.010.010.010.010.010.010.010.011.01.20.20.110.110.100.100.100.110.100.120.120.110.090.100.60.040.030.030.030.030.020.030.030.030.030.040.031.00.010.020.020.020.020.020.020.020.020.010.020.021501.01.00.20.090.090.100.100.100.080.100.090.100.100.110.100.60.040.040.040.050.050.040.050.050.050.050.050.051.00.030.030.030.030.030.030.030.030.030.030.030.031.21.00.20.040.040.040.040.050.040.040.040.040.040.040.040.60.010.010.010.010.010.010.010.010.010.010.010.011.00.010.010.010.010.010.010.010.010.010.010.010.011.01.20.20.080.080.100.090.090.090.080.090.090.090.110.080.60.030.030.030.030.020.030.020.030.030.020.030.031.00.010.010.020.010.010.010.010.010.020.010.020.022001.01.00.20.090.100.100.100.110.100.110.100.100.090.100.090.60.040.040.040.040.040.040.040.040.050.040.040.051.00.030.030.030.030.030.030.030.030.030.030.030.031.21.00.20.040.040.040.040.040.040.040.040.040.040.040.040.60.010.010.010.010.020.010.010.010.010.010.010.011.00.090.010.010.010.010.010.010.010.010.010.010.011.01.20.20.080.090.080.080.090.080.070.080.080.070.080.080.60.030.020.030.020.020.020.020.020.020.020.020.021.00.010.010.020.010.010.010.020.020.010.010.010.01Mean0.040.040.040.040.040.040.040.040.040.040.040.04The performances of 12 Hi + PIs and 12 CSA_Hs are further summarized in Figure5. From the boxplots shown in Figure 5, 12 CSA_Hs indicate a better capability on searching near-optimal solutions than those of 12 Hi + PIs, and it seems that there is no difference among the group of CSA_Hs and among the group of Hi + PIs.Figure 5
The boxplots of 12 heuristics and 12 CSA-Hs algorithms (largen).The following analysis of the simulation data applies statistical methods in the aim to have science evidence to that whether the differentiation of performance between the groups of 12 heuristics and the 12 CSA_Hs are significant statistically, and the performances within the 12 heuristics or within the 12 CSA_Hs are not significant statistically.In order to establish the difference of performance between the 12 heuristics and CSA_Hs for small size ofn, a linear model was fitted to AEPs on the affected factors, n, α, and the type of (β1,β2), on software SAS 9.4. Four normality tests of the error term in the fitted linear model were adopted. The p values of these tests are less than 0.05 and are listed in Table 6 (columns 3 and 4), for example, the p value is less than 0.01 obtained from the Kolmogorov–Smirnov test. Thus, for the commonly used significance level 0.05, the normality assumption of the AEPs is invalid. Therefore, instead of using a parametric statistical method, the DSCF procedure (Dwass–Steel–Critchlow–Fligner, [38]), a nonparametric statistical method, was utilized to allow a multiple comparison among the 12 Hs + PI and 12 CSA_Hs to fulfill the characteristic of the simulation observations. Table 7 exhibits the comparative outcomes. The performances among all pairs of any one of the 12 heuristics and any one of the12 CSA_Hs are significant different statistically. Moreover, any pair of differences of AEPs between the 12 heuristics is not significant statistically, and any pair of differences of AEPs between the 12 CSA_Hs is also not significant statistically.Table 6
Normality tests of AEP and RPD.
Tests for normality of AEPTests for normality of RPDMethod of testValue of statisticp valueValue of statisticp valueShapiro–WilkW0.9663<0.0001W0.9540<0.0001Kolmogorov–SmirnovD0.0810<0.0100D0.0871<0.0100Cramer–von MisesW-Sq0.8688<0.0050W-Sq1.0028<0.0050Anderson–DarlingA-Sq6.3696<0.0050A-Sq7.0661<0.0050Table 7
A multiple comparison between 12 heuristics and 12 CSA_Hs (smalln).
p valueCSA_H2CSA_H3CSA_H4CSA_H5CSA_H6CSA_H7CSA_H8CSA_H9CSA_H10CSA_H11CSA_H12H1 + PIH2 + PIH3 + PIH4 + PIH5 + PIH6 + PIH7 + PIH8 + PIH9 + PIH10 + IIH11 + PIH12 + PICSA_H11.001.001.001.001.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H21.001.001.001.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H31.001.001.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H41.001.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H51.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H61.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H71.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H81.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H91.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H101.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H111.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H12<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01H1 + PI1.001.001.001.000.991.001.000.991.001.001.00H2 + PI1.001.001.001.001.001.001.000.991.001.00H3 + PI1.001.000.991.001.001.001.001.001.00H4 + PI1.000.971.001.000.981.001.000.98H5 + PI0.991.001.000.991.001.000.99H6 + PI0.991.001.000.920.991.00H7 + PI1.000.991.001.000.99H8 + PI1.001.001.001.00H9 + PI0.961.001.00H10 + PI1.000.96H11 + PI1.00Regarding the large size of jobs, another linear model was fitted to RPDs on the affected factor,n, α, and the type of (β1,β2). The p values of the four normality tests of the error term in the fitted linear model are less than 0.05 and are listed in Table 6 (columns 5 and 6). Table 8 illustrates the results of another multiple comparison on the 12 heuristics and 12 CSA_Hs for large n. The conclusion about the performances of (within) 12 heuristics and (within) the 12 CSA_Hs is almost the same as that from the comparisons for the small n; we would not repeat here because only some of the p values are slightly different between Tables 7 and 8.Table 8
A multiple comparison between 12 heuristics and 12 CSA_Hs (largen).
p valueCSA_H2CSA_H3CSA_H4CSA_H5CSA_H6CSA_H7CSA_H8CSA_H9CSA_H10CSA_H11CSA_H12H1 + PIH2 + PIH3 + PIH4 + PIH5 + PIH6 + PIH7 + PIH8 + PIH9 + PIH10 + IIH11 + PIH12 + PICSA_H11.001.001.001.001.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H21.001.001.001.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H31.001.001.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H41.001.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H51.001.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H61.001.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H71.001.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H81.001.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H91.001.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H101.001.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H111.00<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01CSA_H12<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01<0.01H1 + PI1.001.001.001.000.991.001.000.990.991.001.00H2 + PI1.001.001.001.001.001.000.990.991.001.00H3 + PI1.001.000.991.001.001.001.001.001.00H4 + PI1.000.880.991.000.981.001.000.99H5 + PI0.991.001.000.991.001.001.00H6 + PI1.001.000.790.830.991.00H7 + PI1.000.970.961.000.99H8 + PI0.990.991.001.00H9 + PI1.000.990.99H10 + PI1.000.99H11 + PI1.00


## 7. Conclusions

This paper studies the scenario-dependent processing times in a two-machine flow-shop environment on which the measurement is the total completion time. Because of the NP-hardness, we designed a branch-and-bound (B&B) method and developed a lower bound and two superior properties to enhance the searching efficiency of the B&B method. Then, we proposed 12 simple heuristics which were improved by a pairwise interchange method, coded as Hi + PIs, and further devised a cloud theory-based simulated annealing (CSA) algorithm. The CSA algorithm fed with the initial solutions produced 12 simple heuristics (without any further improvement) to form 12 versions of the CSA algorithm, coded as CSA_Hs. The computer experiments were conducted to investigate the efficiency of the 12 heuristics, Hi + PIs, and 12 CSA_Hs. It was noticed that the CSA_Hs produce better solutions compared with 12 heuristics. In addition, statistical methods were applied to perform the analysis of the experimental data, and we verified the significant difference among the groups of the Hi + PIs and the CSA_Hs.As for the future investigation, other characteristics of a scheduling problem like release times of jobs might also incur the uncertain feature. Thus, a potential future research direction could consider this issue by developing structural properties for algorithm design to incorporate this aspect. Deriving more heuristics based on the total completion time criterion in references [39–42] is also a worthy future issue.



---

*Source: 3530701-2020-06-13.xml*