# A Genetic Algorithm-Based Approach for Single-Machine Scheduling with Learning Effect and Release Time

Authors: Der-Chiang Li; Peng-Hsiang Hsu; Chih-Chieh Chang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The way to gain knowledge and experience of producing a product in a firm can be seen as new solution for reducing the unit cost in scheduling problems, which is known as “learning effects.” In the scheduling of batch processing machines, it is sometimes advantageous to form a nonfull batch, while in other situations it is a better strategy to wait for future job arrivals in order to increase the fullness of the batch. However, research with learning effect and release times is relatively unexplored. Motivated by this observation, we consider a single-machine problem with learning effect and release times where the objective is to minimize the total completion times. We develop a branch-and-bound algorithm and a genetic algorithm-based heuristic for this problem. The performances of the proposed algorithms are evaluated and compared via computational experiments, which showed that our approach has superior ability in this scenario.


---

## Body

## 1. Introduction

Learning effect has been considered as the most intensive phenomenon since it has been proposed in Biskup [1]. The basic concept has been set to fix the processing time of scheduling sequence job from the first job to the last job, which demonstrated that the processing time can be improved after continuous learning. Moreover, some researches also indicated that learning effect can be regarded as a controllable and important component affect processing time in scheduling problems (Vickson, Nowicki and Zdrzałka, and Cheng et al. [2–4]). Although there were many researches focusing on this phenomenon, all of them sometimes assumed that all jobs were allowed to process on machine in time. However, the release times must be considered in many real-world applications in order to make this assumption valid. For example, products in a semiconductor wafer fabrication facilities undergo several hundreds of manufacturing steps such as reentrant process flows, sequence-dependent setups, diversity of product mix, and batch processing. With such complexities, it would be a great challenge to meet the customers’ requirements such as different priorities, ready times, and due dates. In the presence of unequal ready times, the application of a nonfull batch would sometimes be advantageous. In some cases it would be better to wait for new jobs to arrive to increase the completeness of the batch (Mönch et al. [5]). Following are some researches that focus on scheduling problem by considering both learning effect and release times (Lee et al., Eren, Wu and Liu, Toksarı, Wu et al., Ahmadizar and Hosseini, Rudek, Li and Hsu, Kung et al., and Yin et al. [6–16]). In this paper, we would like to discuss the single-machine total completion time problem with sum of processing time-based learning and release times, given that it is a topic still to be studied and explored.Rinnooy Kan [17] showed that the same problem without learning consideration was NP-hard unless the release times were identical. Therefore, we apply the branch-and-bound algorithm and genetic algorithm search for the optimal solution and near-optimal solutions. The results show that the branch and bound algorithm has solved the instances less than or equal to 24 jobs. Moreover, GA also shows good performance in computational experiments.The rest of the paper is organized as follows. Some learning effect works are described in Section2. In Section 3, the description of notations and the problem formulation are given. Some dominance properties and two lower bounds are developed to enhance the search efficiency for the optimal solution, followed by descriptions of the genetic algorithm and the branch-and-bound algorithms are shown in Section 4. The results of a computational experiment are given in Section 5, and the conclusions are given in the last section.


## 2. Related Works

There were some related researches dealing with scheduling problem via learning effect. In Heizer and Render [18], authors verified that unit costs decrease while a firm gains more product knowledge and experience. Cheng and Wang [19] introduced the framework of learning effect in a single machine. More recently, Biskup [20] provided reviews of state-of-the-art scheduling. Wang et al. [21] studied the time-dependent learning effect in scheduling recently and came up with the same learning model as proposed by Kuo and Yang [22], where the job processing time is a function of total normal processing time of the previously scheduled jobs. Cheng et al. [23] brought up with a new learning model in which the actual processing time of a job depends on both the job’s scheduled position and the processing times of the jobs that are already processed. The two models proposed by Biskup [1] and Koulamas and Kyparisis [24] were further combined by Wu and Lee, Lee and Wu, and Yin et al. [25–27]. Also, a new experience-based learning effect model, which is based on the S-shaped learning curve, where job processing times would be dependent on the experience of the processor, was introduced and analyzed by Janiak and Rudek [28]. S.-J. Yang and D.-L. Yang [29] investigated a new group learning effect model on scheduling problem aiming to minimize the total processing time. Yin et al. [30] brought a general learning effect model into the field of scheduling which states that the actual processing time of a job is a general function of both the total actual processing times of the jobs already processed and the job’s scheduled position. They had shown that the problems of minimizing makespan and the sum of the kth power of completion time could be solved in polynomial time, respectively. A single-machine scheduling problem with a truncation learning effect proposed by Wu et al. [31] states that job processing time depends on the processing times of the jobs already processed and a controlled parameter. They also showed that polynomial time can be used to solve some single-machine scheduling problems. J.-B. Wang and M.-Z. Wang [32] also came up with a revised model based on general learning effect and proved that some single-machine and flowshop scheduling problems can be solved using polynomial time. Lu et al. [33], applying different learning effect models simultaneously, studied several single-machine scheduling problems and concluded that under the proposed models the scheduling problems of minimization of the makespan, the total completion time, and the sum of the kth power of job completion times can be solved in polynomial time. J.-B. Wang and J.-J. Wang [34] studied learning effect model where the actual processing time of a job is not only a nonincreasing function of the total weighted normal processing times of the jobs already processed, but also a nonincreasing function of the job’s scheduled position, where the weight is a position-dependent weight. They also show that their approach can solve the problem in polynomial time. Li et al. [35] investigated several single-machine problems with a truncated sum of processing times based learning effect that remain polynomially solvable. Cheng et al. [36] addressed two-machine flowshop scheduling with a truncated learning function while minimizing the makespan. They applied a branch-and-bound and three heuristic algorithms to derive the optimal and near-optimal solutions. Wu [37] studied two-agent scheduling on a single machine involving the learning effects and deteriorating jobs simultaneously. The objective is to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent.


## 3. Notation and Problem Formulation

Before formulating the problem, we first introduce some notations that will be used throughout the paper.n: the number of jobs.
S, S
′, S
*, S
1: the sequences of jobs.
J
i, J
j: the job i and job j.
p
i: the normal processing time of job i.
p
[
i
]
(
S
): the normal processing time for the job scheduled in the ith position in S.
p
(
i
): the ith job processing time when they are in a nondecreasing order.
p
j
r: the actual processing time of a given job j if it is scheduled in the rth position.
r
i: the release time of job i.
r
[
i
]
(
S
): the release time of a job scheduled in the ith position in S.
r
(
i
): the ith job release time when they are in a nondecreasing order.
a: the learning ratio, where a
≤
0.
C
i
(
S
), C
i
(
S
′
): the completion time of job i in S and S
′.
C
i
(
S
*
): the completion time of job i in optimal schedule S
*.
C
[
i
]
(
S
), C
[
i
]
(
S
1
): the completion time of a job scheduled in the ith position in S and S
1.
TC
(
S
), TC
(
S
′
): the total completion times of sequences S and S
′.
π
,
π
′
,
π
c: the subsequences of jobs.The formulation of the problem is described as follows. There aren jobs to be processed on a single machine. The machine can handle one job at a time and machine idle and job preemption are not allowed. Each job j has a normal processing time p
j and a release time r
j. The general job learning model is p
j
r
=
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a, where p
j
r is the actual processing time of job j scheduled in the rth position and a
≤
0 is a learning ratio. The objective of this problem is to find an optimal schedule S
* that minimizes the total completion time; that is, ∑
i
=
1
n
C
i
(
S
*
)
≤
∑
i
=
1
n
C
i
(
S
) for any schedule S. Using the standard three-field notation of Graham et al. [38], our scheduling problem can be denoted as 1
/
p
j
r
=
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
/
∑
C.


## 4. The Branch-and-Bound and Genetic Algorithms

In this paper, we will apply the branch-and-bound and genetic algorithms search for the optimal solution and obtain near-optimal solution, respectively. First, in order to facilitate the searching process and improve the branching procedure, we develop some adjacent pairwise interchange properties and two lower bounds to use in branch-and-bound algorithm. Then, the procedure of the genetic algorithms is given at last.


### 4.1. Dominance Properties

Before presenting the adjacent pairwise interchange properties, we provide two lemmas, which will be used in the proofs of the properties in the sequel.Lemma 1.
Letf
(
x
)
=
1
+
a
x
(
1
-
x
)
a
-
1
-
(
1
+
x
)
a, then f
(
x
)
≥
0, for a
≤
0 and x
>
0.Lemma 2.
Letg
(
λ
)
=
(
λ
-
1
)
+
(
1
+
λ
x
)
a
-
λ
(
1
+
x
)
a, then g
(
λ
)
≥
0, for λ
≥
1, a
≤
0, and x
>
0.To fathom the searching tree, we develop some dominance properties based on a pairwise interchange of two adjacent jobsJ
i and J
j. Let S
=
(
π
,
J
i
,
J
j
,
π
′
) and S
′
=
(
π
,
J
j
,
J
i
,
π
′
) be two sequences in which π and π
′ denote partial sequences. To show that S dominates S
′, it suffices to show that C
i
(
S
)
+
C
j
(
S
)
≤
C
j
(
S
′
)
+
C
i
(
S
′
) and C
j
(
S
)
<
C
i
(
S
′
). In addition, let t be the completion time of the last job in subsequence π with (r
-
1) jobs.Property 1.
Ifp
i
<
p
j and max
⁡
{
r
i
,
r
j
}
≤
t, then S dominates S
′.Proof.
Sincemax
⁡
{
r
i
,
r
j
}
≤
t, we have
(1)
C
i
(
S
)
=
t
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
,
C
j
(
S
)
=
t
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
+
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
i
)
a
,
C
j
(
S
′
)
=
t
+
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
,
C
i
(
S
′
)
=
t
+
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
j
)
a
.
After taking the difference of (1), we have
(2)
C
i
(
S
′
)
-
C
j
(
S
)
=
(
p
j
-
p
i
)
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
j
)
a
-
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
i
)
a
.
On substituting λ
=
p
j
/
p
i, u
=
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
), and x
=
(
p
i
/
(
1
+
∑
l
=
1
n
p
l
)
) into (2) and simplifying it, we obtain
(3)
C
i
(
S
′
)
-
C
j
(
S
)
=
p
i
u
a
[
(
λ
-
1
)
+
(
1
+
λ
x
)
a
-
λ
(
1
+
x
)
a
]
.
By Lemma 2, with λ
>
1, a
≤
0, and x
>
0, we have C
i
(
S
′
)
-
C
j
(
S
)
>
0.
Moreover, after taking the difference of total completion times (TC) between sequencesS and S
′, we have
(4)
TC
(
S
′
)
-
TC
(
S
)
=
[
C
j
(
S
′
)
+
C
i
(
S
′
)
]
-
[
C
i
(
S
)
+
C
j
(
S
)
]
=
2
(
p
j
-
p
i
)
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
j
)
a
-
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
i
)
a
.
By (3), it can be easily shown that (4) is nonnegative for p
i
<
p
j. Therefore, S dominates S
′.The proofs of Properties2 to 5 are omitted since they are similar to that of Property 1.Property 2.
Ifr
i
≤
t
≤
r
j
≤
t
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a and p
i
<
p
j, then S dominates S
′.Property 3.
Ift
≥
r
i and t
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
<
r
j, then S dominates S
′.Property 4.
Ift
≤
r
i
≤
r
j, r
i
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
≥
r
j, and p
i
<
p
j, then S dominates S
′.Property 5.
Ift
≤
r
i and r
i
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
<
r
j, then S dominates S
′.In order to further determine the ordering of the remaining unscheduled jobs to further speed up the searching process, we provide the following property. Assume thatS
=
(
π
,
π
c
) is a sequence of jobs where π is the scheduled part containing k jobs and π
c is the unscheduled part. Let S
1
=
(
π
,
π
′
) be the sequence in which the unscheduled jobs are arranged in a nondecreasing order of job processing times; that is, p
(
k
+
1
)
≤
p
(
k
+
2
)
≤
⋯
≤
p
(
n
).Property 6.
IfC
[
k
]
(
S
1
)
>
ma
x
j
∈
π
c
{
r
j
}, then S
1
=
(
π
,
π
′
) dominates sequences of the type (π
,
π
c) for any unscheduled sequence π
c.Proof.
SinceC
[
k
]
(
S
1
)
>
ma
x
j
∈
π
c
{
r
j
}, it implies that all the unscheduled jobs are ready to be processed on time C
[
k
]
(
S
1
). To obtain the optimal subsequence, let S
1
=
(
π
,
π
′
) be the sequence in which the unscheduled jobs are arranged in nondecreasing order of jobs processing times.


### 4.2. Lower Bounds

In this subsection, we develop two lower bounds by using the following lemma from Hardy et al. [39].Lemma 3.
Suppose thata
i and b
i are two sequences of numbers. The sum ∑
i
=
1
n
a
i
b
i of products of the corresponding elements is the least if the sequences are monotonic in the opposite sense.First, letP
S be a partial schedule in which the order of the first k jobs has been determined and let S be a complete schedule obtained from P
S. By definition, the completion time for the (
k
+
1
)
th job is
(5)
C
[
k
+
1
]
(
S
)
=
max
⁡
{
C
[
k
]
(
S
)
,
r
[
k
+
1
]
}
+
p
[
k
+
1
]
(
1
+
∑
l
=
1
k
p
[
l
]
)
a
≥
C
[
k
]
(
S
)
+
p
[
k
+
1
]
(
1
+
∑
l
=
1
k
p
[
l
]
)
a
.
Similarly, the completion time for the (
k
+
j
)
th job is
(6)
C
[
k
+
j
]
(
S
)
≥
C
[
k
]
(
S
)
+
∑
i
=
1
j
p
(
k
+
i
)
(
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
i
-
1
p
(
k
+
l
)
)
a
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
1
≤
j
≤
n
-
k
.
The first term on the right hand side of (6) is known, and a lower bound of the total completion time for the partial sequence P
S can be obtained by minimizing the second term. Since the value of (
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
i
-
1
p
[
k
+
l
]
)
a is a decreasing function of ∑
l
=
1
i
-
1
p
[
k
+
l
], the total completion time is minimized by sequencing the unscheduled jobs according to the shortest processing time (SPT) rule according to Lemma 3. Consequently, the first lower bound is
(7)
L
B
1
=
∑
i
=
1
k
C
[
i
]
(
S
)
+
∑
j
=
1
n
-
k
C
^
(
j
)
,
where C
^
(
j
)
=
C
[
k
]
(
S
)
+
∑
i
=
1
j
p
(
k
+
i
)
(
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
i
-
1
p
(
n
-
k
+
l
-
1
)
)
a. On the other hand, this lower bound may not be tight if the release time is long. To overcome this situation, a second lower bound is established by taking account of the release time. The completion time for the (k
+
1)th job is
(8)
C
[
k
+
1
]
(
S
)
=
max
⁡
{
C
[
k
]
(
S
)
,
r
[
k
+
1
]
}
+
p
[
k
+
1
]
(
1
+
∑
l
=
1
k
p
[
l
]
)
a
≥
r
[
k
+
1
]
(
S
)
+
p
[
k
+
1
]
(
1
+
∑
l
=
1
k
p
[
l
]
)
a
.
Similarly, the completion time for the (
k
+
j
)
th job is
(9)
C
[
k
+
j
]
(
S
)
≥
r
[
k
+
j
]
(
S
)
+
p
[
k
+
j
]
(
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
j
-
1
p
[
k
+
l
]
)
a
,
C
[
k
+
j
]
(
S
)
≥
r
[
k
+
j
]
(
S
)
+
p
[
k
+
j
]
C
[
k
+
j
]
(
S
)
≥
1
≤
j
≤
n
-
k
.
Note that C
[
k
+
j
]
(
S
) is greater than or equal to r
(
k
+
j
)
′, where r
(
k
+
1
)
′
≤
r
(
k
+
2
)
′
≤
⋯
≤
r
(
n
)
′ denote the release times of the unscheduled jobs arranged in a nondecreasing order. The second term on the right hand side of (9) is minimized by the SPT rule since (
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
j
-
1
p
[
k
+
l
]
)
a is a decreasing function of ∑
l
=
1
j
-
1
p
[
k
+
l
]. It follows that we have the following second lower bound:
(10)
L
B
2
=
∑
i
=
1
k
C
[
i
]
+
∑
j
=
1
n
-
k
C
~
(
j
)
,
where C
~
(
j
)
=
r
(
k
+
j
)
′
(
S
)
+
p
(
k
+
1
)
′
(
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
j
-
1
p
(
n
-
k
+
l
-
1
)
′
)
a. Note that p
(
k
+
j
)
′ and r
(
k
+
j
)
′ do not necessarily come from the same job. In order to make the lower bound tighter, we choose the maximum value from (7) and (10) as the lower bounds of P
S. That is,
(11)
LB
=
max
⁡
{
L
B
1
,
L
B
2
}
.


### 4.3. The Procedure of Genetic Algorithms

A genetic algorithm (GA) is an optimization method that mimics natural processes. GA was invented by Holland [40] and the most widely used to solve numerical optimization problems in a wide variety of application fields, including biology, economics, engineering, business, agriculture, telecommunications, and manufacturing. For example in Goldberg [41], authors using GA in engineering design problems is reviewed in Gen and Cheng [42]. Soolaki et al. [43] use a GA to solve an airline boarding problem with linear programming models [44, 45] and use genetic algorithms to optimize the parameters for the given test collections. GAs start evolving by generating an initial population of chromosomes. Then, a fitness function is used to compute the relative fitness of each chromosome of the population. The selection, crossover, and mutation operators are used in succession to create a new population of chromosomes for the next generation. This approach has gained increasing popularity in solving many combinatorial optimization problems in a wide variety of different disciplines.


#### 4.3.1. Initial Settings

In a GA, every problem is presented by a code and each code is seen as a gene. The existing genes can be combined and seen as a chromosome, each of which is one of the feasible solutions to a problem. However, traditional representation of GA does not work for scheduling problems (Etiler et al. [46]). In dealing with this condition, this study adopts the same method that a structure can describe the jobs as a sequence in the problem. To specify our approach, several initial sequences are adopted. In GA1, jobs are placed according to the shortest processing times (SPT) first rule. In GA2, jobs are arranged in earliest ready times (ERT) first rule. In GA3, jobs are arranged in a nondecreasing order on the sum of job processing times and ready times. Note that before performing GA, NEH algorithm (Nawaz et al. [47]) is utilized to improve the quality of the solutions obtained from the previous rules to reduce many idle periods. The process of GA1, GA2, and GA3 are different initial sequences and use the same selection, crossover, mutation operators, population size, and generations to obtain near-optimal solution. In addition, the fourth genetic algorithm, denoted as GA4, is the best one among GA1, GA2, and GA3; that is, G
A
4
=
min
⁡
⁡
{
G
A
1
,
G
A
2
,
G
A
3
}.In order to avoid rapidly observing a local optimum in a small population or consume more waiting time in a large one, this study set a suitable population size as 60(
N
=
60
) in a preliminary trial. It is also an important work to evaluate the fitness of selected chromosomes that each of the chromosomes is included or excluded from a feasible solution. The main goal of this study is to minimize the total completion time. Assume that S
i
(
t
) is the ith string in the ith generation and the total completion time of S
i
(
t
) is ∑
j
=
1
n
C
j
(
S
i
(
t
)
). Then, the fitness function of S
i
(
t
) can be represented as f
(
S
i
(
t
)
). Following are the calculations of the strings in fitness function:
(12)
f
(
S
i
(
t
)
)
=
ma
x
1
≤
l
≤
N
{
∑
j
=
1
n
C
j
(
S
l
(
t
)
)
}
-
∑
j
=
1
n
C
j
(
S
i
(
t
)
)
.
Moreover, it is also crucial work to ensure that the probability of selection for a sequence with lower value of the objective function is higher. Thus, the probability, P
(
S
i
(
t
)
), can be written as follows:
(13)
P
(
S
i
(
t
)
)
=
f
(
S
i
(
t
)
)
∑
i
=
1
n
f
(
S
i
(
t
)
)
.


#### 4.3.2. Operators

There are a few operators that are used in this study. Following are the descriptions of those operators, crossover, mutation, and selection.(a) Crossover.This is an operator that exchanges some of the genes of the selected parents, with the main concept being that the descendant can inherit the advantages of its parents. This study applied the linear order crossover operator (LOX) proposed by Falkenauer and Bouffouix [48] and is one of the better performers among the others (Etiler et al. [46]). The probability of crossover is set to 1.(b) Mutation.The main object of mutation is to achieve for an overall optimal solution and to avoid a locally optimal one. In this study, the mutation rates (
P
m
) are set at 0.10 based on our preliminary experiment as shown in Figure 1. For (
n
,
a
,
θ
,
N
,
g
)
=
(
20
,
-
0.05
,
0.5
,
60
,
100
n
), 100 sets of data were randomly generated to evaluate the performance of the proposed algorithms with varying values of P
m. The results showed that the proposed algorithms had the least mean error percentage at P
m
=
0.10.Figure 1
The performance of the genetic algorithms for variousP
m at (
n
,
a
,
θ
,
N
,
g
)
=
(
20
,
-
0.05
,
0.5
,
60
,
100
n
).(c) Selection.This is a process that determines the probability of each chromosome and is used to decide the better chromosomes with the better fitness value. The evolution implemented in our algorithm is based on the elitist list. We copy the best offspring and use them to generate some of the next generation. The rest of the offspring are generated from the parent chromosomes by the roulette wheel selection method, which can maintain the variety of genes.


#### 4.3.3. Stopping Criteria

In the preliminary experiment, the proposed GAs are terminated after100
*
n generations as shown in Figures 2 and 3. For (
n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
), the above 100 sets of randomly generated data were used to evaluate the performance of the proposed algorithms with varying values of g. The results showed that the least mean error percentage of the proposed algorithms would stabilize with reasonable CPU time range after g
=
100
n.Figure 2
The performance of the genetic algorithms for variousg at (n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
).Figure 3
The performance of the genetic algorithms for variousg at (
n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
).


## 4.1. Dominance Properties

Before presenting the adjacent pairwise interchange properties, we provide two lemmas, which will be used in the proofs of the properties in the sequel.Lemma 1.
Letf
(
x
)
=
1
+
a
x
(
1
-
x
)
a
-
1
-
(
1
+
x
)
a, then f
(
x
)
≥
0, for a
≤
0 and x
>
0.Lemma 2.
Letg
(
λ
)
=
(
λ
-
1
)
+
(
1
+
λ
x
)
a
-
λ
(
1
+
x
)
a, then g
(
λ
)
≥
0, for λ
≥
1, a
≤
0, and x
>
0.To fathom the searching tree, we develop some dominance properties based on a pairwise interchange of two adjacent jobsJ
i and J
j. Let S
=
(
π
,
J
i
,
J
j
,
π
′
) and S
′
=
(
π
,
J
j
,
J
i
,
π
′
) be two sequences in which π and π
′ denote partial sequences. To show that S dominates S
′, it suffices to show that C
i
(
S
)
+
C
j
(
S
)
≤
C
j
(
S
′
)
+
C
i
(
S
′
) and C
j
(
S
)
<
C
i
(
S
′
). In addition, let t be the completion time of the last job in subsequence π with (r
-
1) jobs.Property 1.
Ifp
i
<
p
j and max
⁡
{
r
i
,
r
j
}
≤
t, then S dominates S
′.Proof.
Sincemax
⁡
{
r
i
,
r
j
}
≤
t, we have
(1)
C
i
(
S
)
=
t
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
,
C
j
(
S
)
=
t
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
+
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
i
)
a
,
C
j
(
S
′
)
=
t
+
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
,
C
i
(
S
′
)
=
t
+
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
j
)
a
.
After taking the difference of (1), we have
(2)
C
i
(
S
′
)
-
C
j
(
S
)
=
(
p
j
-
p
i
)
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
j
)
a
-
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
i
)
a
.
On substituting λ
=
p
j
/
p
i, u
=
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
), and x
=
(
p
i
/
(
1
+
∑
l
=
1
n
p
l
)
) into (2) and simplifying it, we obtain
(3)
C
i
(
S
′
)
-
C
j
(
S
)
=
p
i
u
a
[
(
λ
-
1
)
+
(
1
+
λ
x
)
a
-
λ
(
1
+
x
)
a
]
.
By Lemma 2, with λ
>
1, a
≤
0, and x
>
0, we have C
i
(
S
′
)
-
C
j
(
S
)
>
0.
Moreover, after taking the difference of total completion times (TC) between sequencesS and S
′, we have
(4)
TC
(
S
′
)
-
TC
(
S
)
=
[
C
j
(
S
′
)
+
C
i
(
S
′
)
]
-
[
C
i
(
S
)
+
C
j
(
S
)
]
=
2
(
p
j
-
p
i
)
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
j
)
a
-
p
j
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
+
p
i
)
a
.
By (3), it can be easily shown that (4) is nonnegative for p
i
<
p
j. Therefore, S dominates S
′.The proofs of Properties2 to 5 are omitted since they are similar to that of Property 1.Property 2.
Ifr
i
≤
t
≤
r
j
≤
t
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a and p
i
<
p
j, then S dominates S
′.Property 3.
Ift
≥
r
i and t
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
<
r
j, then S dominates S
′.Property 4.
Ift
≤
r
i
≤
r
j, r
i
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
≥
r
j, and p
i
<
p
j, then S dominates S
′.Property 5.
Ift
≤
r
i and r
i
+
p
i
(
1
+
∑
l
=
1
r
-
1
p
[
l
]
)
a
<
r
j, then S dominates S
′.In order to further determine the ordering of the remaining unscheduled jobs to further speed up the searching process, we provide the following property. Assume thatS
=
(
π
,
π
c
) is a sequence of jobs where π is the scheduled part containing k jobs and π
c is the unscheduled part. Let S
1
=
(
π
,
π
′
) be the sequence in which the unscheduled jobs are arranged in a nondecreasing order of job processing times; that is, p
(
k
+
1
)
≤
p
(
k
+
2
)
≤
⋯
≤
p
(
n
).Property 6.
IfC
[
k
]
(
S
1
)
>
ma
x
j
∈
π
c
{
r
j
}, then S
1
=
(
π
,
π
′
) dominates sequences of the type (π
,
π
c) for any unscheduled sequence π
c.Proof.
SinceC
[
k
]
(
S
1
)
>
ma
x
j
∈
π
c
{
r
j
}, it implies that all the unscheduled jobs are ready to be processed on time C
[
k
]
(
S
1
). To obtain the optimal subsequence, let S
1
=
(
π
,
π
′
) be the sequence in which the unscheduled jobs are arranged in nondecreasing order of jobs processing times.


## 4.2. Lower Bounds

In this subsection, we develop two lower bounds by using the following lemma from Hardy et al. [39].Lemma 3.
Suppose thata
i and b
i are two sequences of numbers. The sum ∑
i
=
1
n
a
i
b
i of products of the corresponding elements is the least if the sequences are monotonic in the opposite sense.First, letP
S be a partial schedule in which the order of the first k jobs has been determined and let S be a complete schedule obtained from P
S. By definition, the completion time for the (
k
+
1
)
th job is
(5)
C
[
k
+
1
]
(
S
)
=
max
⁡
{
C
[
k
]
(
S
)
,
r
[
k
+
1
]
}
+
p
[
k
+
1
]
(
1
+
∑
l
=
1
k
p
[
l
]
)
a
≥
C
[
k
]
(
S
)
+
p
[
k
+
1
]
(
1
+
∑
l
=
1
k
p
[
l
]
)
a
.
Similarly, the completion time for the (
k
+
j
)
th job is
(6)
C
[
k
+
j
]
(
S
)
≥
C
[
k
]
(
S
)
+
∑
i
=
1
j
p
(
k
+
i
)
(
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
i
-
1
p
(
k
+
l
)
)
a
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
1
≤
j
≤
n
-
k
.
The first term on the right hand side of (6) is known, and a lower bound of the total completion time for the partial sequence P
S can be obtained by minimizing the second term. Since the value of (
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
i
-
1
p
[
k
+
l
]
)
a is a decreasing function of ∑
l
=
1
i
-
1
p
[
k
+
l
], the total completion time is minimized by sequencing the unscheduled jobs according to the shortest processing time (SPT) rule according to Lemma 3. Consequently, the first lower bound is
(7)
L
B
1
=
∑
i
=
1
k
C
[
i
]
(
S
)
+
∑
j
=
1
n
-
k
C
^
(
j
)
,
where C
^
(
j
)
=
C
[
k
]
(
S
)
+
∑
i
=
1
j
p
(
k
+
i
)
(
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
i
-
1
p
(
n
-
k
+
l
-
1
)
)
a. On the other hand, this lower bound may not be tight if the release time is long. To overcome this situation, a second lower bound is established by taking account of the release time. The completion time for the (k
+
1)th job is
(8)
C
[
k
+
1
]
(
S
)
=
max
⁡
{
C
[
k
]
(
S
)
,
r
[
k
+
1
]
}
+
p
[
k
+
1
]
(
1
+
∑
l
=
1
k
p
[
l
]
)
a
≥
r
[
k
+
1
]
(
S
)
+
p
[
k
+
1
]
(
1
+
∑
l
=
1
k
p
[
l
]
)
a
.
Similarly, the completion time for the (
k
+
j
)
th job is
(9)
C
[
k
+
j
]
(
S
)
≥
r
[
k
+
j
]
(
S
)
+
p
[
k
+
j
]
(
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
j
-
1
p
[
k
+
l
]
)
a
,
C
[
k
+
j
]
(
S
)
≥
r
[
k
+
j
]
(
S
)
+
p
[
k
+
j
]
C
[
k
+
j
]
(
S
)
≥
1
≤
j
≤
n
-
k
.
Note that C
[
k
+
j
]
(
S
) is greater than or equal to r
(
k
+
j
)
′, where r
(
k
+
1
)
′
≤
r
(
k
+
2
)
′
≤
⋯
≤
r
(
n
)
′ denote the release times of the unscheduled jobs arranged in a nondecreasing order. The second term on the right hand side of (9) is minimized by the SPT rule since (
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
j
-
1
p
[
k
+
l
]
)
a is a decreasing function of ∑
l
=
1
j
-
1
p
[
k
+
l
]. It follows that we have the following second lower bound:
(10)
L
B
2
=
∑
i
=
1
k
C
[
i
]
+
∑
j
=
1
n
-
k
C
~
(
j
)
,
where C
~
(
j
)
=
r
(
k
+
j
)
′
(
S
)
+
p
(
k
+
1
)
′
(
1
+
∑
l
=
1
k
p
[
l
]
+
∑
l
=
1
j
-
1
p
(
n
-
k
+
l
-
1
)
′
)
a. Note that p
(
k
+
j
)
′ and r
(
k
+
j
)
′ do not necessarily come from the same job. In order to make the lower bound tighter, we choose the maximum value from (7) and (10) as the lower bounds of P
S. That is,
(11)
LB
=
max
⁡
{
L
B
1
,
L
B
2
}
.


## 4.3. The Procedure of Genetic Algorithms

A genetic algorithm (GA) is an optimization method that mimics natural processes. GA was invented by Holland [40] and the most widely used to solve numerical optimization problems in a wide variety of application fields, including biology, economics, engineering, business, agriculture, telecommunications, and manufacturing. For example in Goldberg [41], authors using GA in engineering design problems is reviewed in Gen and Cheng [42]. Soolaki et al. [43] use a GA to solve an airline boarding problem with linear programming models [44, 45] and use genetic algorithms to optimize the parameters for the given test collections. GAs start evolving by generating an initial population of chromosomes. Then, a fitness function is used to compute the relative fitness of each chromosome of the population. The selection, crossover, and mutation operators are used in succession to create a new population of chromosomes for the next generation. This approach has gained increasing popularity in solving many combinatorial optimization problems in a wide variety of different disciplines.


### 4.3.1. Initial Settings

In a GA, every problem is presented by a code and each code is seen as a gene. The existing genes can be combined and seen as a chromosome, each of which is one of the feasible solutions to a problem. However, traditional representation of GA does not work for scheduling problems (Etiler et al. [46]). In dealing with this condition, this study adopts the same method that a structure can describe the jobs as a sequence in the problem. To specify our approach, several initial sequences are adopted. In GA1, jobs are placed according to the shortest processing times (SPT) first rule. In GA2, jobs are arranged in earliest ready times (ERT) first rule. In GA3, jobs are arranged in a nondecreasing order on the sum of job processing times and ready times. Note that before performing GA, NEH algorithm (Nawaz et al. [47]) is utilized to improve the quality of the solutions obtained from the previous rules to reduce many idle periods. The process of GA1, GA2, and GA3 are different initial sequences and use the same selection, crossover, mutation operators, population size, and generations to obtain near-optimal solution. In addition, the fourth genetic algorithm, denoted as GA4, is the best one among GA1, GA2, and GA3; that is, G
A
4
=
min
⁡
⁡
{
G
A
1
,
G
A
2
,
G
A
3
}.In order to avoid rapidly observing a local optimum in a small population or consume more waiting time in a large one, this study set a suitable population size as 60(
N
=
60
) in a preliminary trial. It is also an important work to evaluate the fitness of selected chromosomes that each of the chromosomes is included or excluded from a feasible solution. The main goal of this study is to minimize the total completion time. Assume that S
i
(
t
) is the ith string in the ith generation and the total completion time of S
i
(
t
) is ∑
j
=
1
n
C
j
(
S
i
(
t
)
). Then, the fitness function of S
i
(
t
) can be represented as f
(
S
i
(
t
)
). Following are the calculations of the strings in fitness function:
(12)
f
(
S
i
(
t
)
)
=
ma
x
1
≤
l
≤
N
{
∑
j
=
1
n
C
j
(
S
l
(
t
)
)
}
-
∑
j
=
1
n
C
j
(
S
i
(
t
)
)
.
Moreover, it is also crucial work to ensure that the probability of selection for a sequence with lower value of the objective function is higher. Thus, the probability, P
(
S
i
(
t
)
), can be written as follows:
(13)
P
(
S
i
(
t
)
)
=
f
(
S
i
(
t
)
)
∑
i
=
1
n
f
(
S
i
(
t
)
)
.


### 4.3.2. Operators

There are a few operators that are used in this study. Following are the descriptions of those operators, crossover, mutation, and selection.(a) Crossover.This is an operator that exchanges some of the genes of the selected parents, with the main concept being that the descendant can inherit the advantages of its parents. This study applied the linear order crossover operator (LOX) proposed by Falkenauer and Bouffouix [48] and is one of the better performers among the others (Etiler et al. [46]). The probability of crossover is set to 1.(b) Mutation.The main object of mutation is to achieve for an overall optimal solution and to avoid a locally optimal one. In this study, the mutation rates (
P
m
) are set at 0.10 based on our preliminary experiment as shown in Figure 1. For (
n
,
a
,
θ
,
N
,
g
)
=
(
20
,
-
0.05
,
0.5
,
60
,
100
n
), 100 sets of data were randomly generated to evaluate the performance of the proposed algorithms with varying values of P
m. The results showed that the proposed algorithms had the least mean error percentage at P
m
=
0.10.Figure 1
The performance of the genetic algorithms for variousP
m at (
n
,
a
,
θ
,
N
,
g
)
=
(
20
,
-
0.05
,
0.5
,
60
,
100
n
).(c) Selection.This is a process that determines the probability of each chromosome and is used to decide the better chromosomes with the better fitness value. The evolution implemented in our algorithm is based on the elitist list. We copy the best offspring and use them to generate some of the next generation. The rest of the offspring are generated from the parent chromosomes by the roulette wheel selection method, which can maintain the variety of genes.


### 4.3.3. Stopping Criteria

In the preliminary experiment, the proposed GAs are terminated after100
*
n generations as shown in Figures 2 and 3. For (
n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
), the above 100 sets of randomly generated data were used to evaluate the performance of the proposed algorithms with varying values of g. The results showed that the least mean error percentage of the proposed algorithms would stabilize with reasonable CPU time range after g
=
100
n.Figure 2
The performance of the genetic algorithms for variousg at (n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
).Figure 3
The performance of the genetic algorithms for variousg at (
n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
).


## 4.3.1. Initial Settings

In a GA, every problem is presented by a code and each code is seen as a gene. The existing genes can be combined and seen as a chromosome, each of which is one of the feasible solutions to a problem. However, traditional representation of GA does not work for scheduling problems (Etiler et al. [46]). In dealing with this condition, this study adopts the same method that a structure can describe the jobs as a sequence in the problem. To specify our approach, several initial sequences are adopted. In GA1, jobs are placed according to the shortest processing times (SPT) first rule. In GA2, jobs are arranged in earliest ready times (ERT) first rule. In GA3, jobs are arranged in a nondecreasing order on the sum of job processing times and ready times. Note that before performing GA, NEH algorithm (Nawaz et al. [47]) is utilized to improve the quality of the solutions obtained from the previous rules to reduce many idle periods. The process of GA1, GA2, and GA3 are different initial sequences and use the same selection, crossover, mutation operators, population size, and generations to obtain near-optimal solution. In addition, the fourth genetic algorithm, denoted as GA4, is the best one among GA1, GA2, and GA3; that is, G
A
4
=
min
⁡
⁡
{
G
A
1
,
G
A
2
,
G
A
3
}.In order to avoid rapidly observing a local optimum in a small population or consume more waiting time in a large one, this study set a suitable population size as 60(
N
=
60
) in a preliminary trial. It is also an important work to evaluate the fitness of selected chromosomes that each of the chromosomes is included or excluded from a feasible solution. The main goal of this study is to minimize the total completion time. Assume that S
i
(
t
) is the ith string in the ith generation and the total completion time of S
i
(
t
) is ∑
j
=
1
n
C
j
(
S
i
(
t
)
). Then, the fitness function of S
i
(
t
) can be represented as f
(
S
i
(
t
)
). Following are the calculations of the strings in fitness function:
(12)
f
(
S
i
(
t
)
)
=
ma
x
1
≤
l
≤
N
{
∑
j
=
1
n
C
j
(
S
l
(
t
)
)
}
-
∑
j
=
1
n
C
j
(
S
i
(
t
)
)
.
Moreover, it is also crucial work to ensure that the probability of selection for a sequence with lower value of the objective function is higher. Thus, the probability, P
(
S
i
(
t
)
), can be written as follows:
(13)
P
(
S
i
(
t
)
)
=
f
(
S
i
(
t
)
)
∑
i
=
1
n
f
(
S
i
(
t
)
)
.


## 4.3.2. Operators

There are a few operators that are used in this study. Following are the descriptions of those operators, crossover, mutation, and selection.(a) Crossover.This is an operator that exchanges some of the genes of the selected parents, with the main concept being that the descendant can inherit the advantages of its parents. This study applied the linear order crossover operator (LOX) proposed by Falkenauer and Bouffouix [48] and is one of the better performers among the others (Etiler et al. [46]). The probability of crossover is set to 1.(b) Mutation.The main object of mutation is to achieve for an overall optimal solution and to avoid a locally optimal one. In this study, the mutation rates (
P
m
) are set at 0.10 based on our preliminary experiment as shown in Figure 1. For (
n
,
a
,
θ
,
N
,
g
)
=
(
20
,
-
0.05
,
0.5
,
60
,
100
n
), 100 sets of data were randomly generated to evaluate the performance of the proposed algorithms with varying values of P
m. The results showed that the proposed algorithms had the least mean error percentage at P
m
=
0.10.Figure 1
The performance of the genetic algorithms for variousP
m at (
n
,
a
,
θ
,
N
,
g
)
=
(
20
,
-
0.05
,
0.5
,
60
,
100
n
).(c) Selection.This is a process that determines the probability of each chromosome and is used to decide the better chromosomes with the better fitness value. The evolution implemented in our algorithm is based on the elitist list. We copy the best offspring and use them to generate some of the next generation. The rest of the offspring are generated from the parent chromosomes by the roulette wheel selection method, which can maintain the variety of genes.


## 4.3.3. Stopping Criteria

In the preliminary experiment, the proposed GAs are terminated after100
*
n generations as shown in Figures 2 and 3. For (
n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
), the above 100 sets of randomly generated data were used to evaluate the performance of the proposed algorithms with varying values of g. The results showed that the least mean error percentage of the proposed algorithms would stabilize with reasonable CPU time range after g
=
100
n.Figure 2
The performance of the genetic algorithms for variousg at (n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
).Figure 3
The performance of the genetic algorithms for variousg at (
n
,
a
,
θ
,
N
,
P
m
)
=
(
20
,
-
0.05
,
0.5
,
60
,
0.10
).


## 5. Computational Experiment

A computational experiment was conducted to evaluate the efficiency of the branch-and-bound algorithm and the accuracies of the genetic algorithms. The algorithms were coded in Fortran and run on Compaq Visual Fortran version 6.6 on an Intel(R) Core(TM)2 Quad CPU 2.66 GHz with 4 GB RAM on Windows Vista. The experimental design followed Reeves [49] design. The job processing times were generated from a uniform distribution over the integers between 1 and 20 in every case, while the release times were generated from a uniform distribution over the integers on (
0
,
20
n
θ
), where n is the number of jobs. Five different sets of problem instances were generated by giving θ the values 1
/
n, 0.25, 0.5, 0.75, and 1.For the branch-and-bound algorithm, the average and the maximum numbers of nodes as well as the average and the maximum execution times (in seconds) were recorded. For the three genetic algorithms, the mean and the maximum error percentages were recorded, where the error percentage was calculated as(14)
(
G
A
i
-
T
C
*
)
T
C
*
*
100
%
,
where G
A
i
(
i
=
1,2
,
3,4
) is the total completion time obtained from the genetic algorithmand T
C
* is the total completion time of the optimal schedule. The computational times of the heuristic algorithms were not recorded since they were finished within a second.In the computational experiment, four different numbers of jobs(
n
=
12
,
16
,
20, and 24
), four different values of learning effect (
a
=
-
0.05
,
-
0.10
,
-
0.15, and  -
0.20
), and five different values of generation parameter of release times (
θ
=
1
/
n
,
0.25
,
0.5
,
0.75
,
and
1
) were tested in the branch-and-bound algorithm. As a consequence, 80 experimental situations were examined. A set of 20 instances were randomly generated for each situation and a total of 1600 problems were tested. The algorithms were set to skip to the next set of data if the number of nodes exceeded 108. The results are presented in Table 1 and Figures 4, 5, 6, and 7. Figures 4–7 showed the average number of nodes for various θ and a at job size 12, 16, 20, and 24, respectively. The average number of nodes decreased as the value of θ increased when n was greater than 16. This was the direct result of the efficiency of LB1 and LB2. As θ increased, the frequency of applications of LB2 would increase. Consequently, it would yield longer release times in those cases and the properties were more powerful. Moreover, LB1 is more efficient than LB2. Table 1 and Figures 4–7 also showed whether in job size, the algorithms had the least mean number of nodes at θ
=
1
/
n. It was due to the fact that with θ
=
1
/
n, the release time was relatively short and the completion time would readily exceed the release time. In those cases, Property 6 was applied more frequently; conversely, the completion time would not easily exceed the release time when the values of θ increased. Moreover, the number of nodes increased exponentially as the number of jobs increased, which was typical of an NP-hard problem. As illustrated in Table 1, when n
=
24, there were five cases in which the branch-and-bound algorithm could solve all the problems optimally larger than 1
0
8 nodes. The branch-and-bound algorithm had the worst performance when (
n
,
a
,
θ
)
=
(
24
,
-
0.05,0.25
) with 8.7
×
1
0
7 nodes and 5234 seconds. With θ fixed at 1
/
n, the decrease of the completion time would be relatively small at the beginning when the learning effectwas small (e.g., a
=
-
0.05). In other words, the completion time would easily exceed the release time which would expedite the timing of invoking Property 6 and consequently the average number of nodes would be smaller. With θ
=
0.25, as n increased, the corresponding least average number of nodes would occur at greater values of learning effect.Table 1
The performance of the branch- and-bound and genetic algorithms.
n
a
θ
Branch- and-bound algorithm
GA1
GA2
GA3
GA4
Node
CPU time
OF
Error  percentage
Mean
Max
Mean
Max
Mean
Max
Mean
Max
Mean
Max
Mean
Max
12
−0.05
1/n
42
385
0.0031
0.0156
20
0.0858
1.7151
0.0000
0.0000
0.0401
0.8013
0.0000
0.0000
0.25
549
1781
0.0187
0.0624
20
0.1055
2.1091
0.0142
0.2839
0.0000
0.0000
0.0000
0.0000
0.50
473
1189
0.0140
0.0312
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.75
414
1013
0.0125
0.0312
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
569
2427
0.0164
0.0624
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
−0.10
1/n
62
488
0.0023
0.0156
20
0.1646
2.0568
0.1617
2.0568
0.0000
0.0000
0.0000
0.0000
0.25
1047
4318
0.0312
0.1092
20
0.0044
0.0878
0.0044
0.0878
0.0283
0.5665
0.0000
0.0000
0.50
480
1321
0.0140
0.0468
20
0.0000
0.0000
0.0684
1.3676
0.0019
0.0373
0.0000
0.0000
0.75
786
5291
0.0203
0.1404
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
396
1382
0.0125
0.0468
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
−0.15
1/n
21
71
0.0016
0.0156
20
0.0206
0.4130
0.0000
0.0000
0.0360
0.4130
0.0000
0.0000
0.25
817
4363
0.0226
0.0936
20
0.0000
0.0000
0.0000
0.0000
0.1228
2.4567
0.0000
0.0000
0.50
493
1969
0.0148
0.0624
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.75
286
803
0.0094
0.0312
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
417
1259
0.0117
0.0312
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
−0.20
1/n
47
336
0.0023
0.0156
20
0.1295
2.5896
0.1295
2.5896
0.0003
0.0069
0.0000
0.0000
0.25
1091
6689
0.0289
0.1560
20
0.0106
0.2119
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.50
337
948
0.0109
0.0312
20
0.0314
0.6284
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.75
452
1121
0.0117
0.0312
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
319
1387
0.0086
0.0312
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
16
−0.05
1/n
74
365
0.0078
0.0312
20
0.2066
3.4518
0.2202
2.7743
0.1114
1.2163
0.0608
1.2163
0.25
39325
105847
2.0108
5.8188
20
0.4522
5.3071
0.1479
1.7548
0.0621
0.4629
0.0309
0.3126
0.50
18779
107488
0.8697
4.4616
20
0.0052
0.1035
0.0935
1.6983
0.0849
1.6983
0.0000
0.0000
0.75
22967
290574
0.9259
10.2025
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
5144
34260
0.2535
1.5288
20
0.0041
0.0811
0.0115
0.2306
0.0000
0.0000
0.0000
0.0000
−0.10
1/n
91
323
0.0086
0.0312
20
0.1813
3.4958
0.2368
2.7957
0.1906
1.9030
0.0000
0.0000
0.25
53237
291654
2.5826
12.7297
20
0.3151
2.5393
0.2824
2.1606
0.1918
2.1606
0.1271
2.1606
0.50
15022
193968
0.6778
8.1277
20
0.0616
1.0305
0.0154
0.3088
0.0154
0.3088
0.0000
0.0000
0.75
15144
197196
0.6474
8.0029
20
0.0000
0.0000
0.0000
0.0000
0.0006
0.0120
0.0000
0.0000
1.00
3403
9875
0.1794
0.4992
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
−0.15
1/n
118
1368
0.0101
0.1092
20
0.2462
4.5183
0.0431
0.6619
0.0103
0.2068
0.0000
0.0000
0.25
52185
484662
2.2994
19.0165
20
0.0762
0.8319
0.3212
3.7507
0.0969
1.0191
0.0418
0.8319
0.50
17808
101503
0.8221
4.6020
20
0.0740
0.7668
0.0356
0.6773
0.0574
0.6773
0.0339
0.6773
0.75
3763
16453
0.1997
0.8112
20
0.0000
0.0000
0.0000
0.0000
0.0067
0.1343
0.0000
0.0000
1.00
3882
14411
0.1911
0.7020
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
−0.20
1/n
200
828
0.0172
0.0624
20
0.1832
2.6781
0.3397
1.7660
0.3644
2.2420
0.0000
0.0000
0.25
25881
149925
1.1224
5.3664
20
0.0140
0.2772
0.0299
0.4614
0.0098
0.1922
0.0002
0.0034
0.50
11829
48284
0.5819
2.3556
20
0.0000
0.0000
0.0072
0.1431
0.0000
0.0000
0.0000
0.0000
0.75
2687
12382
0.1427
0.5928
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
2047
5258
0.1076
0.2340
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
20
−0.05
1/n
82
278
0.0156
0.0624
20
1.6268
7.4028
0.3538
6.9562
0.0113
0.2265
0.0000
0.0000
0.25
1319111
4407360
105.9941
322.4697
20
0.7803
2.9510
0.5928
3.2815
0.8700
4.2205
0.2480
1.5709
0.50
963361
9983475
61.8895
568.7017
20
0.0377
0.4016
0.1608
1.7464
0.2224
1.5708
0.0033
0.0510
0.75
323776
2518001
22.9485
183.1606
20
0.0022
0.0446
0.0000
0.0000
0.0027
0.0446
0.0000
0.0000
1.00
41188
138955
3.3642
11.1072
20
0.0017
0.0338
0.0017
0.0338
0.0000
0.0000
0.0000
0.0000
−0.10
1/n
1345
14123
0.1716
1.7317
20
0.6707
3.4958
0.4690
2.8787
0.4353
3.4958
0.0000
0.0000
0.25
2134707
16978059
154.3318
1204.4214
20
0.3845
2.3175
0.1848
0.6798
0.3536
2.1979
0.0460
0.2909
0.50
202434
1320363
15.6266
102.4927
20
0.0000
0.0000
0.0045
0.0786
0.0000
0.0000
0.0000
0.0000
0.75
67733
450297
5.5645
34.5229
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
30928
238389
2.6192
18.5483
20
0.0023
0.0462
0.0000
0.0000
0.0023
0.0462
0.0000
0.0000
−0.15
1/n
293
2224
0.0429
0.2964
20
0.1670
1.3088
0.1845
2.9345
0.1835
2.9345
0.0000
0.0000
0.25
1539138
7544291
103.9052
497.0186
20
0.4685
2.9738
0.1876
1.0582
0.2690
1.9134
0.0544
0.9353
0.50
235214
2737579
16.9066
192.0840
20
0.0046
0.0923
0.0032
0.0641
0.0073
0.1284
0.0000
0.0000
0.75
56901
281822
4.5716
22.5576
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
17992
51529
1.5163
3.6973
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
−0.20
1/n
698
4825
0.0991
0.6240
20
0.2436
1.5781
0.4239
4.0426
0.2224
1.5781
0.1927
1.5781
0.25
4348006
64668017
275.0735
4000.4590
20
0.1596
1.4118
0.0549
0.2968
0.2765
2.1869
0.0203
0.2249
0.50
107201
675811
8.0878
47.6895
20
0.0000
0.0000
0.0000
0.0000
0.0058
0.1155
0.0000
0.0000
0.75
31529
163854
2.5990
11.0918
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
15118
63845
1.3198
4.9453
20
0.0000
0.0000
0.0016
0.0324
0.0016
0.0318
0.0000
0.0000
24
−0.05
1/n
478
2082
0.1248
0.4836
20
0.4707
3.9003
0.2017
2.0990
0.1368
1.8118
0.0959
1.8118
0.25
43205517
87504444
5233.8760
10604.3535
13
0.4991
2.1418
0.6032
1.9032
0.4607
2.0265
0.2283
1.3231
0.50
11780220
66191783
1305.4869
6594.8027
19
0.0758
1.0456
0.0313
0.2363
0.1334
1.0456
0.0161
0.2363
0.75
1216867
4261994
156.2529
470.8125
20
0.0056
0.1126
0.0198
0.3359
0.0174
0.1871
0.0000
0.0000
1.00
888475
5439067
114.4057
692.4417
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
−0.10
1/n
1074
12050
0.2496
2.6364
20
0.7378
4.2545
0.3868
2.4023
0.2577
1.8340
0.0541
0.6057
0.25
24953166
53006630
2854.7095
6344.0156
11
0.4324
2.2382
0.5843
2.9043
0.6883
2.5478
0.3452
2.2382
0.50
3116322
31612798
366.1781
3815.9717
20
0.0137
0.1184
0.0087
0.0883
0.0075
0.1028
0.0000
0.0000
0.75
513685
2435858
67.2926
296.4331
20
0.0000
0.0000
0.0015
0.0306
0.0112
0.1371
0.0000
0.0000
1.00
270431
1462391
35.2609
196.0620
20
0.0000
0.0000
0.0052
0.1037
0.0039
0.0771
0.0000
0.0000
−0.15
1/n
674
2613
0.1693
0.6084
20
0.7280
7.8202
0.3115
2.7017
0.2512
3.4255
0.0284
0.5683
0.25
23417410
61951876
2538.7673
6371.3604
15
0.9250
3.3429
0.2948
1.2902
0.2232
1.7855
0.0499
0.4354
0.50
4118014
36622393
474.9373
3927.6216
20
0.0114
0.1193
0.0053
0.1058
0.0000
0.0000
0.0000
0.0000
0.75
661765
5958864
87.4869
792.0327
20
0.0073
0.1458
0.0075
0.1509
0.0043
0.0867
0.0000
0.0000
1.00
837932
11995859
96.8626
1324.4172
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
−0.20
1/n
3126
15554
0.7082
3.1980
20
0.1942
3.2396
0.4290
3.3146
0.3196
3.2396
0.1669
3.2396
0.25
9333827
72575949
999.3219
8068.2031
15
0.0589
0.2822
0.0646
0.7914
0.0844
0.7331
0.0204
0.2057
0.50
384242
2271989
50.8384
280.8486
20
0.0038
0.0760
0.0130
0.2596
0.0130
0.2596
0.0000
0.0000
0.75
570054
4053320
70.1732
531.1990
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
1.00
233727
1202819
29.1574
132.6006
20
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
Note: “OF” denotes the number of instances in 20 sets of data that can be solved in less than 108 nodes by using the branch- and-bound method.Figure 4
The performance of the branch-and-bound algorithms for variousθ and a at n
=
12.Figure 5
The performance of the branch-and-bound algorithms for variousθ and a at n
=
16.Figure 6
The performance of the branch-and-bound algorithms for variousθ and a at n
=
20.Figure 7
The performance of the branch-and-bound algorithms for variousθ and a at n
=
24.The performance of the proposed GA algorithms, out of the 80 evaluations and a total of 1600 problems, was tested. The number of times that each of the objective functions of the GA1, GA2, and GA3 algorithms had the smallest mean error percentage was 45, 41, and 49, respectively. In addition, in Table 1 and Figures 8, 9, and 10, their performances were not affected with the learning rate, the generation parameter θ of release times, or the number of jobs. None of the three genetic algorithms had absolutely dominant performance in terms of mean error percentage. However, the combined algorithm GA4 strikingly outperformed each of the three algorithms in terms of the maximum mean error percentage among all the 80 scenarios with varying learning rates, numbers of jobs, and values of θ. The maximum mean error percentages of GA1, GA2, GA3, and GA4 were 1.6268%, 0.6032%, 0.8700%, and 0.3452%, respectively. The maximum mean error percentage of GA1 was more than four times that of GA4. The combined algorithm GA4 also clearly outperformed each of the three algorithms in terms of the maximum error percentage. The worst cases of the corresponding algorithms were 7.8202%, 6.9562%, 4.2205%, and 3.2396%, respectively. The worst case error of GA1 was more than twice that of GA4. Thus, we would recommend the combined algorithm GA4.Figure 8
The performance of the genetic algorithms for variousn.Figure 9
The performance of the genetic algorithms for variousa.Figure 10
The performance of the genetic algorithms for variousθ.


## 6. Conclusions

In this paper, we address a single-machine total completion time problem with the sum of processing times based learning effect and release times. The objective is to minimize the total completion time. The problem without learning consideration is NP-hard one. Thus, we develop a branch-and-bound algorithm incorporating with several dominances and two lower bounds to derive optimal solution and genetic algorithms that was proposed to obtain near-optimal solutions, respectively.The branch-and-bound algorithm performs well to solve the instances of less than or equal to 24 jobs in a reasonable amount of time. In the different varying parameter, the proposed genetic algorithms are quite accurate for small size problems and the mean error percentage of the proposed genetic algorithms are less than 0.35%. Another interesting topic for future study is to consider and study the problem in the multimachine environments or multicriteria cases.



---

*Source: 249493-2014-03-04.xml*