# A Hybrid IP/GA Approach to the Parallel Production Lines Scheduling Problem

Authors: Huizhi Ren; Shenshen Sun
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

A special parallel production lines scheduling problem is studied in this paper. Considering the time window and technical constraints, a mixed integer linear programming (MILP) model is formulated for the problem. A few valid inequalities are deduced and a hybrid mixed integer linear programming/constraint programming (MILP/CP) decomposition strategy is introduced. Based on them, a hybrid integer programming/genetic algorithm (IP/GA) approach is proposed to solve the problem. At last, the numerical experiments demonstrate that the proposed solution approach is effective and efficient.


---

## Body

## 1. Introduction

Electric wire and cables are usually continuously produced and can be in coil packaging (or circle packing) [1]. In the large cable manufacturing enterprise, there is usually more than one continuous cable production line and cables can be produced on most of the lines. For the same cable product, the different lines always take different production cost and different production time. It raises a parallel scheduling problem over these production lines. The objective is to minimize the total production cost. The due time of each cable product and technological requirements of each cable production line need to be satisfied. The problem can be viewed as a parallel machine scheduling problem with complicated constraints of continuous cable production lines. It includes two kinds of scheduling decisions: a job allocation decision over multiple machines (cable production lines) and a job sequencing decision on each machine (cable production line).The parallel machine scheduling problem is a common combinatorial optimization problem and there have been a lot of related researches published. In the 1970s, a series of researches have ever focused on problem complexity analysis, as shown in Table1, where the symbol description system in Graham et al. [2] was adopted and the identical parallel machine problems with various objectives in literature [3–6] were proven to be NP-hard while the heterogeneous parallel machine scheduling problem with total complete times was provided an algorithm with O
n
log
⁡
n complexity. Later, Dessouky et al. [7] also proved that heterogeneous parallel machine problems, including Q
/
r
i, p
i
=
1
/
C
m
a
x, Q
/
p
i
=
1
/
∑
ϖ
i
c
i, Q
/
p
i
=
1
/
L
m
a
x, and Q
/
p
i
=
1
/
∑
T
i, have O
n
log
⁡
n complexity. Various kinds of algorithms have been developed to solve the parallel machine scheduling problems of NP-hardness, including the intelligent optimization algorithms, such as Tabu Search [8–10], Simulated Annealing [11], and genetic algorithm [12, 13] and optimization algorithms, such as Branch and Bound [14–17], Dynamic Programming [18–20], and Column Generation [21–23].Table 1
The complexity research of various parallel machine problems in the 1970s.
Literature
Year
Problem variants
Complexity
Karp [3]
1972
P
2
/
/
C
m
a
x
NP-hard
Bruno et al. [4]
1974
P
2
/
/
∑
ϖ
i
c
i
NP-hard
Lenstra [5]
1977
I
/
r
i
/
∑
c
i
NP-hard
Garey and Johnson [6]
1978
P
/
/
C
m
a
x
NP-complete
Horowitz and Sahni [29]
1976
Q
/
/
∑
c
i
O
n
log
⁡
nIt is worth noting that a hybrid mixed integer linear programming/constraint programming (MILP/CP) approach has been proposed to solve a class of parallel machine scheduling problems (Harjunkoski et al. [24], Jain and Grossmann [25], Hooker [26], and Maravelias and Grossmann [27]) which are similar to the problem studied in this paper. The approach divides the parallel scheduling problem into a job allocation master problem and a series of single machine scheduling subproblems. It applies the mixed integer linear programming (MILP) to solve the former master problem and constraint programming (CP) to the latter subproblems. Typically, the process needs to be iterated because the CP always encounters an infeasibility in solving the single machine scheduling subproblem. The hybrid MILP/CP approach can obtain an optimal solution after a number of iterations. Its limitation is the computational inefficiency. It can deal with only small-scale problems in an acceptable CPU time, although some improvements have been developed [27, 28] to reduce the number of iterations.The hybrid MILP/CP approach can also be applied to the parallel cable production line scheduling problem after revising its CP model according to the particular scheduling requirement of the cable production line. The hybrid MILP/CP approach, though dealing with only some small-scale problems, motivates us to combine the integer programming (IP) and genetic algorithm (GA) together to develop the hybrid IP/GA approach to the parallel cable production lines scheduling problem. In the hybrid IP/GA approach, the traditional exact optimization method (IP) and the intelligent optimization method (GA) can complement each other to strengthen the solving process, similar to what the MILP and CP perform in the hybrid MILP/CP approach. This is our main contribution in the paper.The outline of this paper is as follows. Section2 describes constraints of the problem and provides its integer programming model. In Section 3, a few valid inequalities are deduced and a hybrid MILP/CP model is presented. In Section 4, a hybrid IP/GA approach is proposed to resolve the problem. Section 5 tests the proposed solution approach. Section 6 concludes the paper.


## 2. Problem Description and Mathematical Model

### 2.1. The Problem Description

In the cable manufacturing enterprise of our own interest, cables are produced coil by coil through the equipped production lines and thus a cable coil, hereinafter referred to as the “cable,” will be viewed as a job to be scheduled. The cable requires different processing time and cost on different production lines because the lines are configured with different product preferences. The processing time, including the setup time, is assumed to be independent of processing sequence and thus the setup time will be ignored (or included in the processing time) in this problem. The scheduling objective is to minimize the total processing cost.There are always some cables requiring more cable rubber and the production line needs to provide more heated rubber for these cables, which will form a technical constraint for the scheduling problem. To facilitate the problem description, the cables that need more rubber will be classified into “type B” and others into “type A.” The cables of type B cannot be processed consecutively in a production line and several cables of type A are needed between processing two successive cables of type B; otherwise the cable rubber quality could be impaired.Another constraint comes from the time window of each cable. Since the cable cores are handed off from the upstream process, each coil has a release time in the cable production line. In addition, most cables have the contracted delivery time. These two times constitute the time window constraint.A cable production scheduling problem instance is illustrated in Figure1. It needs to schedule seven cables (or jobs, labeled as J
1
,
J
2
,
…
,
J
7 in Figure 1) over two production lines (labeled as L
1 and L
2). Cables J
1 and J
2 belong to type B and others belong to type A. As shown in the top part of Figure 1, each cable has its own time window r
i
,
d
i and two different processing times, p
1
1 and p
1
2, corresponding to the two production lines, respectively. A schedule arrangement is shown in the bottom part of Figure 1. For the time window constraint and technical requirement (forbidding cables J
1 and J
2 to be processed continuously on line L
1 or L
2), no production line processes cable J
2 and thus the schedule is infeasible.Figure 1
An illustration of the cable parallel production lines scheduling problem.


### 2.2. The Mixed Integer Linear Programming Model

To define and formulate the problem explicitly, the following notations need to be introduced to represent all coils, production lines, coil type parameters, and so on:N: set of cables and N
=
0
,
1
,
2
,
…
,
n, where 0 is a dummy cable.
M: set of cable production lines, M
=
1
,
2
,
…
,
m.
B: set of cables belonging to type B.
A: set of cables belonging to type A, A
∩
B
=
∅, A
∪
B
=
N.
Q: number of necessary cables of type A between successive cables of type B in a production line.
r
i: release time of cable i,  i
∈
N.
d
i: due time of cable i,  i
∈
N.
c
i
j: production cost of cable i on line j.
p
i
j: production time of cable i produced on line j.
Z: a sufficiently large constant.To represent cable assignment decisions over the production lines and scheduling decisions on each line, we introduce the following decision variables:y
i
j
=

0
,
i
f
c
a
b
l
e
i
i
s
p
r
o
d
u
c
e
d
o
n
l
i
n
e
j
;
1
,
o
t
h
e
r
w
i
s
e
.
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
x
i
i
′
j
=

0
,
i
f
c
a
b
l
e
i
′
i
s
p
r
o
d
u
c
e
d
i
m
m
e
d
i
a
t
e
l
y
a
f
t
e
r
i
o
n
l
i
n
e
j
;
1
,
o
t
h
e
r
w
i
s
e
.
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
S
i: start time of producing cable i,  i
∈
N.
C
i: complete time of cable i,  i
∈
N.The following auxiliary variables are also introduced to represent the number of consecutive cables of type A on a production line, which is necessary to represent the technological requirement of production lines:a
i: number of consecutive cables of type A before cable i,  i
∈
A.Based on the above notations, the parallel cable production lines scheduling problem can be formulated as the following mixed integer linear programming model:(1)
M
i
n
∑
i
∈
N
∖
0
∑
j
∈
M
c
i
j
y
i
j
(2)
s
.
t
.
∑
j
∈
M
y
i
j
=
1
,
i
∈
N
∖
0
(3)
∑
i
∈
N
,
i
≠
i
′
x
i
i
′
j
=
y
i
′
j
,
i
′
∈
N
∖
0
,
j
∈
M
(4)
∑
i
′
∈
N
,
i
′
≠
i
x
i
i
′
j
=
y
i
j
,
i
∈
N
∖
0
,
j
∈
M
(5)
∑
i
′
∈
N
∖
0
x
0
i
′
j
≤
1
,
j
∈
M
(6)
a
i
′
≤
Z
1
-
∑
j
∈
M
∑
i
∈
B
x
i
i
′
j
,
i
′
∈
A
(7)
a
i
′
≤
a
i
+
1
+
Z
1
-
∑
j
∈
M
x
i
i
′
j
,
i
,
i
′
∈
A
(8)
∑
j
∈
M
x
i
i
′
j
≤
0
,
i
,
i
′
∈
B
(9)
a
i
≥
Q
-
1
-
Z
1
-
∑
j
∈
M
x
i
i
′
j
,
i
∈
A
,
i
′
∈
B
(10)
S
i
≥
r
i
,
i
∈
N
∖
0
(11)
C
i
≤
d
i
,
i
∈
N
∖
0
(12)
S
i
′
-
C
i
≥
Z
∑
j
∈
M
x
i
i
′
j
-
1
,
i
,
i
′
∈
N
∖
0
(13)
C
i
-
S
i
≥
∑
j
∈
M
p
i
j
y
i
j
,
i
∈
N
∖
0
(14)
x
i
i
′
j
,
y
i
j
∈
0,1
,
i
,
i
′
∈
N
,
j
∈
M
(15)
S
i
,
C
i
≥
0
,
i
∈
N
(16)
a
i
∈
0,1
,
2
,
…
,
n
,
i
∈
A
.The objective function (1) of the model is to minimize the total production cost of the adopted cable production tasks assignments. Constraints (2)–(5) state the logic relations among the decision variables. Constraint (2) ensures that a production line is assigned to each cable. Constraints (3) and (4) ensure that each cable has one preceding cable and one succeeding cable, respectively. Constraint (5) states that each line has at most one starting cable, which implies that there are at most m available lines.Constraints (6)–(9) aim to the technical requirement that there are enough cables of type A between any two successive cables of type B on the same line. Among them, constraint (6) states that a
i
′
≤
0 if its preceding cable belongs to type B. Constraint (7) calculates the number of consecutive cables of type A. Constraint (8) prevents the consecutive cables of type B while constraint (9) guarantees no less than Q cables of type A between any two cables on the same line.Constraints (10) and (11) are the time window constraints. Constraint (12) ensures the cable production sequence on the same line and constraint (13) provides enough production time for each assignment. Constraints (14)–(16) provide value ranges for the variables.


## 2.1. The Problem Description

In the cable manufacturing enterprise of our own interest, cables are produced coil by coil through the equipped production lines and thus a cable coil, hereinafter referred to as the “cable,” will be viewed as a job to be scheduled. The cable requires different processing time and cost on different production lines because the lines are configured with different product preferences. The processing time, including the setup time, is assumed to be independent of processing sequence and thus the setup time will be ignored (or included in the processing time) in this problem. The scheduling objective is to minimize the total processing cost.There are always some cables requiring more cable rubber and the production line needs to provide more heated rubber for these cables, which will form a technical constraint for the scheduling problem. To facilitate the problem description, the cables that need more rubber will be classified into “type B” and others into “type A.” The cables of type B cannot be processed consecutively in a production line and several cables of type A are needed between processing two successive cables of type B; otherwise the cable rubber quality could be impaired.Another constraint comes from the time window of each cable. Since the cable cores are handed off from the upstream process, each coil has a release time in the cable production line. In addition, most cables have the contracted delivery time. These two times constitute the time window constraint.A cable production scheduling problem instance is illustrated in Figure1. It needs to schedule seven cables (or jobs, labeled as J
1
,
J
2
,
…
,
J
7 in Figure 1) over two production lines (labeled as L
1 and L
2). Cables J
1 and J
2 belong to type B and others belong to type A. As shown in the top part of Figure 1, each cable has its own time window r
i
,
d
i and two different processing times, p
1
1 and p
1
2, corresponding to the two production lines, respectively. A schedule arrangement is shown in the bottom part of Figure 1. For the time window constraint and technical requirement (forbidding cables J
1 and J
2 to be processed continuously on line L
1 or L
2), no production line processes cable J
2 and thus the schedule is infeasible.Figure 1
An illustration of the cable parallel production lines scheduling problem.


## 2.2. The Mixed Integer Linear Programming Model

To define and formulate the problem explicitly, the following notations need to be introduced to represent all coils, production lines, coil type parameters, and so on:N: set of cables and N
=
0
,
1
,
2
,
…
,
n, where 0 is a dummy cable.
M: set of cable production lines, M
=
1
,
2
,
…
,
m.
B: set of cables belonging to type B.
A: set of cables belonging to type A, A
∩
B
=
∅, A
∪
B
=
N.
Q: number of necessary cables of type A between successive cables of type B in a production line.
r
i: release time of cable i,  i
∈
N.
d
i: due time of cable i,  i
∈
N.
c
i
j: production cost of cable i on line j.
p
i
j: production time of cable i produced on line j.
Z: a sufficiently large constant.To represent cable assignment decisions over the production lines and scheduling decisions on each line, we introduce the following decision variables:y
i
j
=

0
,
i
f
c
a
b
l
e
i
i
s
p
r
o
d
u
c
e
d
o
n
l
i
n
e
j
;
1
,
o
t
h
e
r
w
i
s
e
.
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
x
i
i
′
j
=

0
,
i
f
c
a
b
l
e
i
′
i
s
p
r
o
d
u
c
e
d
i
m
m
e
d
i
a
t
e
l
y
a
f
t
e
r
i
o
n
l
i
n
e
j
;
1
,
o
t
h
e
r
w
i
s
e
.
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
S
i: start time of producing cable i,  i
∈
N.
C
i: complete time of cable i,  i
∈
N.The following auxiliary variables are also introduced to represent the number of consecutive cables of type A on a production line, which is necessary to represent the technological requirement of production lines:a
i: number of consecutive cables of type A before cable i,  i
∈
A.Based on the above notations, the parallel cable production lines scheduling problem can be formulated as the following mixed integer linear programming model:(1)
M
i
n
∑
i
∈
N
∖
0
∑
j
∈
M
c
i
j
y
i
j
(2)
s
.
t
.
∑
j
∈
M
y
i
j
=
1
,
i
∈
N
∖
0
(3)
∑
i
∈
N
,
i
≠
i
′
x
i
i
′
j
=
y
i
′
j
,
i
′
∈
N
∖
0
,
j
∈
M
(4)
∑
i
′
∈
N
,
i
′
≠
i
x
i
i
′
j
=
y
i
j
,
i
∈
N
∖
0
,
j
∈
M
(5)
∑
i
′
∈
N
∖
0
x
0
i
′
j
≤
1
,
j
∈
M
(6)
a
i
′
≤
Z
1
-
∑
j
∈
M
∑
i
∈
B
x
i
i
′
j
,
i
′
∈
A
(7)
a
i
′
≤
a
i
+
1
+
Z
1
-
∑
j
∈
M
x
i
i
′
j
,
i
,
i
′
∈
A
(8)
∑
j
∈
M
x
i
i
′
j
≤
0
,
i
,
i
′
∈
B
(9)
a
i
≥
Q
-
1
-
Z
1
-
∑
j
∈
M
x
i
i
′
j
,
i
∈
A
,
i
′
∈
B
(10)
S
i
≥
r
i
,
i
∈
N
∖
0
(11)
C
i
≤
d
i
,
i
∈
N
∖
0
(12)
S
i
′
-
C
i
≥
Z
∑
j
∈
M
x
i
i
′
j
-
1
,
i
,
i
′
∈
N
∖
0
(13)
C
i
-
S
i
≥
∑
j
∈
M
p
i
j
y
i
j
,
i
∈
N
∖
0
(14)
x
i
i
′
j
,
y
i
j
∈
0,1
,
i
,
i
′
∈
N
,
j
∈
M
(15)
S
i
,
C
i
≥
0
,
i
∈
N
(16)
a
i
∈
0,1
,
2
,
…
,
n
,
i
∈
A
.The objective function (1) of the model is to minimize the total production cost of the adopted cable production tasks assignments. Constraints (2)–(5) state the logic relations among the decision variables. Constraint (2) ensures that a production line is assigned to each cable. Constraints (3) and (4) ensure that each cable has one preceding cable and one succeeding cable, respectively. Constraint (5) states that each line has at most one starting cable, which implies that there are at most m available lines.Constraints (6)–(9) aim to the technical requirement that there are enough cables of type A between any two successive cables of type B on the same line. Among them, constraint (6) states that a
i
′
≤
0 if its preceding cable belongs to type B. Constraint (7) calculates the number of consecutive cables of type A. Constraint (8) prevents the consecutive cables of type B while constraint (9) guarantees no less than Q cables of type A between any two cables on the same line.Constraints (10) and (11) are the time window constraints. Constraint (12) ensures the cable production sequence on the same line and constraint (13) provides enough production time for each assignment. Constraints (14)–(16) provide value ranges for the variables.


## 3. Valid Inequalities, a Hybrid MILP/CP Solution Method, and Lower Bound for the Problem

### 3.1. Valid Inequalities

In this section, a few valid inequalities will be introduced. To the problem definition, MILP model (1)–(16) is already appropriate and all the valid inequalities are redundant, but they can reduce the computing time if we attempt to directly solve the model through optimization software. It is more important that the valid inequalities can reflect the problem features and work for the heuristic approach.Production Capacity Inequality. Consider the following:(17)
∑
i
∈
N
y
i
j
p
i
j
≤
Max
⁡
d
i
∣
i
∈
N
-
Min
⁡
r
i
∣
i
∈
N
,
j
∈
M
.Inequality (17) prevents total production times of assignments to any line more than its capacity in the scheduling horizon. For the case in Figure 1, cables J
1, J
2, J
4, and J
5 cannot be assigned to line L
1 concurrently because inequality p
11
+
p
21
+
p
41
+
p
51
>
Max
⁡
d
i
∣
i
∈
N
-
Min
⁡
r
i
∣
i
∈
N
=
d
2
-
r
1 stands, which conflicts with inequality (17), as shown in Figure 2(a).Figure 2
Cable assignments excluded by the valid inequalities.
(a)
A cable assignment against the production capacity inequality
(b)
An assignment against the production time equilibrium inequalityThere is still a tighter inequality which takes into consideration the production tasks balancing in time.Production Time Equilibrium Inequality. Consider the following:(18)
∑
i
∈
Ψ
r
i
′
,
d
i
′
′
y
i
j
p
i
j
≤
d
i
′
′
-
r
i
′
,
i
,
i
′
∈
N
,
d
i
′
′
>
r
i
′
,
j
∈
M
,where Ψ
r
i
′
,
d
i
′
′
=
i
∣
r
i
≥
r
i
′
a
n
d
d
i
≤
d
i
′
′
,
i
∈
N includes all cables that need to be produced in time window r
i
′
,
d
i
′
′.Inequality (17) can be viewed as a special case of inequality (18) and inequality (18) is a tighter inequality. For the case illustrated in Figure 1, Ψ
r
1
,
d
6
=
1
,
3
,
6 and cable combination J
1, J
3, and J
6 can be excluded from L
1 through inequality (18), although the cable combination meets inequality (17), as shown in Figure 2(b).It is worth noting that inequality (18) is not adequate to ensure the production equilibrium absolutely in time because the real production duration is less than the given time window and permitted to slide in the time windows. Therefore, the assignment scheme satisfying inequality (18) can still be infeasible for one or more productions even if ignoring the technical requirements (see [24, 28] for more details). In addition, inequality (18) can be significantly tightened again as in Ren and Liu [28].Limit of Cable Rate of Type B in a Production Line. In effect, the technical constraint (9) limits the ratio of the cable numbers of type B and type A in a production line: (19)
∑
i
∈
A
y
i
j
≥
Q
-
1
∑
i
∈
B
y
i
j
,
j
∈
M
.Inequality (19) provides a filtering mechanism for the cable assignment over the production lines. For the assignment in Figure 2(a), cable combination J
1, J
2, and J
4 can be filtered out from any line when Q
≥
2, because at least two cables of type A are necessary between cables J
1 and J
2.


### 3.2. Hybrid MILP/CP Approach and Lower Bound for the Problem

In the hybrid MILP/CP approach [24, 25], the parallel cable production lines scheduling problem should be decomposed into a relaxed master problem, focusing on the cable assignment decision, and a single production line scheduling subproblem. The relaxed master problem can be formulated into an IP model by formulae (1), (2), and (18). The subproblem for a single production line is formulated by the following CP model:(20)
All-different
W
;
b
W
k
+
1
b
W
k
+
2
i
⋯
+
b
W
k
+
Q
=
Q
∨
L
<
k
+
Q
(21)
i
f
W
k
∈
B
b
W
k
+
1
+
b
W
k
+
2
+
⋯
+
b
W
k
+
Q
=
Q
∨
L
<
k
+
Q
(22)
T
h
e
r
e
q
u
i
r
e
d
p
r
o
d
u
c
t
i
o
n
t
i
m
e
a
n
d
t
i
m
e
w
i
n
d
o
w
c
o
n
s
t
r
a
i
n
t
s
.In the above CP model,W
k denotes the ith cable on the considered production line and L is the number of cables assigned to the line. Formula (20) means that the L cables are all different from each other. Formula (21) is the technical constraint in the line which requires at least Q cables of type A immediately after a cable of type B.As illustrated in Figure3, the hybrid MILP/CP approach begins with solving the relaxed master problem through solving the corresponding IP model optimally. Here, the IP model is solved by ILOG Cplex, a commercial optimization software package. Based on the optimal solution to the master problem, the cable set for each production line can be determined temporarily. The CP model (20)–(22), solved by ILOG Scheduler (an ILOG CP Optimizer), can deal with the m single line scheduling subproblems. If the m subproblems are all feasible and m single line schedules are obtained, the computing process terminates and the optimal solution is obtained. Otherwise, a “cut,” a kind of constraint to eliminate the current infeasible cable assignments (as formulated by inequality (23)), will be constructed and appended to the master problem model which will trigger a new repeat. The iterated process will repeat until all the m feasible single line schedules are obtained.Figure 3
Illustration of the hybrid MILP/CP approach.The “cut” in the iterating process can be formulated as(23)
∑
i
∈
Ω
y
i
j
∗
≤
Ω
-
1
,where j
∗ is the production line encountering infeasibility and Ω is a set of cables that contribute to the infeasibility.The hybrid approach, with improvement in Ren and Liu [28], can solve only small-scale problems, even if ignoring the special technical constraints. For the problem instances of larger size in this paper, it can provide a lower bound and the lower bound can be increased with the more cuts in iterations. But the iterating process can become very time consuming and the lower bound always keeps fixed in many iterations for large problem sizes. Another significance of the hybrid approach is to give an initial cable assignment scheme. Although it is typically infeasible, our heuristic solution can view it as a starting point of the search process.


## 3.1. Valid Inequalities

In this section, a few valid inequalities will be introduced. To the problem definition, MILP model (1)–(16) is already appropriate and all the valid inequalities are redundant, but they can reduce the computing time if we attempt to directly solve the model through optimization software. It is more important that the valid inequalities can reflect the problem features and work for the heuristic approach.Production Capacity Inequality. Consider the following:(17)
∑
i
∈
N
y
i
j
p
i
j
≤
Max
⁡
d
i
∣
i
∈
N
-
Min
⁡
r
i
∣
i
∈
N
,
j
∈
M
.Inequality (17) prevents total production times of assignments to any line more than its capacity in the scheduling horizon. For the case in Figure 1, cables J
1, J
2, J
4, and J
5 cannot be assigned to line L
1 concurrently because inequality p
11
+
p
21
+
p
41
+
p
51
>
Max
⁡
d
i
∣
i
∈
N
-
Min
⁡
r
i
∣
i
∈
N
=
d
2
-
r
1 stands, which conflicts with inequality (17), as shown in Figure 2(a).Figure 2
Cable assignments excluded by the valid inequalities.
(a)
A cable assignment against the production capacity inequality
(b)
An assignment against the production time equilibrium inequalityThere is still a tighter inequality which takes into consideration the production tasks balancing in time.Production Time Equilibrium Inequality. Consider the following:(18)
∑
i
∈
Ψ
r
i
′
,
d
i
′
′
y
i
j
p
i
j
≤
d
i
′
′
-
r
i
′
,
i
,
i
′
∈
N
,
d
i
′
′
>
r
i
′
,
j
∈
M
,where Ψ
r
i
′
,
d
i
′
′
=
i
∣
r
i
≥
r
i
′
a
n
d
d
i
≤
d
i
′
′
,
i
∈
N includes all cables that need to be produced in time window r
i
′
,
d
i
′
′.Inequality (17) can be viewed as a special case of inequality (18) and inequality (18) is a tighter inequality. For the case illustrated in Figure 1, Ψ
r
1
,
d
6
=
1
,
3
,
6 and cable combination J
1, J
3, and J
6 can be excluded from L
1 through inequality (18), although the cable combination meets inequality (17), as shown in Figure 2(b).It is worth noting that inequality (18) is not adequate to ensure the production equilibrium absolutely in time because the real production duration is less than the given time window and permitted to slide in the time windows. Therefore, the assignment scheme satisfying inequality (18) can still be infeasible for one or more productions even if ignoring the technical requirements (see [24, 28] for more details). In addition, inequality (18) can be significantly tightened again as in Ren and Liu [28].Limit of Cable Rate of Type B in a Production Line. In effect, the technical constraint (9) limits the ratio of the cable numbers of type B and type A in a production line: (19)
∑
i
∈
A
y
i
j
≥
Q
-
1
∑
i
∈
B
y
i
j
,
j
∈
M
.Inequality (19) provides a filtering mechanism for the cable assignment over the production lines. For the assignment in Figure 2(a), cable combination J
1, J
2, and J
4 can be filtered out from any line when Q
≥
2, because at least two cables of type A are necessary between cables J
1 and J
2.


## 3.2. Hybrid MILP/CP Approach and Lower Bound for the Problem

In the hybrid MILP/CP approach [24, 25], the parallel cable production lines scheduling problem should be decomposed into a relaxed master problem, focusing on the cable assignment decision, and a single production line scheduling subproblem. The relaxed master problem can be formulated into an IP model by formulae (1), (2), and (18). The subproblem for a single production line is formulated by the following CP model:(20)
All-different
W
;
b
W
k
+
1
b
W
k
+
2
i
⋯
+
b
W
k
+
Q
=
Q
∨
L
<
k
+
Q
(21)
i
f
W
k
∈
B
b
W
k
+
1
+
b
W
k
+
2
+
⋯
+
b
W
k
+
Q
=
Q
∨
L
<
k
+
Q
(22)
T
h
e
r
e
q
u
i
r
e
d
p
r
o
d
u
c
t
i
o
n
t
i
m
e
a
n
d
t
i
m
e
w
i
n
d
o
w
c
o
n
s
t
r
a
i
n
t
s
.In the above CP model,W
k denotes the ith cable on the considered production line and L is the number of cables assigned to the line. Formula (20) means that the L cables are all different from each other. Formula (21) is the technical constraint in the line which requires at least Q cables of type A immediately after a cable of type B.As illustrated in Figure3, the hybrid MILP/CP approach begins with solving the relaxed master problem through solving the corresponding IP model optimally. Here, the IP model is solved by ILOG Cplex, a commercial optimization software package. Based on the optimal solution to the master problem, the cable set for each production line can be determined temporarily. The CP model (20)–(22), solved by ILOG Scheduler (an ILOG CP Optimizer), can deal with the m single line scheduling subproblems. If the m subproblems are all feasible and m single line schedules are obtained, the computing process terminates and the optimal solution is obtained. Otherwise, a “cut,” a kind of constraint to eliminate the current infeasible cable assignments (as formulated by inequality (23)), will be constructed and appended to the master problem model which will trigger a new repeat. The iterated process will repeat until all the m feasible single line schedules are obtained.Figure 3
Illustration of the hybrid MILP/CP approach.The “cut” in the iterating process can be formulated as(23)
∑
i
∈
Ω
y
i
j
∗
≤
Ω
-
1
,where j
∗ is the production line encountering infeasibility and Ω is a set of cables that contribute to the infeasibility.The hybrid approach, with improvement in Ren and Liu [28], can solve only small-scale problems, even if ignoring the special technical constraints. For the problem instances of larger size in this paper, it can provide a lower bound and the lower bound can be increased with the more cuts in iterations. But the iterating process can become very time consuming and the lower bound always keeps fixed in many iterations for large problem sizes. Another significance of the hybrid approach is to give an initial cable assignment scheme. Although it is typically infeasible, our heuristic solution can view it as a starting point of the search process.


## 4. Hybrid IP/GA Approach to the Problem

Genetic algorithm (GA) is a metaheuristic based on evolution population and explores multiple solutions concurrently and thus performs well at global search which is complementary for the optimality (with infeasibility) and solution directivity of the integer programming (IP) method. More GA details can be found in Goldberg [30], Grefenstette [31], and Oliveto and Witt [32]. There are some published studies of genetic algorithm applications in kinds of scheduling problems [33–37]. Through evolution, they find high-quality solutions within reasonable computing time.Generally, a desirable GA can converge quickly at the same time avoiding premature convergence to low-quality solutions. In practice, it needs a good balance between computational time and the solution quality [32]. To improve the GA searching process, an optimization approach, the integer programming (IP) method based on the IP model (1), (2), and (18), is introduced to the iterating steps. It can not only improve the GA searching process but also provide a better lower bound to evaluate the final solution quality.


### 4.1. Framework of the Hybrid IP/GA

The hybrid IP/GA approach is illustrated in Figure4. It is characterized by the interaction between IP and GA in the iterating process. The optimization method with IP model provides cable assignment schemes to the GA and the GA feeds back to the IP model some “cuts.” These “cuts” can cut off some cable assignment schemes and tighten the IP model in turn. The tighter model can possibly produce better solution (cable assignment scheme) and better lower bound.Figure 4
The algorithm framework of the hybrid IP/GA approach.


#### 4.1.1. Generating Cable Assignment Schemes through IP

As mentioned in Section3.2, it can provide a cable assignment scheme to solve IP model (1), (2), and (18) through the optimization software (such as ILOG Cplex). To satisfy the technical constraint, inequality (19) can also be inserted into the IP model. The cable assignment scheme can be extended to a solution through applying the earliest due date (EDD) rule to each production line. The solution, which violates one or more of the time window constraints in most cases but is “optimal” for the objective function, can be taken as a seed to generate the initial chromosomes for GA. The infeasibility can be accepted for chromosome but causes a great penalty in the fitness function.In the evolution process of GA, the IP model can be attached with a series of “cuts,” inequalities as formula (23), and generate more diverse cable assignment schemes. The cable assignment schemes can also be extended to solutions and provide diverse chromosomes to the GA. In our hybrid algorithm, the IP model solver is called for a certain number of generations.


#### 4.1.2. Generating Cuts for IP in the GA Generations

Some of the chromosomes and their infeasibility information in the GA generations need to be retained and form “cuts” to be appended to the IP model. To generate new cable assignment schemes, the cut set of IP model needs to be updated each time the IP solver is called; otherwise, it will generate the same scheme as the last.An infeasibility and the “cut” are illustrated in Figure5. It is infeasible to assign cablesJ
1andJ
2to line L
1, irrespective of the processing sequence, due to the nonpreemption and time window constraint, although it satisfies inequality (18). Based on formula (23), a “cut,” formulated as inequality y
11
+
y
21
≤
1, can be appended into the IP model of the master problem to eliminate the infeasible cable assignment.Figure 5
The “cut” for an infeasible cable assignment.It is worth noting that the infeasibility needs to be verified through CP model in Section3.2 because our single machine scheduling process is not an exact algorithm and cannot guarantee a feasible schedule for each feasible cable combination on a single production line although it does in most cases. If the infeasibility is denied by the CP solver, that is, a feasible schedule is outputted, the cable combination assigned to the line should be accepted and the related solution should be a feasible solution. In the numeric tests, the presumptive case has never happened. On the other hand, some feasible cable assignments can also be used to form “cuts” to make the initial cable assignments more diverse.Because the CP solver can waste more computing time and too many cuts can decrease the solving speed of the IP model, the infeasible cable combinations (or cuts) need to be selected carefully. In the hybrid approach, only cuts from the assignment schemes with currently optimal objectives can be selected to the CP model.Typically, IP model (i.e., the relaxed master problem) with more cuts has more chance to improve the lower bound for the problem.


### 4.2. Genetic Coding for the Problem

To facilitate the crossover and mutter operators, the vector-group coding method [38] is adopted. In the coding method, a chromosome is constructed using a sequence of two-dimensional vectors as follows:(24)
C
h
=
g
1
g
2
⋯
g
n
=
h
1
h
2
⋯
h
n
k
1
k
2
⋯
k
n
,where g
i
=
h
i
k
i represents the ith genein chromosome C
h, h
i
∈
Nis a cable,k
i
∈
Mis production line to process cableh
i, and h
1
,
h
2
,
…
,
h
k
=
N
∖
0. The cables assigned to the same line will be processed in gene order of the chromosome.The start time of each cable production is equal to the maximum of the complete time of the previous cable and its own release time.


### 4.3. Fitness Function and Selection Operator

Since the objective function needs to be minimized and some chromosome can be infeasible, we define a new referred function by(25)
f
′
s
=
f
s
+
N
s
P
,wheref
sis the objective function value of chromosome s, N
s is the number of cables that violate their respective time windows or technical constraint (9), and P is a predefined constant larger than the expected value off
s.We use a common selection operator: roulette-wheel selection. A dynamic linear fitness function [30] U
t
s
=
1
.
1
max
⁡
f
′
s
∣
s
∈
P
t
-
f
′
s, where t is the generation number of the current populationP
t.


### 4.4. Crossover Operator

Based on the vector-group coded chromosomes, we adopt one-point and two-point extended order crossovers. Let two chromosomes,C
h
=
g
1
g
2
⋯
g
nand C
h
′
=
g
1
′
g
2
′
⋯
g
n
′, serve as the present chromosomes. The following describes how to cross over to produce new chromosome.In the one-point extended order crossover, a random integerλ with 1
≤
λ
<
m is first generated to decide the crossover position. New chromosome C
h
′
′
=
g
1
g
2
⋯
g
λ
g
λ
+
1
′
⋯
g
n
′ if g
1
,
g
2
,
…
,
g
λ and g
λ
+
1
′
,
…
,
g
n
′ do not include a common cable; otherwise, discard genes with common cable in C
h
′ and insert the genes corresponding to the lost cables in C
h
′, since the number of common cables must be equal to the number of lost ones. It can generate different chromosome to reverse the C
h and C
h
′.In the two-point extended order crossover, two random integersλ
1 andλ
2 with 1
≤
λ
1
<
λ
2
<
m are first generated to decide the crossover positions. New chromosome C
h
′
′
=
g
1
′
g
2
′
⋯
g
λ
1
g
λ
1
+
1
g
λ
2
⋯
g
λ
2
+
1
′
⋯
g
n
′ if no replicate cable is involved in the crossover. The treatment for the replicate cable is the same as that in the one-point crossover.


### 4.5. Mutation Operator

The bit-mutation and swap-mutation are adopted. In view of the signification of line assignment decisions for cables, the bit-mutation mutates only the second row of the chromosome genes, replacing it with a random number from1
,
2
,
…
,
m. It changes the production line to process the cable.The swap-mutation swaps randomly selected gene values in a chromosome. It can change only the production sequence of one or two production lines. The technical and time window constraints can be involved in the mutation.


### 4.6. Local Search

To improve the evolution process, a simple local search, based on the swap and insert neighborhoods, is applied to all chromosomes in the population for all generations while a local search, based on a variable-depth cycle exchange neighborhood (see Luo and Tang [39] for more details), is applied to chromosomes when the best solution found so far has not changed for 10 generations.The swap neighborhood is obtained through exchanging the assigned production lines of each pair of genes in the given chromosome. The production orders should be exchanged if the pair of genes is corresponding to the same line. The processing sequence should be changed locally according to the technical constraint (formula (9)) and EDD rule which can improve the solution, if the production lines are exchanged. Similar to the swap neighborhood, the insert neighborhood involves inserting a cable to another line or a different position in the same line. The technical constraint has a higher priority than the EDD ruler when they conflict.


## 4.1. Framework of the Hybrid IP/GA

The hybrid IP/GA approach is illustrated in Figure4. It is characterized by the interaction between IP and GA in the iterating process. The optimization method with IP model provides cable assignment schemes to the GA and the GA feeds back to the IP model some “cuts.” These “cuts” can cut off some cable assignment schemes and tighten the IP model in turn. The tighter model can possibly produce better solution (cable assignment scheme) and better lower bound.Figure 4
The algorithm framework of the hybrid IP/GA approach.


### 4.1.1. Generating Cable Assignment Schemes through IP

As mentioned in Section3.2, it can provide a cable assignment scheme to solve IP model (1), (2), and (18) through the optimization software (such as ILOG Cplex). To satisfy the technical constraint, inequality (19) can also be inserted into the IP model. The cable assignment scheme can be extended to a solution through applying the earliest due date (EDD) rule to each production line. The solution, which violates one or more of the time window constraints in most cases but is “optimal” for the objective function, can be taken as a seed to generate the initial chromosomes for GA. The infeasibility can be accepted for chromosome but causes a great penalty in the fitness function.In the evolution process of GA, the IP model can be attached with a series of “cuts,” inequalities as formula (23), and generate more diverse cable assignment schemes. The cable assignment schemes can also be extended to solutions and provide diverse chromosomes to the GA. In our hybrid algorithm, the IP model solver is called for a certain number of generations.


### 4.1.2. Generating Cuts for IP in the GA Generations

Some of the chromosomes and their infeasibility information in the GA generations need to be retained and form “cuts” to be appended to the IP model. To generate new cable assignment schemes, the cut set of IP model needs to be updated each time the IP solver is called; otherwise, it will generate the same scheme as the last.An infeasibility and the “cut” are illustrated in Figure5. It is infeasible to assign cablesJ
1andJ
2to line L
1, irrespective of the processing sequence, due to the nonpreemption and time window constraint, although it satisfies inequality (18). Based on formula (23), a “cut,” formulated as inequality y
11
+
y
21
≤
1, can be appended into the IP model of the master problem to eliminate the infeasible cable assignment.Figure 5
The “cut” for an infeasible cable assignment.It is worth noting that the infeasibility needs to be verified through CP model in Section3.2 because our single machine scheduling process is not an exact algorithm and cannot guarantee a feasible schedule for each feasible cable combination on a single production line although it does in most cases. If the infeasibility is denied by the CP solver, that is, a feasible schedule is outputted, the cable combination assigned to the line should be accepted and the related solution should be a feasible solution. In the numeric tests, the presumptive case has never happened. On the other hand, some feasible cable assignments can also be used to form “cuts” to make the initial cable assignments more diverse.Because the CP solver can waste more computing time and too many cuts can decrease the solving speed of the IP model, the infeasible cable combinations (or cuts) need to be selected carefully. In the hybrid approach, only cuts from the assignment schemes with currently optimal objectives can be selected to the CP model.Typically, IP model (i.e., the relaxed master problem) with more cuts has more chance to improve the lower bound for the problem.


## 4.1.1. Generating Cable Assignment Schemes through IP

As mentioned in Section3.2, it can provide a cable assignment scheme to solve IP model (1), (2), and (18) through the optimization software (such as ILOG Cplex). To satisfy the technical constraint, inequality (19) can also be inserted into the IP model. The cable assignment scheme can be extended to a solution through applying the earliest due date (EDD) rule to each production line. The solution, which violates one or more of the time window constraints in most cases but is “optimal” for the objective function, can be taken as a seed to generate the initial chromosomes for GA. The infeasibility can be accepted for chromosome but causes a great penalty in the fitness function.In the evolution process of GA, the IP model can be attached with a series of “cuts,” inequalities as formula (23), and generate more diverse cable assignment schemes. The cable assignment schemes can also be extended to solutions and provide diverse chromosomes to the GA. In our hybrid algorithm, the IP model solver is called for a certain number of generations.


## 4.1.2. Generating Cuts for IP in the GA Generations

Some of the chromosomes and their infeasibility information in the GA generations need to be retained and form “cuts” to be appended to the IP model. To generate new cable assignment schemes, the cut set of IP model needs to be updated each time the IP solver is called; otherwise, it will generate the same scheme as the last.An infeasibility and the “cut” are illustrated in Figure5. It is infeasible to assign cablesJ
1andJ
2to line L
1, irrespective of the processing sequence, due to the nonpreemption and time window constraint, although it satisfies inequality (18). Based on formula (23), a “cut,” formulated as inequality y
11
+
y
21
≤
1, can be appended into the IP model of the master problem to eliminate the infeasible cable assignment.Figure 5
The “cut” for an infeasible cable assignment.It is worth noting that the infeasibility needs to be verified through CP model in Section3.2 because our single machine scheduling process is not an exact algorithm and cannot guarantee a feasible schedule for each feasible cable combination on a single production line although it does in most cases. If the infeasibility is denied by the CP solver, that is, a feasible schedule is outputted, the cable combination assigned to the line should be accepted and the related solution should be a feasible solution. In the numeric tests, the presumptive case has never happened. On the other hand, some feasible cable assignments can also be used to form “cuts” to make the initial cable assignments more diverse.Because the CP solver can waste more computing time and too many cuts can decrease the solving speed of the IP model, the infeasible cable combinations (or cuts) need to be selected carefully. In the hybrid approach, only cuts from the assignment schemes with currently optimal objectives can be selected to the CP model.Typically, IP model (i.e., the relaxed master problem) with more cuts has more chance to improve the lower bound for the problem.


## 4.2. Genetic Coding for the Problem

To facilitate the crossover and mutter operators, the vector-group coding method [38] is adopted. In the coding method, a chromosome is constructed using a sequence of two-dimensional vectors as follows:(24)
C
h
=
g
1
g
2
⋯
g
n
=
h
1
h
2
⋯
h
n
k
1
k
2
⋯
k
n
,where g
i
=
h
i
k
i represents the ith genein chromosome C
h, h
i
∈
Nis a cable,k
i
∈
Mis production line to process cableh
i, and h
1
,
h
2
,
…
,
h
k
=
N
∖
0. The cables assigned to the same line will be processed in gene order of the chromosome.The start time of each cable production is equal to the maximum of the complete time of the previous cable and its own release time.


## 4.3. Fitness Function and Selection Operator

Since the objective function needs to be minimized and some chromosome can be infeasible, we define a new referred function by(25)
f
′
s
=
f
s
+
N
s
P
,wheref
sis the objective function value of chromosome s, N
s is the number of cables that violate their respective time windows or technical constraint (9), and P is a predefined constant larger than the expected value off
s.We use a common selection operator: roulette-wheel selection. A dynamic linear fitness function [30] U
t
s
=
1
.
1
max
⁡
f
′
s
∣
s
∈
P
t
-
f
′
s, where t is the generation number of the current populationP
t.


## 4.4. Crossover Operator

Based on the vector-group coded chromosomes, we adopt one-point and two-point extended order crossovers. Let two chromosomes,C
h
=
g
1
g
2
⋯
g
nand C
h
′
=
g
1
′
g
2
′
⋯
g
n
′, serve as the present chromosomes. The following describes how to cross over to produce new chromosome.In the one-point extended order crossover, a random integerλ with 1
≤
λ
<
m is first generated to decide the crossover position. New chromosome C
h
′
′
=
g
1
g
2
⋯
g
λ
g
λ
+
1
′
⋯
g
n
′ if g
1
,
g
2
,
…
,
g
λ and g
λ
+
1
′
,
…
,
g
n
′ do not include a common cable; otherwise, discard genes with common cable in C
h
′ and insert the genes corresponding to the lost cables in C
h
′, since the number of common cables must be equal to the number of lost ones. It can generate different chromosome to reverse the C
h and C
h
′.In the two-point extended order crossover, two random integersλ
1 andλ
2 with 1
≤
λ
1
<
λ
2
<
m are first generated to decide the crossover positions. New chromosome C
h
′
′
=
g
1
′
g
2
′
⋯
g
λ
1
g
λ
1
+
1
g
λ
2
⋯
g
λ
2
+
1
′
⋯
g
n
′ if no replicate cable is involved in the crossover. The treatment for the replicate cable is the same as that in the one-point crossover.


## 4.5. Mutation Operator

The bit-mutation and swap-mutation are adopted. In view of the signification of line assignment decisions for cables, the bit-mutation mutates only the second row of the chromosome genes, replacing it with a random number from1
,
2
,
…
,
m. It changes the production line to process the cable.The swap-mutation swaps randomly selected gene values in a chromosome. It can change only the production sequence of one or two production lines. The technical and time window constraints can be involved in the mutation.


## 4.6. Local Search

To improve the evolution process, a simple local search, based on the swap and insert neighborhoods, is applied to all chromosomes in the population for all generations while a local search, based on a variable-depth cycle exchange neighborhood (see Luo and Tang [39] for more details), is applied to chromosomes when the best solution found so far has not changed for 10 generations.The swap neighborhood is obtained through exchanging the assigned production lines of each pair of genes in the given chromosome. The production orders should be exchanged if the pair of genes is corresponding to the same line. The processing sequence should be changed locally according to the technical constraint (formula (9)) and EDD rule which can improve the solution, if the production lines are exchanged. Similar to the swap neighborhood, the insert neighborhood involves inserting a cable to another line or a different position in the same line. The technical constraint has a higher priority than the EDD ruler when they conflict.


## 5. Computational Experiments

To test the performance of the formulated mathematical model and the proposed heuristic approach with improvement strategies, we complemented all the involved programs under the development environment of VC++ 2010 and solved the IP model and CP withILog Cplex andILog Scheduler, respectively. The experiments were all performed on a computer with Win 7 operating system, 2.8 Ghz Intel 2 Core CPU, and 4 GB RAM.


### 5.1. Configuration of the Hybrid IP/GA Approach

GA parameters for all problems were set to be the same: population size = 100, crossover probability = 1, mutation probability = 0.1, and the algorithm stops when gap between the lower bound and the best solution found so far has not been improved for 60 generations, the gap is lower than 0.5%, or the total number of generations reaches 600 (which comes from the computing time limit). The IP master problem was triggered when the best solution found so far has not been improved for 30 generations.


### 5.2. Test Problem Instances

We tested 12 problem instances in the numerical experiments from a practical cable production enterprise, which had five production lines but only four of them were available in these instances. The production cost and times were both estimated based on the empirical data. The number of necessary cables of type A between successive cables of type B in a production line was three and thusQ
=
3 in all test problems and the proportion of type B was less than 20% in practice.To test the developed hybrid IP/GA approach thoroughly, a series of problem instances of six different sizes were generated through imitating the practical data. Each problem size has 12 instances. The processing costs (c
i
j for cable i and production line j) were random integers from uniform distribution of U
20
,
100, which magnified the practical figures about 10 times for more comparability. The processing times were from U
30
,
60. The release times (r
i) were from U
0
,
T
m
a
x and due times d
i
=
r
i
+
δ
p
i, where T
m
a
x should be large enough to ensure the feasibility, p
i
=
M
a
x
{
p
i
j
∣
j
∈
M
} is the maximal processing time of the cable i, and δ is a magnification factor randomly from U
1.5
,
3.5.


### 5.3. Computational Results

The small sized problems were first solved to optimality using the hybrid MILP/CP algorithm and then solved by the proposed hybrid IP/GA. The small sized problem instances were cut out from the 12 practical instances.n
×
m represented the problem size, where n and m denote the number of cables and production lines, respectively. Table 2 shows the experimental results with the different problem sizes. For the 12 problems of small size, the hybrid IP/GA also obtained almost all the optimal solutions but did not verify the optimality for two of them.Table 2
Experimental result for the small sized problems.
Problem
n
×
m
Objective value
CPU time (seconds)
MILP/CP
IP/GA
MILP/CP
IP/GA
1
12
×
2
56
56
3.41
<1
2
12
×
2
58
58
0.86
<1
3
16
×
2
61
61
1.14
1.13
4
16
×
2
79
79
14.87
1.21
5
15
×
3
81
81
3.48
1.79
6
15
×
3
67
67
∗
143.34
2.76
7
18
×
3
94
94
23.55
4.84
8
18
×
3
87
87
6.56
4.16
9
16
×
4
67
67
31.42
2.89
10
16
×
4
53
53
39.38
4.54
11
20
×
4
102
102
∗
207.51
5.30
12
20
×
4
113
113
71.35
6.13
∗The optimal solution is obtained but gap is not equal to 0.The experimental results for the 12 practical problems are listed in Table3. Each problem has four production lines and the problem size is represented by the number of cables. In the table, G
a
p
=
O
b
j
e
c
t
i
v
e
v
a
l
u
e
-
L
o
w
e
r
b
o
u
n
d
/
L
o
w
e
r
b
o
u
n
d is used to evaluate the solution quality. The average relative gap was 2.78% and the average CPU-s was 83.Table 3
Experimental results for the practical problems.
Problem
Size
Objective value
Gap (%)
CPU time (seconds)
IP/GA
LB
1
41
172
170
1.32
34
2
46
229
226
1.37
58
3
51
231
222
3.87
117
4
51
244
240
1.52
13
5
55
283
275
2.95
47
6
59
375
367
1.93
143
7
64
396
388
1.98
13
8
67
424
409
3.74
16
9
72
446
421
5.97
231
10
78
487
475
2.47
39
11
86
400
394
1.49
208
12
88
503
480
4.71
71
Average
2.78
83For the six sets of randomly generated problem instances, Table4 lists the average solution gap and CPU-seconds. The average relative gap was 2.51% and the average computing time was 121 CPU-seconds. In addition, the number of iterations reaches up to the limit (600 generations) for most of the instances.Table 4
The average experiment results for the generated 6 problem sizes.
Group number
Size
Gap (%)
CPU time (seconds)
1
40
×
3
1.32
34
2
8
0
×
3
3.87
118
3
12
0
×
3
2.61
156
4
50
×
4
1.57
29
5
100
×
4
2.17
126
6
15
0
×
4
3.54
265
Average
2.51
121To further test the performance of the hybrid IP/GA approach, we also solved the problems with a GA by Vallada and Ruiz [40], which was proposed to solve unrelated parallel machine scheduling problem sharing similarities with our problem. Figure 6 shows the comparison results of the average relative objective value (ARD) of the group of practical problem instances and six sets of randomly generated instances. From the results, the efficiency of our algorithm in solving our problem has been verified. In addition, our proposed hybrid IP/GA approach can provide a better lower bound for the problem.Figure 6
The ARD comparison of the IP/GA from an existing GA.


### 5.4. Computational Analysis

From the computational results, all the problem instances can be resolved in acceptable computing times (no more than 5 min) by these algorithms. In those experiments, the IP model can provide the cable assignment schemes to the GA as well as the lower bound to evaluate the solution quality. Moreover, we have the following observations:(1)
In Table2, the proposed hybrid IP/GA approach performs much better than the hybrid MILP/CP approach in solution efficiency particularly to the instances with larger sizes. For the solution quality, they reached the same objective function value for all the instances but the former failed to reduce the gap to 0, meaning that the solution optimality cannot be validated by its own lower bound.
(2)
In Tables3 and 4, the computation times increase with the problem size but the solution quality is relatively stable. It implies that the solution quality is seldom affected by the problem size but depends mainly on the permitted number of iterations, since most of iterations reach up to the limit.
(3)
The IP model contributes to improving the solution as well as providing the lower bound. The cable assignment schemes obtained through resolving the IP model, aiming at the optimal objective, can lead the GA to search around the optimum point.


## 5.1. Configuration of the Hybrid IP/GA Approach

GA parameters for all problems were set to be the same: population size = 100, crossover probability = 1, mutation probability = 0.1, and the algorithm stops when gap between the lower bound and the best solution found so far has not been improved for 60 generations, the gap is lower than 0.5%, or the total number of generations reaches 600 (which comes from the computing time limit). The IP master problem was triggered when the best solution found so far has not been improved for 30 generations.


## 5.2. Test Problem Instances

We tested 12 problem instances in the numerical experiments from a practical cable production enterprise, which had five production lines but only four of them were available in these instances. The production cost and times were both estimated based on the empirical data. The number of necessary cables of type A between successive cables of type B in a production line was three and thusQ
=
3 in all test problems and the proportion of type B was less than 20% in practice.To test the developed hybrid IP/GA approach thoroughly, a series of problem instances of six different sizes were generated through imitating the practical data. Each problem size has 12 instances. The processing costs (c
i
j for cable i and production line j) were random integers from uniform distribution of U
20
,
100, which magnified the practical figures about 10 times for more comparability. The processing times were from U
30
,
60. The release times (r
i) were from U
0
,
T
m
a
x and due times d
i
=
r
i
+
δ
p
i, where T
m
a
x should be large enough to ensure the feasibility, p
i
=
M
a
x
{
p
i
j
∣
j
∈
M
} is the maximal processing time of the cable i, and δ is a magnification factor randomly from U
1.5
,
3.5.


## 5.3. Computational Results

The small sized problems were first solved to optimality using the hybrid MILP/CP algorithm and then solved by the proposed hybrid IP/GA. The small sized problem instances were cut out from the 12 practical instances.n
×
m represented the problem size, where n and m denote the number of cables and production lines, respectively. Table 2 shows the experimental results with the different problem sizes. For the 12 problems of small size, the hybrid IP/GA also obtained almost all the optimal solutions but did not verify the optimality for two of them.Table 2
Experimental result for the small sized problems.
Problem
n
×
m
Objective value
CPU time (seconds)
MILP/CP
IP/GA
MILP/CP
IP/GA
1
12
×
2
56
56
3.41
<1
2
12
×
2
58
58
0.86
<1
3
16
×
2
61
61
1.14
1.13
4
16
×
2
79
79
14.87
1.21
5
15
×
3
81
81
3.48
1.79
6
15
×
3
67
67
∗
143.34
2.76
7
18
×
3
94
94
23.55
4.84
8
18
×
3
87
87
6.56
4.16
9
16
×
4
67
67
31.42
2.89
10
16
×
4
53
53
39.38
4.54
11
20
×
4
102
102
∗
207.51
5.30
12
20
×
4
113
113
71.35
6.13
∗The optimal solution is obtained but gap is not equal to 0.The experimental results for the 12 practical problems are listed in Table3. Each problem has four production lines and the problem size is represented by the number of cables. In the table, G
a
p
=
O
b
j
e
c
t
i
v
e
v
a
l
u
e
-
L
o
w
e
r
b
o
u
n
d
/
L
o
w
e
r
b
o
u
n
d is used to evaluate the solution quality. The average relative gap was 2.78% and the average CPU-s was 83.Table 3
Experimental results for the practical problems.
Problem
Size
Objective value
Gap (%)
CPU time (seconds)
IP/GA
LB
1
41
172
170
1.32
34
2
46
229
226
1.37
58
3
51
231
222
3.87
117
4
51
244
240
1.52
13
5
55
283
275
2.95
47
6
59
375
367
1.93
143
7
64
396
388
1.98
13
8
67
424
409
3.74
16
9
72
446
421
5.97
231
10
78
487
475
2.47
39
11
86
400
394
1.49
208
12
88
503
480
4.71
71
Average
2.78
83For the six sets of randomly generated problem instances, Table4 lists the average solution gap and CPU-seconds. The average relative gap was 2.51% and the average computing time was 121 CPU-seconds. In addition, the number of iterations reaches up to the limit (600 generations) for most of the instances.Table 4
The average experiment results for the generated 6 problem sizes.
Group number
Size
Gap (%)
CPU time (seconds)
1
40
×
3
1.32
34
2
8
0
×
3
3.87
118
3
12
0
×
3
2.61
156
4
50
×
4
1.57
29
5
100
×
4
2.17
126
6
15
0
×
4
3.54
265
Average
2.51
121To further test the performance of the hybrid IP/GA approach, we also solved the problems with a GA by Vallada and Ruiz [40], which was proposed to solve unrelated parallel machine scheduling problem sharing similarities with our problem. Figure 6 shows the comparison results of the average relative objective value (ARD) of the group of practical problem instances and six sets of randomly generated instances. From the results, the efficiency of our algorithm in solving our problem has been verified. In addition, our proposed hybrid IP/GA approach can provide a better lower bound for the problem.Figure 6
The ARD comparison of the IP/GA from an existing GA.


## 5.4. Computational Analysis

From the computational results, all the problem instances can be resolved in acceptable computing times (no more than 5 min) by these algorithms. In those experiments, the IP model can provide the cable assignment schemes to the GA as well as the lower bound to evaluate the solution quality. Moreover, we have the following observations:(1)
In Table2, the proposed hybrid IP/GA approach performs much better than the hybrid MILP/CP approach in solution efficiency particularly to the instances with larger sizes. For the solution quality, they reached the same objective function value for all the instances but the former failed to reduce the gap to 0, meaning that the solution optimality cannot be validated by its own lower bound.
(2)
In Tables3 and 4, the computation times increase with the problem size but the solution quality is relatively stable. It implies that the solution quality is seldom affected by the problem size but depends mainly on the permitted number of iterations, since most of iterations reach up to the limit.
(3)
The IP model contributes to improving the solution as well as providing the lower bound. The cable assignment schemes obtained through resolving the IP model, aiming at the optimal objective, can lead the GA to search around the optimum point.


## 6. Conclusion

In this paper, a special parallel production lines scheduling problem was studied. A mixed integer programming model considering time window and technical constraints was first formulated. A few valid inequalities were deduced and a hybrid MILP/CP approach was introduced. Based on them, a hybrid IP/GA algorithm was proposed to solve the problem. The numerical experiments were carried out which demonstrated that the proposed solution approach was effective and efficient.This study highlighted the advantage of combining the traditional exact optimization (IP) with intelligent optimization (GA) method. Other intelligent optimization methods can also be able to hybridize to the IP (or MILP) method. It is more interesting and challenging to hybridize the IP (or MILP) to more elements of the GA (or other heuristics) and deepen the hybridization for the purpose of improving the solution approach.



---

*Source: 5201937-2016-05-12.xml*