# Single-Machine Scheduling with Upper Bounded Maintenance Time under the Deteriorating Effect

Authors: Pengfei Xue; Yulin Zhang
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

We consider a single-machine scheduling problem with upper bounded actual
processing time and upper bounded maintenance time under deteriorating effect. The actual
processing time of a job is a position-dependent power function. If the actual processing time
of a job exceeds the upper bound, tardiness penalty of the job should be paid. And if the
maintenance time exceeds the corresponding upper bound, tardiness penalty of the maintenance
should also be paid. The maintenance duration studied in the paper is a position-dependent
exponential function. The objective is to find jointly the optimal maintenance frequency and
the optimal job sequence to minimize the total cost, which is a linear function of the makespan
and the total tardiness. We show that the studied scheduling problem can be transformed as a
classic assignment problem to solve. There is also shown that a special case of the scheduling
problem can be optimally solved by a lower order algorithm.


---

## Body

## 1. Introduction

In recent years, scheduling problems with the deteriorating effect have attracted increasing attention. In case of the deteriorating effect, the actual processing time of a job will be longer if it is scheduled later in a sequence. Browne and Yechiali [1] initiated research on scheduling problem with the deteriorating effect, where the actual processing time of a job is a linear nondecreasing start-time-dependent function. A time-dependent deteriorating model was proposed by Rudek [2], where the actual time required to perform a job is a function of the sum of the normal processing time of jobs already processed. For extensive surveys related to time-dependent processing time, the reader can refer to the papers [3–7]. Hsu et al. [8] studied single-machine scheduling and due date assignment problems with position-dependent processing time. They showed that the problems are polynomial time solvable. Mosheiov [9] investigated the scheduling problem with general, nondecreasing, job-dependent, and position-dependent deterioration function under the setting of parallel identical machines to minimize the total load. Rustogi and Strusevich [10] presented polynomial-time algorithms for single-machine problems with generalized positional deterioration effects under machine maintenance. They assumed that the decisions should be taken regarding possible sequences of jobs and on the number of maintenance activities to be included into a schedule to minimize the overall makespan. More recent papers which have considered position-dependent job processing time could be seen in [11–14].Researchers have studied a variety of scheduling problems with job completion time due window. Jobs should be finished as close as possible to their due dates to cope with global competition and improve customer demand. A job will have to be stored in inventory when it is finished before its due date, which may lead to an earliness penalty. Contrarily, a job will get a tardiness penalty when it is finished after its due date because it violates the contractual obligation with the customer. For extensive surveys related to scheduling problems with the job completion time due window, reader can refer to the papers [15–19]. In this paper, we set the upper bound for the actual processing time of each job. The actual processing time of a job is required to be within a given interval; otherwise tardiness penalty should be paid. For example, in brick manufacturing processes, the actual processing time cannot exceed a given upper bound; otherwise the brick may have quality flaws.On the other hand, it is reasonable and necessary to perform maintenance in manufacturing processes, because it can help improve the production efficiency. Some scheduling problems with deteriorating effect and machine maintenance have been studied. A single-machine scheduling problem with a cyclic process of deteriorating effect and maintenance activities was addressed by Kuo and Yang [20]. For the problem, they provided polynomial algorithms to minimize the makespan. Zhao and Tang [21] extended the model of Kuo and Yang [20]. The position-dependent deteriorating effect they considered is described by a general exponential function. They claimed that the problem can be transformed as a classic assignment problem to solve. Chen [22] studied a single-machine scheduling problem with periodic maintenance activities and nonresumable jobs to minimize the number of tardy jobs. S. J. Yang and D. L. Yang [12] considered a single-machine scheduling problem with position-dependent deteriorating effect under variable maintenance activities to minimize the makespan of all jobs. It is necessary to maintain the machine, but the maintenance time should be completed within a time interval, otherwise it will affect the machine efficiency (see, e.g., Lee and Chen [23] and Kubzin and Strusevich [24]). Thus, in this paper, we set the upper bound for the maintenance time. Once the maintenance time exceeds the upper bound, the tardiness penalty of the maintenance should also be paid.However, to the best of our knowledge, research on scheduling simultaneously with upper bounded actual processing time of a job and upper bounded maintenance time under deteriorating effect considerations has rarely been studied. Motivated by these points, this paper investigates a scheduling problem with upper bounded actual processing time of a job and upper bounded maintenance time under deteriorating effect. If the actual processing time of a job exceeds the upper bound, tardiness penalty of the job should be paid. And if the maintenance time exceeds the corresponding upper bound, tardiness penalty of the maintenance should also be paid since it will affect the machine efficiency. We assume that the machine may be subject to several maintenance activities during the scheduling horizon and the maintenance duration is a variable function. The objective is to minimize the total cost, which is assumed to conclude production fee and total tardiness costs, through exploring jointly the optimal maintenance frequency, the optimal maintenance position, and the optimal job sequences. We show that the studied problem in the scheduling problem remains polynomially solvable.The remaining part of this paper is structured as follows. We formally introduce the notation and terminology used throughout the rest of this paper in the next section. In Section3, we propose the main results of this paper. In Section 4, we conclude with a summary of the results and suggest directions for future research.


## 2. Notations and Problem Formulation

Consider a single machine to process a set ofn independent jobs, which are all available for processing at time zero. The machine can handle one job at a time. In manufacturing processes, the job preemption is not allowed. To improve the production efficiency, maintenance activities may be performed on the machine. During maintenance the machine is stopped, and the machine will revert to its initial state after the maintenance. We assume that the actual processing time of a job will be longer when it is scheduled later in a sequence due to the deteriorating effect of the machine. And the maintenance duration is a function of the maintenance position of the machine. The jobs will be processed from a group consecutively. Thus, the schedule can be denoted as σ=[G1,M1,G2,M2,…,Gk,Mk,Gk+1],0≤k≤(n-1), where Gi, 1≤i≤k+1, denotes the ith group and Mi, 1≤i≤k, denotes the ith maintenance. C[l,r] is the completion time of the job scheduled in rth position of the lth group. The following a positional deterioration model of the actual processing time of job Jj is discussed. The actual processing time of job Jj, if scheduled in position r of group Gi, is given by
(1)p[i,j]r=p[i,j]ra[i,j],fori=1,2,…,k+1,j,r=1,2,…,ni,
where p[i,j] is the normal processing time of job Jj and  a[i,j] is the deteriorating factor of job Jj. The number of jobs of group Gi is denoted as ni.In this study, we examine a model of the maintenance duration which concerns the position-dependent deteriorating effect. If the maintenance is theith maintenance in the sequence, its actual maintenance duration is defined by
(2)mi=t0b(i-1),fori=1,2,…,k,
where t0>0 denotes the basic maintenance time and b>1 is the deteriorating factor of the maintenance. If the maintenance is arranged later in the sequence, the actual maintenance duration will be longer in this model due to the deteriorating effect.Observing from (1), we find no matter what the group is, the actual processing time of job Jj is only dependent on its position in a group. For convenience, we reformulate (1) as follows:
(3)pjr=pjraj,forj=1,2,…,n,r=1,2,…,ni,6666666666666666666666666i=1,2,…,k+1,
where pj and aj>0 are the normal processing time and the deteriorating factor of job Jj, respectively.Letpjb0 denote the upper bound of the actual processing time of job Jj, where b0>1 is a constant number. The tardiness of job Jj is denoted as Tj; that is, Tj=max{0,pjr-pjb0}. Then it can be obtained that the total tardiness of all jobs is ∑j=1n‍Tj. Let t0u denote the upper bound of the maintenance time, where u>1 is a constant number. The tardiness of the ith maintenance is denoted as Ti′, that is, Ti′=max{0,t0b(i-1)-t0u}. Then the total tardiness of all maintenances is denoted by ∑i=1k‍Ti′. Let Cmax denote the makespan; that is, Cmax=max{Cj∣j=1,…,n}.In manufacturing processes, the length of working time determines the production fee. The tardiness penalties are assumed to be linear relationship with the total tardiness of all jobs and all maintenances, respectively. Thus, in the case of setting the upper bounds for the processing time of jobs and maintenance time of the machine simultaneously, we define the total cost as follows:(4)TC=αCmax+β∑j=1nTj+γ∑i=1kTi′,
where α,β, and γ are the unit production fee, the unit tardiness cost of all jobs, and the unit tardiness cost of all maintenances, respectively. α, β, and γ should be positive numbers, that is, α>0, β>0, and γ>0. The objective of this study is to minimize the total cost through exploring jointly the optimal maintenance frequency, the optimal maintenance positions, and the optimal job sequences.


## 3. Total Cost Minimization

Using the three-field notationα/β/γ of Graham et al. [25], we denote our problem as 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC, where M and k denote the maintenance and the maintenance frequency, respectively. We set the upper bounds for the actual processing time of each job and the maintenance time of the machine simultaneously. If the actual processing time of a job exceeds the upper bound, the tardiness penalty should be paid. And if the maintenance time also exceeds the corresponding upper bound, tardiness penalty of the maintenance should also be paid. The associated objective of the problem 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC is given by
(5)TC=αCmax+β∑j=1nTj+γ∑i=1kTi′.Agroup balance principle was presented by Kuo and Yang [20]. In the next part, we will prove that the group balance principle remains valid for the problem 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC. Assume that there are n independent jobs to be assigned. If the machine is maintained k times in a schedule, then the jobs are divided into (k+1) groups. Application of the group balance principle ensures that the number of jobs in groups is as close as possible.


### 3.1. Group Balance Principle

Assume that the machine is maintainedk times in a schedule and the jobs are divided into (k+1) groups. The number of the jobs in every group is ⌈n/(k+1)⌉-1 or ⌈n/(k+1)⌉, that is, ⌈n/(k+1)⌉-1≤ni≤⌈n/(k+1)⌉.Lemma 1.
For the problem1/pjr=pjraj,M=k,mi=t0b(i-1)/TC, there exists such an optimal schedule that the number of jobs in groups satisfies the group balance principle.Proof.
Using the similar proof of Lemma 2 in Zhao and Tang [21], we assume that an optimal schedule σ consisting of n independent jobs and k maintenance activities does not satisfy the group balance principle. The maintenance and group sequence σ can be described as σ=(G1,M1,G2,M2,…,Gk,Mk,Gk+1). Then somewhere in σ there must exist at least two groups Gi and Gj, in which the difference in the number of jobs is greater than one. We assume that ni>nj, then ni-nj>1, where ni and nj denote the number of jobs in the Gi and Gj, respectively. Let π1, π2, and π3 denote the partial schedules of the σ, then σ=(π1,Gi,Mi,π2,Gj,Mj,π3).
Move the last job of groupGi to the last position of group Gj, then we obtain a new schedule σ′=(π1,Gi′,Mi,π2,Gj′,Mj,π3). The moving of the job J[i,ni] is illustrated by Figure 1. For simplicity, we let the job J[i,ni] be the job Jj. In schedule σ and σ′, the production cost of the other jobs remains unchanged since the positions of them remain unchanged. Let TC(pj) and TC′(pj) denote the contribution of pj to the total cost in the schedule σ and σ′, respectively. Since the maintenance duration is only dependent on its position in the schedule, moving the last job of group Gi to the last position of group Gj can not change the maintenance time. Then in the schedules σ and σ′, γ∑i=1kTi′ remains unchanged.
In scheduleσ, the contribution of pj to the total cost is given by
(6)TC(pj)=αpjniaj+βmax{0,pjniaj-pjb0},
where aj is the deteriorating factor of job Jj.
In scheduleσ′, the contribution of pj to the total cost is given by
(7)TC′(pj)=αpj(nj+1)aj+βmax{0,pj(nj+1)aj-pjb0}.
Combining (6) and (7), we get the following equality:
(8)TC(pj)-TC′(pj)=αpj(niaj-(nj+1)aj)+β(max{0,pjniaj-pjb0}+β--max{0,pj(nj+1)aj-pjb0}).
Since α>0,β>0,ni-nj>1, and aj>0, we can obtain that TC(pj)-TC′(pj)>0. Hence, we can obtain that the total cost of schedule σ′ is less than that of schedule σ, which contradicts the optimality of schedule σ. Lemma 1 is proved.Figure 1
The illustration of the moving of jobJ[i,ni].In the following, we show that the problem1/pjr=pjraj,M=k,mi=t0b(i-1)/TC remains polynomially solvable and can be solved in O(n4) time. The associated total cost is given by
(9)TC=αCmax+βΣj=1nTj+γΣi=1kTi′=α(∑i=1k+1‍∑r=1ni‍p[i,r]ra[i,r]+∑i=1k‍t0b(i-1))+β∑i=1k+1‍∑r=1ni‍max{0,p[i,r]ra[i,r]-p[i,r]b0}+γ∑i=1kmax{0,t0b(i-1)-t0u}=∑i=1k+1‍∑r=1ni‍(αra[i,r]+βmax{0,ra[i,r]-b0})p[i,r]+∑i=1k‍(αt0b(i-1)+γmax{0,t0b(i-1)-t0u}).
Then, it can be seen whatever the group is, the contribution of a job to the total cost only depends on its position in a group, and for the given k,  ∑i=1k‍(αt0b(i-1)+γmax{0,t0b(i-1)-t0u}) is a constant. We explore to find a polynomial to minimize the total cost. The problem 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC can be reformulated as a standard assignment problem, which can be described as follows:
(10)Minimize∑j=1n‍∑i=1k+1‍∑r=1ni‍wjirxjirMinimize∑j=1n‍∑i=1k+1‍∑r=1ni‍+∑i=1k‍(αt0b(i-1)Minimize∑j=1n‍∑i=1k+1‍∑r=1ni‍666666+γmax{0,t0b(i-1)-t0u})
subject to
(11)∑j=1n‍xjir=1,i=1,2,…,k+1,r=1,2,…,ni,∑i=1k+1‍∑r=1ni‍xjir=1,j=1,2,…,n,xjir=0or1,j=1,2,…,n,i=1,2,…,k+1,6666666666666666666666666666r=1,2,…,ni,
where wjir=(αraj+βmax{0,raj-b0})pj. If job Jj is scheduled in the rth position in group Gi, xjir=1, otherwise xjir=0. Constraint sets (11) can ensure that each job is scheduled exactly once and each position is taken by one job. A special case should be noted as follows. In the case of k=0, there is no maintenance in the schedule, and the objective of the assignment problem is not ∑j=1n‍∑i=1k+1‍∑r=1ni‍wjirxjir+∑i=1k‍(αt0b(i-1)+γmax{0,t0b(i-1)-t0u}), but ∑j=1n‍∑i=1k+1‍∑r=1ni‍wjirxjir.It is known that the assignment problem can be optimally solved inO(n3) time by the classic Hungarian algorithm. In order to minimize the total cost, we propose a polynomial time algorithm to determine jointly the optimal k and the optimal job sequence.Algorithm 2.
Step
1. For each k(k=0,1,…,n-1), solve the assignment problem (10)-(11), and let the corresponding objective value be TC(k).
Step
2. Let (TC(k))*=min(TC(k),(k=0,1,…,n-1)), and the corresponding schedule is the result schedule.Theorem 3.
The problem1/pjr=pjraj,M=k,mi=t0b(i-1)/TC can be optimally solved by Algorithm 2 in O(n4) time.Proof.
For a fixed maintenance frequencyk, we can obtain the optimal maintenance positions and the number of jobs in each group by Lemma 1. The problem 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC can be optimally solved via the assignment problem (10)-(11) in O(n3) time. Note that k has n possible values. Then, (TC(k))*=min(TC(k),(k=0,1,…,n-1)) is the optimal objective value for the considered problem. Therefore, to solve the problem 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC, the computational complexity is O(n4).Using the similar method of Theorem3, the following corollary can be easily obtained.Corollary 4.
For the scheduling problem of only setting the upper bound for the actual processing time of a job, it can be optimally solved inO(n4) time.In the following, we investigate a special case of the problem1/pjr=pjraj,M=k,mi=t0b(i-1)/TC. Let the deteriorating factor aj=a, where a is a common deteriorating factor. We denote the special case of the problem as 1/pjr=pjra,M=k,mi=t0b(i-1)/TC and explore to find a more efficient algorithm.First, we give a lemma which is useful for the following results.Lemma 5.
If sequencex1,x2,…,xn is ordered nondecreasingly and sequence y1,y2,…,yn is ordered nonincreasingly, the sum ∑i=1n‍xiyi of products of the corresponding elements is minimized [26].Theorem 6.
The problem1/pjr=pjra,M=k,mi=t0b(i-1)/TC can be optimally solved by scheduling the jobs in a nonincreasing order of their normal processing time pj and then arranging the jobs one by one into each group in turn. The time complexity of the problem is O(nlogn).Proof.
For a given maintenance frequencyk=k0, let h be the remainder of n divided by (k0+1); that is,  h=mod(n,k0+1). If h≠0, without loss of generality, we assume that there are d jobs in each of the first h groups and (d-1) jobs in each of the other groups. Let w[i,r]=αra+βmax{0,ra-b0}, where w[i,r] is the positional weight of the corresponding job. Then the associated total cost is given as follows:
(12)TC=αCmax+β∑j=1nTj+γ∑i=1k0Ti′(13)=∑i=1h‍∑r=1d‍w[i,r]p[i,r]+∑i=h+1k0+1‍∑r=1d-1‍w[i,r]p[i,r]+∑i=1k0‍(αb(i-1)+γmax{0,b(i-1)-u})t0.
Since α,t0,b,γ, and u are constant numbers, for the given k0, ∑i=1k0‍(αb(i-1)+γmax{0,b(i-1)-u})t0 is a constant number. From (13), it can be seen that
(14)α+βmax{0,1-b0}=w[1,1]=w[2,1]=⋯=w[k0+1,1]<α2a+βmax{0,2a-b0}=w[1,2]=w[2,2]=⋯=w[k0+1,2]<⋯<α(d-1)a+βmax{0,(d-1)a-b0}=w[1,d-1]=w[2,d-1]=⋯=w[k0+1,d-1]<αda+βmax{0,da-b0}=w[1,d]=w[2,d]=⋯=w[h,d].
Hence, if
(15)p[1,1]≥p[2,1]≥⋯≥p[k0+1,1]≥p[1,2]≥p[2,2]≥⋯≥p[k0+1,2]≥⋯≥p[1,d-1]≥p[2,d-1]≥⋯≥p[k0+1,d-1]≥p[1,d]≥p[2,d]≥⋯≥p[h,d],
then, by Lemma 5, the total cost is the least one. Therefore, there exists an optimal schedule in which jobs are scheduled in nonincreasing order of their normal processing time. Then, schedule the job in the first position of each group one by one. If the first position of each group is filled, then schedule the remaining job in the second position of each group one by one. If all the second positions are filled, fill the third position, and so on, until all jobs are scheduled. The time complexity of arranging the jobs in a nonincreasing order of their normal processing time is O(nlogn). The time complexity of assigning n jobs one by one to each group in turn in a nonincreasing order of their normal processing time is O(1). Thus, the problem 1/pjr=pjra,M=k,mi=t0b(i-1)/TC can be optimally solved in O(nlogn) time.We demonstrate the results of Theorem6 in the following example.Example 7.
Data:n=5,p1=3,p2=5,p3=5,p4=8,p5=11,a=0.2,α=2,β=25, γ=100,t0=4,b=1.1,u=1.2,andb0=1.3. The values of the number of jobs in each group, the positional weights, the optimal schedule, and the total cost are given in Table 1.
Observing from Table1, it can be seen that the case of k=1 is optimal. The jobs should be divided into 2 groups, where n1=3,n2=2. The optimal schedule is (11, 5, 3, 8, 5). Then TC*=70.47.Table 1
The number of jobs in each group, the positional weights, the optimal schedule, and the total cost.
k
The number of jobs in each group
The positional weights
The optimal schedule
T
C
0
n
1
=
5
w
[
1,1
]
=
2.00
,
w
[
1,2
]
=
2.30
,
w
[
1,3
]
=
2.49
,
w
[
1,4
]
=
3.13
,
w
[
1,5
]
=
4.75
(11, 8, 5, 5, 3)
82.75
1
n
1
=
3
,
n
2
=
2
w
[
1,1
]
=
2.00
,
w
[
1,2
]
=
2.30
,
w
[
1,3
]
=
2.49
,
w
[
2,1
]
=
2.00
,
w
[
2,2
]
=
2.30
(11, 5, 3, 8, 5)
70.47
2
n
1
=
2
,
n
2
=
2
,
n
3
=
1
w
[
1,1
]
=
2.00
,
w
[
1,2
]
=
2.30
,
w
[
2,1
]
=
2.00
,
w
[
2,2
]
=
2.30
,
w
[
3,1
]
=
2.00
(11, 5, 8, 3, 5)
70.60
3
n
1
=
2
,
n
2
=
1
,
n
3
=
1
,
n
4
=
1
w
[
1,1
]
=
2.00
,
w
[
1,2
]
=
2.30
,
w
[
2,1
]
=
2.00
,
w
[
3,1
]
=
2.00
,
w
[
4,1
]
=
2.00
(11, 3, 8, 5, 5)
82.78
4
n
1
=
1
,
n
2
=
1
,
n
3
=
1
,
n
4
=
1
,
n
5
=
1
w
[
1,1
]
=
2.00
,
w
[
2,1
]
=
2.00
,
w
[
3,1
]
=
2.00
,
w
[
4,1
]
=
2.00
,
w
[
5,1
]
=
2.00
(11, 8, 5, 5, 3)
144.93


## 3.1. Group Balance Principle

Assume that the machine is maintainedk times in a schedule and the jobs are divided into (k+1) groups. The number of the jobs in every group is ⌈n/(k+1)⌉-1 or ⌈n/(k+1)⌉, that is, ⌈n/(k+1)⌉-1≤ni≤⌈n/(k+1)⌉.Lemma 1.
For the problem1/pjr=pjraj,M=k,mi=t0b(i-1)/TC, there exists such an optimal schedule that the number of jobs in groups satisfies the group balance principle.Proof.
Using the similar proof of Lemma 2 in Zhao and Tang [21], we assume that an optimal schedule σ consisting of n independent jobs and k maintenance activities does not satisfy the group balance principle. The maintenance and group sequence σ can be described as σ=(G1,M1,G2,M2,…,Gk,Mk,Gk+1). Then somewhere in σ there must exist at least two groups Gi and Gj, in which the difference in the number of jobs is greater than one. We assume that ni>nj, then ni-nj>1, where ni and nj denote the number of jobs in the Gi and Gj, respectively. Let π1, π2, and π3 denote the partial schedules of the σ, then σ=(π1,Gi,Mi,π2,Gj,Mj,π3).
Move the last job of groupGi to the last position of group Gj, then we obtain a new schedule σ′=(π1,Gi′,Mi,π2,Gj′,Mj,π3). The moving of the job J[i,ni] is illustrated by Figure 1. For simplicity, we let the job J[i,ni] be the job Jj. In schedule σ and σ′, the production cost of the other jobs remains unchanged since the positions of them remain unchanged. Let TC(pj) and TC′(pj) denote the contribution of pj to the total cost in the schedule σ and σ′, respectively. Since the maintenance duration is only dependent on its position in the schedule, moving the last job of group Gi to the last position of group Gj can not change the maintenance time. Then in the schedules σ and σ′, γ∑i=1kTi′ remains unchanged.
In scheduleσ, the contribution of pj to the total cost is given by
(6)TC(pj)=αpjniaj+βmax{0,pjniaj-pjb0},
where aj is the deteriorating factor of job Jj.
In scheduleσ′, the contribution of pj to the total cost is given by
(7)TC′(pj)=αpj(nj+1)aj+βmax{0,pj(nj+1)aj-pjb0}.
Combining (6) and (7), we get the following equality:
(8)TC(pj)-TC′(pj)=αpj(niaj-(nj+1)aj)+β(max{0,pjniaj-pjb0}+β--max{0,pj(nj+1)aj-pjb0}).
Since α>0,β>0,ni-nj>1, and aj>0, we can obtain that TC(pj)-TC′(pj)>0. Hence, we can obtain that the total cost of schedule σ′ is less than that of schedule σ, which contradicts the optimality of schedule σ. Lemma 1 is proved.Figure 1
The illustration of the moving of jobJ[i,ni].In the following, we show that the problem1/pjr=pjraj,M=k,mi=t0b(i-1)/TC remains polynomially solvable and can be solved in O(n4) time. The associated total cost is given by
(9)TC=αCmax+βΣj=1nTj+γΣi=1kTi′=α(∑i=1k+1‍∑r=1ni‍p[i,r]ra[i,r]+∑i=1k‍t0b(i-1))+β∑i=1k+1‍∑r=1ni‍max{0,p[i,r]ra[i,r]-p[i,r]b0}+γ∑i=1kmax{0,t0b(i-1)-t0u}=∑i=1k+1‍∑r=1ni‍(αra[i,r]+βmax{0,ra[i,r]-b0})p[i,r]+∑i=1k‍(αt0b(i-1)+γmax{0,t0b(i-1)-t0u}).
Then, it can be seen whatever the group is, the contribution of a job to the total cost only depends on its position in a group, and for the given k,  ∑i=1k‍(αt0b(i-1)+γmax{0,t0b(i-1)-t0u}) is a constant. We explore to find a polynomial to minimize the total cost. The problem 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC can be reformulated as a standard assignment problem, which can be described as follows:
(10)Minimize∑j=1n‍∑i=1k+1‍∑r=1ni‍wjirxjirMinimize∑j=1n‍∑i=1k+1‍∑r=1ni‍+∑i=1k‍(αt0b(i-1)Minimize∑j=1n‍∑i=1k+1‍∑r=1ni‍666666+γmax{0,t0b(i-1)-t0u})
subject to
(11)∑j=1n‍xjir=1,i=1,2,…,k+1,r=1,2,…,ni,∑i=1k+1‍∑r=1ni‍xjir=1,j=1,2,…,n,xjir=0or1,j=1,2,…,n,i=1,2,…,k+1,6666666666666666666666666666r=1,2,…,ni,
where wjir=(αraj+βmax{0,raj-b0})pj. If job Jj is scheduled in the rth position in group Gi, xjir=1, otherwise xjir=0. Constraint sets (11) can ensure that each job is scheduled exactly once and each position is taken by one job. A special case should be noted as follows. In the case of k=0, there is no maintenance in the schedule, and the objective of the assignment problem is not ∑j=1n‍∑i=1k+1‍∑r=1ni‍wjirxjir+∑i=1k‍(αt0b(i-1)+γmax{0,t0b(i-1)-t0u}), but ∑j=1n‍∑i=1k+1‍∑r=1ni‍wjirxjir.It is known that the assignment problem can be optimally solved inO(n3) time by the classic Hungarian algorithm. In order to minimize the total cost, we propose a polynomial time algorithm to determine jointly the optimal k and the optimal job sequence.Algorithm 2.
Step
1. For each k(k=0,1,…,n-1), solve the assignment problem (10)-(11), and let the corresponding objective value be TC(k).
Step
2. Let (TC(k))*=min(TC(k),(k=0,1,…,n-1)), and the corresponding schedule is the result schedule.Theorem 3.
The problem1/pjr=pjraj,M=k,mi=t0b(i-1)/TC can be optimally solved by Algorithm 2 in O(n4) time.Proof.
For a fixed maintenance frequencyk, we can obtain the optimal maintenance positions and the number of jobs in each group by Lemma 1. The problem 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC can be optimally solved via the assignment problem (10)-(11) in O(n3) time. Note that k has n possible values. Then, (TC(k))*=min(TC(k),(k=0,1,…,n-1)) is the optimal objective value for the considered problem. Therefore, to solve the problem 1/pjr=pjraj,M=k,mi=t0b(i-1)/TC, the computational complexity is O(n4).Using the similar method of Theorem3, the following corollary can be easily obtained.Corollary 4.
For the scheduling problem of only setting the upper bound for the actual processing time of a job, it can be optimally solved inO(n4) time.In the following, we investigate a special case of the problem1/pjr=pjraj,M=k,mi=t0b(i-1)/TC. Let the deteriorating factor aj=a, where a is a common deteriorating factor. We denote the special case of the problem as 1/pjr=pjra,M=k,mi=t0b(i-1)/TC and explore to find a more efficient algorithm.First, we give a lemma which is useful for the following results.Lemma 5.
If sequencex1,x2,…,xn is ordered nondecreasingly and sequence y1,y2,…,yn is ordered nonincreasingly, the sum ∑i=1n‍xiyi of products of the corresponding elements is minimized [26].Theorem 6.
The problem1/pjr=pjra,M=k,mi=t0b(i-1)/TC can be optimally solved by scheduling the jobs in a nonincreasing order of their normal processing time pj and then arranging the jobs one by one into each group in turn. The time complexity of the problem is O(nlogn).Proof.
For a given maintenance frequencyk=k0, let h be the remainder of n divided by (k0+1); that is,  h=mod(n,k0+1). If h≠0, without loss of generality, we assume that there are d jobs in each of the first h groups and (d-1) jobs in each of the other groups. Let w[i,r]=αra+βmax{0,ra-b0}, where w[i,r] is the positional weight of the corresponding job. Then the associated total cost is given as follows:
(12)TC=αCmax+β∑j=1nTj+γ∑i=1k0Ti′(13)=∑i=1h‍∑r=1d‍w[i,r]p[i,r]+∑i=h+1k0+1‍∑r=1d-1‍w[i,r]p[i,r]+∑i=1k0‍(αb(i-1)+γmax{0,b(i-1)-u})t0.
Since α,t0,b,γ, and u are constant numbers, for the given k0, ∑i=1k0‍(αb(i-1)+γmax{0,b(i-1)-u})t0 is a constant number. From (13), it can be seen that
(14)α+βmax{0,1-b0}=w[1,1]=w[2,1]=⋯=w[k0+1,1]<α2a+βmax{0,2a-b0}=w[1,2]=w[2,2]=⋯=w[k0+1,2]<⋯<α(d-1)a+βmax{0,(d-1)a-b0}=w[1,d-1]=w[2,d-1]=⋯=w[k0+1,d-1]<αda+βmax{0,da-b0}=w[1,d]=w[2,d]=⋯=w[h,d].
Hence, if
(15)p[1,1]≥p[2,1]≥⋯≥p[k0+1,1]≥p[1,2]≥p[2,2]≥⋯≥p[k0+1,2]≥⋯≥p[1,d-1]≥p[2,d-1]≥⋯≥p[k0+1,d-1]≥p[1,d]≥p[2,d]≥⋯≥p[h,d],
then, by Lemma 5, the total cost is the least one. Therefore, there exists an optimal schedule in which jobs are scheduled in nonincreasing order of their normal processing time. Then, schedule the job in the first position of each group one by one. If the first position of each group is filled, then schedule the remaining job in the second position of each group one by one. If all the second positions are filled, fill the third position, and so on, until all jobs are scheduled. The time complexity of arranging the jobs in a nonincreasing order of their normal processing time is O(nlogn). The time complexity of assigning n jobs one by one to each group in turn in a nonincreasing order of their normal processing time is O(1). Thus, the problem 1/pjr=pjra,M=k,mi=t0b(i-1)/TC can be optimally solved in O(nlogn) time.We demonstrate the results of Theorem6 in the following example.Example 7.
Data:n=5,p1=3,p2=5,p3=5,p4=8,p5=11,a=0.2,α=2,β=25, γ=100,t0=4,b=1.1,u=1.2,andb0=1.3. The values of the number of jobs in each group, the positional weights, the optimal schedule, and the total cost are given in Table 1.
Observing from Table1, it can be seen that the case of k=1 is optimal. The jobs should be divided into 2 groups, where n1=3,n2=2. The optimal schedule is (11, 5, 3, 8, 5). Then TC*=70.47.Table 1
The number of jobs in each group, the positional weights, the optimal schedule, and the total cost.
k
The number of jobs in each group
The positional weights
The optimal schedule
T
C
0
n
1
=
5
w
[
1,1
]
=
2.00
,
w
[
1,2
]
=
2.30
,
w
[
1,3
]
=
2.49
,
w
[
1,4
]
=
3.13
,
w
[
1,5
]
=
4.75
(11, 8, 5, 5, 3)
82.75
1
n
1
=
3
,
n
2
=
2
w
[
1,1
]
=
2.00
,
w
[
1,2
]
=
2.30
,
w
[
1,3
]
=
2.49
,
w
[
2,1
]
=
2.00
,
w
[
2,2
]
=
2.30
(11, 5, 3, 8, 5)
70.47
2
n
1
=
2
,
n
2
=
2
,
n
3
=
1
w
[
1,1
]
=
2.00
,
w
[
1,2
]
=
2.30
,
w
[
2,1
]
=
2.00
,
w
[
2,2
]
=
2.30
,
w
[
3,1
]
=
2.00
(11, 5, 8, 3, 5)
70.60
3
n
1
=
2
,
n
2
=
1
,
n
3
=
1
,
n
4
=
1
w
[
1,1
]
=
2.00
,
w
[
1,2
]
=
2.30
,
w
[
2,1
]
=
2.00
,
w
[
3,1
]
=
2.00
,
w
[
4,1
]
=
2.00
(11, 3, 8, 5, 5)
82.78
4
n
1
=
1
,
n
2
=
1
,
n
3
=
1
,
n
4
=
1
,
n
5
=
1
w
[
1,1
]
=
2.00
,
w
[
2,1
]
=
2.00
,
w
[
3,1
]
=
2.00
,
w
[
4,1
]
=
2.00
,
w
[
5,1
]
=
2.00
(11, 8, 5, 5, 3)
144.93


## 4. Conclusions

The paper investigated a single-machine scheduling problem with upper bounded actual processing time and upper bounded maintenance time under deteriorating effect. The maintenance duration studied in the paper is a position-dependent exponential function. The objective is to minimize the total cost that is a linear function of the makespan and the tardiness penalties. We proved that the problem considered can be optimally solved inO(n4) time. Moreover, for a special case that the deteriorating factor of the job processing time is assumed as a constant, we showed that the total cost minimization problem with deteriorating effect can be solved in O(nlogn) time. We provided a numerical example for the special case, where the optimal solutions can be easily obtained. Future research may focus on the scheduling problem with upper bounded actual position-dependent processing time and upper bounded maintenance time under deteriorating effect in the context of parallel machine scheduling problems or job-shop scheduling problems.



---

*Source: 756251-2013-05-09.xml*