# Single-Machine Scheduling with Job Rejection, Deteriorating Effects, and Deteriorating Maintenance Activities

Authors: Haiwei Nian; Zhizhong Mao
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper addresses the single-machine scheduling problems with simultaneous considerations of job rejection, deterioration effects, and deteriorating multimaintenance activities. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the single machine. Three deterioration effect models are investigated, and it is assumed that each machine may be subject to several maintenance activities over the scheduling horizon, and the duration of the maintenance depends on its running time. Moreover, due to the restriction of the budget of maintenance, the upper bound of the total maintenance frequencies on the machine is assumed to be known in advance. The objective is to find jointly the optimal accepted job set, the optimal maintenance frequencies, the optimal maintenance positions, and the optimal accepted job sequence such that the cost function based on the total completion time and rejection penalty is minimized. It is shown that all the versions of the problem under study are polynomial time solutions.


---

## Body

## 1. Introduction

In classical deterministic scheduling models, the processing conditions, including the job processing times, are usually viewed as given constants. However, in many real-life situations, the processing conditions may vary over time, thereby affecting the actual durations of job processing. This leads to the study of scheduling models with variable job processing times. There are several categories of models that address scheduling problems with variable processing times. For example, the actual processing time of a job gets shorter if the job is scheduled later (such a phenomenon is called the “learning effect”). In scheduling with deterioration, the later a job starts, the longer it takes to process the job (such a job is called a “deteriorating job”). Furthermore, the job processing time can be modelled as a mixed form of both learning and deterioration. Applications of scheduling models with variable job processing times can be found in the forging process in steel plants, in silverware production, finance management, or workforce learning. The corresponding scheduling problems have received considerable research attention. For reviews of scheduling problems involving the learning effect, the reader may refer to Cheng and Wang [1], Cheng et al. [2, 3], Janiak and Rudek [4–6], Kuo et al. [7], Lee and Lai [8], Rudek [9], and Yin et al. [10, 11], while for reviews of research on scheduling with job deterioration, the reader may refer to Bachman et al. [12, 13], Inderfurth et al. [14], Janiak and Kovalyov [15], Mazdeh et al. [16], Yin et al. [17–19], and Zhao and Tang [20]. For studies considering a mixed form of both learning and deterioration, we refer the reader to Cheng et al. [21], Wang [22, 23], Wang and Cheng [24], Wang et al. [25–27], Yang and Kuo [28], and Yin and Xu [29]. The reader may also make reference to Alidaee and Womer [30], Biskup [31], and Cheng et al. [32] for recent state-of-the-art reviews in this area, as well as for discussion of practical applications of the models.Most literature in scheduling assumes that machines are available at all times. However, machines subject to maintenance are found prevalently in process industries and manufacturing systems. In the real world, machines are usually not continuously available due to maintenance activities, tool changes, or breakdowns. It is well-known that the maintenance activity is important to improve the production efficiency of the machines or the quality of the products. During the maintenance activity, the machine is unavailable for processing jobs. Scheduling in such an environment is specified as scheduling with availability constraints and it has attracted many researchers. For details on this stream of research, the reader may refer to the comprehensive surveys by Schmidt [33] and Ma et al. [34]. Moreover, in order to model a more realistic production system, the problem of joint scheduling with the deterioration effect and maintenance activity has received the attention of many researchers, including Cheng et al. [21], Gawiejnowicz [35], Ji et al. [36], Lee and Wu [37], Low et al. [38], Lodree and Geiger [39], Wu and Lee [40], Rustogi and Strusevich [41], S. Yang and D. Yang [42–44], and Zhao and Tang [45].On the other hand, scheduling problems have been extensively studied in the literature under the assumption that all jobs have to be processed. However, in many cases the scheduler has to make a higher level decision on how to partition the set of jobs into a set of accepted and a set of rejected jobs and to efficiently schedule the set of accepted jobs among the machines. Job rejection may be considered, for example, in cases where the machine capacity is too low and does not allow the scheduler to process all the jobs. In such cases, the rejected jobs may be either outsourced or not get served at all, thus incurring a rejection penalty either due to an outsourcing cost or due to loss of income and reputation (see [46]). The idea of scheduling with rejection is relatively new. It was first introduced by Bartal et al. [47], who studied the problem of minimizing the sum of makespan and rejection penalties on a set of identical parallel machines, focusing on approximations. Since then, scheduling problems with rejection jobs have been extensively studied in the literature. Recently, Shabtay et al. [46] offer a very robust approach to scheduling with rejection by providing a bicriteria analysis of a large set of scheduling problems that can all be represented by (or reduced to) the same mathematical formulation.In this problem, we investigate the scheduling problems with simultaneous considerations of rejected jobs, deterioration effects, and deteriorating multimaintenance activities which extends the problem considered in S. Yang and D. Yang [42] by allowing rejected jobs. The objective is to find jointly the accepted job set, the optimal maintenance frequencies, the optimal maintenance positions, and the optimal accepted job sequences such that the cost function based on the total completion time and rejection penalty is minimized. To the best of our knowledge, there are no papers in which such a problem has been studied so far. The rest of the paper is organized as follows: Section 2 formulates the problems under study. Section 3 addresses the optimal solution of the case where no maintenance is scheduled in the sequence. Section 4 provides polynomial time solutions for all the problems studied. We conclude the paper and suggest some future research topics in the last section.


## 2. Problem Definition

The single-machine scheduling with job rejection, deteriorating effects, and deteriorating maintenance activities may be stated as follows. Assume that there is a set ofn independent jobs N={J1,J2,…,Jn} to be processed on a single machine. The machine can handle at most one job at a time and job preemption is not allowed. Each job Jj becomes available for processing at time zero, requires a nonnegative normal processing time pj, and has a nonnegative rejection penalty ej. For each job we must decide either to schedule that job on the machine or to reject it. If we reject job Jj, we pay its rejection penalty ej. We denote the sets of accepted jobs and rejected jobs by A and A¯, respectively. Due to the deteriorating effects, maintenance may be performed on the machine to improve its production efficiency. In order to model a realistic manufacturing system, the machine may be subject to several maintenance activities during the planning horizon. As in S. Yang and D. Yang [42], we assume that the duration of each maintenance activity is a linear function of the running time of the machine and is denoted by mi=α+βti, where α>0 is the basic time of maintenance activity, β>0 is the deteriorating maintenance factor, and ti is the running time of the machine between the (i-1)th and ith maintenance activities of the machine. We further assume that a maintenance activity can be scheduled immediately after completing the processing of any job. After maintenance, the machine reverts to its initial condition and the deteriorating effect starts a new. The upper bound of the maintenance frequency on the machine due to the restriction of budget of maintenance is assumed to be known in advance. Denote by k and k0 the maintenance frequency and the upper bound of the maintenance frequency on the machine, respectively, where k≤k0≤n-1.There are three basic types of deteriorating effect investigated in our paper. The first type concerns the job-dependent deteriorating effect; that is, if jobJj is scheduled in the rth position, then its actual processing time pjr is defined by
(1)pjr=pjraj,j,r=1,2,…,n,
where aj>0 is its deteriorating factor of job Jj.The second type concerns the linear position-dependent deteriorating effect; that is, if jobJj is scheduled in the rth position, then its actual processing time pjr is defined by
(2)pjr=pj+bjr,j,r=1,2,…,n,
where bj>0 is the deteriorating ratio of job Jj.The third type concerns the linear time-dependent deteriorating effect model; that is, if jobJj is scheduled in the rth position, then its actual processing time pjr is defined by
(3)pjr=pj+csr,j,r=1,2,…,n,
where c>0 is the common deteriorating factor and sr is the starting time of a job processed in the position r in a sequence; that is, s1=0.The problem in this paper is to determine simultaneously the accepted job setA, the optimal maintenance frequencies, the optimal maintenance positions, and the optimal accepted job sequence S for minimizing the objective function
(4)Z(S,A,Ma)=∑j=1na‍C[j]+∑j∈A¯‍ej
when the upper bound of the maintenance frequency on the machine is given in advance, where na is the number of accepted jobs and C[j] denotes the completion time of the jth job in the accepted job sequence. Using the standard three-field notation introduced by Graham et al. [48], our scheduling problem can be denoted as 1∣pjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej‍, where pjr, ma, and k0 in the second field represent the type of deteriorating effect, the maintenance activity, and the upper bound of the maintenance frequency on the machine, respectively.


## 3. Optimal Solution for the Case Where There Is No Maintenance

In this section we first study the problems under the case that there is no maintenance scheduled during the planning horizon (i.e.,k=0) and show that all the problems studied are polynomially solvable. We begin with providing a useful lemma which will be used later.Lemma 1 (see [49]).
Consider two sequences of positive real numbersxi and yi(i=1,2,…,n). The value of ∑i=1nxiyi is the least if the sequences are monotonic in the opposite sense.Since the objective function is regular, there is an optimal schedule for the problems under consideration in which all the accepted jobs are processed consecutively without idle time and the first job starts at time 0.


### 3.1. The Problem1∣pjr=pjraj∣∑j=1naC[j]+∑j∈A¯ej

This subsection addresses the problem of finding the accepted job setA and the optimal accepted job sequence to minimize the objective function given by (4) under model (1).For a fixed job sequenceπ=(S,A¯) with na accepted jobs in the order of S, where S=(J[1],…,J[na]), (4) can be reformulated as
(5)Z(S,A¯)=∑r=1na‍(na-r+1)p[r]ra[r]+∑j∈A¯‍ej,
where p[r] and a[r] denote the normal processing time and aging factor of the job scheduled in the rth position in S, respectively.Theorem 2.
Given the number of accepted jobs, the problem1∣pjr=pjraj∣∑j=1naC[j]+∑j∈A¯ej can be formulated as an assignment problem.Proof.
Let the number of accepted jobs bena(1≤na≤n). By (5), we can define
(6)wjrna={(na-r+1)pjrajr=1,2,…,na,ejr=na+1,…,n,
as the cost of assigning job Jj(j=1,2,…,n) to the rth (r=1,2,…,n) position in the schedule. Furthermore, let xjr be the decision variable such that xjr=1 if job Jj is in the rth position, and xjr=0 otherwise, for j,r=1,2,…,n. Then the scheduling problem can be formulated as the following assignment problem:
(P1)Min∑j=1n‍∑r=1n‍wjrnaxjr,s.t.∑r=1n‍xjr=1,j=1,2,…,n,0000.∑j=1n‍xjr=1,r=1,2,…,n,0000.xjr∈{0,1},j,r=1,2,…,n.
The result follows.Summing up the above analysis, the following solution algorithm can be presented for the problem1∣pjr=pjraj∣∑j=1naC[j]+∑j∈A¯ej.Algorithm 3.
Consider the following.
Step  1. For na=0, calculate F(0)=∑j=1nej.
Step  2. For 1≤na≤n, solve the above assignment problem (P1) and calculate the corresponding objective value F(na).
Step  3. The optimal objective value is min{F(na)∣0≤na≤n}.Theorem 4.
Algorithm3 solves the problem 1∣pjr=pjraj∣∑j=1naC[j]+∑j∈A¯ej in O(n4) time.Proof.
The correctness of Algorithm3 follows directly from Theorem 2. Step 1 requires O(n) time, while Step 2 needs to solve n − 1 assignment problems where each one can be solved in O(n3) time. Therefore, the overall time complexity of the algorithm is O(n4).Now, let us turn our attention to the special case whereaj=a for each j=1,2,…,n, denoted as 1∣pjr=pjra∣∑j=1naC[j]+∑j∈A¯ej. In this case, (5) can be reformulated as follows. 								(7)Z(S,A¯)=∑r=1na‍ξrp[r]+∑j∈A¯‍ej,
where ξr=(na-r+1)ra for r=1,2,…,n.In what follows, we renumber the jobs in the nonincreasing order of their normal processing times (LPT order) and design a dynamic programming algorithm for the problem1∣pjr=pjra∣∑j=1naC[j]+∑j∈A¯ej as follows.Let(j,r)ma be a state, where ma is the number of accepted jobs, j represents that the jobs {J1,J2,…,Jj} have been considered, and r, 0≤r≤j, represents how many of these jobs have been sequenced as accepted jobs, and let fma(j,r) be an optimal solution value for the state (j,r)ma, and let Sma(j,r) be any schedule in state (j,r)ma with solution value fma(j,r). By definition, set fma(j,r)=+∞ if no such schedule exists.For givenna, calculate each ξr values according to (7) for r=1,…,na. Sort ξr in nondecreasing order and reindex them as ξjna for j=1,…,na such that ξ1na≤ξ2na≤⋯≤ξnana. According to Lemma 1, the lth accepted job in {J1,…,Jj} should be matched with ξlna. Thus, the schedule Sma(j,r) must have been constructed by taking one of the following two decisions in a previous state.(1)
Jj is scheduled as an accepted job: in this case Sma(j,r) must have been obtained from schedule Sma(j-1,r-1) and fma(j,r)=fma(j-1,r-1)+pjξrna.(2)
Jj is scheduled as a rejected job: in this case Sma(j,r) must have been obtained from schedule Sma(j-1,r) and fma(j,r)=fma(j-1,r)+ej.Based on the above analysis, we can develop an algorithm as follows.Algorithm 5.
Consider the following.
Step  1. Renumber the jobs in the LPT order.
Step  2. For 0≤na≤n, we have the following.Step  2.1. Calculate each ξr values according to (7) for r=1,…,na. Sort ξr in nondecreasing order and reindex them as ξjna for j=1,…,na such that ξ1na≤ξ2na≤⋯≤ξnana. Initialize
(8)fma(j,r)={0ifj=r=0,+∞otherwise.Step  2.2. For r=0,1,…,min{ma,j}, compute
(9)fma(j,r)=min{fma(j-1,r-1)+pjξrnafma(j-1,r)+ej.Step  3. The optimal objective value is F=min{fma(n,ma)∣0≤ma≤n} and the resulting optimal accepted job sequence can be found by backtracking.For each givenna, the algorithm generates no more than n2 states and computing each fma(j,r) requires constant time, so the time complexity is O(n3). This implies the following theorem.Theorem 6.
Algorithm5 solves the problem 1∣pjr=pjra∣∑j=1naC[j]+∑j∈A¯ej in O(n3) time.


### 3.2.  The Problem1∣pjr=pj+bjr∣∑j=1naC[j]+∑j∈A¯ej

This subsection addresses the problem of finding the accepted job setA and the optimal accepted job sequence to minimize the objective function given by (4) under model (2).For a fixed job sequenceπ=(S,A¯) with na accepted jobs in the order of S, where S=(J[1],…,J[na]), (4) can be reformulated as
(10)Z(S,A¯)=∑r=1na‍(na-r+1)(p[r]+rb[r])+∑j∈A¯‍ej.Theorem 7.
Given the number of accepted jobs, the problem1∣pjr=pj+bjr∣∑j=1naC[j]+∑j∈A¯ej can be formulated as an assignment problem.Proof.
Let the number of accepted jobs bena  (1≤na≤n). By (5), we can define
(11)ɛjrna={(na-r+1)(pj+rbj)r=1,2,…,na,ejr=na+1,…,n,
as the cost of assigning job Jj(j=1,2,…,n) to the rth (r=1,2,…,n) position in the schedule. Furthermore, let xjr be the decision variable such that xjr=1 if job Jj is in the rth position, and xjr=0 otherwise, for j,r=1,2,…,n. Then the scheduling problem can be formulated as the following assignment problem:
(P2)Min∑j=1n‍∑r=1n‍ɛjrnaxjrs.t.∑r=1n‍xjr=1,j=1,2,…,n,0000∑j=1n‍xjr=1,r=1,2,…,n,0000xjr∈{0,1},j,r=1,2,…,n.
The result follows.Summing up the above analysis, the following solution algorithm can be presented for the problem1∣pjr=pj+bjr∣∑j=1naC[j]+∑j∈A¯ej.Algorithm 8.
Consider the following.
Step  1. For na=0, calculate F(0)=∑j=1nej.
Step  2. For 1≤na≤n, solve the above assignment problem (P2) and calculate the corresponding objective value F(na).
Step  3. The optimal objective value is min{F(na)∣0≤na≤n}.Theorem 9.
Algorithm8 solves the problem 1∣pjr=pj+bjr∣∑j=1naC[j]+∑j∈A¯ej in O(n4) time.


### 3.3.  The Problem1∣pjr=pj+csr∣∑j=1naC[j]+∑j∈A¯ej

This subsection addresses the problem of finding the accepted job setA and the optimal accepted job sequence to minimize the objective function given by (4) under model (3).For a fixed job sequenceπ=(S,A¯) with na accepted jobs in the order of S, where S=(J[1],…,J[na]), (4) can be reformulated as
(12)Z(S,A¯)=∑r=1na‍ηrp[r]+∑j∈A¯‍ej,
where ηr=∑l=0na-r‍(1+c)l. Since c>0, we have that η1>η2>⋯>ηna.Defineφr=∑l=0r‍(1+c)l for r=1,2,…,n. Then φ1<φ2<⋯<φn. Assume that the jobs have been reindexed in the LPT order. In what follows, we design a backward dynamic programming algorithm for the problem 1∣pjr=pj+csr∣∑j=1naC[j]+∑j∈A¯ej. Let (j,r) be a state, in which j represents that the jobs {Jj,Jj+1,…,Jn} have been considered, and r, 0≤r≤n-j+1, represents how many of these jobs have been sequenced as accepted jobs, and let f(j,r) be an optimal solution value for the state (j,r) and S(j,r) any schedule in state (j,r) with solution value f(j,r). By definition, set f(j,r)=+∞ if no such schedule exists. Then, the schedule S(j,r) must have been constructed by taking one of the following two decisions in a previous state.(1)
Jj is scheduled as an accepted job: in this case, by Lemma 1, the lth accepted job in {Jj,Jj+1,…,Jn} should be matched with φl; hence S(j,r) must have been obtained from schedule S(j+1,r-1) and f(j,r)=fma(j+1,r-1)+pjφr.(2)
Jj is scheduled as a rejected job: in this case S(j,r) must have been obtained from schedule S(j+1,r) and f(j,r)=f(j+1,r)+ej.The dynamic programming algorithm can be formally stated as follows.Algorithm 10.
Consider the following.
Step  1. Renumber the jobs in the LPT order.
Step  2. Initialize
(13)f(j,r)={0ifj=r=0,+∞otherwise.
Step  3. For r=0,1,…,j, compute
(14)f(j,r)=min{f(j+1,r-1)+pjφrf(j+1,r)+ej.
Step  4. The optimal objective value is F=min{F(1,r)∣0≤r≤n} and the resulting optimal accepted job sequence can be found by backtracking.Theorem 11.
Algorithm10 solves the problem 1∣pjr=pj+csr∣∑j=1naC[j]+∑j∈A¯ej in O(n2) time.


## 3.1. The Problem1∣pjr=pjraj∣∑j=1naC[j]+∑j∈A¯ej

This subsection addresses the problem of finding the accepted job setA and the optimal accepted job sequence to minimize the objective function given by (4) under model (1).For a fixed job sequenceπ=(S,A¯) with na accepted jobs in the order of S, where S=(J[1],…,J[na]), (4) can be reformulated as
(5)Z(S,A¯)=∑r=1na‍(na-r+1)p[r]ra[r]+∑j∈A¯‍ej,
where p[r] and a[r] denote the normal processing time and aging factor of the job scheduled in the rth position in S, respectively.Theorem 2.
Given the number of accepted jobs, the problem1∣pjr=pjraj∣∑j=1naC[j]+∑j∈A¯ej can be formulated as an assignment problem.Proof.
Let the number of accepted jobs bena(1≤na≤n). By (5), we can define
(6)wjrna={(na-r+1)pjrajr=1,2,…,na,ejr=na+1,…,n,
as the cost of assigning job Jj(j=1,2,…,n) to the rth (r=1,2,…,n) position in the schedule. Furthermore, let xjr be the decision variable such that xjr=1 if job Jj is in the rth position, and xjr=0 otherwise, for j,r=1,2,…,n. Then the scheduling problem can be formulated as the following assignment problem:
(P1)Min∑j=1n‍∑r=1n‍wjrnaxjr,s.t.∑r=1n‍xjr=1,j=1,2,…,n,0000.∑j=1n‍xjr=1,r=1,2,…,n,0000.xjr∈{0,1},j,r=1,2,…,n.
The result follows.Summing up the above analysis, the following solution algorithm can be presented for the problem1∣pjr=pjraj∣∑j=1naC[j]+∑j∈A¯ej.Algorithm 3.
Consider the following.
Step  1. For na=0, calculate F(0)=∑j=1nej.
Step  2. For 1≤na≤n, solve the above assignment problem (P1) and calculate the corresponding objective value F(na).
Step  3. The optimal objective value is min{F(na)∣0≤na≤n}.Theorem 4.
Algorithm3 solves the problem 1∣pjr=pjraj∣∑j=1naC[j]+∑j∈A¯ej in O(n4) time.Proof.
The correctness of Algorithm3 follows directly from Theorem 2. Step 1 requires O(n) time, while Step 2 needs to solve n − 1 assignment problems where each one can be solved in O(n3) time. Therefore, the overall time complexity of the algorithm is O(n4).Now, let us turn our attention to the special case whereaj=a for each j=1,2,…,n, denoted as 1∣pjr=pjra∣∑j=1naC[j]+∑j∈A¯ej. In this case, (5) can be reformulated as follows. 								(7)Z(S,A¯)=∑r=1na‍ξrp[r]+∑j∈A¯‍ej,
where ξr=(na-r+1)ra for r=1,2,…,n.In what follows, we renumber the jobs in the nonincreasing order of their normal processing times (LPT order) and design a dynamic programming algorithm for the problem1∣pjr=pjra∣∑j=1naC[j]+∑j∈A¯ej as follows.Let(j,r)ma be a state, where ma is the number of accepted jobs, j represents that the jobs {J1,J2,…,Jj} have been considered, and r, 0≤r≤j, represents how many of these jobs have been sequenced as accepted jobs, and let fma(j,r) be an optimal solution value for the state (j,r)ma, and let Sma(j,r) be any schedule in state (j,r)ma with solution value fma(j,r). By definition, set fma(j,r)=+∞ if no such schedule exists.For givenna, calculate each ξr values according to (7) for r=1,…,na. Sort ξr in nondecreasing order and reindex them as ξjna for j=1,…,na such that ξ1na≤ξ2na≤⋯≤ξnana. According to Lemma 1, the lth accepted job in {J1,…,Jj} should be matched with ξlna. Thus, the schedule Sma(j,r) must have been constructed by taking one of the following two decisions in a previous state.(1)
Jj is scheduled as an accepted job: in this case Sma(j,r) must have been obtained from schedule Sma(j-1,r-1) and fma(j,r)=fma(j-1,r-1)+pjξrna.(2)
Jj is scheduled as a rejected job: in this case Sma(j,r) must have been obtained from schedule Sma(j-1,r) and fma(j,r)=fma(j-1,r)+ej.Based on the above analysis, we can develop an algorithm as follows.Algorithm 5.
Consider the following.
Step  1. Renumber the jobs in the LPT order.
Step  2. For 0≤na≤n, we have the following.Step  2.1. Calculate each ξr values according to (7) for r=1,…,na. Sort ξr in nondecreasing order and reindex them as ξjna for j=1,…,na such that ξ1na≤ξ2na≤⋯≤ξnana. Initialize
(8)fma(j,r)={0ifj=r=0,+∞otherwise.Step  2.2. For r=0,1,…,min{ma,j}, compute
(9)fma(j,r)=min{fma(j-1,r-1)+pjξrnafma(j-1,r)+ej.Step  3. The optimal objective value is F=min{fma(n,ma)∣0≤ma≤n} and the resulting optimal accepted job sequence can be found by backtracking.For each givenna, the algorithm generates no more than n2 states and computing each fma(j,r) requires constant time, so the time complexity is O(n3). This implies the following theorem.Theorem 6.
Algorithm5 solves the problem 1∣pjr=pjra∣∑j=1naC[j]+∑j∈A¯ej in O(n3) time.


## 3.2.  The Problem1∣pjr=pj+bjr∣∑j=1naC[j]+∑j∈A¯ej

This subsection addresses the problem of finding the accepted job setA and the optimal accepted job sequence to minimize the objective function given by (4) under model (2).For a fixed job sequenceπ=(S,A¯) with na accepted jobs in the order of S, where S=(J[1],…,J[na]), (4) can be reformulated as
(10)Z(S,A¯)=∑r=1na‍(na-r+1)(p[r]+rb[r])+∑j∈A¯‍ej.Theorem 7.
Given the number of accepted jobs, the problem1∣pjr=pj+bjr∣∑j=1naC[j]+∑j∈A¯ej can be formulated as an assignment problem.Proof.
Let the number of accepted jobs bena  (1≤na≤n). By (5), we can define
(11)ɛjrna={(na-r+1)(pj+rbj)r=1,2,…,na,ejr=na+1,…,n,
as the cost of assigning job Jj(j=1,2,…,n) to the rth (r=1,2,…,n) position in the schedule. Furthermore, let xjr be the decision variable such that xjr=1 if job Jj is in the rth position, and xjr=0 otherwise, for j,r=1,2,…,n. Then the scheduling problem can be formulated as the following assignment problem:
(P2)Min∑j=1n‍∑r=1n‍ɛjrnaxjrs.t.∑r=1n‍xjr=1,j=1,2,…,n,0000∑j=1n‍xjr=1,r=1,2,…,n,0000xjr∈{0,1},j,r=1,2,…,n.
The result follows.Summing up the above analysis, the following solution algorithm can be presented for the problem1∣pjr=pj+bjr∣∑j=1naC[j]+∑j∈A¯ej.Algorithm 8.
Consider the following.
Step  1. For na=0, calculate F(0)=∑j=1nej.
Step  2. For 1≤na≤n, solve the above assignment problem (P2) and calculate the corresponding objective value F(na).
Step  3. The optimal objective value is min{F(na)∣0≤na≤n}.Theorem 9.
Algorithm8 solves the problem 1∣pjr=pj+bjr∣∑j=1naC[j]+∑j∈A¯ej in O(n4) time.


## 3.3.  The Problem1∣pjr=pj+csr∣∑j=1naC[j]+∑j∈A¯ej

This subsection addresses the problem of finding the accepted job setA and the optimal accepted job sequence to minimize the objective function given by (4) under model (3).For a fixed job sequenceπ=(S,A¯) with na accepted jobs in the order of S, where S=(J[1],…,J[na]), (4) can be reformulated as
(12)Z(S,A¯)=∑r=1na‍ηrp[r]+∑j∈A¯‍ej,
where ηr=∑l=0na-r‍(1+c)l. Since c>0, we have that η1>η2>⋯>ηna.Defineφr=∑l=0r‍(1+c)l for r=1,2,…,n. Then φ1<φ2<⋯<φn. Assume that the jobs have been reindexed in the LPT order. In what follows, we design a backward dynamic programming algorithm for the problem 1∣pjr=pj+csr∣∑j=1naC[j]+∑j∈A¯ej. Let (j,r) be a state, in which j represents that the jobs {Jj,Jj+1,…,Jn} have been considered, and r, 0≤r≤n-j+1, represents how many of these jobs have been sequenced as accepted jobs, and let f(j,r) be an optimal solution value for the state (j,r) and S(j,r) any schedule in state (j,r) with solution value f(j,r). By definition, set f(j,r)=+∞ if no such schedule exists. Then, the schedule S(j,r) must have been constructed by taking one of the following two decisions in a previous state.(1)
Jj is scheduled as an accepted job: in this case, by Lemma 1, the lth accepted job in {Jj,Jj+1,…,Jn} should be matched with φl; hence S(j,r) must have been obtained from schedule S(j+1,r-1) and f(j,r)=fma(j+1,r-1)+pjφr.(2)
Jj is scheduled as a rejected job: in this case S(j,r) must have been obtained from schedule S(j+1,r) and f(j,r)=f(j+1,r)+ej.The dynamic programming algorithm can be formally stated as follows.Algorithm 10.
Consider the following.
Step  1. Renumber the jobs in the LPT order.
Step  2. Initialize
(13)f(j,r)={0ifj=r=0,+∞otherwise.
Step  3. For r=0,1,…,j, compute
(14)f(j,r)=min{f(j+1,r-1)+pjφrf(j+1,r)+ej.
Step  4. The optimal objective value is F=min{F(1,r)∣0≤r≤n} and the resulting optimal accepted job sequence can be found by backtracking.Theorem 11.
Algorithm10 solves the problem 1∣pjr=pj+csr∣∑j=1naC[j]+∑j∈A¯ej in O(n2) time.


## 4. Problems1∣pjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej

In this section we address the problem1∣pjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej and show that all the problems consideration are polynomially solvable.If the machine is subject tok times of maintenance, then there are (k+1) groups of jobs in the accepted job sequence. Let G1,G2,…,Gk+1 denote the groups of accepted jobs in the schedule. Then the group of accepted jobs and maintenance sequence can be denoted as (G1,M1,G2,M2,…,Gk,Mk,Gk+1), where Mj represents the jth maintenance activity. Denote by P(n,k+1)=(n1,n2,…,nk+1) the allocation vector of the number of jobs in each group, where nj≥1 is the number of jobs in group Gj and ∑j=1k+1nj=n. Then group Gj can be denoted as Gj=(J[j1],J[j2],…,J[jnj]).Analogous to the analysis in Section3, since the objective function is regular, there is an optimal schedule for the problems under consideration in which all the accepted jobs are processed consecutively without idle time and the first job starts at time 0.


### 4.1. The Problem1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej

For a fixed job sequence and maintenance activitiesπ=(G1,M1,G2,M2,…,Gk,Mk,Gk+1,A¯) with na accepted jobs, (4) can be reformulated as
(15)Z(S,A¯,MA)=∑l=1k‍(na-∑m=1l‍nm)α+∑l=1k+1‍∑r=1nl‍wr(l)+∑r=na+1n‍e[r],
where wr(l)=[(nl-r+1+na-∑m=1lnm)+(na-∑m=1lnm)β]p[lr]ra[lr], p[lr] and a[lr] denote the normal processing time and deteriorating factor of the job scheduled in the rth position in l-group, respectively.Theorem 12.
Given the number of accepted jobs, the problem1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej can be formulated as an assignment problem.Proof.
Let the number of accepted jobs bena(1≤na≤n), and let xjr be the decision variable such that xjr=1 if job Jj is in the rth position, and xjr=0 otherwise, for j,r=1,2,…,n. Then the scheduling problem can be formulated as the following assignment problem:
(P3)Min∑l=1k‍(na-yl)α000..000.+∑j=1n‍(∑l=1k+1‍∑r=yl-1yl‍[(na-r+1)+(na-yl)β]00000000…000.00×pj(r-yl-1)ajxjr+∑r=na+1n‍ejxjr),s.t.∑r=1n‍xjr=1,j=1,2,…,n,0000∑j=1n‍xjr=1,r=1,2,…,n,0000xjr∈{0,1},j,r=1,2,…,n,
where yl=∑m=1lnm, for l=1,…,k+1, and y0=0. The result follows.Summing up the above analysis, the following solution algorithm can be presented for the problem1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej.Algorithm 13.
Consider the following.
Step  1. For na=0, calculate f(0)=∑j=1nej.
Step  2. For given na, k, and vector P(na,k+1)=(n1,n2,…,nk+1), solve the above assignment problem (P3) and calculate the corresponding objective value f(na,k,P(na,k+1)).
Step  3. The optimal objective value is min{f(na,k,P(na,k+1))∣0≤na≤n,1≤k≤na-1,∑j=1k+1nj=na}.Theorem 14.
Algorithm13 solves the problem 1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej in O(nk0+4) time.Proof.
The correction follows directly from Theorem12. Step 1 requires O(n) time. For given na, k, and P(na,k+1), solving this assignment problem requires an effort of O(n3). Now, the question is how many P(na,k+1) vectors exist. For given na and k, the number of jobs nj in group Gj may be 1,…,na-1, for j=1,…,k+1 and the number of jobs assigned to the last group (i.e., Gk+1) can be determined uniquely by the numbers of jobs on the first k groups. Thus we conclude that the upper bound of the number of P(na,k+1) vectors is (na-1)k≤nk≤nk0. Therefore, the overall time complexity of the algorithm is indeed O(nk0+4).Now, let us turn our attention to the special case whereaj=a for each j=1,2,…,n, denoted as 1∣pjr=pjra, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej. In this case, (4) can be reformulated as follows:
(16)Z(S,A¯,MA)=∑l=1k‍(na-∑m=1l‍nm)α+∑l=1k+1‍∑r=1nl‍ξr(l)p[lr]+∑r=na+1n‍e[r],
where
(17)ξr(l)=[(nl-r+1+na-∑m=1l‍nm)00+(na-∑m=1l‍nm)β]ra,
for l=1,…,k+1 and r=1,…,nl.Assume that the jobs have been reindexed in the LPT order. In what follows, we develop a forward dynamic programming algorithm to solve the problem1∣pjr=pjra, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej. Let (j,r)(ma,k,P(ma,k)) be a state, where j represents that the jobs {J1,J2,…,Jj} have been considered, and r, 0≤r≤j, represents how many of these jobs have been sequenced as accepted jobs, while in the final optimal schedule for the whole job set, it contains exactly ma accepted jobs, k maintenance activities, and ni jobs in group Gi for i=1,…,k+1. Let f(ma,k,P(ma,k))(j,r) be an optimal solution value for the state (j,r)(ma,k,P(ma,k)) and S(ma,k,P(ma,k))(j,r) any schedule in state (j,r)(ma,k,P(ma,k)) with solution value f(ma,k,P(ma,k))(j,r). By definition, set f(ma,k,P(ma,k))(j,r)=+∞ if no such schedule exists.For givenma, k, and P(ma,k), calculate each ξr(l) values according to (17) for l=1,…,k+1 and r=1,…,nl. Sort ξr(l) in nondecreasing order and reindex them as ξj(ma,k,P(ma,k)) for j=1,…,na such that ξ1(ma,k,P(ma,k))≤ξ2(ma,k,P(ma,k))≤⋯≤ξna(ma,k,P(ma,k)). According to Lemma 1, the lth accepted job in {J1,…,Jj} should be matched with ξl(ma,k,P(ma,k)). Thus, the schedule S(ma,k,P(ma,k))(j,r) must have been constructed by taking one of the following two decisions in a previous state.(1)
JobJj is scheduled as an accepted job. In this case, S(ma,k,P(ma,k))(j,r) must have been obtained from schedule S(ma,k,P(ma,k))(j-1,r-1) and
(18)f(ma,k,P(ma,k))(j,r)=f(ma,k,P(ma,k))(j-1,r-1)+pjξr(ma,k,P(ma,k)).(2)
JobJj is scheduled as a rejected job. In this case, S(ma,k,P(ma,k))(j,r) must have been obtained from schedule S(ma,k,P(ma,k))(j-1,r) and
(19)f(ma,k,P(ma,k))(j,r)=f(ma,k,P(ma,k))(j-1,r-1)+ej.Based on the above analysis, we can develop an algorithm as follows.Algorithm 15.
Consider the following.
Step  1. Reindex the jobs in the in the LPT order.
Step  2. For 0≤ma≤n, 0≤k≤min{k0,ma-1}, and P(ma,k)=(n1,…,nk+1), we have the following.
Step  2.1. Calculate ξ(l)(r) for l=1,…,k+1 and r=1,…,nl according to (17). Sort ξr(l) in nondecreasing order and reindex them as ξj(ma,k,P(ma,k)) for j=1,…,na such that ξ1(ma,k,P(ma,k))≤ξ2(ma,k,P(ma,k))≤⋯≤ξna(ma,k,P(ma,k)).
Step  2.2. For 0≤j≤n, 0≤r≤j, do as follows.
Initialize(20)f(ma,k,P(ma,k))(j,r)={0ifj=r=0,+∞otherwise,
and compute
(21)f(ma,k,P(ma,k))(j,r)=min{f(ma,k,P(ma,k))(j-1,r-1)+pjξr(ma,k,P(ma,k)),f(ma,k,P(ma,k))(j-1,r-1)+ej.
Step3. The optimal solution value is min{f(ma,k,P(ma,k))(n,ma)+∑l=1k‍(na − ∑m=1l‍nm)α∣0≤ma≤n,0≤k≤min{k0,ma-1},∑j=1k+1nj=na} and the optimal schedule can be found by backtracking.Theorem 16.
Algorithm15 solves the problem 1∣pjr=pjra, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej in O(nk0+3) time.Proof.
Optimality is guaranteed by the principles underlying dynamic programming. We now consider the computational complexity of the dynamic programming solution algorithm. For each givenma and k, the number of vectors P(l,m) can be approximated as nk0, while for each given l, m, and P(l,m), we have at most n2 states and computing each f(ma,k,P(ma,k))(j,r) requires constant time. Therefore, the overall time complexity of the algorithm is O(nk0+3).


### 4.2.  The Problem1∣pjr=pj+bjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej

For a fixed job sequence and maintenance activitiesπ=(G1,M1,G2,M2,…,Gk,Mk,Gk+1,A¯) with na accepted jobs in the order of S, (4) can be reformulated as
(22)Z(S,A¯,MA)=∑l=1k‍(na-∑m=1l‍nm)α+∑l=1k+1‍∑r=1nl‍ɛr(l)(p[lr]+b[lr]r)+∑r=na+1n‍e[r],
where
(23)ɛr(l)=[(nl-r+1+na-∑m=1l‍nm)+(na-∑m=1l‍nm)β]
for l=1,…,k+1 and r=1,…,nl.Theorem 17.
Given the number of accepted jobs, the problem1∣pjr=pj+bjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej can be formulated as an assignment problem.Proof.
Let the number of accepted jobs bena(1≤na≤n), and let xjr be the decision variable such that xjr=1 if job Jj is in the rth position, and xjr=0 otherwise, for j,r=1,2,…,n. Then the scheduling problem can be formulated as the following assignment problem:
(P4)Min∑l=1k‍(na-yl)α00000.000+∑j=1n‍(∑l=1k+1‍∑r=yl-1yl‍[(na-r+1)+(na-yl)β]0000000000000000×(pj+bj(r-yl-1))xjr0000000000000000+∑r=na+1n‍ejxjr),s.t.∑r=1n‍xjr=1,j=1,2,…,n,0000∑j=1n‍xjr=1,r=1,2,…,n,0000xjr∈{0,1},j,r=1,2,…,n,
where yl=∑m=1lnm, for l=1,…,k+1, and y0=0. The result follows.Summing up the above analysis, the following solution algorithm can be presented for the problem1∣pjr=pj+bjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej.Algorithm 18.
Consider the following.
Step  1. For na=0, calculate F(0)=∑j=1nej.
Step  2. For given na, k, and vector P(na,k+1)=(n1,n2,…,nk+1), solve the above assignment problem (P4) and calculate the corresponding objective value F(na,k,P(na,k+1)).
Step  3. The optimal objective value is min{F(na,k,P(na,k+1))∣0≤na≤n, 1≤k≤na-1,∑j=1k+1nj=na}.Theorem 19.
Algorithm18 solves the problem 1∣pjr=pj+bjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej in O(nk0+4) time.


### 4.3.  The Problem1∣pjr=pj+csr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej

For a fixed job sequence and maintenance activitiesπ=(G1,M1,G2,M2,…,Gk,Mk,Gk+1,A¯) with na accepted jobs in the order of S, (4) can be reformulated as
(24)Z(S,A¯,MA)=∑l=1k‍(na-∑m=1l‍nm)α+∑l=1k+1‍∑r=1nl‍ηr(l)p[lr]+∑r=na+1n‍e[r],
where
(25)ηr(l)=(1+β)(na-∑m=1l‍nm)(1+c)nl-r+∑i=1nl-r‍(1+c)i
for l=1,…,k+1 and r=1,…,nl.Analogous to the problem1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej, Algorithm 13 also can be used for solving the problem 1∣pjr=pj+csr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej by replacing ξr(l) with ηr(l).Theorem 20.
The problem1∣pjr=pj+csr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej can be solved in O(nk0+3) time.


## 4.1. The Problem1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej

For a fixed job sequence and maintenance activitiesπ=(G1,M1,G2,M2,…,Gk,Mk,Gk+1,A¯) with na accepted jobs, (4) can be reformulated as
(15)Z(S,A¯,MA)=∑l=1k‍(na-∑m=1l‍nm)α+∑l=1k+1‍∑r=1nl‍wr(l)+∑r=na+1n‍e[r],
where wr(l)=[(nl-r+1+na-∑m=1lnm)+(na-∑m=1lnm)β]p[lr]ra[lr], p[lr] and a[lr] denote the normal processing time and deteriorating factor of the job scheduled in the rth position in l-group, respectively.Theorem 12.
Given the number of accepted jobs, the problem1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej can be formulated as an assignment problem.Proof.
Let the number of accepted jobs bena(1≤na≤n), and let xjr be the decision variable such that xjr=1 if job Jj is in the rth position, and xjr=0 otherwise, for j,r=1,2,…,n. Then the scheduling problem can be formulated as the following assignment problem:
(P3)Min∑l=1k‍(na-yl)α000..000.+∑j=1n‍(∑l=1k+1‍∑r=yl-1yl‍[(na-r+1)+(na-yl)β]00000000…000.00×pj(r-yl-1)ajxjr+∑r=na+1n‍ejxjr),s.t.∑r=1n‍xjr=1,j=1,2,…,n,0000∑j=1n‍xjr=1,r=1,2,…,n,0000xjr∈{0,1},j,r=1,2,…,n,
where yl=∑m=1lnm, for l=1,…,k+1, and y0=0. The result follows.Summing up the above analysis, the following solution algorithm can be presented for the problem1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej.Algorithm 13.
Consider the following.
Step  1. For na=0, calculate f(0)=∑j=1nej.
Step  2. For given na, k, and vector P(na,k+1)=(n1,n2,…,nk+1), solve the above assignment problem (P3) and calculate the corresponding objective value f(na,k,P(na,k+1)).
Step  3. The optimal objective value is min{f(na,k,P(na,k+1))∣0≤na≤n,1≤k≤na-1,∑j=1k+1nj=na}.Theorem 14.
Algorithm13 solves the problem 1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej in O(nk0+4) time.Proof.
The correction follows directly from Theorem12. Step 1 requires O(n) time. For given na, k, and P(na,k+1), solving this assignment problem requires an effort of O(n3). Now, the question is how many P(na,k+1) vectors exist. For given na and k, the number of jobs nj in group Gj may be 1,…,na-1, for j=1,…,k+1 and the number of jobs assigned to the last group (i.e., Gk+1) can be determined uniquely by the numbers of jobs on the first k groups. Thus we conclude that the upper bound of the number of P(na,k+1) vectors is (na-1)k≤nk≤nk0. Therefore, the overall time complexity of the algorithm is indeed O(nk0+4).Now, let us turn our attention to the special case whereaj=a for each j=1,2,…,n, denoted as 1∣pjr=pjra, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej. In this case, (4) can be reformulated as follows:
(16)Z(S,A¯,MA)=∑l=1k‍(na-∑m=1l‍nm)α+∑l=1k+1‍∑r=1nl‍ξr(l)p[lr]+∑r=na+1n‍e[r],
where
(17)ξr(l)=[(nl-r+1+na-∑m=1l‍nm)00+(na-∑m=1l‍nm)β]ra,
for l=1,…,k+1 and r=1,…,nl.Assume that the jobs have been reindexed in the LPT order. In what follows, we develop a forward dynamic programming algorithm to solve the problem1∣pjr=pjra, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej. Let (j,r)(ma,k,P(ma,k)) be a state, where j represents that the jobs {J1,J2,…,Jj} have been considered, and r, 0≤r≤j, represents how many of these jobs have been sequenced as accepted jobs, while in the final optimal schedule for the whole job set, it contains exactly ma accepted jobs, k maintenance activities, and ni jobs in group Gi for i=1,…,k+1. Let f(ma,k,P(ma,k))(j,r) be an optimal solution value for the state (j,r)(ma,k,P(ma,k)) and S(ma,k,P(ma,k))(j,r) any schedule in state (j,r)(ma,k,P(ma,k)) with solution value f(ma,k,P(ma,k))(j,r). By definition, set f(ma,k,P(ma,k))(j,r)=+∞ if no such schedule exists.For givenma, k, and P(ma,k), calculate each ξr(l) values according to (17) for l=1,…,k+1 and r=1,…,nl. Sort ξr(l) in nondecreasing order and reindex them as ξj(ma,k,P(ma,k)) for j=1,…,na such that ξ1(ma,k,P(ma,k))≤ξ2(ma,k,P(ma,k))≤⋯≤ξna(ma,k,P(ma,k)). According to Lemma 1, the lth accepted job in {J1,…,Jj} should be matched with ξl(ma,k,P(ma,k)). Thus, the schedule S(ma,k,P(ma,k))(j,r) must have been constructed by taking one of the following two decisions in a previous state.(1)
JobJj is scheduled as an accepted job. In this case, S(ma,k,P(ma,k))(j,r) must have been obtained from schedule S(ma,k,P(ma,k))(j-1,r-1) and
(18)f(ma,k,P(ma,k))(j,r)=f(ma,k,P(ma,k))(j-1,r-1)+pjξr(ma,k,P(ma,k)).(2)
JobJj is scheduled as a rejected job. In this case, S(ma,k,P(ma,k))(j,r) must have been obtained from schedule S(ma,k,P(ma,k))(j-1,r) and
(19)f(ma,k,P(ma,k))(j,r)=f(ma,k,P(ma,k))(j-1,r-1)+ej.Based on the above analysis, we can develop an algorithm as follows.Algorithm 15.
Consider the following.
Step  1. Reindex the jobs in the in the LPT order.
Step  2. For 0≤ma≤n, 0≤k≤min{k0,ma-1}, and P(ma,k)=(n1,…,nk+1), we have the following.
Step  2.1. Calculate ξ(l)(r) for l=1,…,k+1 and r=1,…,nl according to (17). Sort ξr(l) in nondecreasing order and reindex them as ξj(ma,k,P(ma,k)) for j=1,…,na such that ξ1(ma,k,P(ma,k))≤ξ2(ma,k,P(ma,k))≤⋯≤ξna(ma,k,P(ma,k)).
Step  2.2. For 0≤j≤n, 0≤r≤j, do as follows.
Initialize(20)f(ma,k,P(ma,k))(j,r)={0ifj=r=0,+∞otherwise,
and compute
(21)f(ma,k,P(ma,k))(j,r)=min{f(ma,k,P(ma,k))(j-1,r-1)+pjξr(ma,k,P(ma,k)),f(ma,k,P(ma,k))(j-1,r-1)+ej.
Step3. The optimal solution value is min{f(ma,k,P(ma,k))(n,ma)+∑l=1k‍(na − ∑m=1l‍nm)α∣0≤ma≤n,0≤k≤min{k0,ma-1},∑j=1k+1nj=na} and the optimal schedule can be found by backtracking.Theorem 16.
Algorithm15 solves the problem 1∣pjr=pjra, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej in O(nk0+3) time.Proof.
Optimality is guaranteed by the principles underlying dynamic programming. We now consider the computational complexity of the dynamic programming solution algorithm. For each givenma and k, the number of vectors P(l,m) can be approximated as nk0, while for each given l, m, and P(l,m), we have at most n2 states and computing each f(ma,k,P(ma,k))(j,r) requires constant time. Therefore, the overall time complexity of the algorithm is O(nk0+3).


## 4.2.  The Problem1∣pjr=pj+bjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej

For a fixed job sequence and maintenance activitiesπ=(G1,M1,G2,M2,…,Gk,Mk,Gk+1,A¯) with na accepted jobs in the order of S, (4) can be reformulated as
(22)Z(S,A¯,MA)=∑l=1k‍(na-∑m=1l‍nm)α+∑l=1k+1‍∑r=1nl‍ɛr(l)(p[lr]+b[lr]r)+∑r=na+1n‍e[r],
where
(23)ɛr(l)=[(nl-r+1+na-∑m=1l‍nm)+(na-∑m=1l‍nm)β]
for l=1,…,k+1 and r=1,…,nl.Theorem 17.
Given the number of accepted jobs, the problem1∣pjr=pj+bjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej can be formulated as an assignment problem.Proof.
Let the number of accepted jobs bena(1≤na≤n), and let xjr be the decision variable such that xjr=1 if job Jj is in the rth position, and xjr=0 otherwise, for j,r=1,2,…,n. Then the scheduling problem can be formulated as the following assignment problem:
(P4)Min∑l=1k‍(na-yl)α00000.000+∑j=1n‍(∑l=1k+1‍∑r=yl-1yl‍[(na-r+1)+(na-yl)β]0000000000000000×(pj+bj(r-yl-1))xjr0000000000000000+∑r=na+1n‍ejxjr),s.t.∑r=1n‍xjr=1,j=1,2,…,n,0000∑j=1n‍xjr=1,r=1,2,…,n,0000xjr∈{0,1},j,r=1,2,…,n,
where yl=∑m=1lnm, for l=1,…,k+1, and y0=0. The result follows.Summing up the above analysis, the following solution algorithm can be presented for the problem1∣pjr=pj+bjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej.Algorithm 18.
Consider the following.
Step  1. For na=0, calculate F(0)=∑j=1nej.
Step  2. For given na, k, and vector P(na,k+1)=(n1,n2,…,nk+1), solve the above assignment problem (P4) and calculate the corresponding objective value F(na,k,P(na,k+1)).
Step  3. The optimal objective value is min{F(na,k,P(na,k+1))∣0≤na≤n, 1≤k≤na-1,∑j=1k+1nj=na}.Theorem 19.
Algorithm18 solves the problem 1∣pjr=pj+bjr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej in O(nk0+4) time.


## 4.3.  The Problem1∣pjr=pj+csr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej

For a fixed job sequence and maintenance activitiesπ=(G1,M1,G2,M2,…,Gk,Mk,Gk+1,A¯) with na accepted jobs in the order of S, (4) can be reformulated as
(24)Z(S,A¯,MA)=∑l=1k‍(na-∑m=1l‍nm)α+∑l=1k+1‍∑r=1nl‍ηr(l)p[lr]+∑r=na+1n‍e[r],
where
(25)ηr(l)=(1+β)(na-∑m=1l‍nm)(1+c)nl-r+∑i=1nl-r‍(1+c)i
for l=1,…,k+1 and r=1,…,nl.Analogous to the problem1∣pjr=pjraj, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej, Algorithm 13 also can be used for solving the problem 1∣pjr=pj+csr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej by replacing ξr(l) with ηr(l).Theorem 20.
The problem1∣pjr=pj+csr, ma≤k0∣∑j=1naC[j]+∑j∈A¯ej can be solved in O(nk0+3) time.


## 5. Conclusions

This paper studies the single-machine scheduling problems with simultaneous considerations of job rejection, deterioration effects, and deteriorating multimaintenance activities with the objective of finding jointly the accepted job set, the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences such that the cost function based on the total completion time and rejection penalty is minimized, in which the upper bound of the total maintenance frequencies on the machine is assumed to be known in advance. The main results obtained are summarized in Table1. Future research may focus on studying other models of maintenance duration, in multi-machine settings, and optimizing other performance measures.Table 1
The summary of the obtained results.
Objective function
Complexity
Maintenance
Reference
1
|
p
j
r
=
p
j
r
a
j
|
∑
j
=
1
n
a
C
[
j
]
+
∑
j
∈
A
¯
e
j
O
(
n
4
)
Not scheduled
Theorem4
1
|
p
j
r
=
p
j
r
a
|
∑
j
=
1
n
a
C
[
j
]
+
∑
j
∈
A
¯
e
j
O
(
n
3
)
Not scheduled
Theorem6
1
|
p
j
r
=
p
j
+
b
j
r
|
∑
j
=
1
n
a
C
[
j
]
+
∑
j
∈
A
¯
e
j
O
(
n
3
)
Not scheduled
Theorem9
1
|
p
j
r
=
p
j
+
c
s
r
|
∑
j
=
1
n
a
C
[
j
]
+
∑
j
∈
A
¯
e
j
O
(
n
2
)
Not scheduled
Theorem11
1
|
p
j
r
=
p
j
r
a
j
,
m
a
≤
k
0
|
∑
j
=
1
n
a
C
[
j
]
+
∑
j
∈
A
¯
e
j
O
(
n
k
0
+
4
)
Scheduled
Theorem14
1
|
p
j
r
=
p
j
r
a
,
m
a
≤
k
0
|
∑
j
=
1
n
a
C
[
j
]
+
∑
j
∈
A
¯
e
j
O
(
n
k
0
+
3
)
Scheduled
Theorem16
1
|
p
j
r
=
p
j
+
b
j
r
,
m
a
≤
k
0
|
∑
j
=
1
n
a
C
[
j
]
+
∑
j
∈
A
¯
e
j
O
(
n
k
0
+
4
)
Scheduled
Theorem19
1
|
p
j
r
=
p
j
+
c
s
r
,
m
a
≤
k
0
|
∑
j
=
1
n
a
C
[
j
]
+
∑
j
∈
A
¯
e
j
O
(
n
k
0
+
3
)
Scheduled
Theorem20



---

*Source: 389120-2013-10-24.xml*