# Single Machine Problem with Multi-Rate-Modifying Activities under a Time-Dependent Deterioration

Authors: M. Huang; Huaping Wu; Vincent Cho; W. H. Ip; Xingwei Wang; C. K. Ng
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The single machine scheduling problem with multi-rate-modifying activities under a time-dependent deterioration to minimize makespan is studied. After examining the characteristics of the problem, a number of properties and a lower bound are proposed. A branch and bound algorithm and a heuristic algorithm are used in the solution, and two special cases are also examined. The computational experiments show that, for the situation with a rate-modifying activity, the proposed branch and bound algorithm can solve situations with 50 jobs within a reasonable time, and the heuristic algorithm can obtain the near-optimal solution with an error percentage less than 0.053 in a very short time. In situations with multi-rate-modifying activities, the proposed branch and bound algorithm can solve the case with 15 jobs within a reasonable time, and the heuristic algorithm can obtain the near-optimal with an error percentage less than 0.070 in a very short time. The branch and bound algorithm and the heuristic algorithm are both shown to be efficient and effective.


---

## Body

## 1. Introduction

In the classical deterministic scheduling problems, job processing times are supposed to be constant; however, it is not the case for all industrial processes, for example, in cleaning assignments, fire fighting, steel production, and so on. A job that is processed later takes more time than when it is processed earlier, and the phenomenon is known as scheduling with deterioration jobs [1].J. N. D. Gupta and S. K. Gupta [1] and Browne and Yechiali [2] first proposed the job deterioration scheduling problem, and since then, it has been extensively studied. For instance, Wang et al. present a single machine scheduling problem with deteriorating jobs, where the jobs are subject to several constraints. They proved that minimizing the makespan and the total weighted completion time can be determined in polynomial time [3]. Cheng and Sun considered the problem with a linear deteriorating function [4] and showed that several related problems are NP-hard and used dynamic programming for solution [4]. Yan et al. studied a single machine scheduling problem with the effects of deteriorating and learning based on group consumption, in which the actual processing time of a job is a function of the starting time and position in the group [5]. Wang and Cheng addressed the machine scheduling problem with deterioration and learning effects simultaneously and gave polynomial solutions for single machine problems [6]. Ng et al. also studied the problem of scheduling n deteriorating jobs with release dates on a single machine [7]. These studies all focused on linear deteriorating jobs. A few papers refer to nonlinear deterioration jobs. Kuo and Yang introduced a single machine with a time-dependent learning effect based on the notion that the more the one practices, the better the one learns [8]. In this regard, jobs processed later need less time than that for normal processing due to the learning effect. They defined a time-dependent learning effect as follows. Let pir be the actual processing time of Ji(i=1,2,…,n) if it is scheduled in position r in a sequence. a[r] is the normal processing time of a job if scheduled in the rth position of a sequence. ai is the normal (sequence-independent) processing time of job Ji. Namely,
(1)pir=(1+a[1]+a[2]+⋯+a[r-1])bai=(1+∑s=1r-1a[s])bai,
where b≤0 and b is a constant learning index. According to the time-dependent learning effect introduced by Kuo and Yang [8], Wang et al. considered the single machine scheduling problem with a time-dependent deterioration [9]. They defined the actual processing times as follows:
(2)pir=(1+a[1]+a[2]+⋯+a[r-1])bai=(1+∑s=1r-1a[s])bai,
where b≥0 is a constant deterioration index. They showed that a single machine problem can be solved polynomially under the proposed model. Bank et al. addressed two machine scheduling problems with deterioration effects in which the actual job processing time was a function of its starting time [10]. Sun et al. considered flow shop scheduling problems with deteriorating jobs in which the actual job processing time was defined as a function of its start time [11].On the other hand, if the machine is stopped for maintenance, it can change from a subnormal production state to a normal one [12, 13]. Therefore, a scheduling model in a realistic environment should consider machine maintenance [12]. For example, in electronic assembly lines, Lee and Leon first considered the single machine scheduling problem with a rate-modifying activity (RMA) [13]. They solved problems with a number of objective functions by polynomial and pseudopolynomial algorithms. Later, Lodree et al. introduced human characteristics into scheduling models [14]. Motivated by the rate-modifying activity, Lodree and Christopher integrated a rate-modifying activity into machine environments [15] and assumed that the processing time of each job is 1 and followed a variation of simple linear deterioration.The concept of deterioration effects and maintenance activities has been mentioned in a few publications in the literature. However, there are no research results on scheduling models with time-dependent deterioration jobs in which the normal processing job times are arbitrary and multi-RMAs. Hence, the main contribution of this paper was two aspects: one is for jobs with arbitrary normal processing time and nonlinear deterioration, and the other is for multi-RMAs.The remaining sections of this paper are organized as follows. In Section2, the problem is formulated. In Section 3, the branch and bound and the heuristic algorithm are proposed for solving single machine makespan minimization problem with an RMA, under nonlinear time-dependent deterioration, and a special case of this problem is given. In Section 4, similar ideas are used to solve the problem of single machine makespan minimization with multi-RMAs under a nonlinear time-dependent deterioration, and a special case is also given. The numerical experiments are described in Section 5, followed by the conclusions in the last section.


## 2. Problem Formulation and Notation

This paper studies the single machine scheduling problem with an RMA or multi-RMAs under a time-dependent deterioration to minimize the makespan. More formally, this problem can be described as follows.Assume that there aren independent jobs J={1,2,…,n} to be processed nonpreemptively on a single machine which is available at time 0. The release times of all jobs are 0. The normal processing time of each job i(i∈J) is ai. If it is scheduled in position r(1≤r≤n) in a given sequence, then the normal processing time can be denoted as a[r]. The deterioration rate b(b>0) is a constant. The actual processing time of job i is pir if it is scheduled in position r(1≤r≤n) in a given sequence. pir is a function of the normal processing times of all jobs before it; that is, pir=(1+a[1]+a[2]+⋯+a[r-1])bai. To decrease the deterioration effect, an RMA with duration t (i.e., maintenance time) needs to be considered and inserted in a certain position km(m=1,2,…,M,1≤M≤n,1≤km≤n) in a sequence; namely, the RMA is assigned before the kmth job (such as in Figure 1), where M denotes the number of RMAs inserted in the sequence. After the RMA, the machine can be fully restored [14], and the actual processing time of the first job after it is the normal processing time of the job. When multi-RMAs are inserted in a sequence, the actual processing time of a job i can be denoted as follows:
(3)pir={[1+a[1]+a[2]+⋯+a[r-1]]bair=1,2,…,k1-1[1+a[k1]+a[k1+1]+⋯+a[r-k1]]bair=k1,…,k2-1⋮[1+a[km]+a[km+1]+⋯+a[r-km]]bair=km,…,km+1⋮[1+a[kM]+a[kM+1]+⋯+a[r-kM]]bair=kM,…,n.Figure 1
The position of maintenance times.The objective is to jointly find the number of RMAs and positions of each RMA and an optimal scheduleS* to minimize the makespan Cmax. Specifically, when M=1, the objective is to jointly find a position k for inserting an RMA and the optimal schedule S* to minimize the makespan Cmax.In this study, we consider the problem of minimizing the makespan with an RMA or multi-RMAs on a single machine under a time-dependent deterioration. We denote them as1|pir,rm|Cmax and 1|pir,mrm|Cmax, respectively, by using the three-field notation scheme α|β|γ introduced by Graham et al. [16], where rm represents inserting an RMA and mrm denotes multi-RMAs for modifying the processing rate of the machine.


## 3. The Problem of1|pir,rm|Cmax

Here, the single machine problem with assigning an RMA in a sequence under a time-dependent deterioration is considered. Firstly, several preliminaries are proposed in Section3.1, followed by the branch and bound algorithm and heuristic algorithm in Sections 3.2 and 3.3, respectively. Finally, a special case is described.


### 3.1. Preliminaries

In this subsection, several properties and a lower bound are proposed for solving the problem of1|pir,rm|Cmax.For convenience, assume thatS={π,rm,π′} is a full schedule, in which π and π′ are partial sequences, and set amax=maxi=1n{ai} and amin=maxi=1n{ai}. Based on these values, the following properties and lemmas are proposed.Property 1.
It is never optimal to schedule an RMA in the first sequence positionk=1 (similar to Lodree et al. [14]).Property 2.
If an RMA is assigned in a given positionk and the elements in π and π′ are known, then there is an optimal schedule obtained by sequencing jobs in a nondecreasing order of ai in π and π′, respectively.Proof.
If an RMA is assigned in a given positionk, the elements in π and π′ are known, and the release times of all jobs are 0. Hence, minimizing makespan of the schedule S is equal to minimizing the makespan of π and π′, respectively.
Firstly, we prove how to order jobs inπ so as to minimize the makespan of π. Assume that π={Q,i,j,Q′} with job i in the rth position and job j in the (r+1)th position. The completion time of the last job in Q is tQ, and the sum of the normal processing times of jobs in Q is P, and 0<ai<aj. Also  π-={Q,j,i,Q′} is obtained from exchanging the position i and j in π.
According to the above statement, the completion time of jobj in π is as follows:
(4)Cj(π)=tQ+ai(1+P)b+aj(1+P+a[r])b=tQ+ai(1+P)b+aj(1+P+ai)b.
The completion time of jobi in π- is:
(5)Ci(π-)=tQ+aj(1+P)b+ai(1+P+a[r])b=tQ+aj(1+P)b+ai(1+P+aj)b.
Setδ=1+P, λ=ai/aj, and μ=aj/δ, then
(6)Cj(π)-Ci(π-)=(ai-aj)(1+P)b+aj(1+P+ai)b-ai(1+P+aj)b=(ai-aj)δb+aj(δ+ai)b-ai(δ+aj)b.
Sinceδ=1+P≠0, the two sides of (6) are divided by δb, then
(7)Cj(π)-Ci(π-)δb=(ai-aj)+aj(1+aiδ)b-ai(1+ajδ)b=(λaj-aj)+aj(1+λajδ)b-λaj(1+ajδ)b=aj(λ-1)+aj(1+λμ)b-λaj(1+μ)b=aj[λ-1+(1+λμ)b-λ(1+μ)b]=aj[λ(1-(1+μ)b)-(1-(1+λμ)b)].
Setf(λ)=λ(1-(1+μ)b)-(1-(1+λμ)b), and the first derivative of f(λ) is
(8)f′(λ)=1-(1+μ)b-bμ(1+λμ)b-1.
Since0<ai<aj and 0<λ<1, clearly f′(λ)<0; that is, f(λ) is a decreasing function for λ∈(0,1), then f(λ)<f(0)=0.
Equation (7) can be expressed as
(9)Cj(π)-Ci(π-)δb=ajf(λ)<0.
If the two sides of (9) are multiplied by δb, then
(10)Cj(π)-Ci(π-)<0.
That is, Cj(π)<Ci(π-), so there is an optimal schedule obtained by sequencing jobs in nondecreasing order of ai in π.
Similarly, we also can prove that there is an optimal schedule obtained by sequencing jobs in nondecreasing order ofai in π′.
Therefore, if an RMA is assigned in a given positionk, and the elements in π and π′ are known, there is an optimal schedule obtained by sequencing jobs in nondecreasing order of ai in π and π′, respectively.Property 3.
For a given scheduleS={π,rm,π′}, and a new schedule S′={π′,rm,π} is obtained by changing π with π′, Cmax(S)=Cmax(S′).Proof.
Since the job processing times after an RMA are not dependent on that of jobs before the RMA and the makespan is equal to the sum of the completion time of the last job inπ and that of the last job in π′, therefore the makespan has nothing to do with the order of π and π′.According to the above properties, the following two lemmas can be obtained.Lemma 1.
If an RMA is scheduled in the second position (the last position) in a full scheduleS and the normal processing time of the first job (the last job) in π (π′) is not equal to amax, then there is an optimal solution S* with which the normal processing time of the last job in π′ (π) is amax.Lemma 2.
If an RMA is scheduled in the second position (the last position) in a full scheduleS and the normal processing time of the first job (the last job) in π (π′) is not equal to amin, then there is an optimal solution S* with which the normal processing time of the first job in π′ (π) is amin.The two lemmas can be easily determined from the above two properties; hence, their proofs are not included in the paper.In the following, the lower bound is presented according to the completion time.For the scheduleS, when r+1<k, the completion time of the (r+1)th job is
(11)C[r+1](S)=C[r](S)+a[r+1](1+a[1]+a[2]+⋯+a[r])b.According to a similar deduction, whenr+l<k, the completion time of the (r+l)th job is
(12)C[r+l](S)=C[r+l-1](S)+a[r+l](1+a[1]+a[2]+⋯+a[r+l-1])b=C[r](S)+∑i=1la[r+i](1+∑j=1r+i-1a[j])b≥C[r](S)+∑i=1la[r+i].
When r+l=k, the completion time of the kth job is C[k](S)≥C[r](S)+∑i=1k-r-1a[r+i]+t+a[k].Whenr+l>k, the completion time of the (r+l)th job is C[r+l](S)≥C[r](S)+∑i=1la[r+i]+t.Similarly, whenr+l=n, the completion time of the nth job is C[n](S)≥C[r](S)+∑i=1n-ra[r+i]+t. That is, the makespan of schedule S is
(13)Cmax(S)≥C[r](S)+∑i=1n-ra[r+i]+t.
Therefore, the lower bound is
(14)LB=C[r](S)+∑i=1n-ra[r+i]+t.


### 3.2. The Branch and Bound Algorithm

The branch and bound algorithm mainly uses a backtracking method, which incorporates a system with jumping characteristics. The former adapts the depth first search strategy to start from a root node to the whole solution space. When the algorithm searches any node in the solution space tree, it needs to judge whether the subtree of the node as a root contains solutions of the problem or not. If not, it will jump over all the subtrees of the node as a root and then backtrack to its father node step by step. Otherwise, it continues to search for its subtrees. If a whole sequence is obtained and its objective value is less than the current one, then it will replace the current one. These reflect the method using jumping characteristics. Moreover, since the backtracking method only records a current sequence and its lower bound, it makes the storage space become small, to a great extent. In this paper, the depth first search and the lower bound are adopted in the branch and bound procedure, respectively. Dominance properties and the lower bound are used for eliminating a node which does not satisfy the solutions of the problem. The primary procedure of the branch and bound algorithm is described as follows.Step 1 (the position of the RMA).
Set the initial position of the RMAk=2.Step 2 (initial solution).
Obtain an initial solution according to the short processing time rule.Step 3 (branching).
Search the whole solution space tree according to the depth first search strategy.Step 4 (eliminating).
Apply the properties and lemmas in Section3.1 to eliminate the dominant partial sequences.Step 5 (calculating).
Calculate the lower bound for the partial sequences. If it is less than the current optimal solution, continue to search in its branches. When a whole sequence is obtained, replace the current optimal sequence with it. Otherwise, eliminate it, and go to Step6.Step 6 (backtracking).
Backtrack to the father node of the current node and continue to search for other branches.Step 7 (stopping).
Repeat Steps3 to 5 until no more nodes can be searched, then set k=k+1, and go to Step 3.Obtain the makespanCBR* of an optimal solution from the above steps. Then, in the case without scheduling an RMA, compute the makespan CNR* of a sequence by ordering the normal job processing time using the short processing time (SPT) rule, compare CNR* with CR*, and select the smallest value between of them.


### 3.3. A Heuristic Algorithm

Since the branch and bound algorithm takes a long time for a large size and cannot be accepted, a heuristic algorithm is proposed for obtaining the near-optimal solution to a problem. To understand easily, firstly, we give a heuristic algorithm for the problem1|pir,rm|Cmax.Based on the above Property2 and Lemma 1, a heuristic algorithm is proposed. The main idea is to order the normal job processing time according to the SPT rule. Then, for each job with a current maximum normal processing time in set A, we try to determine where it is scheduled, in π or π′. The details of the heuristic algorithm are as follows. Assume that S*={π,rm,π′} and π and π′ are empty.Step 1.
Obtain a sequenceA={J[1],J[2],…,J[n]} by ordering the normal processing time of jobs using the SPT rule.Step 2.
Select the job with the largest normal processing timeamax=maxai∈A{ai} added to π and eliminate amax from set A.Step 3.
Select the job with the largest normal processing timeamax=maxai∈A{ai} adding to π′ and eliminate amax from the set A.Step 4.
Select the job with the largest normal processing timeamax=maxai∈A{ai} inserted before all jobs in π, eliminate amax from the set A, and calculate the makespan C′(S*). Then, eliminate amax from π, insert it before all jobs in π′, and calculate the makespan C′′(S*).Step 5.
CompareC′(S*) and C′′(S*), and if C′(S*)<C′′(S*), eliminate amax from π′ and insert it before all jobs in π. Otherwise, go to Step 6.Step 6.
Repeat Steps4 to 5 until A=ϕ. At this time, the algorithm stops.Obtain the makespanCHR* of an optimal solution from the above steps. Then, in the case without scheduling an RMA, compute the makespan CNR* of a sequence by ordering the normal job processing time using the short processing time (SPT) rule, compare CNR* with CHR*, and select the smallest one of them.It is easy to see the normal job processing time ordered by the SPT rule in Step1. The job with the largest normal processing time is assigned in π in Step 2. The job with the second largest normal processing time is assigned in π′ in Step 3. In Steps 4 and 5, the job with the current largest normal processing time in set A is assigned in π or π′ according to Property 2 and Lemma 1. The stopping condition of the algorithm is given in Step 6.In order to better understand the details of the heuristic algorithm, an example is given.Example 3.
Consider thatn=5, a1=2, a2=5, a3=3, a4=6, and a5=1. The deterioration rate is b=2, and the duration of the RMA is t=2.For solving, we have the following.(1)
According to the SPT rule, obtain a sequenceA={5,1,3,2,4}, π=Φ, and π′=Φ. Go to Step 2.(2)
Job4 with the largest normal processing time amax=6, add it to π and eliminate it from the set A, then π={4}, A={5,1,3,2} and π′=Φ. Go to Step 3.(3)
Job2 with the largest normal processing time amax=5; add it to π′ and eliminate it from the set A; then π={4}, A={5,1,3}, and π′={2}. Go to Step 4.(4)
Job3 with the largest normal processing time amax=3. Firstly, insert job 3 before all jobs in π; then π={3,4}, A={5,1}, and π′={2}. Calculate the makespan C′=3+6(1+3)2+2+5=106. Secondly, eliminate job 3 from π, insert job 3 before all jobs in π′, then π={4}, A={5,1} and π′={3,2}. Calculate the makespan C′′=6+2+3+5(1+3)2=91. Go to Step 5.(5)
SinceC′>C′′, then π={4}, A={5,1}, and π′={3,2}. Go to Step 6.(6)
SinceA≠Φ, go to Step 4.(7)
Job1 with the largest normal processing time amax=2. Firstly, insert job 1 before all jobs in π, then π={1,4}, A={5}, and π′={3,2}. Calculate the makespan C′=141. Secondly, eliminate the job 1 from π, insert job 1 before all jobs in π′, then π={4}, A={5}, and π′={1,3,2}. Calculate the makespan C′′=217. Go to Step 5.(8)
SinceC′<C′′, eliminate job 1 from π′, and insert it before all jobs in π again; then π={1,4}, A={5}, and π′={3,2}. Go to Step 6.(9)
SinceA≠Φ, go to Step 4.(10)
Job5 is the only one in A. Firstly, insert job 5 before all jobs in π, then π={5,1,4}, A=Φ, and π′={3,2}. Calculate the makespan C′=190. Secondly, eliminate job 5 from π, insert job 5 before all jobs in π′, then π={1,4}, A=Φ, and π′={5,3,2}. Calculate the makespan C′′=196. Go to Step 5.(11)
SinceC′<C′′, eliminate job 5 from π′, and insert it before all jobs in π again, then π={5,1,4}, A=Φ and π′={3,2}. Go to Step 6.(12)
SinceA=Φ, the algorithm stops, CHR*=C′=190. Compute the makespan CNR*=1166 of a sequence by ordering the normal job processing time using the short processing time (SPT) rule in the case without scheduling an RMA. Clearly, an optimal schedule is obtained from the heuristic algorithm.


### 3.4. The Special Case1|pir,rm,ai=a|Cmax

This subsection considers the special case1|pir,rm,ai=a|Cmax, where the normal processing time for all jobs is a.In a given sequence, while an RMA is inserted in positionk, the makespan can be expressed as follows:
(15)Cmax(k)=a+a(1+a)b+⋯+a(1+(k-2)a)b+t+a+a(1+a)b+⋯+a(1+(n-k)a)b.Clearly, the makespan is related to the sequence positionk. The problem can be solved by determining the value k to minimize (15). To determine the value k, we propose the following properties.Property 4.
(a) For an oddn and 1<k≤n, it has Cmax((n+1)/2)=Cmax((n+1)/2+1); and if k<(n+1)/2, then Cmax(k)>Cmax(k+1); if k>(n+1)/2, then Cmax(k)<Cmax(k+1).
(b) For an evenn and 1<k≤n, if k<n/2, then Cmax(k)>Cmax(k+1); if k>n/2+1, then Cmax(k)<Cmax(k+1).Proof.
(a) When the RMA is scheduled in the sequence positionk and k+1, the makespan can be expressed as follows:
(16)Cmax(k)=p+p(1+p)b+⋯+p(1+(k-2)p)b+t+p+p(1+p)b+⋯+p(1+(n-k)p)b,Cmax(k+1)=p+p(1+p)b+⋯+p(1+(k-2)p)b+p(1+(k-1)p)b+t+p+p(1+p)b+⋯+p(1+(n-k-1)p)b,Cmax(k)-Cmax(k+1)=p[(1+(n-k)p)b-(1+(k-1)p)b],Cmax(n+12)-Cmax(n+12+1)=0.
That is, Cmax((n+1)/2)=Cmax((n+1)/2+1).
Ifk<(n+1)/2 and p>0, we have (1+(n-k)p)b>(1+(k-1)p)b, Cmax(k)>Cmax(k+1).
Ifk>(n+1)/2 and p>0, we have (1+(n-k)p)b<(1+(k-1)p)b, Cmax(k)<Cmax(k+1).
The proof for (b) is analogous.Theorem 4.
The optimal policy for scheduling an RMA of lengtht under a time-dependent deterioration with b≥0 for all jobs is as follows. If n is an odd integer and t<p∑i=0(n-1)/2[(1+((n+1)/2-1+i)p)b-(1+ip)b], assign the RMA to sequence position k*=(n+1)/2 or k*=(n+1)/2+1. If n is an even integer and t<p∑i=0n/2-1[(1+(n/2+i)p)b-(1+ip)b], assign the RMA to sequence position k*=n/2+1. Otherwise, do not schedule the RMA.Proof.
(For an oddn). Based on Property 4, we have
(17)Cmax(n+12)<Cmax(n+12-1)<⋯<Cmax(2),Cmax(n+12+1)<Cmax(n+12+2)<⋯<Cmax(n).
Since Cmax((n+1)/2)=Cmax((n+1)/2+1), (17) imply that the minimum makespan occurs when k*=(n+1)/2 or k*=(n+1)/2+1.
LetCmax(k>n) represent the makespan without scheduling an RMA. Thus the RMA is scheduled only if Cmax(k*)<Cmax(k>n); that is,
(18)Cmax(n+12)=p+p(1+p)b+⋯+p(1+(n+12-2)p)b+t+p+p(1+p)b+⋯+p(1+(n-n+12)p)b,Cmax(k>n)=p+p(1+p)b+⋯+p(1+(n-1)p)b.
Since Cmax(k*)<Cmax(k>n), then t<p∑i=0(n-1)/2[(1+((n+1)/2-1+i)p)b-(1+ip)b].
Again, an analogous proof holds ifn is an even integer. This concludes the proof.


## 3.1. Preliminaries

In this subsection, several properties and a lower bound are proposed for solving the problem of1|pir,rm|Cmax.For convenience, assume thatS={π,rm,π′} is a full schedule, in which π and π′ are partial sequences, and set amax=maxi=1n{ai} and amin=maxi=1n{ai}. Based on these values, the following properties and lemmas are proposed.Property 1.
It is never optimal to schedule an RMA in the first sequence positionk=1 (similar to Lodree et al. [14]).Property 2.
If an RMA is assigned in a given positionk and the elements in π and π′ are known, then there is an optimal schedule obtained by sequencing jobs in a nondecreasing order of ai in π and π′, respectively.Proof.
If an RMA is assigned in a given positionk, the elements in π and π′ are known, and the release times of all jobs are 0. Hence, minimizing makespan of the schedule S is equal to minimizing the makespan of π and π′, respectively.
Firstly, we prove how to order jobs inπ so as to minimize the makespan of π. Assume that π={Q,i,j,Q′} with job i in the rth position and job j in the (r+1)th position. The completion time of the last job in Q is tQ, and the sum of the normal processing times of jobs in Q is P, and 0<ai<aj. Also  π-={Q,j,i,Q′} is obtained from exchanging the position i and j in π.
According to the above statement, the completion time of jobj in π is as follows:
(4)Cj(π)=tQ+ai(1+P)b+aj(1+P+a[r])b=tQ+ai(1+P)b+aj(1+P+ai)b.
The completion time of jobi in π- is:
(5)Ci(π-)=tQ+aj(1+P)b+ai(1+P+a[r])b=tQ+aj(1+P)b+ai(1+P+aj)b.
Setδ=1+P, λ=ai/aj, and μ=aj/δ, then
(6)Cj(π)-Ci(π-)=(ai-aj)(1+P)b+aj(1+P+ai)b-ai(1+P+aj)b=(ai-aj)δb+aj(δ+ai)b-ai(δ+aj)b.
Sinceδ=1+P≠0, the two sides of (6) are divided by δb, then
(7)Cj(π)-Ci(π-)δb=(ai-aj)+aj(1+aiδ)b-ai(1+ajδ)b=(λaj-aj)+aj(1+λajδ)b-λaj(1+ajδ)b=aj(λ-1)+aj(1+λμ)b-λaj(1+μ)b=aj[λ-1+(1+λμ)b-λ(1+μ)b]=aj[λ(1-(1+μ)b)-(1-(1+λμ)b)].
Setf(λ)=λ(1-(1+μ)b)-(1-(1+λμ)b), and the first derivative of f(λ) is
(8)f′(λ)=1-(1+μ)b-bμ(1+λμ)b-1.
Since0<ai<aj and 0<λ<1, clearly f′(λ)<0; that is, f(λ) is a decreasing function for λ∈(0,1), then f(λ)<f(0)=0.
Equation (7) can be expressed as
(9)Cj(π)-Ci(π-)δb=ajf(λ)<0.
If the two sides of (9) are multiplied by δb, then
(10)Cj(π)-Ci(π-)<0.
That is, Cj(π)<Ci(π-), so there is an optimal schedule obtained by sequencing jobs in nondecreasing order of ai in π.
Similarly, we also can prove that there is an optimal schedule obtained by sequencing jobs in nondecreasing order ofai in π′.
Therefore, if an RMA is assigned in a given positionk, and the elements in π and π′ are known, there is an optimal schedule obtained by sequencing jobs in nondecreasing order of ai in π and π′, respectively.Property 3.
For a given scheduleS={π,rm,π′}, and a new schedule S′={π′,rm,π} is obtained by changing π with π′, Cmax(S)=Cmax(S′).Proof.
Since the job processing times after an RMA are not dependent on that of jobs before the RMA and the makespan is equal to the sum of the completion time of the last job inπ and that of the last job in π′, therefore the makespan has nothing to do with the order of π and π′.According to the above properties, the following two lemmas can be obtained.Lemma 1.
If an RMA is scheduled in the second position (the last position) in a full scheduleS and the normal processing time of the first job (the last job) in π (π′) is not equal to amax, then there is an optimal solution S* with which the normal processing time of the last job in π′ (π) is amax.Lemma 2.
If an RMA is scheduled in the second position (the last position) in a full scheduleS and the normal processing time of the first job (the last job) in π (π′) is not equal to amin, then there is an optimal solution S* with which the normal processing time of the first job in π′ (π) is amin.The two lemmas can be easily determined from the above two properties; hence, their proofs are not included in the paper.In the following, the lower bound is presented according to the completion time.For the scheduleS, when r+1<k, the completion time of the (r+1)th job is
(11)C[r+1](S)=C[r](S)+a[r+1](1+a[1]+a[2]+⋯+a[r])b.According to a similar deduction, whenr+l<k, the completion time of the (r+l)th job is
(12)C[r+l](S)=C[r+l-1](S)+a[r+l](1+a[1]+a[2]+⋯+a[r+l-1])b=C[r](S)+∑i=1la[r+i](1+∑j=1r+i-1a[j])b≥C[r](S)+∑i=1la[r+i].
When r+l=k, the completion time of the kth job is C[k](S)≥C[r](S)+∑i=1k-r-1a[r+i]+t+a[k].Whenr+l>k, the completion time of the (r+l)th job is C[r+l](S)≥C[r](S)+∑i=1la[r+i]+t.Similarly, whenr+l=n, the completion time of the nth job is C[n](S)≥C[r](S)+∑i=1n-ra[r+i]+t. That is, the makespan of schedule S is
(13)Cmax(S)≥C[r](S)+∑i=1n-ra[r+i]+t.
Therefore, the lower bound is
(14)LB=C[r](S)+∑i=1n-ra[r+i]+t.


## 3.2. The Branch and Bound Algorithm

The branch and bound algorithm mainly uses a backtracking method, which incorporates a system with jumping characteristics. The former adapts the depth first search strategy to start from a root node to the whole solution space. When the algorithm searches any node in the solution space tree, it needs to judge whether the subtree of the node as a root contains solutions of the problem or not. If not, it will jump over all the subtrees of the node as a root and then backtrack to its father node step by step. Otherwise, it continues to search for its subtrees. If a whole sequence is obtained and its objective value is less than the current one, then it will replace the current one. These reflect the method using jumping characteristics. Moreover, since the backtracking method only records a current sequence and its lower bound, it makes the storage space become small, to a great extent. In this paper, the depth first search and the lower bound are adopted in the branch and bound procedure, respectively. Dominance properties and the lower bound are used for eliminating a node which does not satisfy the solutions of the problem. The primary procedure of the branch and bound algorithm is described as follows.Step 1 (the position of the RMA).
Set the initial position of the RMAk=2.Step 2 (initial solution).
Obtain an initial solution according to the short processing time rule.Step 3 (branching).
Search the whole solution space tree according to the depth first search strategy.Step 4 (eliminating).
Apply the properties and lemmas in Section3.1 to eliminate the dominant partial sequences.Step 5 (calculating).
Calculate the lower bound for the partial sequences. If it is less than the current optimal solution, continue to search in its branches. When a whole sequence is obtained, replace the current optimal sequence with it. Otherwise, eliminate it, and go to Step6.Step 6 (backtracking).
Backtrack to the father node of the current node and continue to search for other branches.Step 7 (stopping).
Repeat Steps3 to 5 until no more nodes can be searched, then set k=k+1, and go to Step 3.Obtain the makespanCBR* of an optimal solution from the above steps. Then, in the case without scheduling an RMA, compute the makespan CNR* of a sequence by ordering the normal job processing time using the short processing time (SPT) rule, compare CNR* with CR*, and select the smallest value between of them.


## 3.3. A Heuristic Algorithm

Since the branch and bound algorithm takes a long time for a large size and cannot be accepted, a heuristic algorithm is proposed for obtaining the near-optimal solution to a problem. To understand easily, firstly, we give a heuristic algorithm for the problem1|pir,rm|Cmax.Based on the above Property2 and Lemma 1, a heuristic algorithm is proposed. The main idea is to order the normal job processing time according to the SPT rule. Then, for each job with a current maximum normal processing time in set A, we try to determine where it is scheduled, in π or π′. The details of the heuristic algorithm are as follows. Assume that S*={π,rm,π′} and π and π′ are empty.Step 1.
Obtain a sequenceA={J[1],J[2],…,J[n]} by ordering the normal processing time of jobs using the SPT rule.Step 2.
Select the job with the largest normal processing timeamax=maxai∈A{ai} added to π and eliminate amax from set A.Step 3.
Select the job with the largest normal processing timeamax=maxai∈A{ai} adding to π′ and eliminate amax from the set A.Step 4.
Select the job with the largest normal processing timeamax=maxai∈A{ai} inserted before all jobs in π, eliminate amax from the set A, and calculate the makespan C′(S*). Then, eliminate amax from π, insert it before all jobs in π′, and calculate the makespan C′′(S*).Step 5.
CompareC′(S*) and C′′(S*), and if C′(S*)<C′′(S*), eliminate amax from π′ and insert it before all jobs in π. Otherwise, go to Step 6.Step 6.
Repeat Steps4 to 5 until A=ϕ. At this time, the algorithm stops.Obtain the makespanCHR* of an optimal solution from the above steps. Then, in the case without scheduling an RMA, compute the makespan CNR* of a sequence by ordering the normal job processing time using the short processing time (SPT) rule, compare CNR* with CHR*, and select the smallest one of them.It is easy to see the normal job processing time ordered by the SPT rule in Step1. The job with the largest normal processing time is assigned in π in Step 2. The job with the second largest normal processing time is assigned in π′ in Step 3. In Steps 4 and 5, the job with the current largest normal processing time in set A is assigned in π or π′ according to Property 2 and Lemma 1. The stopping condition of the algorithm is given in Step 6.In order to better understand the details of the heuristic algorithm, an example is given.Example 3.
Consider thatn=5, a1=2, a2=5, a3=3, a4=6, and a5=1. The deterioration rate is b=2, and the duration of the RMA is t=2.For solving, we have the following.(1)
According to the SPT rule, obtain a sequenceA={5,1,3,2,4}, π=Φ, and π′=Φ. Go to Step 2.(2)
Job4 with the largest normal processing time amax=6, add it to π and eliminate it from the set A, then π={4}, A={5,1,3,2} and π′=Φ. Go to Step 3.(3)
Job2 with the largest normal processing time amax=5; add it to π′ and eliminate it from the set A; then π={4}, A={5,1,3}, and π′={2}. Go to Step 4.(4)
Job3 with the largest normal processing time amax=3. Firstly, insert job 3 before all jobs in π; then π={3,4}, A={5,1}, and π′={2}. Calculate the makespan C′=3+6(1+3)2+2+5=106. Secondly, eliminate job 3 from π, insert job 3 before all jobs in π′, then π={4}, A={5,1} and π′={3,2}. Calculate the makespan C′′=6+2+3+5(1+3)2=91. Go to Step 5.(5)
SinceC′>C′′, then π={4}, A={5,1}, and π′={3,2}. Go to Step 6.(6)
SinceA≠Φ, go to Step 4.(7)
Job1 with the largest normal processing time amax=2. Firstly, insert job 1 before all jobs in π, then π={1,4}, A={5}, and π′={3,2}. Calculate the makespan C′=141. Secondly, eliminate the job 1 from π, insert job 1 before all jobs in π′, then π={4}, A={5}, and π′={1,3,2}. Calculate the makespan C′′=217. Go to Step 5.(8)
SinceC′<C′′, eliminate job 1 from π′, and insert it before all jobs in π again; then π={1,4}, A={5}, and π′={3,2}. Go to Step 6.(9)
SinceA≠Φ, go to Step 4.(10)
Job5 is the only one in A. Firstly, insert job 5 before all jobs in π, then π={5,1,4}, A=Φ, and π′={3,2}. Calculate the makespan C′=190. Secondly, eliminate job 5 from π, insert job 5 before all jobs in π′, then π={1,4}, A=Φ, and π′={5,3,2}. Calculate the makespan C′′=196. Go to Step 5.(11)
SinceC′<C′′, eliminate job 5 from π′, and insert it before all jobs in π again, then π={5,1,4}, A=Φ and π′={3,2}. Go to Step 6.(12)
SinceA=Φ, the algorithm stops, CHR*=C′=190. Compute the makespan CNR*=1166 of a sequence by ordering the normal job processing time using the short processing time (SPT) rule in the case without scheduling an RMA. Clearly, an optimal schedule is obtained from the heuristic algorithm.


## 3.4. The Special Case1|pir,rm,ai=a|Cmax

This subsection considers the special case1|pir,rm,ai=a|Cmax, where the normal processing time for all jobs is a.In a given sequence, while an RMA is inserted in positionk, the makespan can be expressed as follows:
(15)Cmax(k)=a+a(1+a)b+⋯+a(1+(k-2)a)b+t+a+a(1+a)b+⋯+a(1+(n-k)a)b.Clearly, the makespan is related to the sequence positionk. The problem can be solved by determining the value k to minimize (15). To determine the value k, we propose the following properties.Property 4.
(a) For an oddn and 1<k≤n, it has Cmax((n+1)/2)=Cmax((n+1)/2+1); and if k<(n+1)/2, then Cmax(k)>Cmax(k+1); if k>(n+1)/2, then Cmax(k)<Cmax(k+1).
(b) For an evenn and 1<k≤n, if k<n/2, then Cmax(k)>Cmax(k+1); if k>n/2+1, then Cmax(k)<Cmax(k+1).Proof.
(a) When the RMA is scheduled in the sequence positionk and k+1, the makespan can be expressed as follows:
(16)Cmax(k)=p+p(1+p)b+⋯+p(1+(k-2)p)b+t+p+p(1+p)b+⋯+p(1+(n-k)p)b,Cmax(k+1)=p+p(1+p)b+⋯+p(1+(k-2)p)b+p(1+(k-1)p)b+t+p+p(1+p)b+⋯+p(1+(n-k-1)p)b,Cmax(k)-Cmax(k+1)=p[(1+(n-k)p)b-(1+(k-1)p)b],Cmax(n+12)-Cmax(n+12+1)=0.
That is, Cmax((n+1)/2)=Cmax((n+1)/2+1).
Ifk<(n+1)/2 and p>0, we have (1+(n-k)p)b>(1+(k-1)p)b, Cmax(k)>Cmax(k+1).
Ifk>(n+1)/2 and p>0, we have (1+(n-k)p)b<(1+(k-1)p)b, Cmax(k)<Cmax(k+1).
The proof for (b) is analogous.Theorem 4.
The optimal policy for scheduling an RMA of lengtht under a time-dependent deterioration with b≥0 for all jobs is as follows. If n is an odd integer and t<p∑i=0(n-1)/2[(1+((n+1)/2-1+i)p)b-(1+ip)b], assign the RMA to sequence position k*=(n+1)/2 or k*=(n+1)/2+1. If n is an even integer and t<p∑i=0n/2-1[(1+(n/2+i)p)b-(1+ip)b], assign the RMA to sequence position k*=n/2+1. Otherwise, do not schedule the RMA.Proof.
(For an oddn). Based on Property 4, we have
(17)Cmax(n+12)<Cmax(n+12-1)<⋯<Cmax(2),Cmax(n+12+1)<Cmax(n+12+2)<⋯<Cmax(n).
Since Cmax((n+1)/2)=Cmax((n+1)/2+1), (17) imply that the minimum makespan occurs when k*=(n+1)/2 or k*=(n+1)/2+1.
LetCmax(k>n) represent the makespan without scheduling an RMA. Thus the RMA is scheduled only if Cmax(k*)<Cmax(k>n); that is,
(18)Cmax(n+12)=p+p(1+p)b+⋯+p(1+(n+12-2)p)b+t+p+p(1+p)b+⋯+p(1+(n-n+12)p)b,Cmax(k>n)=p+p(1+p)b+⋯+p(1+(n-1)p)b.
Since Cmax(k*)<Cmax(k>n), then t<p∑i=0(n-1)/2[(1+((n+1)/2-1+i)p)b-(1+ip)b].
Again, an analogous proof holds ifn is an even integer. This concludes the proof.


## 4. The Problem of1|pir,mrm|Cmax

In this section, the single machine problem assigning multi-RMAs in a sequence under time-dependent deterioration is considered. Firstly, several preliminaries are proposed in Section4.1, followed by the branch and bound algorithm and a heuristic algorithm in Sections 4.2 and 4.3, respectively. Finally, a special case is shown.


### 4.1. Preliminaries

In this subsection, several properties and a lower bound are proposed for solving the problem of1|pir,mrm|Cmax.Property 5.
IfM RMAs are assigned in given positions, jobs are divided into M+1 groups, and the elements in each group are known, then there is an optimal schedule that can be obtained by sequencing jobs in nondecreasing order of ai in each group.The proof of Property5 is similar to that of Property 2.Property 6.
For a given scheduleS={π1,rmk1,π2,rmk2,…,πm,rmkm,…,rmkM,πM+1}, the makespan remains equivalent by arbitrarily exchanging two groups.The proof of Property6 is similar to Property 3.


### 4.2. The Branch and Bound Algorithm

In solving the problem1|pir,mrm|Cmax, the branch and bound algorithm needs to add an outside cycle and change properties. The primary procedure is described as follows.Step 1.
Set the number of RMAsM=1.Step 2 (the position of the RMA).
Set the initial position of the RMA fork=2.Step 3 (initial solution).
Obtain the initial solution according to the short processing time rule.Step 4 (branching).
Search the whole solution space tree according to the depth first search strategy.Step 5 (eliminating).
Apply properties in Section4.1 to eliminate the dominant partial sequences.Step 6 (calculating).
Calculate the lower bound for the partial sequences. If it is less than the current optimal solution, continue to search in its branch. When a whole sequence is obtained, replace the current optimal sequence with it. Otherwise, eliminate it, and go to Step7.Step 7 (backtracking).
Backtrack to the father node of the current node and continue to search other branches.Step 8 (stopping).
Repeat Steps4 to 6 until no more nodes can be searched, and then set k=k+1, and go to Step 4. Repeat the above steps until k>n, then set M=M+1, and go to Step 4. Repeat the above steps until M>n. At this time, the algorithm stops.Similarly, obtain the makespanCBR* of an optimal solution from the above steps. Then, in the case without scheduling an RMA, compute the makespan CNR* of a sequence by ordering the normal job processing time using the short processing time (SPT) rule, and compare CNR* with CR*, selecting the smallest one of them.


### 4.3. A Heuristic Algorithm

For the problem1|pir,mrm|Cmax, the above heuristic algorithm is still efficient. It only needs to add M(1≤M≤n) cycles, then assign jobs to m(m=1,2,…M) groups according to the heuristic algorithm.


### 4.4. The Special Case1|pir,mrm,ai=a|Cmax

This subsection considers the special case1|pir,mrm,ai=a|Cmax, where the normal processing time for all jobs is a, and mrm denotes the multi-rate-modifying activities inserted in the sequence.Property 7.
If the number of multi-rate-modifying activitiesm is given, and jobs are divided into m+1 groups, then there exists an optimal schedule in which each group includes ⌊n/m⌋ or ⌊n/m⌋+1 jobs.Proof.
Assume that one of the groups includes the number of jobs greater than⌊n/m⌋+1, then jobs are moved in other groups to decrease the makespan until each group includes ⌊n/m⌋ or ⌊n/m⌋+1 jobs.Property 8.
The time complexity for the problem1|pir,mrm,ai=a|Cmax is O(n2).Proof.
For finding the optimal schedule with the determinate numberm, we need to check the value of m from 1 to n, and calculate the makespan corresponding with each m. Then, we compare them and select the value of m corresponding to the minimal makespan. Moreover, the time complexity in calculating the makespan is O(n). Hence, the time complexity of the problem 1|pir,mrm,ai=a|Cmax is O(n2).


## 4.1. Preliminaries

In this subsection, several properties and a lower bound are proposed for solving the problem of1|pir,mrm|Cmax.Property 5.
IfM RMAs are assigned in given positions, jobs are divided into M+1 groups, and the elements in each group are known, then there is an optimal schedule that can be obtained by sequencing jobs in nondecreasing order of ai in each group.The proof of Property5 is similar to that of Property 2.Property 6.
For a given scheduleS={π1,rmk1,π2,rmk2,…,πm,rmkm,…,rmkM,πM+1}, the makespan remains equivalent by arbitrarily exchanging two groups.The proof of Property6 is similar to Property 3.


## 4.2. The Branch and Bound Algorithm

In solving the problem1|pir,mrm|Cmax, the branch and bound algorithm needs to add an outside cycle and change properties. The primary procedure is described as follows.Step 1.
Set the number of RMAsM=1.Step 2 (the position of the RMA).
Set the initial position of the RMA fork=2.Step 3 (initial solution).
Obtain the initial solution according to the short processing time rule.Step 4 (branching).
Search the whole solution space tree according to the depth first search strategy.Step 5 (eliminating).
Apply properties in Section4.1 to eliminate the dominant partial sequences.Step 6 (calculating).
Calculate the lower bound for the partial sequences. If it is less than the current optimal solution, continue to search in its branch. When a whole sequence is obtained, replace the current optimal sequence with it. Otherwise, eliminate it, and go to Step7.Step 7 (backtracking).
Backtrack to the father node of the current node and continue to search other branches.Step 8 (stopping).
Repeat Steps4 to 6 until no more nodes can be searched, and then set k=k+1, and go to Step 4. Repeat the above steps until k>n, then set M=M+1, and go to Step 4. Repeat the above steps until M>n. At this time, the algorithm stops.Similarly, obtain the makespanCBR* of an optimal solution from the above steps. Then, in the case without scheduling an RMA, compute the makespan CNR* of a sequence by ordering the normal job processing time using the short processing time (SPT) rule, and compare CNR* with CR*, selecting the smallest one of them.


## 4.3. A Heuristic Algorithm

For the problem1|pir,mrm|Cmax, the above heuristic algorithm is still efficient. It only needs to add M(1≤M≤n) cycles, then assign jobs to m(m=1,2,…M) groups according to the heuristic algorithm.


## 4.4. The Special Case1|pir,mrm,ai=a|Cmax

This subsection considers the special case1|pir,mrm,ai=a|Cmax, where the normal processing time for all jobs is a, and mrm denotes the multi-rate-modifying activities inserted in the sequence.Property 7.
If the number of multi-rate-modifying activitiesm is given, and jobs are divided into m+1 groups, then there exists an optimal schedule in which each group includes ⌊n/m⌋ or ⌊n/m⌋+1 jobs.Proof.
Assume that one of the groups includes the number of jobs greater than⌊n/m⌋+1, then jobs are moved in other groups to decrease the makespan until each group includes ⌊n/m⌋ or ⌊n/m⌋+1 jobs.Property 8.
The time complexity for the problem1|pir,mrm,ai=a|Cmax is O(n2).Proof.
For finding the optimal schedule with the determinate numberm, we need to check the value of m from 1 to n, and calculate the makespan corresponding with each m. Then, we compare them and select the value of m corresponding to the minimal makespan. Moreover, the time complexity in calculating the makespan is O(n). Hence, the time complexity of the problem 1|pir,mrm,ai=a|Cmax is O(n2).


## 5. Numerical Experiments

In this section, the numerical experiment designs are as follows. The normal processing times of all jobs are generated from a uniform distribution over the integers between 1 and 100. The deterioration rateb takes the values of 0.05, 0.07, and 0.09. For the single machine scheduling problem with a rate-modifying activity, the size of job n takes the values of 5, 10, 15, 20, 25, 30, 35, 40, 45, and 50. For the single machine scheduling problem with multi-rate-modifying activities, the size of job n takes the values of 5, 7, 9, 11, 13, and 15, with the duration of the RMA t=30. There are 50 n-b combinations. Based on these, the CPU time and the solution performance of the branch and bound (B & B) and the heuristic algorithm (HA) are tested.Two algorithms are used on the same personal computer with an Intel (R) Core (TM) 2 processor. The results of1|pir,rm|Cmax and 1|pir,mrm|Cmax are recorded in Tables 1 and 2, respectively. In Table 1, it shows the optimal position of the RMA k from the heuristic algorithm and the error percentage of the heuristic algorithm relative to the optimal solution obtained from the branch and bound algorithm; that is, the error percentage is var=(H-H*)/H*×100%, where H is a solution from the heuristic algorithm and H* is the optimal solution from the branch and bound. It also gives the CPU time of the branch and bound, the optimal position of the RMA k, and the optimal solutions from the branch and bound. Since the CPU time of the heuristic algorithm for all sizes of jobs is less than 1 s, it is omitted. Difference between Tables 1 and 2 records the number of RMAs and their positions. Here, “—” denotes no position.Table 1
Comparison of results from B & B; HA for1|pir,rm|Cmax.
n
b
Branch and bound
Heuristic algorithm
n
b
Branch and bound
Heuristic algorithm
Optimal solution
k
CPU time (s)
Var
k
Optimal solution
k
CPU time (s)
Var
k
0.05
231.26
3
0
0.039
2
0.05
1737.96
15
66.782
0.023
28
5
0.07
319.34
4
0
0.037
2
30
0.07
2103.11
13
67.438
0.028
4
0.09
483.31
3
0
0.051
4
0.09
3080.54
16
66.313
0.015
21
0.05
739.34
6
0.200
0.029
2
0.05
2177.56
19
154.984
0.016
31
10
0.07
653.29
5
0.201
0.053
2
35
0.07
2652.92
22
153.266
0.014
28
0.09
666.42
6
0.182
0.052
3
0.09
2790.96
18
153.484
0.020
8
0.05
801.51
9
1.656
0.025
12
0.05
2362.75
26
318.391
0.018
37
15
0.07
918.13
10
1.656
0.035
14
40
0.07
2929.35
23
317.781
0.015
10
0.09
916.67
5
1.657
0.041
14
0.09
2532.46
22
322.297
0.034
37
0.05
1102.83
14
7.625
0.035
2
0.05
3074.90
27
611.469
0.015
7
20
0.07
1044.45
13
7.594
0.030
18
45
0.07
3082.73
24
610.953
0.023
40
0.09
1381.71
11
7.594
0.036
4
0.09
3568.99
21
610.282
0.031
41
0.05
1693.42
14
25.016
0.021
4
0.05
3337.76
25
1092.14
0.025
48
25
0.07
1530.00
17
25.063
0.020
21
50
0.07
3758.05
23
1091.81
0.020
8
0.09
2169.22
17
25.047
0.034
4
0.09
4285.62
28
1089.73
0.015
13Table 2
Comparison of results from B & B; HA for1|pir,mrm|Cmax.
n
b
Branch and bound
Heuristic algorithm
Optimal solution
M
Positions
CPU time (s)
Var
M
Positions
0.05
253.11
1
2
0.031
0.011
0
—
5
0.07
255.50
1
3
0.031
0.055
0
—
0.09
366.12
2
4, 5
0.031
0.058
1
5
0.05
390.36
0
—
0.328
0.012
0
—
7
0.07
567.46
2
4, 5
0.344
0.037
3
5, 6, 7
0.09
344.59
1
5
0.328
0.070
1
7
0.05
637.21
1
7
2.672
0.025
0
—
9
0.07
451.64
1
3
2.172
0.042
1
9
0.09
660.17
4
5, 6, 7, 8
2.719
0.049
4
6, 7, 8, 9
0.05
559.14
1
5
26.563
0.031
0
—
11
0.07
858.35
3
6, 7, 9
31.500
0.032
5
7, 8, 9, 10, 11
0.09
853.83
6
2, 4, 5, 6, 8, 9
31.078
0.025
6
6, 7, 8, 9, 10, 11
0.05
826.54
1
11
486.547
0.034
1
13
13
0.07
826.22
1
10
359.484
0.048
3
11, 12, 13
0.09
1051.81
8
2, 5, 6, 7, 8, 9, 10, 11
509.407
0.024
7
7, 8, 9, 10, 11, 12, 13
0.05
867.21
1
9
6810.547
0.035
2
14, 15
15
0.07
1062.18
1
7
5164.200
0.013
0
—
0.09
1117.52
6
4, 6, 8, 10, 13, 14
9923.344
0.017
7
9, 10, 11, 12, 13, 14, 15Observations from Table1 are as follows. (1)
The branch and bound algorithm can obtain the optimal solution when the job size is less than or equal to 50, and the running time gradually increases with increase of the job size.(2)
For the heuristic algorithm, the maximum error percentage of the heuristic algorithm is no more than 0.053. For certain sizes of jobs, the error percentage of the heuristic algorithm slowly increases with deterioration rate increase. Moreover, according to Table1, the mean error percentage var related to the job size for the heuristic algorithm is given in Figure 2. From Figure 2, it is seen that the mean error percentage decreases with increase of the job size, and the maximum mean error percentage is only 0.042.Figure 2
The mean error rate of the HA for1|pir,rm|Cmax.Observations of the results from Table2 are as follows. (1)
The branch and bound algorithm can obtain the optimal solution when the job size is less than or equal to 15, and the running time suddenly increases when the job size is 15.(2)
For the heuristic algorithm, the maximum error percentage of the heuristic algorithm is not more than 0.070. According to Table2, the mean error percentage var related to the job size for the heuristic algorithm is shown in Figure 3. From Figure 3, it is seen that the mean error percentage still decreases with job size increase, and the maximum mean error percentage is only 0.041.Figure 3
The mean error rate of the HA for1|pir,mrm|Cmax.Based on the above analysis, the branch and bound algorithm can solve problems with RMA or multi-rate-modifying activity within a reasonable time. The heuristic algorithm can obtain near-optimal solutions for the problem in a very short time. Therefore, the two algorithms proposed in this paper are very efficient and effective for the single machine scheduling problem with rate-modifying activity under a time-dependent deterioration. At the same time, they can be also used as a reference for other problems with the rate-modifying activity.


## 6. Conclusion

This paper integrates a time-dependent deterioration considered as a nonlinear function multi-rate-modifying activities into the single machine scheduling problem to minimize makespan. A branch and bound algorithm and a heuristic algorithm are proposed to solve such problems. At the same time, for special cases, the propositions, theorems, correlated proofs on the optimal policy of scheduling the RMA for minimal makespan are derived. Finally, the results of numerical experiments indicate that the branch and bound algorithm and the heuristic algorithm are efficient. In future, the research will be extended to single machine scheduling problems with release dates and due dates, which are more general cases in actuality.



---

*Source: 135610-2013-06-03.xml*