# Two-Agent Single-Machine Scheduling of Jobs with Time-Dependent Processing Times and Ready Times

Authors: Jan-Yee Kung; Yuan-Po Chao; Kuei-I Lee; Chao-Chung Kang; Win-Chin Lin
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Scheduling involving jobs with time-dependent processing times has recently attracted much research attention. However, multiagent scheduling with simultaneous considerations of jobs with time-dependent processing times and ready times is relatively unexplored. Inspired by this observation, we study a two-agent single-machine scheduling problem in which the jobs have both time-dependent processing times and ready times. We consider the model in which the actual processing time of a job of the first agent is a decreasing function of its scheduled position while the actual processing time of a job of the second agent is an increasing function of its scheduled position. In addition, each job has a different ready time. The objective is to minimize the total completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We propose a branch-and-bound and several genetic algorithms to obtain optimal and near-optimal solutions for the problem, respectively. We also conduct extensive computational results to test the proposed algorithms and examine the impacts of different problem parameters on their performance.


---

## Body

## 1. Introduction

In many scheduling models researchers assume that the job processing times are known and fixed parameters. However, the job processing times can be prolonged due to deterioration or shortened due to learning over time in real-life situations. Browne and Yechiali [1] present fire-fighting as an example of job deterioration while Biskup [2] cites workers’ skill improvement as an example of job learning. Both examples and their corresponding situations are referred to as “time-dependent scheduling” in the literature.Time-dependent scheduling was first introduced by J. N. D. Gupta and S. K. Gupta [3] and Browne and Yechiali [1] for deterioration jobs, whereas by Biskup [2] for the learning effect. Since then, a lot of scheduling models involving job time-dependent processing times have been proposed from a variety of perspectives. For more detailed reviews of scheduling problems with deteriorating jobs, we refer the reader to Alidaee and Womer [4] and Cheng et al. [5], and for a detailed review of scheduling problems with learning effects, we refer the reader to Biskup [6]. More recently, scheduling research that considers both deteriorating jobs and learning effects has become popular. For details on this stream of scheduling research, the reader may refer to Wang [7], Wang and Cheng [8, 9], Wang and Liu [10], Wang and Guo [11], Zhang and Yan [12], Yang [13], and Zhu et al. [14], among others.In the past, the scheduling literature was dominated by studies that deal with a single criterion. In reality, jobs might come from several agents (customers) that have different requirements to meet. However, scheduling research in the multiple-agent setting involving jobs with time-dependent processing times is relatively unexplored. Among the few studies on this topic, Liu and Tang [15] studied multiagent scheduling with deteriorating jobs in which they assumed that the actual processing time of job Jj is δjt, where δj>0 and t denote the deteriorating rate and starting time of Jj, respectively. Liu et al. [16] considered two two-agent problems with position-dependent processing times. In the aging-effect model, they assumed that the actual processing time of Jj is pj+br (pj+bv) if it belongs to agent A(B). Meanwhile, in the learning-effect model, they assumed that the actual processing time of Jj is pj-br (pj-bv) if it belongs to agent A(B), where r (or v) denotes the job position and b,b>0, is the aging or learning effect. Cheng et al. [17] considered a two-agent scheduling problem in which they assumed that, given a schedule, the actual processing time of a job of the first agent is a function of position-based learning while the actual processing time of a job of the second agent is a function of position-based deterioration. 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. Wu et al. [18] studied two-agent scheduling in which the actual processing time of Jj is pj(1+∑l=1r-1p[l])a (pj(1+∑l=1r-1p[l])β) if it is a job of AG0 (AG1) scheduled in the rth position of a sequence. Their objective function is to find an optimal schedule to minimize ∑j=1nwjCj(S)(1-Ij), subject to max1≤j≤n{Lj(S)Ij}≤0. They proposed branch-and-bound and ant colony algorithms to solve the problem. However, they ignored job ready times. Wu et al. [19] considered a single-machine problem with the sum-of-processing time based learning effect and release times, where the objective is to minimize the total weighted completion time. They assumed that the actual processing time of job j is pjr=pj(1-∑l=1r-1p[l]/∑l=1npl)a if it is scheduled in the rth position, where a≥1 is a learning ratio common to all the jobs. They proposed a branch-and-bound algorithm and a genetic heuristic-based algorithm to treat the problem. Wu et al. [18] used a branch-and-bound and a ant colony algorithm to solve a two-agent scheduling with learning and deteriorating jobs. Lun et al. [20] and Zhang et al. [21] gave applications of multiagent scheduling of jobs with ready times in the shipping industry. Specifically, ships belonging to shipping companies (multiple agents) call at a port at different times. The port needs to find a suitable schedule to serve the ships. In this context, the port is the single machine and the arriving ships from different shipping companies are jobs belonging to different agents with ready times. Inspired by this and other applications, we study in this paper a two-agent single-machine scheduling problem in which the jobs have both time-dependent processing times and ready times. We consider the model in which the actual processing time of a job of the first agent is a decreasing function of its scheduled position while the actual processing time of a job of the second agent is an increasing function of its scheduled position. The objective is to minimize the total completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent.The remainder of this paper is organized as follows. We present the problem formulation in the next section. In Section3 we discuss the computational complexity of the problem. In Section 4 we develop some dominance properties and a lower bound to enhance the search efficiency for the optimal solution, followed by introducing a branch-and-bound and several genetic algorithms. In Section 5 we present the results of computational experiments conducted to assess the performance of the proposed algorithms. We conclude the paper and suggest some topics for future research in the last section.


## 2. Model Formulation

We formulate the scheduling problem under study as follows. There aren jobs for processing on a single machine. Each job Jj becomes available for processing at time rj≥0. Each job belongs to one of two agents, namely, AG0 and AG1. For job Jj, there is a normal processing time pj and an agent code Ij, where Ij=0 if Jj∈AG0 and Ij=1 if Jj∈AG1. We assume that all the jobs of AG0 have a position-based learning rate a with a≤0, while all the jobs of AG1 have a position-based deteriorating rate b with b≥0. Under the proposed model, the actual processing time of Jj is pjra (pjrb) if it belongs to AG0 (AG1) and is scheduled in position r of a sequence.For a given scheduleS, let Cj(S) be the completion time of Jj, and Uj(S)=1 if Cj(S)>dj and zero otherwise. The objective is to find an optimal schedule to minimize ∑j=1nCj(S)(1-Ij), subject to ∑j=1nUj(S)Ij=0. Adopting the three-field notation scheme α|β|γA:γB introduced by Agnetis et al. [22], we denote the problem as 1|rj,pjr=pjrx,x∈{a,b}|∑j=1nCj(S)(1-Ij):∑j=1nUj(S)Ij=0.As for the major results of research on multiagent scheduling without learning effects or deteriorating jobs, the reader may refer to Baker and Smith [23], Agnetis et al. [22], Yuan et al. [24], Cheng et al. [25, 26], Ng et al. [27], Agnetis et al. [28], Mor and Mosheiov [29, 30], Yin et al. [31, 32], and so forth.


## 3. Branch-and-Bound Algorithm

Due to the fact that our proposed problem is an NP-hard one (see [33]), in this section we apply the branch-and-bound technique to search for the optimal solution. In order to facilitate the searching process, we first develop some dominance properties, followed by presenting a lower bound to fathom the searching tree. We then present the procedures of branch-and-bound algorithm and suggest some heuristics.


### 3.1. Dominance Rules

Assume that scheduleS has two adjacent jobs Ji and Jj with Ji immediately preceding Jj. Perform a pairwise interchange of Ji and Jj to derive a new sequence S′. In addition, assume that Ji and Jj are in the rth and (r+1)th positions of S and that the starting time to process job Ji in S is t.Lemma 1.
IfJi,Jj∈AG0,rj≥max{ri,t}+pira, then S dominates S′.Proof.
The completion times of jobsJi and Jj in S and S′ are, respectively,
(1)Ci(S)=max{ri,t}+pira,Cj(S)=max{max{ri,t}+pira,rj}+pj(r+1)a,Cj(S′)=max{rj,t}+pjra,Ci(S′)=max{max{rj,t}+pjra,ri}+pi(r+1)a,
Fromrj≥max{ri,t}+pira, we have
(2)Ci(S′)>Cj(S′)=max{rj,t}+pjra>rj+pj(r+1)a=Cj(S)>Ci(S).
It follows that Ci(S′)+Cj(S′)>Cj(S)+Ci(S), so S dominates S′.Lemma 2.
IfJi,Jj∈AG0, max{ri,t}≤rj<max{ri,t}+pira and pi<pj, then S dominates S′.Proof.
By the assumption and Lemma1, the completion times of jobs Ji and Jj in S and S′ can be reformulated as
(3)Ci(S)=max{ri,t}+pira,Cj(S)=max{ri,t}+pira+pj(r+1)a,Cj(S′)=max{rj,t}+pjra,Ci(S′)=max{rj,t}+pjra+pi(r+1)a,
respectively. From max{ri,t}≤rj and pi<pj, it is easy to see that Ci(S′)>Cj(S) and Cj(S′)>Ci(S). It follows that S dominates S′.Lemma 3.
IfJi,Jj∈AG0, max{rj,t}≤ri<max{rj,t}+pjra, and (pj-pi)(ra-(r+1)a)≥ri-max{rj,t}, then S dominates S′.Proof.
The proof is similar to that of Lemma2.Lemma 4.
IfJi,Jj∈AG0, max{ri,rj}≤t, and pi<pj, then S dominates S′.Proof.
The proof is similar to that of Lemma2.Lemma 5.
IfJi,Jj∈AG1,max{ri,t}+pirb≤di<max{max{rj,t}+pjrb,ri}+pi(r+1)b, and max{max{ri,t}+pirb,rj}+pj(r+1)b≤dj, then S dominates S′.Proof.
The completion times of jobsJi and Jj in S and S′ are, respectively,
(4)Ci(S)=max{ri,t}+pirb,Cj(S)=max{max{ri,t}+pirb,rj}+pj(r+1)b,Cj(S′)=max{rj,t}+pjrb,Ci(S′)=max{max{rj,t}+pjrb,ri}+pi(r+1)b.
The given conditions lead toCi(S)≤di<Ci(S′) and Cj(S)≤dj, implying that schedule S′ is infeasible. Hence, S dominates S′.Lemma 6.
IfJi,Jj∈AG1 and max{max{rj,t}+pjrb,ri}+pi(r+1)b<max{max{ri,t}+pirb,rj}+pj(r+1)b≤min{di,dj}, then S dominates S′.Proof.
The given condition implies thatUi(S′)+Uj(S′)=Ui(S)+Uj(S)=0 and Ci(S′)>Cj(S), so S dominates S′.The proofs of Lemmas7 to 9 are omitted since they are similar to those of Lemmas 1 and 2.Lemma 7.
IfJi∈AG0,Jj∈AG1,ri<max{rj,t}+pjrb, and max{max{ri,t}+pira,rj}+pj(r+1)b≤min{max{rj,t}+pjrb+pi(r+1)a,dj}, then S dominates S′.Lemma 8.
IfJi∈AG1,Jj∈AG0 and max{ri,t}+pirb≤di<max{max{rj,t}+pjra,ri}+pi(r+1)b, then S dominates S′.Lemma 9.
IfJi∈AG1,Jj∈AG0 and max{ri,t}+pirb≤min{di,rj}, then S dominates S′.Next, we present two lemmas to determine the feasibility of a partial sequence. Let(π,π′) be a sequence of jobs where π is the scheduled part with k jobs and π′ is the unscheduled part. Moreover, let C[k] be the completion time of the last job in π.Lemma 10.
If there is a jobJj∈AG1∩π′ such that max{C[k],rj}+pj(k+1)b>dj, then sequence (π,π′) is not a feasible solution.Lemma 11.
If all the unscheduled jobs belong toAG0 and there exists a job Jj∈π′ such that max{C[k],rj}+pj(k+1)a≤rk for all job Jk∈π′∖{Jj}, then job Jj may be assigned to the (k+1)th position.Lemma 12.
If all the unscheduled jobs belong toAG0 and max{rj}Jj∈π′≤t, then the shortest processing time (SPT) rule gives an optimal sequence for the remaining unscheduled jobs.


### 3.2. A Lower Bound for1|rj,pjrA=pjAra,pjrB=pjBrb|∑CjA:∑UjB≤0

The efficiency of the branch-and-bound algorithm depends greatly on the lower bounds for the partial sequences. In this subsection we propose a lower bound. Let PS be a partial schedule in which the order of the firstk jobs is determined and US be the unscheduled part with (n-k) jobs, where there are n0 jobs belonging to AG0 and n1 jobs belonging to AG1 with n0+n1=n-k. Moreover, let p[j],r[j], and C[j] denote the normal processing time, release time, and completion time of the jth job in a sequence, respectively, where j={1,2,…,n}. A lower bound for the partial sequence PS is obtained by scheduling the jobs belonging to AG0 first in the SPT order and then scheduling the jobs belonging to AG1 in any order. Then the completion time of the (k+1)th job is
(5)C[k+1]=max{r[k+1],C[k]}+p[k+1](k+1)a≥C[k]+p[k+1]na.Similarly, the completion time for the(k+2)th job is
(6)C[k+1]=max{r[k+2],C[k+1]}+p[k+2](k+2)a≥C[k+1]+p[k+2]na.Continuing in this fashion, the completion time of the(k+l)th job is
(7)C[k+l]=max{r[k+l],C[k+l-1]}+p[k+l](k+l)a≥C[k+l-1]+p[k+l]na.Based on the above analysis, a lower bound for partial sequence PS can be calculated as follows.Algorithm 13.
Step  1. Sort the jobs of AG0 in nondecreasing order of their processing times, that is, p(1)≤p(2)≤⋯≤p(n0).
Step  2. Calculate C-[k+l]=C[k]+na∑j=1lp[k+j] for 1≤l≤n1.Therefore, a lower bound for the partial sequence PS is(8)LB1=∑j∈PSC[j](1-Ij)+∑l=1n1C-[k+l].However, this lower bound may not be tight if the release times are large. To overcome this situation, we propose a second lower bound by taking account of the ready times. By definition, the completion time of the(k+1)th job is
(9)C[k+1]=max{r[k+1],C[k]}+p[k+1](k+1)a≥r[k+1]+p[k+1]na.Similarly, the completion time for the(k+2)th job is
(10)C[k+1]=max{r[k+2],C[k+1]}+p[k+2](k+2)a≥r[k+2]+p[k+2]na.Continuing in this fashion, the completion time of the(k+l)th job is
(11)C[k+l]=max{r[k+l],C[k+l-1]}+p[k+l](k+l)a≥r[k+l]+p[k+l]na.Based on the above analysis, another lower bound for the partial sequence PS can be calculated as follows:(12)LB2=∑j∈PSC[j](1-Ij)+∑l=1n1(r[k+l]A+p[k+l]Ana).In order to make the lower bound tighter, we choose the maximum value between (8) and (12) as the lower bound for PS. That is,
(13)LB=max{LB1,LB2}.


### 3.3. Genetic Algorithms

Genetic algorithm (GA) is a meta-heuristic method that is commonly used to tackle combinatorial optimization problems [34]. A genetic algorithm starts with a set of feasible solutions (population) and iteratively replaces the current population by a new population. It requires a suitable encoding for the problem and a fitness function measures the quality of each encoded solution (chromosome or individual). The reproduction mechanism selects the parents and recombines them using a crossover operator to generate offspring that are submitted to a mutation operator in order to alter them locally [35]. The main steps of the GA are summarized in the following.


#### 3.3.1. Representation of Structure

In this paper we adopt a structure as a sequence of the jobs of the problem based on the method by Etiler et al. [36].


#### 3.3.2. Initial Population

To get the final solution more quickly, we construct the initial population by using three heuristics [37]. We propose the use of three initial sequences. We generate the first initial sequence by arranging the jobs of AG1 in the earliest due date (EDD) order, followed by arranging the jobs of AG0 in the smallest SPT order (recorded as GA1), followed by arranging the jobs of AG0 in the earliest ready times (ERT) first order (recorded as GA2), and followed by arranging the jobs of AG0 in the EDD order (recorded as GA3).


#### 3.3.3. Population Size

Following Chen et al. [38], we use an initial population as one schedule and create other members by applying interchange mutation until the number of members is equal to the population size. We set the population size (say, N) equal to the number of jobs (i.e., N=n) based on preliminary tests.


#### 3.3.4. Fitness Function

Given that the objective of the problem is to minimize the total completion time, we define the fitness function of the strings as follows:(14)f(Si(v))=max1≤l≤N{∑j=1nCj(Sl(v))}-∑j=1nCj(Si(v)),
where Si(v) is the ith string chromosome in the vth generation, ∑j=1nCj(Si(v)) is the total completion time of Si(v), and f(Si(v)) is the fitness function of Si(v). Therefore, the probability of selection of a schedule P(Si(v)) is to ensure that the probability of selection of a sequence with a lower value of the objective function is higher, which is defined as follows:
(15)P(Si(v))=f(Si(v))∑l=1Nf(Sl(v)).


#### 3.3.5. Crossover

Crossover is used to generate a new offspring from two parents. We adopt the partially matched crossover method, which is commonly used in GA [36]. In order to preserve the best schedule that has the minimum total completion time in each generation, we keep it to the next population with no change. This operation enables us to choose a higher crossover with the crossover rate Pc=1.


#### 3.3.6. Mutation

Mutation is used to prevent premature falling into a local optimal in the GA procedure. It can be considered as a transition from a current solution to its neighbourhood solution in a local search algorithm. In this study we set the mutation ratePm at 1.0 based on preliminary experiments.


#### 3.3.7. Selection

In this paper we fix the population sizes atn from generation to generation. Excluding the best schedule that has the minimum total completion time, the rest of the offspring are generated from the parent chromosomes by the roulette wheel method.


#### 3.3.8. Stopping Rule

We end the procedure of the GA after10*n generations based on preliminary experiments.


## 3.1. Dominance Rules

Assume that scheduleS has two adjacent jobs Ji and Jj with Ji immediately preceding Jj. Perform a pairwise interchange of Ji and Jj to derive a new sequence S′. In addition, assume that Ji and Jj are in the rth and (r+1)th positions of S and that the starting time to process job Ji in S is t.Lemma 1.
IfJi,Jj∈AG0,rj≥max{ri,t}+pira, then S dominates S′.Proof.
The completion times of jobsJi and Jj in S and S′ are, respectively,
(1)Ci(S)=max{ri,t}+pira,Cj(S)=max{max{ri,t}+pira,rj}+pj(r+1)a,Cj(S′)=max{rj,t}+pjra,Ci(S′)=max{max{rj,t}+pjra,ri}+pi(r+1)a,
Fromrj≥max{ri,t}+pira, we have
(2)Ci(S′)>Cj(S′)=max{rj,t}+pjra>rj+pj(r+1)a=Cj(S)>Ci(S).
It follows that Ci(S′)+Cj(S′)>Cj(S)+Ci(S), so S dominates S′.Lemma 2.
IfJi,Jj∈AG0, max{ri,t}≤rj<max{ri,t}+pira and pi<pj, then S dominates S′.Proof.
By the assumption and Lemma1, the completion times of jobs Ji and Jj in S and S′ can be reformulated as
(3)Ci(S)=max{ri,t}+pira,Cj(S)=max{ri,t}+pira+pj(r+1)a,Cj(S′)=max{rj,t}+pjra,Ci(S′)=max{rj,t}+pjra+pi(r+1)a,
respectively. From max{ri,t}≤rj and pi<pj, it is easy to see that Ci(S′)>Cj(S) and Cj(S′)>Ci(S). It follows that S dominates S′.Lemma 3.
IfJi,Jj∈AG0, max{rj,t}≤ri<max{rj,t}+pjra, and (pj-pi)(ra-(r+1)a)≥ri-max{rj,t}, then S dominates S′.Proof.
The proof is similar to that of Lemma2.Lemma 4.
IfJi,Jj∈AG0, max{ri,rj}≤t, and pi<pj, then S dominates S′.Proof.
The proof is similar to that of Lemma2.Lemma 5.
IfJi,Jj∈AG1,max{ri,t}+pirb≤di<max{max{rj,t}+pjrb,ri}+pi(r+1)b, and max{max{ri,t}+pirb,rj}+pj(r+1)b≤dj, then S dominates S′.Proof.
The completion times of jobsJi and Jj in S and S′ are, respectively,
(4)Ci(S)=max{ri,t}+pirb,Cj(S)=max{max{ri,t}+pirb,rj}+pj(r+1)b,Cj(S′)=max{rj,t}+pjrb,Ci(S′)=max{max{rj,t}+pjrb,ri}+pi(r+1)b.
The given conditions lead toCi(S)≤di<Ci(S′) and Cj(S)≤dj, implying that schedule S′ is infeasible. Hence, S dominates S′.Lemma 6.
IfJi,Jj∈AG1 and max{max{rj,t}+pjrb,ri}+pi(r+1)b<max{max{ri,t}+pirb,rj}+pj(r+1)b≤min{di,dj}, then S dominates S′.Proof.
The given condition implies thatUi(S′)+Uj(S′)=Ui(S)+Uj(S)=0 and Ci(S′)>Cj(S), so S dominates S′.The proofs of Lemmas7 to 9 are omitted since they are similar to those of Lemmas 1 and 2.Lemma 7.
IfJi∈AG0,Jj∈AG1,ri<max{rj,t}+pjrb, and max{max{ri,t}+pira,rj}+pj(r+1)b≤min{max{rj,t}+pjrb+pi(r+1)a,dj}, then S dominates S′.Lemma 8.
IfJi∈AG1,Jj∈AG0 and max{ri,t}+pirb≤di<max{max{rj,t}+pjra,ri}+pi(r+1)b, then S dominates S′.Lemma 9.
IfJi∈AG1,Jj∈AG0 and max{ri,t}+pirb≤min{di,rj}, then S dominates S′.Next, we present two lemmas to determine the feasibility of a partial sequence. Let(π,π′) be a sequence of jobs where π is the scheduled part with k jobs and π′ is the unscheduled part. Moreover, let C[k] be the completion time of the last job in π.Lemma 10.
If there is a jobJj∈AG1∩π′ such that max{C[k],rj}+pj(k+1)b>dj, then sequence (π,π′) is not a feasible solution.Lemma 11.
If all the unscheduled jobs belong toAG0 and there exists a job Jj∈π′ such that max{C[k],rj}+pj(k+1)a≤rk for all job Jk∈π′∖{Jj}, then job Jj may be assigned to the (k+1)th position.Lemma 12.
If all the unscheduled jobs belong toAG0 and max{rj}Jj∈π′≤t, then the shortest processing time (SPT) rule gives an optimal sequence for the remaining unscheduled jobs.


## 3.2. A Lower Bound for1|rj,pjrA=pjAra,pjrB=pjBrb|∑CjA:∑UjB≤0

The efficiency of the branch-and-bound algorithm depends greatly on the lower bounds for the partial sequences. In this subsection we propose a lower bound. Let PS be a partial schedule in which the order of the firstk jobs is determined and US be the unscheduled part with (n-k) jobs, where there are n0 jobs belonging to AG0 and n1 jobs belonging to AG1 with n0+n1=n-k. Moreover, let p[j],r[j], and C[j] denote the normal processing time, release time, and completion time of the jth job in a sequence, respectively, where j={1,2,…,n}. A lower bound for the partial sequence PS is obtained by scheduling the jobs belonging to AG0 first in the SPT order and then scheduling the jobs belonging to AG1 in any order. Then the completion time of the (k+1)th job is
(5)C[k+1]=max{r[k+1],C[k]}+p[k+1](k+1)a≥C[k]+p[k+1]na.Similarly, the completion time for the(k+2)th job is
(6)C[k+1]=max{r[k+2],C[k+1]}+p[k+2](k+2)a≥C[k+1]+p[k+2]na.Continuing in this fashion, the completion time of the(k+l)th job is
(7)C[k+l]=max{r[k+l],C[k+l-1]}+p[k+l](k+l)a≥C[k+l-1]+p[k+l]na.Based on the above analysis, a lower bound for partial sequence PS can be calculated as follows.Algorithm 13.
Step  1. Sort the jobs of AG0 in nondecreasing order of their processing times, that is, p(1)≤p(2)≤⋯≤p(n0).
Step  2. Calculate C-[k+l]=C[k]+na∑j=1lp[k+j] for 1≤l≤n1.Therefore, a lower bound for the partial sequence PS is(8)LB1=∑j∈PSC[j](1-Ij)+∑l=1n1C-[k+l].However, this lower bound may not be tight if the release times are large. To overcome this situation, we propose a second lower bound by taking account of the ready times. By definition, the completion time of the(k+1)th job is
(9)C[k+1]=max{r[k+1],C[k]}+p[k+1](k+1)a≥r[k+1]+p[k+1]na.Similarly, the completion time for the(k+2)th job is
(10)C[k+1]=max{r[k+2],C[k+1]}+p[k+2](k+2)a≥r[k+2]+p[k+2]na.Continuing in this fashion, the completion time of the(k+l)th job is
(11)C[k+l]=max{r[k+l],C[k+l-1]}+p[k+l](k+l)a≥r[k+l]+p[k+l]na.Based on the above analysis, another lower bound for the partial sequence PS can be calculated as follows:(12)LB2=∑j∈PSC[j](1-Ij)+∑l=1n1(r[k+l]A+p[k+l]Ana).In order to make the lower bound tighter, we choose the maximum value between (8) and (12) as the lower bound for PS. That is,
(13)LB=max{LB1,LB2}.


## 3.3. Genetic Algorithms

Genetic algorithm (GA) is a meta-heuristic method that is commonly used to tackle combinatorial optimization problems [34]. A genetic algorithm starts with a set of feasible solutions (population) and iteratively replaces the current population by a new population. It requires a suitable encoding for the problem and a fitness function measures the quality of each encoded solution (chromosome or individual). The reproduction mechanism selects the parents and recombines them using a crossover operator to generate offspring that are submitted to a mutation operator in order to alter them locally [35]. The main steps of the GA are summarized in the following.


### 3.3.1. Representation of Structure

In this paper we adopt a structure as a sequence of the jobs of the problem based on the method by Etiler et al. [36].


### 3.3.2. Initial Population

To get the final solution more quickly, we construct the initial population by using three heuristics [37]. We propose the use of three initial sequences. We generate the first initial sequence by arranging the jobs of AG1 in the earliest due date (EDD) order, followed by arranging the jobs of AG0 in the smallest SPT order (recorded as GA1), followed by arranging the jobs of AG0 in the earliest ready times (ERT) first order (recorded as GA2), and followed by arranging the jobs of AG0 in the EDD order (recorded as GA3).


### 3.3.3. Population Size

Following Chen et al. [38], we use an initial population as one schedule and create other members by applying interchange mutation until the number of members is equal to the population size. We set the population size (say, N) equal to the number of jobs (i.e., N=n) based on preliminary tests.


### 3.3.4. Fitness Function

Given that the objective of the problem is to minimize the total completion time, we define the fitness function of the strings as follows:(14)f(Si(v))=max1≤l≤N{∑j=1nCj(Sl(v))}-∑j=1nCj(Si(v)),
where Si(v) is the ith string chromosome in the vth generation, ∑j=1nCj(Si(v)) is the total completion time of Si(v), and f(Si(v)) is the fitness function of Si(v). Therefore, the probability of selection of a schedule P(Si(v)) is to ensure that the probability of selection of a sequence with a lower value of the objective function is higher, which is defined as follows:
(15)P(Si(v))=f(Si(v))∑l=1Nf(Sl(v)).


### 3.3.5. Crossover

Crossover is used to generate a new offspring from two parents. We adopt the partially matched crossover method, which is commonly used in GA [36]. In order to preserve the best schedule that has the minimum total completion time in each generation, we keep it to the next population with no change. This operation enables us to choose a higher crossover with the crossover rate Pc=1.


### 3.3.6. Mutation

Mutation is used to prevent premature falling into a local optimal in the GA procedure. It can be considered as a transition from a current solution to its neighbourhood solution in a local search algorithm. In this study we set the mutation ratePm at 1.0 based on preliminary experiments.


### 3.3.7. Selection

In this paper we fix the population sizes atn from generation to generation. Excluding the best schedule that has the minimum total completion time, the rest of the offspring are generated from the parent chromosomes by the roulette wheel method.


### 3.3.8. Stopping Rule

We end the procedure of the GA after10*n generations based on preliminary experiments.


## 3.3.1. Representation of Structure

In this paper we adopt a structure as a sequence of the jobs of the problem based on the method by Etiler et al. [36].


## 3.3.2. Initial Population

To get the final solution more quickly, we construct the initial population by using three heuristics [37]. We propose the use of three initial sequences. We generate the first initial sequence by arranging the jobs of AG1 in the earliest due date (EDD) order, followed by arranging the jobs of AG0 in the smallest SPT order (recorded as GA1), followed by arranging the jobs of AG0 in the earliest ready times (ERT) first order (recorded as GA2), and followed by arranging the jobs of AG0 in the EDD order (recorded as GA3).


## 3.3.3. Population Size

Following Chen et al. [38], we use an initial population as one schedule and create other members by applying interchange mutation until the number of members is equal to the population size. We set the population size (say, N) equal to the number of jobs (i.e., N=n) based on preliminary tests.


## 3.3.4. Fitness Function

Given that the objective of the problem is to minimize the total completion time, we define the fitness function of the strings as follows:(14)f(Si(v))=max1≤l≤N{∑j=1nCj(Sl(v))}-∑j=1nCj(Si(v)),
where Si(v) is the ith string chromosome in the vth generation, ∑j=1nCj(Si(v)) is the total completion time of Si(v), and f(Si(v)) is the fitness function of Si(v). Therefore, the probability of selection of a schedule P(Si(v)) is to ensure that the probability of selection of a sequence with a lower value of the objective function is higher, which is defined as follows:
(15)P(Si(v))=f(Si(v))∑l=1Nf(Sl(v)).


## 3.3.5. Crossover

Crossover is used to generate a new offspring from two parents. We adopt the partially matched crossover method, which is commonly used in GA [36]. In order to preserve the best schedule that has the minimum total completion time in each generation, we keep it to the next population with no change. This operation enables us to choose a higher crossover with the crossover rate Pc=1.


## 3.3.6. Mutation

Mutation is used to prevent premature falling into a local optimal in the GA procedure. It can be considered as a transition from a current solution to its neighbourhood solution in a local search algorithm. In this study we set the mutation ratePm at 1.0 based on preliminary experiments.


## 3.3.7. Selection

In this paper we fix the population sizes atn from generation to generation. Excluding the best schedule that has the minimum total completion time, the rest of the offspring are generated from the parent chromosomes by the roulette wheel method.


## 3.3.8. Stopping Rule

We end the procedure of the GA after10*n generations based on preliminary experiments.


## 4. Computational Results

We carried out computational experiments to assess the performance of proposed branch-and-bound and genetic algorithms over a range of problem parameters. We coded all the algorithms in FORTRAN using Compaq Visual Fortran version 6.6 and conducted the experiments on a personal computer powered by an Intel Pentium(R) Dual-Core CPU E6300 @ 2.80 GHz with 2 GB RAM operating under Windows XP. We generated the job processing times from a uniform distributionU(1,100). Following the design of Reeves [37], we generated the ready times of the jobs from another uniform distribution U(0,20nλ), where n is the number of jobs and λ is a control parameter. In our tests we set the value of λ at 1/n, 0.25, 0.5, 0.75, and 1. In addition, following the design of Fisher [39], we generated the due dates of the jobs of AG1 from a uniform distribution T×U(1-τ-R/2,1+τ+R/2), where T is the sum of the normal processing times of the n jobs; that is, T=∑i=1npi, τ took the values 0.25 and 0.5, while R took the values 0.25, 0.5, and 0.75. We fixed the proportion of the jobs of agent AG1 at pro=0.5 in the experiments.For the branch-and-bound algorithm, we recorded the average and maximum numbers of nodes, as well as the average (mean) and maximum of the execution times (in seconds). For the proposed GA algorithms, we recorded the mean and maximum percentage errors. We calculate the percentage error of a solution produced by a heuristic algorithm as(16)V-V*V*×100%,
where V and V* are the total completion time of the heuristic and the optimal solution of the jobs of the first agent, respectively. We did not record the computational times of the GA algorithms because they all were less one second to obtain a solution.We carried out the computational experiments in two parts. For the first part of the experiments, we tested instances of the problem atn=14 and 16. Moreover, we took three different values of the learning effect 70%, 80%, and 90% (corresponding to α=-0.515,-0.322,and-0.152, resp.) and three different values of the deteriorating effect 70%, 80%, and 90% (corresponding to β = 0.515, 0.322, and 0.152, resp.). We randomly tested a set of 100 instances for each case. As a result, we examined 54,000 instances. The instances with numbers of nodes few than 108 were recorded as instance solved or IS. We further extracted the relative results to report in the following.As regards the performance of the branch-and-bound algorithm, we see from Figures1, 2, 3, 4, 5, and 6 that the number of nodes declines as the value of λ, τ, or R increases no matter whether n=14 or 16. The reason is due to the fact that our proposed dominance rules and lower bound are more effective at a bigger value of λ, τ, or R.Figure 1
The behavior ofλ at n=14.Figure 2
The behavior ofλ at n=16.Figure 3
The behavior ofτ at n=14.Figure 4
The behavior ofτ at n=16.Figure 5
The behavior ofR at n=14.Figure 6
The behavior ofR at n=16.We observe from Figures7 and 8 the performance trend of the learning effect. As shown in Figures 9 and 10, the instances with larger deteriorating values are easier to solve than those with smaller deteriorating values.Figure 7
The behavior ofa at n=14.Figure 8
The behavior ofa at n=16.Figure 9
The behavior ofβ at n=14.Figure 10
The behavior ofβ at n=16.We also see that the branch-and-bound algorithm generates more nodes for instances with a bigger value ofλ, τ, or R. This also implies that the number of IS at a bigger value of λ, τ, or R is higher than that at a smaller value (i.e., see Figures 11 and 12).Figure 11
The behavior of IS asλ changes at n=14.Figure 12
The behavior of IS asλ changes at n=16.Moreover, Figures13 and 14 show that the instances with a weaker learning effect are easier to solve than those with a stronger learning effect, whereas Figures 15 and 16 show that the deteriorating effect keeps the same trend of IS. The performance of the branch-and-bound algorithm in terms of CPU time over the range of problem parameters tested is similar to that in terms of number of nodes generated.Figure 13
The behavior of IS asa changes at n=14.Figure 14
The behavior of IS asa changes at n=16.Figure 15
The behavior of IS asβ changes at n=14.Figure 16
The behavior of IS asβ changes at n=16.For the performance of the GA heuristics, Figures17, 18, and 19 show that when n=14, the mean percentage errors of GA1, GA2, and GA3 are within the ranges 4.3%–4.7%, 3.7%–4.1%, and 3.75%–3.95%, respectively, regardless of value of λ. Since all the GAs only take less than a second of CPU time to obtain a solution, we further take min{GAi,i=1,2,3} as GA*.Figure 17
The behavior of GA1 as λ varies.Figure 18
The behavior of GA2 as λ varies.Figure 19
The behavior of GA3 as λ varies.We observe from Figure20 that the mean percentage error of GA* declines to within the range 2.3%–2.7%. When n=14, Figures 21, 22, 23, and 24 show that at a bigger value of τ (τ=0.5), GA1, GA2, GA3, and GA* yield smaller percentage errors than at a smaller value of τ (τ=0.25); however, Figures 25, 26, 27, and 28 show that at a smaller value of R, GA1, GA2, GA3, and GA* yield smaller percentage errors than at a bigger value of R.Figure 20
The behavior of GA* asλ varies.Figure 21
The behavior of GA1 as τ varies.Figure 22
The behavior of GA2 as τ varies.Figure 23
The behavior of GA3 as τ varies.Figure 24
The behavior of GA* asτ varies.Figure 25
The behavior of GA1 as R varies.Figure 26
The behavior of GA2 as R varies.Figure 27
The behavior of GA3 as R varies.Figure 28
The behavior of GA* asR varies.As regards the impacts of learning or deteriorating on the proposed GAs, Figures29, 30, 31, and 32 show that all the GAs perform better at a weaker learning effect than a stronger one, but the performance reverses under the deteriorating effect as shown in Figures 33, 34, 35, and 36.Figure 29
The behavior of GA1 as a varies.Figure 30
The behavior of GA2 as a varies.Figure 31
The behavior of GA3 as a varies.Figure 32
The behavior of GA* asa varies.Figure 33
The behavior of GA1 as β varies.Figure 34
The behavior of GA2 as β varies.Figure 35
The behavior of GA3 as β varies.Figure 36
The behavior of GA* asβ varies.Overall, we observe from Figures37 and 38 that the grand means of the mean error percentages of GA2 and GA3 are smaller than those of GA1 when n=12 and 16, respectively.Figure 37
The behavior of GAs atn=14.Figure 38
The behavior of GAs atn=16.The result also shows that GA* performs well and keeps about 3% of the grand means of the mean error percentages, which is clearly lower than those of GA1, GA2, and GA3.In the second part of the experiments, we further assessed the performance of the proposed GA algorithms in solving instances with large numbers of jobs. We setn at 30 and 40 and fixed the parameters as follows: τ took the values of 0.25 and 0.5, while R took the values of 0.25, 0.50, and 0.75. We fixed the proportion of the jobs of agent AG1 at pro=0.5 in the experiments. We set the learning effect at 70%, 80%, and 90% (corresponding to α = −0.515, −0.322, and −0.152, resp.) and the values of the deteriorating effect at 70%, 80%, and 90% (corresponding to β = 0.515, 0.322, and 0.152, resp.). We randomly generated a set of 100 instances for each situation. As a result, we examined 270 experimental situations. For each GA heuristic, we calculate its relative percentage deviation as
(17)RPD=GAi-GA*GA*×100%,
where GAi is the objective function value generated by the GA heuristic and GA*=min{GAi,i=1,2,3} is the GA heuristic that yields the smallest objective function value among the three GA algorithms. We recorded the average and maximum RPD, and the mean execution time for each heuristic. The results are summarized in the following figures.As shown in Figures39, 40, and 41, we observe that the RPD mean of GA1 is in general smaller than those of GA2 and GA3. The effects of a,β,R, and τ are similar to those with smaller numbers of jobs.Figure 39
The behavior of GA1 as λ varies.Figure 40
The behavior of GA2 as λ varies.Figure 41
The behavior of GA3 as λ varies.Overall, we observe from Figures42 and 43 that the grand mean of the RPD of GA1 is smaller than that of GA2 and GA3. The result also shows that GA2 and GA3 slightly outperform GA1 with smaller numbers of jobs, but the result is reversed with larger numbers of jobs. This implies that there is no absolute dominance relationship among three GAs. Thus, we recommend that the GA* be used in order to attain stability and good quality solutions.Figure 42
The behavior of GAs atn=30.Figure 43
The behavior of GAs atn=40.


## 5. Conclusions

In this paper we study a two-agent single-machine scheduling problem with simultaneous considerations of deteriorating jobs, learning effects, and ready times. To search for optimal and near-optimal solutions, we propose a branch-and-bound algorithm incorporated with some dominance rules and a lower bound and three genetic algorithms, respectively.The computational results show that our proposed branch-and-bound algorithm can solve instances with up to 16 jobs with reasonable numbers of nodes and execution times. In addition, the computational experiments reveal that the proposed GA* does well in terms of efficiency and solution quality. Future research may consider other scheduling criteria or study the problem in the multimachine setting.



---

*Source: 806325-2013-07-24.xml*