# Bicriterion Optimization for Flow Shop with a Learning Effect Subject to Release Dates

Authors: Ji-Bo Wang; Jian Xu; Jing Yang
Journal: Complexity
 (2018)

---

## Abstract

This paper investigates a two-machine flow shop problem with release dates in which the job processing times are variable according to a learning effect. The bicriterion is to minimize the weighted sum of makespan and total completion time subject to release dates. We develop a branch-and-bound (B&B) algorithm to solve the problem by using a dominance property, several lower bounds, and an upper bound to speed up the elimination process of the search tree. We further propose a multiobjective memetic algorithm (MOMA), enhanced by an initialization strategy and a global search strategy, to obtain the Pareto front of the problem. Computational experiments are also carried out to examine the effectiveness and the efficiency of the B&B algorithm and the MOMA algorithm.


---

## Body

## 1. Introduction

In many industrial systems, logistics, and service settings, the processing times of jobs can decrease due to the learning effects, i.e., firms and employees perform a job (task) over and over and they learn how to perform more efficiently [1, 2]. This is especially observed in seru production system, consisting of some equipment and workers who produce one or more part types. After undertaking cross-training, the learning effects greatly affect their efficiencies [3]. “As there is a significant involvement of humans in scheduling environments, the number of activities subject to learning is high, too. Hence it seems reasonable to consider learning in scheduling environments” [2]. On the other hand, the importance of flow shop scheduling optimization is widely recognized in many manufacturing and assembling processes, e.g., the internet connectivity problem in 3-tiered client-server databases is a two-machine flow shop problem (see [4]); the scheduling of multimedia date objectives for WWW applications reduces to a two-machine flow shop problem (see [5–7]; see also the reviews given in [6] and [8–10]).More recently, Xu et al. [11], Eren [12], Wu and Lee [13], Rudek [14], Kuo et al. [15], Lee and Chung [16], Sun et al. [17, 18], Cheng et al. [19], Li et al. [20], Wang and Zhang [21], J. B. Wang and J. J. Wang [22], Lai et al. [23], Liu and Feng [24], Wang and Zhang [21], Wu et al. [25], Shiau et al. [26], Lu [27], Qin et al. [28], He [29], and Wang et al. [30] considered flow shop scheduling problems with learning effects, but without release dates. Xu et al. [11] considered the flow shop scheduling problems with position-dependent learning effect, i.e., if job Jj is in position l of a schedule, the actual processing time pijl of job Jj on machine Mi is pijl=pija−bl and pijl=pijlα, where pij denotes the normal processing time of job Jj on Mi and a>0, b≥0, and α≤0 are the learning rates. For several regular objective functions, they presented approximate algorithms. Cheng et al. [19] considered the model pijl=pijlα. For the maximum lateness minimization, they gave a mathematical programming model. Wang et al. [31] considered the model pijl=pijlα. For the total completion time minimization, they gave a branch-and-bound algorithm and several well-known heuristics. Lai et al. [23] considered the model pijl=pijlα. For the total tardiness minimization, they gave a branch-and-bound algorithm and two heuristics. He [29] and Li et al. [20] considered the flow shop scheduling problems with time-dependent learning effect, i.e., if job Jj is in position l of a schedule, the actual processing time pijl of job Jj on machine Mi is pijl=pij1+∑h=1l−1piha, where a≤0 is the learning rate and h denotes the job that occupies the hth position in a sequence. For several regular objective functions, they presented approximate algorithms. Shiau et al. [26] considered the flow shop scheduling problems with general position-dependent learning effect, i.e., if job Jj is in position l of a schedule, the actual processing time pijl of job Jj on machine Mi is pijl=pijgl, where 1=g1≥g2≤⋯≥gn is a nonincreasing function. Sun et al. [18] considered the total weighted completion time minimization flow shop scheduling problem. For three position-dependent learning effects, they gave heuristic algorithms. Cheng et al. [19], Lai et al. [23], Wang et al. [31], Wu and Lee [13], and Wang et al. [30] considered the flow shop scheduling with truncated learning effects. J.-B. Wang and J.-J. Wang [22] considered the flow shop scheduling with a general exponential learning effect. For five regular objective functions, they presented heuristic algorithms. Wang and Zhang [21] considered the flow shop scheduling with position-weighted learning effects. For the weighted sum of makespan and total completion time minimization, they gave a branch-and-bound algorithm and some heuristic algorithms. Qin et al. [28] considered the flow shop group scheduling with position-based learning effect. For four objectives (i.e., the makespan, total completion time, total weighted completion time, and maximum lateness), they gave several heuristics and metaheuristics. For new trends in flow shop scheduling with learning effects, we refer the reader to Rudek [14], Liu and Feng [24], Shiau et al. [26], Lu [27], and He [29].However, in fact, the scheduling with release dates is interesting and closer to real problems [32–34]. With modeling a realistic production system in mind, Yin et al. [35] considered single-machine scheduling with release dates and position-dependent learning effects. To the best of our knowledge, the flow shop scheduling problems with a learning effect and release dates (i.e., the ready times) simultaneously have barely been investigated. Bai et al. [36] is the only identifiable exception. Hence, in this paper, we consider the two-machine flow shop scheduling problem with position-dependent learning effect and release dates, and the objective is to minimize the weighted sum of makespan and total completion time. Obviously, the problem under study is NP-hard [34]; thus, the branch-and-bound algorithm might be a good way to obtain the optimal schedule. We further design an evolutionary multiobjective optimization algorithm to obtain the Pareto front of high quality. This contribution makes a clear distinction between this paper and Bai et al. [36], which solely focuses on a single aggregated objective.The remaining of the paper is organized as follows. In Section2, we formalize the problem. Dominance conditions for the problem are presented in Section 3. Branch-and-bound algorithm is discussed in Section 4. Numerical experiments are conducted in Section 5. The last section concludes the paper.


## 2. Notations and Assumptions

The problem may be stated as follows. We are givenn jobs and two machines M1 and M2. Each machine is available at time zero and the job Jj becomes available at its release date rj≥0. Let J=J1,…,Jj,…,Jn represent the set of jobs which are to be processed on 2 machine permutation flow shop settings. Each job Jj j=1,2,…,n is required to be processed on machine M1 and then M2. As in Biskup [2], Lee and Chung [16], Lee and Wu [37], and Lee et al. [38], if job Jj is in position l of a schedule, then the actual processing times ajl and bjl of job Jj on machines M1 and M2 are
(1)ajl=ajlα,l,j=1,2,…,n,bjl=bjlα,l,j=1,2,…,n,respectively, where ajbj denotes the normal processing time (i.e., the basic processing time before learning effects happened) of job Jj on M1M2 and α=log2LR≤0 is the learning index for both machines M1 and M2 depending on the learning rate LR. For a given schedule π, let C1jπ=C1jC2jπ=Cj be the completion time of job Jj on machine M1M2. The objective is to minimize λCmax+1−λ∑j=1nCj, where Cmax=maxCj∣j=1,2,…,n is the makespan and ∑j=1nCj is the total completion time, 0≤λ≤1. Using the conventional three-field notation for describing scheduling problems (Graham et al. [39]), the problem under consideration can be described as F2LE,rjλCmax+1−λ∑j=1nCj, where LE denotes the learning effect [1, 2].


## 3. Dominance Conditions

In this section, we give some dominance rules forF2LE,rjλCmax+1−λ∑j=1nCj. “Dominance rules are basically necessary conditions for any optimal schedule that can be generated. Applying such rules results in a set of precedence relations between jobs. These precedence relations are then used to reduce the number of branches in a branch-and-bound search tree” (Yin et al. [35]). Let S1=π,Jj,Jk,π′ and S2=π,Jk,Jj,π′ be obtained from S1 by only interchanging jobs Jj and Jk, where π and π′ are partial sequences, and there are l−1 jobs in π. To show that S2 dominates S1, it is sufficient to show that C1jS2≤C1kS1, CjS2≤CkS1, and CkS2+CjS2≤CkS1+CjS1. Let AB denote the last completion time prior to jobs Jj and Jk on machine M1M2 in S1; obviously, A and B remain unchanged in S2.Proposition 1.
If the jobsJk and Jj satisfy the following conditions:
(i)
Eitherrk+aklα+bklα≤rj+ajlα+bjlα or rk+aklα+bklα≤A+ajlα+bjlα or rk+aklα+bklα≤B+bjlα
(ii)
EitherA+aklα+bklα≤rj+ajlα+bjlα or ak+bk≤aj+bj or A+aklα+bklα≤B+bjlα
(iii)
EitherB+bklα≤rj+ajlα+bjlα or B+bklα≤A+ajlα+bjlα or bk≤bj
(iv)
Eitherrk+aklα+ajl+1α≤rj+ajlα+akl+1α or A+aklα+ajl+1α≤rj+ajlα+akl+1α;
(v)
Eitherrk+aklα+ajl+1α≤A+ajlα+akl+1α or aklα+ajl+1α≤ajlα+akl+1α or rj+ajl+1α≤A+ajlα+akl+1α
(vi)
EitherA+aklα+ajl+1α≤rk+akl+1α or rj+ajl+1α≤rk+akl+1α
(vii)
Eitheraklα+ajl+1α+bjl+1α≤ajlα+akl+1α+bkl+1α or aklα+ajl+1α+bjl+1α≤ajlα+bjlα+bkl+1α or A+aklα+ajl+1α+bjl+1α≤B+bjlα+bkl+1α or A+aklα+ajl+1α+bjl+1α≤rj+ajlα+akl+1α+bkl+1α or A+aklα+ajl+1α+bjl+1α≤rj+ajlα+bjlα+bkl+1α or A+aklα+ajl+1α+bjl+1α≤rk+akl+1α+bkl+1α
(viii)
Eitheraklα+bklα+bjl+1α≤ajlα+akl+1α+bkl+1α or aklα+bklα+bjl+1α≤ajlα+bjlα+bkl+1α or A+aklα+bklα+bjl+1α≤B+bjlα+bkl+1α or A+aklα+bklα+bjl+1α≤rj+ajlα+akl+1α+bkl+1α or A+aklα+bklα+bjl+1α≤rj+ajlα+bjlα+bkl+1α or A+aklα+bklα+bjl+1α≤rk+akl+1α+bkl+1α
(ix)
EitherB+bklα+bjl+1α≤A+ajlα+akl+1α+bkl+1α or B+bklα+bjl+1α≤A+ajlα+bjlα+bkl+1α or bklα+bjl+1α≤bjlα+bkl+1α or B+bklα+bjl+1α≤rj+ajlα+akl+1α+bkl+1α or B+bklα+bjl+1α≤rj+ajlα+bjlα+bkl+1α or B+bklα+bjl+1α≤rk+akl+1α+bkl+1α
(x)
Eitherrk+aklα+ajl+1α+bjl+1α≤A+ajlα+akl+1α+bkl+1α or rk+aklα+ajl+1α+bjl+1α≤A+ajlα+bjlα+bkl+1α or rk+aklα+ajl+1α+bjl+1α≤B+bjlα+bkl+1α or rk+aklα+ajl+1α+bjl+1α≤rj+ajlα+akl+1α+bkl+1α or rk+aklα+ajl+1α+bjl+1α≤rj+ajlα+bjlα+bkl+1α or aklα+ajl+1α+bjl+1α≤akl+1α+bkl+1α
(xi)
Eitherrk+aklα+bklα+bjl+1α≤A+ajlα+akl+1α+bkl+1α or rk+aklα+bklα+bjl+1α≤A+ajlα+bjlα+bkl+1α or rk+aklα+bklα+bjl+1α≤B+bjlα+bkl+1α or rk+aklα+bklα+bjl+1α≤rj+ajlα+akl+1α+bkl+1α or rk+aklα+bklα+bjl+1α≤rj+ajlα+bjlα+bkl+1α or aklα+bklα+bjl+1α≤akl+1α+bkl+1α
(xii)
Eitherrj+ajl+1α+bjl+1α≤A+ajlα+akl+1α+bkl+1α or rj+ajl+1α+bjl+1α≤A+ajlα+bjlα+bkl+1α or rj+ajl+1α+bjl+1α≤B+bjlα+bkl+1α or ajl+1α+bjl+1α≤ajlα+akl+1α+bkl+1α or ajl+1α+bjl+1α≤ajlα+bjlα+bkl+1α or rj+ajl+1α+bjl+1α≤rk+akl+1α+bkl+1α
thenS2 dominates S1.Proof 1.
Under schedulesS1 and S2, the completion times of jobs Jj and Jk are
(2)C1jS1=maxA,rj+ajlα,(3)CjS1=maxB,C1jS1+bjlα=maxrj+ajlα+bjlα,A+ajlα+bjlα,B+bjlα,(4)C1kS1=maxC1jS1,rk+akl+1α=maxrj+ajlα+akl+1α,A+ajlα+akl+1α,rk+akl+1α,(5)CkS1=maxC1kS1,CjS1+bkl+1α=maxA+ajrα+akl+1α+bkl+1α,A+ajlα+bjlα+bkl+1α,B+bjlα+bkl+1α,rj+ajlα+akl+1α+bkl+1α,rj+ajlα+bjlα+bkl+1α,rk+akl+1α+bkl+1α,(6)C1kS2=maxA,rk+aklα,(7)CkS2=maxrk+aklα+bklα,A+aklα+bklα,B+bklα,(8)C1jS2=maxrk+aklα+ajl+1α,A+aklα+ajl+1α,rj+ajl+1α,(9)CjS2=maxA+aklα+ajl+1α+bjl+1α,A+aklα+bklα+bjl+1α,B+bklα+bjl+1α,rk+aklα+ajl+1α+bjl+1α,rk+aklα+bklα+bjl+1α,rj+ajl+1α+bjl+1α.
If the casesrk+aklα+bklα≤rj+ajlα+bjlα, A+aklα+bklα≤rj+ajlα+bjlα, B+bklα≤rj+ajlα+bjlα, rk+aklα+ajl+1α≤rj+ajlα+akl+1α, rk+aklα+ajl+1α≤A+ajlα+akl+1α, A+aklα+ajl+1α≤rk+akl+1α, aklα+ajl+1α+bjl+1α≤ajlα+akl+1α+bkl+1α, aklα+bklα+bjl+1α≤ajlα+akl+1α+bkl+1α, B+bklα+bjl+1α≤A+ajlα+akl+1α+bkl+1α, rk+aklα+ajl+1α+bjl+1α≤A+ajlα+akl+1α+bkl+1α, rk+aklα+bklα+bjl+1α≤A+ajlα+akl+1α+bkl+1α, and rj+ajl+1α+bjl+1α≤A+ajlα+akl+1α+bkl+1α can be satisfied, we have the following: first term in (7) ≤ first term in (3), second term in (7) ≤ first term in (3), third term in (7) ≤ first term in (3), first term in (8) ≤ first term in (4), second term in (8) ≤ first term in (4), third term in (8) ≤ first term in (4), first term in (9) ≤ first term in (5), second term in (9) ≤ first term in (5), third term in (9) ≤ first term in (5), fourth term in (9) ≤ first term in (5), fifth term in (9) ≤ first term in (5), and sixth term in (9) ≤ first term in (5).
Hence,C1jS2≤C1kS1, CkS2≤CjS1, CjS2≤CkS1, and CkS2+CjS2≤CjS1+CkS1. Similarly to this case, the other cases can be obtained.


## 4. Branch-and-Bound (B&B) Algorithm

### 4.1. Lower Bound

Letπ=π1,π2 be a schedule in which π1 is the scheduled part, and suppose there are θ jobs in π1, and π2 is the set of so far unscheduled jobs. Let pijθ+1≤j≤n denote the jth smallest normal processing time on machine Mi (i=1 and 2) when jobs in π2 are arranged in an ascending order of the normal processing time on machine Mi. By definition, the completion time of the θ+1th job on machine M2 is
(10)C2θ+1π=maxmaxrθ+1,C1θπ+aθ+1θ+1α,C2θπ+bθ+1θ+1α=maxrθ+1+aθ+1θ+1α+bθ+1θ+1α,C1θπ+aθ+1θ+1α+bθ+1θ+1α,C2θπ+bθ+1θ+1α≥rθ+1aθ+1+bθ+1θ+1α.Similarly,(11)C2θ+jπ≥rθ+j+aθ+j+bθ+jθ+jα,where 1≤j≤n−θ.Hence,(12)Cmax=C2nπ≥rmax+ab¯minnα,where rmax=maxrj∣j∈π2 and ab¯min=minaj+bj∣j∈π2.
(13)∑j=1nCjπ=∑j=1θC2jπ+∑j=θ+1nC2jπ≥∑j=1θC2jπ+∑j=1n−θrθ+j+∑j=1n−θaθ+j+bθ+jθ+jα.Hence,(14)λCmax+1−λ∑j=1nCjπ≥λrmax+ab¯minnα+1−λ×∑j=1θC2jπ+∑j=1n−θrθ+j+∑j=1n−θaθ+j+bθ+jθ+jα=λrmax+ab¯minnα+1−λ∑j=1θC2jπ+∑j=1n−θrθ+j+1−λ∑j=1n−θaθ+j+bθ+jθ+jα.It is noticed that the termλrmax+ab¯minnα+1−λ∑j=1θC2jπ+∑j=1n−θrθ+j is a fixed constant and the term 1−λ∑j=1n−θaθ+j+bθ+jθ+jα is minimized by sequencing the jobs in a nondecreasing order of aj+bj. Consequently, we obtain the first lower bound which is
(15)LB1=λrmax+ab¯minnα+1−λ∑j=1θC2jπ+∑j=1n−θrθ+j+1−λ∑j=1n−θaθ+j+bθ+jθ+jα,where rmax=maxrj∣j∈π2, ab¯min=minaj+bj∣j∈π2, and aθ+1+bθ+1≤aθ+2+bθ+2≤⋯≤an+bn.Similarly,(16)C2θ+jπ≥C1θπ+∑l=1jaθ+lθ+lα+bθ+jθ+jα,where 1≤j≤n−θ.Hence,(17)Cmax≥C1θπ+∑l=1n−θaθ+lθ+lα+bnnα,and the total completion time is
(18)∑j=1nCjπ=∑j=1θC2jπ+∑j=θ+1nC2jπ≥∑j=1θC2jπ+n−θC1θπ+∑j=1n−θ∑l=1jaθ+lθ+lα+∑j=1n−θbθ+jθ+jα.Hence,(19)λCmax+1−λ∑j=1nCjπ≥1−λ∑j=1θC2jπ+λ+1−λn−θC1θπ+λ∑l=1n−θaθ+lθ+lα+bnnα+1−λ∑j=1n−θ∑l=1jaθ+lθ+lα+∑j=1n−θbθ+jθ+jα.Obviously,1−λ∑j=1θC2jπ+λ+1−λn−θC1θπ is a fixed constant, bnnα is minimized by choosing bmin=minbj∣j∈π2 and λ∑l=1n−θaθ+lθ+lα, and 1−λ∑j=1n−θ∑l=1jaθ+lθ+lα+∑j=1n−θbθ+jθ+jα can be minimized by sequencing the jobs in a nondecreasing order of aj and bj, respectively. Consequently, we have
(20)LB2=1−λ∑j=1θC2jπ+λ+1−λn−θC1θπ+λ∑l=1n−θaθ+lθ+lα+bminnα+1−λ∑j=1n−θ∑l=1jaθ+lθ+lα+∑j=1n−θbθ+jθ+jα,where bmin=minbj∣j∈π2 and aθ+1≤aθ+2≤⋯≤anbθ+1≤bθ+2≤⋯≤bn is a nondecreasing order of the normal processing times on M1M2 for the remaining unscheduled jobs (note that al and bl do not necessarily correspond to the same job).Similarly,(21)C2θ+jπ≥C2θπ+∑l=1jbθ+lθ+lα,where 1≤j≤n−θ.Hence,(22)Cmax≥C2θπ+∑l=1n−θbθ+lθ+lα,and
(23)∑j=1nCjπ=∑j=1θC2jπ+∑j=θ+1nC2jπ≥∑j=1θC2jπ+n−θC2θπ+∑j=1n−θ∑l=1jbθ+jθ+lα.Hence,(24)λCmax+1−λ∑j=1nCjπ≥1−λ∑j=1θC2jπ+λ+1−λn−θC2θπ+λ∑l=1n−θbθ+lθ+lα+1−λ∑j=1n−θ∑l=1jbθ+lθ+lα.It is noticed that the term1−λ∑j=1θC2jπ+λ+1−λn−θC2θπ is a fixed constant and the term λ∑l=1n−θbθ+lθ+lα+1−λ∑j=1n−θ∑l=1jbθ+lθ+lα can be minimized by sequencing the jobs in a nondecreasing order of bj. Consequently, we have
(25)LB3=1−λ∑j=1θC2jπ+λ+1−λn−θC2θπ+λ∑l=1n−θbθ+lθ+lα+1−λ∑j=1n−θ∑l=1jbθ+lθ+lα,where bθ+1≤bθ+2≤⋯≤bn is a nondecreasing order of the normal processing times on M2 for the remaining unscheduled jobs.In order to make the lower bound tighter, we choose the maximum valuesLBh, h=1,2,3, as a lower bound for π2, i.e.,
(26)LB=maxLB1,LB2,LB3.


### 4.2. The Algorithm for the Upper Bound

Similarly to Framinan and Leisten [40] (they proposed the Omn4 FL heuristic for solving Fmprmu∑Cj), the FL heuristic can be adjusted for solving F2LE,rjλCmax+1−λ∑j=1nCj. Now, we give the modified FL algorithm.Algorithm 1: FL-based two-phase algorithm (FLTPA).
Phase I
Step 1. Sequence the jobs in nondecreasing order ofrj
Step 2. Sequence the jobs in nondecreasing order ofaj
Step 3. Sequence the jobs in nondecreasing order ofbj.
Step 4. Sequence the jobs in nondecreasing order ofaj+bj
Step 5. Choose the best solution from Steps 1 to 4
Phase II
Step 1. Letπ0 be the schedule obtained from Phase I
Step 2. Setk=2. Select the first two jobs from π0 and select the better between the two possible sequences
Step 3. Incrementk, k=k+1. Select the kth job from π0 and insert it into k possible positions of the best partial sequence obtained so far. Among the k sequences, the best k-job partial sequence is selected based on minimum λCmax+1−λ∑j=1nCj. Next, determine all possible sequences by interchanging jobs in positions i and j of the above partial sequence for all i, j1≤i<k,i<j≤k. Select the best partial sequence among kk−1/2 sequences having minimum λCmax+1−λ∑j=1nCj
Step 4. Ifk=n, then STOP; else, go to Step 3Since Phase I takesOnlogn time and Phase II takes Omn4 time, the overall time complexity of the FLTPA algorithm is Omn4.


### 4.3. The B&B Algorithm

A B&B algorithm that uses the depth first search strategy to solveF2LE,rjλCmax+1−λ∑j=1nCj is proposed. Now the B&B algorithm can be described as follows.Step 1.
Initialization: the FL-based two-phase algorithm (FLTPA) is applied to obtain an upper bound.Step 2.
Fathoming: apply Proposition1 to eliminate the dominated partial sequences from the initial node and their descendants from the tree.Step 3.
Bounding: calculate the lower bound for the node. If the lower bound for an unfathomed partial schedule is larger than the upper bound, eliminate the node and all the nodes following it in the branch. Calculate the objective function valueλCmax+1−λ∑j=1nCj of the completed schedule; if it is less than the upper bound, replace it as the new solution; otherwise, eliminate it.Step 4.
Termination: continue to search all the nodes, and the remaining upper bound is optimal.


### 4.4. The Improved EMO Algorithm

The B&B algorithm outputs the optimal solution, and the LFTPA heuristic outputs a near-optimal solution to the linearly weighted sum ofCmax and ∑j=1nCj. From the perspective of biobjective optimization, evolutionary multiobjective optimization (EMO) algorithm returns at one time a set of nondominated solutions [41–43], i.e., the Pareto front, for the decision-maker’s reference. We propose two strategies to improve the multiobjective memetic algorithm (MOMA) which has successfully solved many difficult numerical optimization problems and outperforms NSGA-II (the nondominated sorting genetic algorithm) and SPEA2 (the improved strength Pareto evolutionary algorithm) for the two-objective and three-objective benchmark flow shop scheduling instances [44].
(1)
Initialization strategy: the initial population consists of one individual generated by the LFTPA heuristic and some others adjusted from that individual by exchanging operators. The number of the LFTPA heuristic-related individuals is equal to half of the population size. The remaining individuals are randomly generated to guarantee population diversity.
(2)
Global search strategy: due to the nondominated sorting and crowd distance calculation mechanisms, NSGA-II has a very good performance to solve many multiobjective problems and is used as global search. Its key operators include selection, crossover, and mutation. We apply the tournament selection operator (see the details in [44]). According to Ishibuchi et al. [45], the two-point crossover and insertion mutation operators are adopted.


## 4.1. Lower Bound

Letπ=π1,π2 be a schedule in which π1 is the scheduled part, and suppose there are θ jobs in π1, and π2 is the set of so far unscheduled jobs. Let pijθ+1≤j≤n denote the jth smallest normal processing time on machine Mi (i=1 and 2) when jobs in π2 are arranged in an ascending order of the normal processing time on machine Mi. By definition, the completion time of the θ+1th job on machine M2 is
(10)C2θ+1π=maxmaxrθ+1,C1θπ+aθ+1θ+1α,C2θπ+bθ+1θ+1α=maxrθ+1+aθ+1θ+1α+bθ+1θ+1α,C1θπ+aθ+1θ+1α+bθ+1θ+1α,C2θπ+bθ+1θ+1α≥rθ+1aθ+1+bθ+1θ+1α.Similarly,(11)C2θ+jπ≥rθ+j+aθ+j+bθ+jθ+jα,where 1≤j≤n−θ.Hence,(12)Cmax=C2nπ≥rmax+ab¯minnα,where rmax=maxrj∣j∈π2 and ab¯min=minaj+bj∣j∈π2.
(13)∑j=1nCjπ=∑j=1θC2jπ+∑j=θ+1nC2jπ≥∑j=1θC2jπ+∑j=1n−θrθ+j+∑j=1n−θaθ+j+bθ+jθ+jα.Hence,(14)λCmax+1−λ∑j=1nCjπ≥λrmax+ab¯minnα+1−λ×∑j=1θC2jπ+∑j=1n−θrθ+j+∑j=1n−θaθ+j+bθ+jθ+jα=λrmax+ab¯minnα+1−λ∑j=1θC2jπ+∑j=1n−θrθ+j+1−λ∑j=1n−θaθ+j+bθ+jθ+jα.It is noticed that the termλrmax+ab¯minnα+1−λ∑j=1θC2jπ+∑j=1n−θrθ+j is a fixed constant and the term 1−λ∑j=1n−θaθ+j+bθ+jθ+jα is minimized by sequencing the jobs in a nondecreasing order of aj+bj. Consequently, we obtain the first lower bound which is
(15)LB1=λrmax+ab¯minnα+1−λ∑j=1θC2jπ+∑j=1n−θrθ+j+1−λ∑j=1n−θaθ+j+bθ+jθ+jα,where rmax=maxrj∣j∈π2, ab¯min=minaj+bj∣j∈π2, and aθ+1+bθ+1≤aθ+2+bθ+2≤⋯≤an+bn.Similarly,(16)C2θ+jπ≥C1θπ+∑l=1jaθ+lθ+lα+bθ+jθ+jα,where 1≤j≤n−θ.Hence,(17)Cmax≥C1θπ+∑l=1n−θaθ+lθ+lα+bnnα,and the total completion time is
(18)∑j=1nCjπ=∑j=1θC2jπ+∑j=θ+1nC2jπ≥∑j=1θC2jπ+n−θC1θπ+∑j=1n−θ∑l=1jaθ+lθ+lα+∑j=1n−θbθ+jθ+jα.Hence,(19)λCmax+1−λ∑j=1nCjπ≥1−λ∑j=1θC2jπ+λ+1−λn−θC1θπ+λ∑l=1n−θaθ+lθ+lα+bnnα+1−λ∑j=1n−θ∑l=1jaθ+lθ+lα+∑j=1n−θbθ+jθ+jα.Obviously,1−λ∑j=1θC2jπ+λ+1−λn−θC1θπ is a fixed constant, bnnα is minimized by choosing bmin=minbj∣j∈π2 and λ∑l=1n−θaθ+lθ+lα, and 1−λ∑j=1n−θ∑l=1jaθ+lθ+lα+∑j=1n−θbθ+jθ+jα can be minimized by sequencing the jobs in a nondecreasing order of aj and bj, respectively. Consequently, we have
(20)LB2=1−λ∑j=1θC2jπ+λ+1−λn−θC1θπ+λ∑l=1n−θaθ+lθ+lα+bminnα+1−λ∑j=1n−θ∑l=1jaθ+lθ+lα+∑j=1n−θbθ+jθ+jα,where bmin=minbj∣j∈π2 and aθ+1≤aθ+2≤⋯≤anbθ+1≤bθ+2≤⋯≤bn is a nondecreasing order of the normal processing times on M1M2 for the remaining unscheduled jobs (note that al and bl do not necessarily correspond to the same job).Similarly,(21)C2θ+jπ≥C2θπ+∑l=1jbθ+lθ+lα,where 1≤j≤n−θ.Hence,(22)Cmax≥C2θπ+∑l=1n−θbθ+lθ+lα,and
(23)∑j=1nCjπ=∑j=1θC2jπ+∑j=θ+1nC2jπ≥∑j=1θC2jπ+n−θC2θπ+∑j=1n−θ∑l=1jbθ+jθ+lα.Hence,(24)λCmax+1−λ∑j=1nCjπ≥1−λ∑j=1θC2jπ+λ+1−λn−θC2θπ+λ∑l=1n−θbθ+lθ+lα+1−λ∑j=1n−θ∑l=1jbθ+lθ+lα.It is noticed that the term1−λ∑j=1θC2jπ+λ+1−λn−θC2θπ is a fixed constant and the term λ∑l=1n−θbθ+lθ+lα+1−λ∑j=1n−θ∑l=1jbθ+lθ+lα can be minimized by sequencing the jobs in a nondecreasing order of bj. Consequently, we have
(25)LB3=1−λ∑j=1θC2jπ+λ+1−λn−θC2θπ+λ∑l=1n−θbθ+lθ+lα+1−λ∑j=1n−θ∑l=1jbθ+lθ+lα,where bθ+1≤bθ+2≤⋯≤bn is a nondecreasing order of the normal processing times on M2 for the remaining unscheduled jobs.In order to make the lower bound tighter, we choose the maximum valuesLBh, h=1,2,3, as a lower bound for π2, i.e.,
(26)LB=maxLB1,LB2,LB3.


## 4.2. The Algorithm for the Upper Bound

Similarly to Framinan and Leisten [40] (they proposed the Omn4 FL heuristic for solving Fmprmu∑Cj), the FL heuristic can be adjusted for solving F2LE,rjλCmax+1−λ∑j=1nCj. Now, we give the modified FL algorithm.Algorithm 1: FL-based two-phase algorithm (FLTPA).
Phase I
Step 1. Sequence the jobs in nondecreasing order ofrj
Step 2. Sequence the jobs in nondecreasing order ofaj
Step 3. Sequence the jobs in nondecreasing order ofbj.
Step 4. Sequence the jobs in nondecreasing order ofaj+bj
Step 5. Choose the best solution from Steps 1 to 4
Phase II
Step 1. Letπ0 be the schedule obtained from Phase I
Step 2. Setk=2. Select the first two jobs from π0 and select the better between the two possible sequences
Step 3. Incrementk, k=k+1. Select the kth job from π0 and insert it into k possible positions of the best partial sequence obtained so far. Among the k sequences, the best k-job partial sequence is selected based on minimum λCmax+1−λ∑j=1nCj. Next, determine all possible sequences by interchanging jobs in positions i and j of the above partial sequence for all i, j1≤i<k,i<j≤k. Select the best partial sequence among kk−1/2 sequences having minimum λCmax+1−λ∑j=1nCj
Step 4. Ifk=n, then STOP; else, go to Step 3Since Phase I takesOnlogn time and Phase II takes Omn4 time, the overall time complexity of the FLTPA algorithm is Omn4.


## 4.3. The B&B Algorithm

A B&B algorithm that uses the depth first search strategy to solveF2LE,rjλCmax+1−λ∑j=1nCj is proposed. Now the B&B algorithm can be described as follows.Step 1.
Initialization: the FL-based two-phase algorithm (FLTPA) is applied to obtain an upper bound.Step 2.
Fathoming: apply Proposition1 to eliminate the dominated partial sequences from the initial node and their descendants from the tree.Step 3.
Bounding: calculate the lower bound for the node. If the lower bound for an unfathomed partial schedule is larger than the upper bound, eliminate the node and all the nodes following it in the branch. Calculate the objective function valueλCmax+1−λ∑j=1nCj of the completed schedule; if it is less than the upper bound, replace it as the new solution; otherwise, eliminate it.Step 4.
Termination: continue to search all the nodes, and the remaining upper bound is optimal.


## 4.4. The Improved EMO Algorithm

The B&B algorithm outputs the optimal solution, and the LFTPA heuristic outputs a near-optimal solution to the linearly weighted sum ofCmax and ∑j=1nCj. From the perspective of biobjective optimization, evolutionary multiobjective optimization (EMO) algorithm returns at one time a set of nondominated solutions [41–43], i.e., the Pareto front, for the decision-maker’s reference. We propose two strategies to improve the multiobjective memetic algorithm (MOMA) which has successfully solved many difficult numerical optimization problems and outperforms NSGA-II (the nondominated sorting genetic algorithm) and SPEA2 (the improved strength Pareto evolutionary algorithm) for the two-objective and three-objective benchmark flow shop scheduling instances [44].
(1)
Initialization strategy: the initial population consists of one individual generated by the LFTPA heuristic and some others adjusted from that individual by exchanging operators. The number of the LFTPA heuristic-related individuals is equal to half of the population size. The remaining individuals are randomly generated to guarantee population diversity.
(2)
Global search strategy: due to the nondominated sorting and crowd distance calculation mechanisms, NSGA-II has a very good performance to solve many multiobjective problems and is used as global search. Its key operators include selection, crossover, and mutation. We apply the tournament selection operator (see the details in [44]). According to Ishibuchi et al. [45], the two-point crossover and insertion mutation operators are adopted.


## 5. Computational Study

Computational experiments were studied to evaluate the effectiveness of the B&B algorithm and the FLTPA heuristic. We coded the B&B algorithm, the FLTPA heuristic, and the improved MOMA in VC++ 6.0 and ran on CPU Intel® Core (TM) i7-4790 3.6 GHz and 8 GB RAM. For the experiments, the parameters are considered as follows:λ=0.5 and the numbers of jobs n: 11, 12, 13, 14, and 15 for small size and 500 and 1000 for large size. The normal processing times of jobs (aj and bj) are randomly generated from the uniform distribution over the integers [1, 100].In order to study the impact of the parameters, the values of the learning effect are taken to be 90% (i.e.,α=log20.9=−0.152), 80% (i.e., α=log20.8=−0.322), and 70% (i.e., α=log20.7=−0.515). The release dates of jobs rj are randomly generated from the uniform distribution over the integers [1, 10,1, 50] and [1, 100].As a consequence, for small-size problems, 45 experimental conditions were examined and 50 replications were randomly generated for each condition. A total of 2250 problems were tested. For large-size problems, 18 experimental conditions were examined and 50 replications were randomly generated for each condition. A total of 900 problems were tested. For the B&B algorithm, the average and maximum number of nodes and the average and the maximum time (in milliseconds) are reported. The percentage error of the solution produced by the FLTPA heuristic is calculated as(27)λCmaxFLTPA+1−λ∑j=1nCjFLTPA−λCmaxOPT+1−λ∑j=1nCjOPTλCmaxOPT+1−λ∑j=1nCjOPT×100%.The results of small-size problems are summarized in Tables1–3. From Tables 1–3, we find that the B&B algorithm can solve a problem of up to 15 jobs in a very short amount of time. The most time-consuming instance took a maximum of 118311 ms for n=15, α=−0.152, and rj~1,10. As for the performance of the FLTPA heuristic, it is seen that the FLTPA heuristic performs very well for the error percentages. The mean error percentage is less than 0.7% for all the tested cases, and the max error percentage is less than 6% for all the tested cases.Table 1
Results of the B&B algorithm and the FLTPA heuristic forrj~1,10.
n
α
CPU time (ms)
Node number
Error
FLTPA
B&B
Mean
Max
Mean
Max
Mean
Max
Mean (%)
Max (%)
11
−0.152
0
0
44.320
172
1265.940
5689
0.131
1.792
−0.322
0.94
16
45.260
280
1283.260
8116
0.120
1.777
−0.515
0.64
16
16.520
187
445.660
5037
0.058
1.151
12
−0.152
0.62
16
151.340
1404
4556.020
44563
0.129
2.105
−0.322
0.3
15
70.540
359
1930.160
9557
0.211
2.973
−0.515
0.62
16
52.420
390
1401.980
9733
0.162
2.043
13
−0.152
0.96
16
385.920
2699
9631.740
76047
0.220
1.798
−0.322
1.26
16
119.180
780
2858.480
17116
0.255
2.622
−0.515
0.64
16
119.800
655
2883.180
15506
0.177
2.497
14
−0.152
2.16
16
1518.840
19,890
36283.359
466540
0.228
2.435
−0.322
1.56
16
543.500
4197
12781.740
96673
0.240
1.913
−0.515
2.18
16
202.180
1872
4837.700
47663
0.147
1.650
15
−0.152
3.12
16
4629.780
118,311
102398.320
2724303
0.198
2.759
−0.322
1.82
16
1299.860
13,869
30514.420
317594
0.157
0.970
−0.515
1.54
16
424.020
5382
10577.960
141059
0.114
0.622Table 2
Results of the B&B algorithm and the FLTPA heuristic forrj~1,50.
n
α
CPU time (ms)
Node number
Error
FLTPA
B&B
Mean
Max
Mean
Max
Mean
Max
Mean
Max
11
−0.152
1.56
16
38.380
219
1120.480
7152
0.301
4.920
−0.322
0
0
22.480
156
623.360
6093
0.117
1.076
−0.515
0.3
15
15.300
47
402.100
1456
0.314
4.642
12
−0.152
0.92
16
110.780
1341
3182.240
40970
0.195
2.423
−0.322
0.94
16
66.140
203
1872.820
6067
0.263
3.295
−0.515
1.26
16
40.860
656
1191.280
21210
0.301
2.267
13
−0.152
1.86
16
274.580
2012
6466.040
43732
0.355
3.760
−0.322
1.6
16
216.180
1186
5390.040
32324
0.375
4.117
−0.515
1.26
16
142.260
1107
3474.940
25696
0.538
5.303
14
−0.152
1.28
16
743.780
5725
17542.561
124227
0.488
2.817
−0.322
3.76
16
272.040
1981
6133.940
43542
0.112
0.942
−0.515
1.58
16
477.660
8361
11843.340
213835
0.480
3.439
15
−0.152
2.84
16
1422.080
10,983
32341.820
272559
0.256
2.603
−0.322
1.88
16
1106.980
12,043
26354.939
285013
0.272
1.663
−0.515
1.84
16
461.180
3854
11786.160
118523
0.207
2.318Table 3
Results of the B&B algorithm and the FLTPA heuristic forrj~1,100.
n
α
CPU time (ms)
Node number
Error
FLTPA
B&B
Mean
Max
Mean
Max
Mean
Max
Mean
Max
11
−0.152
0.62
16
50.860
343
1288.380
11,443
0.634
4.170
−0.322
1.56
16
27.460
94
735.060
2719
0.528
5.771
−0.515
0
0
18.100
125
436.120
3457
0.481
3.671
12
−0.152
1.58
16
108.580
998
2754.880
25142
0.377
3.067
−0.322
0.62
16
46.180
297
1122.220
8368
0.321
1.720
−0.515
1.24
16
50.560
546
1296.280
15767
0.602
4.513
13
−0.152
1.24
16
167.860
920
4312.520
24715
0.365
2.844
−0.322
1.9
16
132.260
1809
3278.320
45866
0.560
3.596
−0.515
1.28
16
94.200
1061
2279.440
26942
0.507
4.397
14
−0.152
1.56
16
433.060
3775
10215.620
97348
0.505
3.298
−0.322
3.46
16
196.220
1170
4658.940
29477
0.550
4.448
−0.515
1.58
16
191.860
1279
4328.420
26003
0.528
4.147
15
−0.152
2.52
16
1491.960
34,819
33631.441
775620
0.586
3.553
−0.322
2.14
16
774.120
8954
17432.561
224454
0.400
2.774
−0.515
3.46
16
561.260
9579
12746.040
211568
0.607
5.383For large-size problems, the termination of the proposed MOMA algorithm is controlled by setting a running time limit of 100 seconds. In order to verify the effectiveness and efficiency, the MOMA is compared with several state-of-the-art EMO algorithms [44], including the hybrid quantum-inspired genetic algorithm (HQGA), the hybrid particle swarm optimization algorithm (HPSO), the hybrid simulated annealing algorithm (HSA), the multiobjective evolutionary algorithm based on decomposition (MOEA/D), and NSGA-II. The parameters of the above algorithms are taken from Liu et al. [44]. The performance of an EMO is reflected by the obtained Pareto front’s proximity and diversity. We consider two metrics for performance measurement. The IGD (inverted generational distance) mainly evaluates the proximity of a Pareto front to the optimal reference set, which consists of nondominated solutions in the grouped Pareto fronts. The smaller the IGD metric is, the better proximity a Pareto front has. And the HV (hypervolume) evaluates the maximal area dominated by a Pareto front, which estimates both the convergence and diversity. The larger the value of HV means the better the integrated performance. As is shown in Figure 1 (Pareto front of a problem instance for n=500, rj~1,50, and α=−0.152), the proposed MOMA clearly dominates the rest of the algorithms. This result is similar for the rest of the problem instances. The dominance relationship is further demonstrated in Tables 4 and 5. MOMA’s smallest IGD values and largest HV values of all instances show that it comprehensively outperforms the other 5 algorithms.Figure 1
Pareto front of a problem instance forn=500, rj~1,50, and α=−0.152.Table 4
The mean IGD value (×106) of 6 algorithms.
n
rj
α
NSGA-II
HPSO
HQGA
HSA
MOEA/D
MOMA
500
[1, 10]
−0.152
6.653
6.770
6.518
6.597
6.569
0.000
−0.322
3.971
4.091
3.866
3.931
4.140
0.000
−0.515
2.197
2.308
2.136
2.179
1.961
0.000
[1, 50]
−0.152
6.713
6.962
6.683
6.755
7.046
0.027
−0.322
3.838
3.995
3.767
3.817
4.248
0.000
−0.515
2.133
2.228
2.098
2.137
2.113
0.000
[1, 100]
−0.152
6.635
6.827
6.506
6.630
6.946
0.004
−0.322
3.837
4.002
3.771
3.796
4.095
0.000
−0.515
2.065
2.142
2.034
2.062
2.128
0.000
1000
[1, 10]
−0.152
2.781
2.799
2.738
2.780
2.223
0.001
−0.322
1.455
1.478
1.450
1.448
0.815
0.000
−0.515
7.305
7.422
7.264
7.279
5.803
0.000
[1, 50]
−0.152
2.707
2.708
2.655
2.689
1.993
0.001
−0.322
1.431
1.454
1.413
1.423
0.968
0.001
−0.515
7.132
7.285
7.071
7.131
5.075
0.000
[1, 100]
−0.152
2.738
2.739
2.688
2.736
1.885
0.000
−0.322
1.428
1.458
1.406
1.422
0.860
0.000
−0.515
6.917
7.035
6.826
6.927
5.706
0.000Table 5
The mean HV values (×1010) of 6 algorithms.
n
rj
α
NSGA-II
HPSO
HQGA
HSA
MOEA/D
MOMA
500
[1, 10]
−0.152
0.619
0.593
0.646
0.632
0.586
2.123
−0.322
1.300
1.187
1.404
1.343
0.985
6.742
−0.515
0.332
0.278
0.365
0.342
0.427
2.195
[1, 50]
−0.152
0.693
0.644
0.697
0.686
0.560
2.187
−0.322
1.562
1.416
1.636
1.586
0.997
7.057
−0.515
0.359
0.311
0.380
0.361
0.306
2.186
[1, 100]
−0.152
0.633
0.599
0.663
0.638
0.543
2.091
−0.322
0.160
0.143
0.166
0.163
0.115
0.714
−0.515
0.390
0.353
0.415
0.392
0.274
2.172
1000
[1, 10]
−0.152
0.298
0.292
0.310
0.298
0.480
1.318
−0.322
0.504
0.475
0.513
0.510
1.721
3.663
−0.515
0.095
0.087
0.097
0.097
0.222
0.970
[1, 50]
−0.152
0.300
0.298
0.314
0.303
0.535
1.320
−0.322
0.516
0.490
0.542
0.530
1.396
3.648
−0.515
0.099
0.089
0.102
0.098
0.286
0.944
[1, 100]
−0.152
0.301
0.299
0.315
0.302
0.587
1.308
−0.322
0.507
0.467
0.536
0.514
1.526
3.581
−0.515
0.102
0.095
0.108
0.101
0.196
0.915Finally, we examine the impact of choice of parameters,n, rj, and α, on algorithm performances. We perform a N-way ANOVA using the commercial software SPSS version 17.0. The impacts of n, rj, and α on the FLTPA heuristic’s error, MOMA’s IGD metric, and MOMA’s HV metric are shown in Tables 6–8, respectively. Throughout the results, when the significance level (the last column in the tables) is under 0.01, the impact is deemed as significant. We observe that rj is significant for the FLTPA heuristic’s performance. The error percentage is much smaller when jobs’ release dates are smaller. This could be explained by smaller release dates that do not tightly restrict the solution space. We further find out that all parameters are not significant for MOMA’s IGD metric, whereas n, α, and n∗α all have a significant impact on MOMA’s HV metric. As n and/or α change, the hypervolume of a Pareto front would change dramatically as large numerical values are involved.Table 6
Tests of between-subject effects to the FLTPA heuristic’s error.
Source
Type III sum of squares
df
Mean square
F
Sig.
Intercept
0.024
1
0.024
434.996
0.000
Error
0.003
49
5.50 × 10−5
rj
0.004
1.738
0.002
64.339
0.000
n
0.000
4
7.15 × 10−5
1.949
0.104
α
9.51 × 10−5
2
4.75 × 10−5
1.035
0.359
rj∗n
0.000
6.094
6.14 × 10−5
1.083
0.373
rj∗α
0.000
3.191
8.99 × 10−5
1.632
0.181
n∗α
0.000
8
3.95 × 10−5
0.777
0.623
rj∗n∗α
0.001
10.777
5.91 × 10−5
0.926
0.513Table 7
Tests of between-subject effects to IGD of MOMA.
Source
Type III sum of squares
df
Mean square
F
Sig.
Intercept
84615121.839
1.000
84615121.839
5.971
0.018
Error
694370982.111
49.000
14170836.370
n
1080878.541
1.000
1080878.541
0.071
0.791
rj
45480148.228
1.445
31473956.059
1.525
0.226
α
130844023.359
1.060
123491834.545
4.492
0.037
rj∗n
29827527.174
1.440
20717814.407
0.967
0.360
rj∗α
10336869.257
1.058
9768265.055
0.342
0.573
n∗α
54777091.926
1.536
35666809.099
0.907
0.385
rj∗n∗α
97890760.041
1.544
63387257.520
1.607
0.211Table 8
Tests of between-subject effects to HV of MOMA.
Source
Type III sum of squares
df
Mean square
F
Sig.
Intercept
1.07913 × 1022
1.000
1.07913 × 1022
96208.156
0.000
Error
5.49614 × 1018
49.000
1.12166 × 1017
n
5.3842 × 1021
1.000
5.3842 × 1021
34294.873
0.000
rj
4.11552 × 1017
1.960
2.09991 × 1017
1.118
0.330
α
8.24917 × 1021
1.214
6.79569 × 1021
33897.141
0.000
rj∗n
2.46247 × 1017
2.000
1.23123 × 1017
0.806
0.450
rj∗α
4.41039 × 1021
1.137
3.87975 × 1021
16984.584
0.000
n∗α
2.48526 × 1017
2.323
1.06983 × 1017
0.366
0.726
rj∗n∗α
3.88625 × 1016
2.376
1.63594 × 1016
0.067
0.957


## 6. Summary and Future Research

In this study, we considered a bicriterion makespan and total completion time minimization flow shop scheduling with a learning effect subject to release dates. We propose a branch-and-bound algorithm and a heuristic algorithm. Numerical studies showed that the FLTPA heuristic was shown to perform well in obtaining near-optimal solutions. Future research may focus on considering the other bicriteria flow shop scheduling problems with a learning effect subject to release dates or studying more efficient heuristic algorithms.



---

*Source: 9149510-2018-10-17.xml*