# A Local Search Algorithm for the Flow Shop Scheduling Problem with Release Dates

Authors: Tao Ren; Meiting Guo; Lin Lin; Yunhui Miao
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

This paper discusses the flow shop scheduling problem to minimize the makespan with release dates. By resequencing the jobs, a modified heuristic algorithm is obtained for handling large-sized problems. Moreover, based on some properties, a local search scheme is provided to improve the heuristic to gain high-quality solution for moderate-sized problems. A sequence-independent lower bound is presented to evaluate the performance of the algorithms. A series of simulation results demonstrate the effectiveness of the proposed algorithms.


---

## Body

## 1. Introduction

In a flow shop scheduling model, each job must be processed on a set of machines in identical order. The goal is to determine the job sequence to optimize a certain predetermined objective function. At any given time, each machine can process at most one job, and each job can be handled by at most one machine. Meanwhile, each job cannot be preempted by the other jobs. Flow shop scheduling problems widely exist in industrial production and mechanical manufacturing. For example, in a steel-making process, molten steel is casted into semifinished slabs by a conticaster; after being heated by the heat furnace, the slabs are rolled into products in rolling mill. Obviously, it is a typical flow shop production model. As most of the problems are strongly NP-hard, it is impossible to obtain the global optimum solution in polynomial time. So the study of flow shop scheduling algorithms is very important for reducing running time and boosting productivity.Since the first scheduling rule was presented by Johnson [1] for the two-machine flow shop problem with objective of makespan (i.e., the maximum completion time) minimization, many works have been conducted on this research area. A comprehensive survey of flow shop makespan problems by 2010 can be found in Potts and Strusevich [2] or Bai and Ren [3]. The up-to-date research works are mentioned as follows. A. Rudek and R. Rudek [4] proved the ordinary NP-hardness for two-machine flow shop makespan problem when job processing times are described by nondecreasing position dependent functions (aging effect) on at least one machine and indicated the strong NP-hardness if job processing times are varying on both machines. Aydilek and Allahverdi [5] presented a polynomial time heuristic algorithm for the two-machine flow shop makespan problem with release dates. For the minimizing makespan in an m-machine flow shop with learning considerations problem, Chung and Tong [6] proposed a dominance theorem and a lower bound to accelerate the branch-and-bound algorithm for seeking the optimal solution. For the criterion of makespan in flow shop model, a high-performing constructive heuristic with an effective tie-breaking strategy was proposed by Ying and Lin [7] to improve the quality of solutions. Similarly, Gupta et al. [8] proposed an alternative heuristic algorithm that is compared with the benchmark, Palmer’s, CDS, and NEH algorithms, to solve n-job and m-machine flow shop scheduling problem with minimizing makespan. For the result of the job-related criterion, Bai [9] presented the asymptotic optimality of the shortest processing time-based algorithms for the flow shop problem to optimize total quadratic completion time with release dates. Bai and Zhang [10] extended the results to a general objective, total k-power completion time (k
≥
3).In this paper, the flow shop scheduling problem for the minimization of makespan with release dates is addressed. Contrary to the static setting in which the jobs are simultaneously available, jobs arrive over time according to their release dates, which more closely approaches practical scheduling environments. Lenstra et al. [11] proved that the two-machine flow shop makespan problem with release dates is strongly NP-hard. It implies that the optimal solution of this problem cannot be found in polynomial time; heuristic algorithm may be more effective to obtain an approximate solution for large-sized problems. Therefore, a new modified GS algorithm (MGS) based on the algorithm of Gonzalez and Sahni [12] is presented for slow shop minimizing makespan with release dates. Then an improved scheme is provided to promote performance of the MGS algorithm. Moreover, a sequence-independent lower bound of the problem is presented. Computational experiments reveal the performances of the MGS algorithm, improved scheme, and lower bound in different size problems.The remainder of this paper is organized as follows. The problem is formulated in Section2, and the MGS algorithm and improved scheme are provided in Sections 3 and 4, respectively. The new lower bound and computational results are given in Section 5. This paper closes with the conclusion in Section 6.


## 2. Problem Statement

In a flow shop problem, a set ofn jobs has to be processed on m different machines in the same order. Job j, j
=
1,2
,
…
,
n, is processed on machines i, i
=
1,2
,
…
,
m, with a nonnegative processing time p
(
i
,
j
) and a release date r
j, which is the earliest time when the job is permitted to process. Each machine can process at most one job and each job can be handled by at most one machine at any given time. The machine processes the jobs in a first come, first served manner. The permutation schedule is considered in this paper, and the intermediate storage between successive machines is unlimited. The completion time of job j, j
=
1,2
,
…
,
n, on machine i,  i
=
1,2
,
…
,
m, is denoted by C
(
i
,
j
). The goal is to determine a job sequence that minimizes the makespan, that is, min
⁡
⁡
{
ma
x
1
≤
j
≤
n
C
(
m
,
j
)
}.


## 3. The Modified GS Algorithm

Gonzalez and Sahni [12] presented the GS algorithm to solve the flow shop makespan problem. Based on its idea, a new heuristic named modified GS (MGS) algorithm is presented to deal with the flow shop makespan problem with release dates. A formal expression of the MGS algorithm is presented as follows.


### 3.1. The MGS Algorithm

Step 1.
Divide them machines into m
-
1 groups.Step 2.
For each machine groupg
=
{
i
-
1
,
i
},  i
=
2
,
3
,
…
,
m, whenever machine i
-
1 becomes idle or new jobs arrive, process the available jobs by Johnson’s rule (i.e., first schedule the jobs with p
g
(
1
,
j
)
<
p
g
(
2
,
j
) in order of nondecreasing p
g
(
1
,
j
) and then schedule the remaining jobs in order of nonincreasing p
g
(
2
,
j
), where p
g
(
k
,
j
) denotes the processing time of job j in group g on machine k,  k
=
1,2); if no job is available, go to Step 3.Step 3.
Wait until a job arrives and go to Step2. If all the jobs have been scheduled, go to Step 4.Step 4.
Terminate the program and calculate the objective valuesZ
g of the schedules. Select the minimum one as the final solution, C
max
⁡
=
min
⁡
1
≤
g
≤
m
-
1
{
Z
g
}.The flowchart of the algorithm is shown in Figure1. An example is proposed to show the execution of the MGS algorithm.Figure 1
The flowchart of the MGS algorithm.Example 1.
A flow shop scheduling problem involves three machines,M
1, M
2, and M
3, and four jobs, J
1, J
2, J
3, and J
4 with release dates. The release dates and processing times of the jobs are listed below. The objective function of the problem is C
max
⁡. Consider(1)
J
1
J
2
J
3
J
4
r
j
0
9
2
7
M
1
2
1
1
3
M
2
5
5
4
4
M
3
6
7
1
7The final sequence of the MGS algorithm is{
J
1
,
J
3
,
J
4
,
J
2
}. And the objective value is C
max
⁡
=
29. The scheduling process is shown in Figure 2.Figure 2
The schedule of the MGS algorithm in Example1.


## 3.1. The MGS Algorithm

Step 1.
Divide them machines into m
-
1 groups.Step 2.
For each machine groupg
=
{
i
-
1
,
i
},  i
=
2
,
3
,
…
,
m, whenever machine i
-
1 becomes idle or new jobs arrive, process the available jobs by Johnson’s rule (i.e., first schedule the jobs with p
g
(
1
,
j
)
<
p
g
(
2
,
j
) in order of nondecreasing p
g
(
1
,
j
) and then schedule the remaining jobs in order of nonincreasing p
g
(
2
,
j
), where p
g
(
k
,
j
) denotes the processing time of job j in group g on machine k,  k
=
1,2); if no job is available, go to Step 3.Step 3.
Wait until a job arrives and go to Step2. If all the jobs have been scheduled, go to Step 4.Step 4.
Terminate the program and calculate the objective valuesZ
g of the schedules. Select the minimum one as the final solution, C
max
⁡
=
min
⁡
1
≤
g
≤
m
-
1
{
Z
g
}.The flowchart of the algorithm is shown in Figure1. An example is proposed to show the execution of the MGS algorithm.Figure 1
The flowchart of the MGS algorithm.Example 1.
A flow shop scheduling problem involves three machines,M
1, M
2, and M
3, and four jobs, J
1, J
2, J
3, and J
4 with release dates. The release dates and processing times of the jobs are listed below. The objective function of the problem is C
max
⁡. Consider(1)
J
1
J
2
J
3
J
4
r
j
0
9
2
7
M
1
2
1
1
3
M
2
5
5
4
4
M
3
6
7
1
7The final sequence of the MGS algorithm is{
J
1
,
J
3
,
J
4
,
J
2
}. And the objective value is C
max
⁡
=
29. The scheduling process is shown in Figure 2.Figure 2
The schedule of the MGS algorithm in Example1.


## 4. The Improved Scheme

To further promote the quality of the solution for medium-scale problems, some properties for two-machine flow shop makespan problem with release dates are presented as follows.Property 1.
For problemF
2
|
r
j
|
C
max
⁡, if two adjacent jobs h and k satisfy (i)
r
h
≤
r
k,
(ii)
p
(
1
,
k
)
≤
p
(
2
,
h
) and p
(
1
,
h
)
≤
p
(
2
,
k
),
(iii)
p
(
1
,
h
)
-
p
(
1
,
k
)
≥
r
k
-
r
h,then the optimal sequence is that job k is scheduled before job h.Proof.
Define the completion times of the two jobs in Sequences{
h
,
k
} and {
k
,
h
} being C
1
(
2
,
j
) and C
2
(
2
,
j
), respectively, j
=
h
,
k. Therefore, for Sequence {
h
,
k
}, (2)
C
1
(
2
,
k
)
=
r
h
+
p
(
1
,
h
)
+
p
(
2
,
h
)
+
p
(
2
,
k
)and, for Sequence {
k
,
h
},(3)
C
2
2
,
h
=
r
k
+
p
1
,
k
+
p
2
,
k
+
p
2
,
h
.By subtraction, it is obtained that(4)
C
1
2
,
k
-
C
2
2
,
h
=
p
1
,
h
-
p
1
,
k
-
r
k
-
r
h
.Note that(5)
p
1
,
h
-
p
1
,
k
≥
r
k
-
r
h
;therefore, (6)
C
1
(
2
,
k
)
-
C
2
(
2
,
h
)
≥
0
.That indicates the optimality of Sequence {
k
,
h
}.Property 2.
For problemF
2
|
r
j
|
C
max
⁡, if two adjacent jobs h and k satisfy(i)
r
h
≤
r
k,
(ii)
p
(
1
,
k
)
≤
p
(
2
,
h
) and p
(
1
,
h
)
≥
p
(
2
,
k
),
(iii)
p
(
2
,
k
)
-
p
(
1
,
k
)
≥
r
k
-
r
h,then the optimal sequence is that job k is scheduled before job h.Proof.
Define the completion times of the two jobs in Sequences{
h
,
k
} and {
k
,
h
} being C
1
(
2
,
j
) and C
2
(
2
,
j
), respectively, j
=
h
,
k. Therefore, for Sequence {
h
,
k
}, (7)
C
1
(
2
,
k
)
=
r
h
+
p
(
1
,
h
)
+
p
(
2
,
h
)
+
p
(
2
,
k
)and, for Sequence {
k
,
h
}, (8)
C
2
2
,
h
=
r
k
+
p
1
,
k
+
p
1
,
h
+
p
2
,
h
.By subtraction, it is obtained that(9)
C
1
2
,
k
-
C
2
2
,
h
=
p
2
,
k
-
p
1
,
k
-
r
k
-
r
h
.Note that(10)
p
2
,
k
-
p
1
,
k
≥
r
k
-
r
h
;therefore,(11)
C
1
(
2
,
k
)
-
C
2
(
2
,
h
)
≥
0
.That indicates the optimality of Sequence {
k
,
h
}.Property 3.
For problemF
2
|
r
j
|
C
max
⁡, if two adjacent jobs h and k satisfy(i)
r
h
≤
r
k,
(ii)
p
(
1
,
k
)
≥
p
(
2
,
h
) and p
(
1
,
h
)
≤
p
(
2
,
k
),
(iii)
p
(
2
,
h
)
-
p
(
1
,
h
)
≥
r
k
-
r
h,then the optimal sequence is that job k is scheduled before job h.Proof.
Define the completion times of the two jobs in Sequences{
h
,
k
} and {
k
,
h
} being C
1
(
2
,
j
) and C
2
(
2
,
j
), respectively, j
=
h
,
k. Therefore, for Sequence {
h
,
k
}, (12)
C
1
(
2
,
k
)
=
r
h
+
p
(
1
,
h
)
+
p
(
1
,
k
)
+
p
(
2
,
k
)and, for Sequence {
k
,
h
}, (13)
C
2
2
,
h
=
r
k
+
p
1
,
k
+
p
2
,
k
+
p
2
,
h
.By subtraction, it is obtained that(14)
C
1
2
,
k
-
C
2
2
,
h
=
p
2
,
h
-
p
1
,
h
-
r
k
-
r
h
.Note that(15)
p
2
,
h
-
p
1
,
h
≥
r
k
-
r
h
;therefore, (16)
C
1
(
2
,
k
)
-
C
2
(
2
,
h
)
≥
0
.That indicates the optimality of Sequence {
k
,
h
}.Property 4.
For problemF
2
|
r
j
|
C
max
⁡, if two adjacent jobs h and k satisfy(i)
r
h
≤
r
k,
(ii)
p
(
1
,
k
)
≥
p
(
2
,
h
) and p
(
1
,
h
)
≥
p
(
2
,
k
),
(iii)
p
(
2
,
k
)
-
p
(
2
,
h
)
≥
r
k
-
r
h,then the optimal sequence is that job k is scheduled before job h.Proof.
Define the completion times of the two jobs in Sequences{
h
,
k
} and {
k
,
h
} being C
1
(
2
,
j
) and C
2
(
2
,
j
), respectively, j
=
h
,
k. Therefore, for Sequence {
h
,
k
}, (17)
C
1
2
,
k
=
r
h
+
p
1
,
h
+
p
1
,
k
+
p
2
,
kand, for Sequence {
k
,
h
}, (18)
C
2
2
,
h
=
r
k
+
p
1
,
k
+
p
1
,
h
+
p
2
,
h
.By subtraction, it is obtained that(19)
C
1
2
,
k
-
C
2
2
,
h
=
p
2
,
k
-
p
2
,
h
-
r
k
-
r
h
.Note that(20)
p
2
,
k
-
p
2
,
h
≥
r
k
-
r
h
;therefore, (21)
C
1
(
2
,
k
)
-
C
2
(
2
,
h
)
≥
0
.That indicates the optimality of Sequence {
k
,
h
}.With these properties, an improved scheme is provided to promote the original solution obtained by the MGS algorithm. In a formal expression of the improved scheme,π
0
,
0
(
x
),  x
=
1,2
,
…
,
n, denotes the job found in the xth position of the original sequence π
0,0, L
(
u
) denotes the number of comparisons that job π
0,0
(
x
) sequentially compares forward with the uth job to a given job in a seed sequence, q denotes the number of comparisons from the current job to the end job, g denotes the number of groups, and Π
k
,
g
(
x
) denotes a sequence set that is generated by exchanging the xth job of π
0,0 with each different job in a seed sequence. The format expression can be summarized as follows.


### 4.1. Improved Scheme

Step 1.
Generate the initial sequenceπ
0,0 with the MGS algorithm and calculate the objective value Z
0,0.Step 2.
Setg
=
1,  x
=
1, and k
=
0.Step 3.
Compare jobπ
0,0
(
x
) forward with the next L
(
u
)
=
h
0 (if h
<
h
0, set L
(
u
)
=
h) jobs in sequence π
k
,
g. If the two jobs a and b satisfy(1)
r
a
≤
r
b,
(2)
one of the following conditions:
(i)
r
b
-
r
a
≤
p
g
(
1
,
a
)
-
p
g
(
1
,
b
),
(ii)
r
b
-
r
a
≤
p
g
(
2
,
b
)
-
p
g
(
1
,
b
),
(iii)
r
b
-
r
a
≤
p
g
(
1
,
a
)
-
p
g
(
2
,
a
),
(iv)
r
b
-
r
a
≤
p
g
(
2
,
b
)
-
p
g
(
2
,
a
),then exchange the jobs, calculate the objective value, and proceed to Step 4.Step 4.
If the objective valueZ
y
,
g obtained in Step 3 is smaller than Z
k
,
g, set  k
:
=
k
+
1 and determine sequence π
k
+
1
,
g, such that Z
k
+
1
,
g
=
min
⁡
{
Z
y
,
g
∣
y
∈
Π
k
,
g
(
x
)
}. If x
≤
n, set x
:
=
x
+
1 and return to Step 3; otherwise, proceed to Step 5.Step 5.
Ifg
≤
m
-
1, set g
:
=
g
+
1 and return to Step 3; otherwise, proceed to Step 6.Step 6.
π
n
,
m
-
1 is the final schedule. Stop.


## 4.1. Improved Scheme

Step 1.
Generate the initial sequenceπ
0,0 with the MGS algorithm and calculate the objective value Z
0,0.Step 2.
Setg
=
1,  x
=
1, and k
=
0.Step 3.
Compare jobπ
0,0
(
x
) forward with the next L
(
u
)
=
h
0 (if h
<
h
0, set L
(
u
)
=
h) jobs in sequence π
k
,
g. If the two jobs a and b satisfy(1)
r
a
≤
r
b,
(2)
one of the following conditions:
(i)
r
b
-
r
a
≤
p
g
(
1
,
a
)
-
p
g
(
1
,
b
),
(ii)
r
b
-
r
a
≤
p
g
(
2
,
b
)
-
p
g
(
1
,
b
),
(iii)
r
b
-
r
a
≤
p
g
(
1
,
a
)
-
p
g
(
2
,
a
),
(iv)
r
b
-
r
a
≤
p
g
(
2
,
b
)
-
p
g
(
2
,
a
),then exchange the jobs, calculate the objective value, and proceed to Step 4.Step 4.
If the objective valueZ
y
,
g obtained in Step 3 is smaller than Z
k
,
g, set  k
:
=
k
+
1 and determine sequence π
k
+
1
,
g, such that Z
k
+
1
,
g
=
min
⁡
{
Z
y
,
g
∣
y
∈
Π
k
,
g
(
x
)
}. If x
≤
n, set x
:
=
x
+
1 and return to Step 3; otherwise, proceed to Step 5.Step 5.
Ifg
≤
m
-
1, set g
:
=
g
+
1 and return to Step 3; otherwise, proceed to Step 6.Step 6.
π
n
,
m
-
1 is the final schedule. Stop.


## 5. Computational Results

In this section, a series of computational experiments are designed to reveal the performances of the proposed algorithm and improved scheme in different size problems. Ten different random tests for each combination of the parameters were, respectively, performed, and the averages are reported. All the algorithms were coded in MATLAB R2012a and implemented on a PC with an Intel Core i7-2600 CPU (3.4 GHz × 4) and 4 GB RAM. The processing times of the jobs were randomly generated from a discrete uniform distribution on[
1,10
] and a discrete normal distribution with expectation 5.5 and variance 1.72.To evaluate the performance of an algorithm for problemF
m
|
r
j
|
C
max
⁡, Bai et al. [13] presented a lower bound (LB
1):(22)
LB
1
=
max
⁡
1
≤
i
≤
m
1
≤
x
≤
n
r
x
+
∑
j
=
x
n
p
(
i
,
j
)
+
∑
k
=
1
i
-
1
p
(
k
,
x
)
+
∑
k
=
i
+
1
m
p
(
k
,
n
)
.However, the value ofLB
1 sometimes may be larger than the optimal value because LB
1 is sequence-dependent. Consider the following example.Example 2.
A two-machine flow shop scheduling problem involves two jobs,J
1 and J
2, with release dates. The release dates and processing times of the jobs are listed below. The objective of the problem is C
max
⁡:(23)
M
1
M
2
r
j
J
1
10
1
0
J
2
1
10
1For sequence {
J
1
,
J
2
}, calculate the value of LB
1:(24)
LB
1
=
r
1
+
p
1,1
+
p
2,1
+
p
2,2
=
0
+
10
+
1
+
10
=
21
.And the optimal schedule of the problem is {
J
2
,
J
1
}. The associated optimal value is(25)
C
max
⁡
OPT
=
r
2
+
p
1,2
+
p
2,2
+
p
2,1
=
1
+
1
+
10
+
1
=
13
.Obviously, LB
1
>
C
max
⁡
(
OPT
).To guarantee that the lower bound value is strictly less than the optimal value, a new lower bound (LB
2) is provided:(26)
LB
2
=
max
⁡
1
≤
i
≤
m
r
x
+
∑
j
=
x
n
p
(
i
,
j
)
+
min
⁡
x
≤
j
≤
n
∑
k
=
1
i
-
1
p
(
k
,
j
)
h
h
h
h
h
h
∑
j
=
x
n
p
i
,
j
+
min
⁡
x
≤
j
≤
n
∑
k
=
1
i
-
1
p
k
,
j
+
min
⁡
x
≤
j
≤
n
∑
k
=
i
+
1
m
p
k
,
j
.Obviously, the last two items inLB
2 guarantee that the lower bound is independent of the job sequence.Theorem 3.
Let the processing timesp
(
i
,
j
), i
=
1,2
,
…
,
m, j
=
1,2
,
…
,
n, be independent random variables having the same continuous distribution with bounded density defined on (
0,1
]. Then, for every j, j
=
1,2
,
…
,
n, with probability one,(27)
lim
n
→
∞
L
B
2
n
=
lim
n
→
∞
C
max
⁡
(
O
P
T
)
n
.Proof.
Without loss of generality,(28)
LB
1
-
LB
2
≤
∑
k
=
1
i
-
1
p
k
,
x
-
min
⁡
x
≤
j
≤
n
∑
k
=
1
i
-
1
p
k
,
j
+
∑
k
=
i
+
1
m
p
k
,
n
-
min
⁡
x
≤
j
≤
n
∑
k
=
i
+
1
m
p
k
,
j
.Dividing n on both sides of (28) and taking limit,(29)
lim
n
→
∞
LB
1
n
=
lim
n
→
∞
LB
2
n
.Bai et al. [13] proved that (30)
lim
n
→
∞
LB
1
n
=
lim
n
→
∞
C
max
⁡
(
OPT
)
n
.Combining (29) and (30) yields the result of Theorem 3.Calculate Example2 with LB
2: (31)
LB
2
=
r
2
+
p
(
1,2
)
+
p
(
2,2
)
+
p
(
2,1
)
=
C
max
⁡
(
OPT
)
.


### 5.1. Tests for the MGS Algorithm

Several numerical tests are conducted to reveal the effectiveness of the MGS algorithm. Three, five, and ten machines and 50, 100, 200, 500, and 1000 jobs are tested, respectively. The release dates are drawn from a discrete uniform distribution on[
1
,
R
t
n
], where n is the number of jobs and R
t is a multiplier with the values of 1, 2, 5, and 8. The DSJF heuristic algorithm presented by Bai and Tang [14] is used as a reference for comparison. First, in Tables 1 and 2, we compare the performance of the MGS algorithm and DSJF heuristic by employing mean relative percentage (
Z
MGS
-
Z
DSJF
)
/
Z
DSJF
×
100%, where Z
MGS is the objective value of the MGS algorithm and Z
DSJF is the objective value of the DSJF heuristic.Table 1
Performance comparison of MGS and DSJF (uniform distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
7.42
3.52
1.80
R
t = 2
6.14
2.17
-
3.21
R
t = 5
-
15.78
-
13.29
-
20.74
R
t = 8
-
24.66
-
19.83
-
22.66
100 jobs
R
t = 1
9.68
8.68
2.34
R
t = 2
4.61
5.07
1.49
R
t = 5
-
21.87
-
23.73
-
15.61
R
t = 8
-
20.01
-
23.69
-
24.37
200 jobs
R
t = 1
12.89
10.13
5.71
R
t = 2
9.11
8.93
6.14
R
t = 5
-
17.62
-
21.26
-
17.40
R
t = 8
-
26.29
-
23.18
-
24.86
500 jobs
R
t = 1
14.82
11.71
10.39
R
t = 2
10.32
11.55
9.10
R
t = 5
-
24.87
-
19.07
-
25.96
R
t = 8
-
18.53
-
21.39
-
28.83
1000 jobs
R
t = 1
15.31
15.31
11.68
R
t = 2
13.03
10.64
10.77
R
t = 5
-
20.82
-
22.72
-
22.22
R
t = 8
-
20.07
-
20.43
-
20.66Table 2
Performance comparison of MGS and DSJF (normal distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
4.29
1.08
-
0.71
R
t = 2
2.48
1.93
-
0.55
R
t = 5
-
19.68
-
19.24
-
14.99
R
t = 8
-
18.13
-
17.06
-
18.33
100 jobs
R
t = 1
5.79
3.62
2.21
R
t = 2
4.40
1.68
1.66
R
t = 5
-
20.74
-
24.99
-
25.53
R
t = 8
-
19.05
-
23.04
-
20.77
200 jobs
R
t = 1
6.73
6.13
3.08
R
t = 2
5.53
4.66
3.61
R
t = 5
-
17.73
-
16.65
-
25.16
R
t = 8
-
13.17
-
18.55
-
19.62
500 jobs
R
t = 1
8.06
6.83
6.15
R
t = 2
6.68
6.57
4.83
R
t = 5
-
21.99
-
24.18
-
19.46
R
t = 8
-
21.09
-
24.58
-
22.19
1000 jobs
R
t = 1
7.91
8.20
7.23
R
t = 2
7.66
7.25
6.14
R
t = 5
-
23.72
-
24.17
-
24.65
R
t = 8
-
17.21
-
23.45
-
20.75In Tables1 and 2, the data show that the performance of the two algorithms is dependent on multiplier R
t. To further determine the dominance of the two algorithms, in Tables 3 and 4, we execute the following experiments with mean relative percentage X
/
20
×
100%, where X denotes the times when the DSJF heuristic dominates the MGS algorithm.Table 3
Dominance tests of DSJF (uniform distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
95
75
70
R
t = 2
85
80
25
R
t = 5
15
5
0
R
t = 8
0
0
0
100 jobs
R
t = 1
100
95
80
R
t = 2
80
90
85
R
t = 5
0
0
15
R
t = 8
0
0
0
200 jobs
R
t = 1
100
95
95
R
t = 2
90
95
95
R
t = 5
25
5
0
R
t = 8
0
0
0
500 jobs
R
t = 1
100
100
100
R
t = 2
90
95
95
R
t = 5
5
15
5
R
t = 8
0
0
0
1000 jobs
R
t = 1
100
100
95
R
t = 2
95
90
90
R
t = 5
5
10
10
R
t = 8
0
0
0Table 4
Dominance tests of DSJF (normal distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
90
60
40
R
t = 2
80
50
40
R
t = 5
0
10
10
R
t = 8
0
0
0
100 jobs
R
t = 1
100
95
95
R
t = 2
100
70
95
R
t = 5
5
5
5
R
t = 8
0
0
0
200 jobs
R
t = 1
100
100
90
R
t = 2
95
95
100
R
t = 5
0
5
0
R
t = 8
0
0
0
500 jobs
R
t = 1
100
100
100
R
t = 2
90
100
95
R
t = 5
10
10
0
R
t = 8
0
0
0
1000 jobs
R
t = 1
95
100
100
R
t = 2
100
95
95
R
t = 5
0
10
5
R
t = 8
0
0
0The results of Tables3 and 4 indicate that the DSJF heuristic completely dominates the MGS algorithm as R
t
=
1 and the opposite case as R
t
=
8. Therefore, in the two cases, obtaining the near-optimal solution with the proper one of the algorithms directly is more practical. To demonstrate the asymptotic optimality of the MGS algorithm, we compare its objective value with the associated value of LB
2. The mean relative percentage (
Z
A
1
-
Z
LB
2
)
/
Z
LB
2  × 100% is employed, where Z
A
1 is the objective value of the MGS algorithm and Z
LB
2 is the objective value of LB
2.The data in Tables5 and 6 indicate the asymptotic optimality of the MGS algorithm. Contrarily, for the fixed number of jobs, ratios enlarge as the number of machines increases from 3 to 10. The cause may be that the larger the number of machines is, the larger the quantity of idle times is, which enlarges the gap between the value of objective and its lower bound.Table 5
Asymptotic performance tests for MGS (uniform distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
5.37
11.74
22.26
R
t = 2
5.55
13.86
20.74
R
t = 5
7.20
13.53
19.77
R
t = 8
1.87
1.76
3.59
100 jobs
R
t = 1
3.61
10.59
17.01
R
t = 2
3.93
9.52
15.40
R
t = 5
3.55
7.01
14.35
R
t = 8
0.90
1.47
2.54
200 jobs
R
t = 1
3.04
5.08
11.27
R
t = 2
4.29
7.94
12.73
R
t = 5
2.75
6.18
10.98
R
t = 8
0.36
0.82
0.88
500 jobs
R
t = 1
1.71
4.33
8.81
R
t = 2
1.26
2.43
10.01
R
t = 5
1.58
3.48
7.39
R
t = 8
0.12
0.36
0.63
1000 jobs
R
t = 1
0.53
2.94
5.59
R
t = 2
3.25
4.69
7.72
R
t = 5
1.12
2.62
5.12
R
t = 8
0.059
0.23
0.30Table 6
Asymptotic performance tests for MGS (normal distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
2.91
7.29
12.67
R
t = 2
3.17
7.23
15.00
R
t = 5
2.85
5.70
9.97
R
t = 8
1.00
1.43
2.98
100 jobs
R
t = 1
2.84
5.22
11.18
R
t = 2
1.91
6.52
10.23
R
t = 5
2.29
4.80
8.20
R
t = 8
0.33
0.55
1.51
200 jobs
R
t = 1
1.52
3.76
7.37
R
t = 2
1.18
4.78
7.59
R
t = 5
1.30
3.01
6.11
R
t = 8
0.27
0.27
1.13
500 jobs
R
t = 1
0.96
2.23
4.57
R
t = 2
1.30
3.67
5.08
R
t = 5
0.89
2.44
4.72
R
t = 8
0.097
0.18
0.48
1000 jobs
R
t = 1
0.69
1.67
3.32
R
t = 2
1.30
1.63
3.26
R
t = 5
0.59
1.65
3.31
R
t = 8
0.032
0.049
0.18


### 5.2. Tests for the Improved Scheme

We compare the effectiveness of the improved scheme (IS) with that of the DSJF heuristic/MGS algorithm. In Tables7 and 8, mean relative percentage (
Z
A
2
-
Z
IS
)
/
Z
IS  × 100% was employed, where Z
A
2 is the objective value of the DSJF heuristic/MGS algorithm and Z
IS is the objective value of IS. Three, five, and ten machines with 20 and 50 jobs are tested, respectively. The value of multiplier R
t is 0.1, 0.04 (for 50 jobs) and 0.05 (for 20 jobs). The processing times of the jobs were randomly generated from a discrete uniform distribution on [
1,10
].Table 7
Comparing IS with the DSJF %.
n = 20
n = 50
m = 3
m = 5
m = 10
m = 3
m = 5
m = 10
R
t = 0.1
3.79
7.08
6.96
R
t = 0.1
0.98
3.64
4.68
R
t = 0.05
5.95
7.66
4.40
R
t = 0.04
2.35
3.97
3.42Table 8
Comparing IS2 with the MGS %.
n = 20
n = 50
m = 3
m = 5
m = 10
m = 3
m = 5
m = 10
R
t = 0.1
5.95
4.54
3.98
R
t = 0.1
2.01
2.80
3.61
R
t = 0.05
5.47
7.10
4.56
R
t = 0.04
2.73
3.63
4.34The results indicate that the improved scheme promotes the performance of the algorithms effectively for moderate-sized problems. As the problem scale and the range of release dates continue to enlarge, the improvement is weakened and the running time lengthens. Therefore, obtaining the near-optimal solution with the MGS algorithm directly for large-scale problems is more practical.


## 5.1. Tests for the MGS Algorithm

Several numerical tests are conducted to reveal the effectiveness of the MGS algorithm. Three, five, and ten machines and 50, 100, 200, 500, and 1000 jobs are tested, respectively. The release dates are drawn from a discrete uniform distribution on[
1
,
R
t
n
], where n is the number of jobs and R
t is a multiplier with the values of 1, 2, 5, and 8. The DSJF heuristic algorithm presented by Bai and Tang [14] is used as a reference for comparison. First, in Tables 1 and 2, we compare the performance of the MGS algorithm and DSJF heuristic by employing mean relative percentage (
Z
MGS
-
Z
DSJF
)
/
Z
DSJF
×
100%, where Z
MGS is the objective value of the MGS algorithm and Z
DSJF is the objective value of the DSJF heuristic.Table 1
Performance comparison of MGS and DSJF (uniform distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
7.42
3.52
1.80
R
t = 2
6.14
2.17
-
3.21
R
t = 5
-
15.78
-
13.29
-
20.74
R
t = 8
-
24.66
-
19.83
-
22.66
100 jobs
R
t = 1
9.68
8.68
2.34
R
t = 2
4.61
5.07
1.49
R
t = 5
-
21.87
-
23.73
-
15.61
R
t = 8
-
20.01
-
23.69
-
24.37
200 jobs
R
t = 1
12.89
10.13
5.71
R
t = 2
9.11
8.93
6.14
R
t = 5
-
17.62
-
21.26
-
17.40
R
t = 8
-
26.29
-
23.18
-
24.86
500 jobs
R
t = 1
14.82
11.71
10.39
R
t = 2
10.32
11.55
9.10
R
t = 5
-
24.87
-
19.07
-
25.96
R
t = 8
-
18.53
-
21.39
-
28.83
1000 jobs
R
t = 1
15.31
15.31
11.68
R
t = 2
13.03
10.64
10.77
R
t = 5
-
20.82
-
22.72
-
22.22
R
t = 8
-
20.07
-
20.43
-
20.66Table 2
Performance comparison of MGS and DSJF (normal distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
4.29
1.08
-
0.71
R
t = 2
2.48
1.93
-
0.55
R
t = 5
-
19.68
-
19.24
-
14.99
R
t = 8
-
18.13
-
17.06
-
18.33
100 jobs
R
t = 1
5.79
3.62
2.21
R
t = 2
4.40
1.68
1.66
R
t = 5
-
20.74
-
24.99
-
25.53
R
t = 8
-
19.05
-
23.04
-
20.77
200 jobs
R
t = 1
6.73
6.13
3.08
R
t = 2
5.53
4.66
3.61
R
t = 5
-
17.73
-
16.65
-
25.16
R
t = 8
-
13.17
-
18.55
-
19.62
500 jobs
R
t = 1
8.06
6.83
6.15
R
t = 2
6.68
6.57
4.83
R
t = 5
-
21.99
-
24.18
-
19.46
R
t = 8
-
21.09
-
24.58
-
22.19
1000 jobs
R
t = 1
7.91
8.20
7.23
R
t = 2
7.66
7.25
6.14
R
t = 5
-
23.72
-
24.17
-
24.65
R
t = 8
-
17.21
-
23.45
-
20.75In Tables1 and 2, the data show that the performance of the two algorithms is dependent on multiplier R
t. To further determine the dominance of the two algorithms, in Tables 3 and 4, we execute the following experiments with mean relative percentage X
/
20
×
100%, where X denotes the times when the DSJF heuristic dominates the MGS algorithm.Table 3
Dominance tests of DSJF (uniform distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
95
75
70
R
t = 2
85
80
25
R
t = 5
15
5
0
R
t = 8
0
0
0
100 jobs
R
t = 1
100
95
80
R
t = 2
80
90
85
R
t = 5
0
0
15
R
t = 8
0
0
0
200 jobs
R
t = 1
100
95
95
R
t = 2
90
95
95
R
t = 5
25
5
0
R
t = 8
0
0
0
500 jobs
R
t = 1
100
100
100
R
t = 2
90
95
95
R
t = 5
5
15
5
R
t = 8
0
0
0
1000 jobs
R
t = 1
100
100
95
R
t = 2
95
90
90
R
t = 5
5
10
10
R
t = 8
0
0
0Table 4
Dominance tests of DSJF (normal distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
90
60
40
R
t = 2
80
50
40
R
t = 5
0
10
10
R
t = 8
0
0
0
100 jobs
R
t = 1
100
95
95
R
t = 2
100
70
95
R
t = 5
5
5
5
R
t = 8
0
0
0
200 jobs
R
t = 1
100
100
90
R
t = 2
95
95
100
R
t = 5
0
5
0
R
t = 8
0
0
0
500 jobs
R
t = 1
100
100
100
R
t = 2
90
100
95
R
t = 5
10
10
0
R
t = 8
0
0
0
1000 jobs
R
t = 1
95
100
100
R
t = 2
100
95
95
R
t = 5
0
10
5
R
t = 8
0
0
0The results of Tables3 and 4 indicate that the DSJF heuristic completely dominates the MGS algorithm as R
t
=
1 and the opposite case as R
t
=
8. Therefore, in the two cases, obtaining the near-optimal solution with the proper one of the algorithms directly is more practical. To demonstrate the asymptotic optimality of the MGS algorithm, we compare its objective value with the associated value of LB
2. The mean relative percentage (
Z
A
1
-
Z
LB
2
)
/
Z
LB
2  × 100% is employed, where Z
A
1 is the objective value of the MGS algorithm and Z
LB
2 is the objective value of LB
2.The data in Tables5 and 6 indicate the asymptotic optimality of the MGS algorithm. Contrarily, for the fixed number of jobs, ratios enlarge as the number of machines increases from 3 to 10. The cause may be that the larger the number of machines is, the larger the quantity of idle times is, which enlarges the gap between the value of objective and its lower bound.Table 5
Asymptotic performance tests for MGS (uniform distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
5.37
11.74
22.26
R
t = 2
5.55
13.86
20.74
R
t = 5
7.20
13.53
19.77
R
t = 8
1.87
1.76
3.59
100 jobs
R
t = 1
3.61
10.59
17.01
R
t = 2
3.93
9.52
15.40
R
t = 5
3.55
7.01
14.35
R
t = 8
0.90
1.47
2.54
200 jobs
R
t = 1
3.04
5.08
11.27
R
t = 2
4.29
7.94
12.73
R
t = 5
2.75
6.18
10.98
R
t = 8
0.36
0.82
0.88
500 jobs
R
t = 1
1.71
4.33
8.81
R
t = 2
1.26
2.43
10.01
R
t = 5
1.58
3.48
7.39
R
t = 8
0.12
0.36
0.63
1000 jobs
R
t = 1
0.53
2.94
5.59
R
t = 2
3.25
4.69
7.72
R
t = 5
1.12
2.62
5.12
R
t = 8
0.059
0.23
0.30Table 6
Asymptotic performance tests for MGS (normal distribution %).
m = 3
m = 5
m = 10
50 jobs
R
t = 1
2.91
7.29
12.67
R
t = 2
3.17
7.23
15.00
R
t = 5
2.85
5.70
9.97
R
t = 8
1.00
1.43
2.98
100 jobs
R
t = 1
2.84
5.22
11.18
R
t = 2
1.91
6.52
10.23
R
t = 5
2.29
4.80
8.20
R
t = 8
0.33
0.55
1.51
200 jobs
R
t = 1
1.52
3.76
7.37
R
t = 2
1.18
4.78
7.59
R
t = 5
1.30
3.01
6.11
R
t = 8
0.27
0.27
1.13
500 jobs
R
t = 1
0.96
2.23
4.57
R
t = 2
1.30
3.67
5.08
R
t = 5
0.89
2.44
4.72
R
t = 8
0.097
0.18
0.48
1000 jobs
R
t = 1
0.69
1.67
3.32
R
t = 2
1.30
1.63
3.26
R
t = 5
0.59
1.65
3.31
R
t = 8
0.032
0.049
0.18


## 5.2. Tests for the Improved Scheme

We compare the effectiveness of the improved scheme (IS) with that of the DSJF heuristic/MGS algorithm. In Tables7 and 8, mean relative percentage (
Z
A
2
-
Z
IS
)
/
Z
IS  × 100% was employed, where Z
A
2 is the objective value of the DSJF heuristic/MGS algorithm and Z
IS is the objective value of IS. Three, five, and ten machines with 20 and 50 jobs are tested, respectively. The value of multiplier R
t is 0.1, 0.04 (for 50 jobs) and 0.05 (for 20 jobs). The processing times of the jobs were randomly generated from a discrete uniform distribution on [
1,10
].Table 7
Comparing IS with the DSJF %.
n = 20
n = 50
m = 3
m = 5
m = 10
m = 3
m = 5
m = 10
R
t = 0.1
3.79
7.08
6.96
R
t = 0.1
0.98
3.64
4.68
R
t = 0.05
5.95
7.66
4.40
R
t = 0.04
2.35
3.97
3.42Table 8
Comparing IS2 with the MGS %.
n = 20
n = 50
m = 3
m = 5
m = 10
m = 3
m = 5
m = 10
R
t = 0.1
5.95
4.54
3.98
R
t = 0.1
2.01
2.80
3.61
R
t = 0.05
5.47
7.10
4.56
R
t = 0.04
2.73
3.63
4.34The results indicate that the improved scheme promotes the performance of the algorithms effectively for moderate-sized problems. As the problem scale and the range of release dates continue to enlarge, the improvement is weakened and the running time lengthens. Therefore, obtaining the near-optimal solution with the MGS algorithm directly for large-scale problems is more practical.


## 6. Conclusions

This paper presented a modified heuristic algorithm, that is, the MGS algorithm, for the flow shop makespan problem with release dates. And an improved scheme was introduced to improve the quality of the original solution. To evaluate the algorithms numerically, a new lower bound that is sequence independent was provided for the problem. The computational results demonstrate the dominance of the MGS algorithm and the effectiveness of the improved scheme.



---

*Source: 320140-2015-03-19.xml*