# Rescheduling Problems with Agreeable Job Parameters to Minimize the Tardiness Costs under Deterioration and Disruption

Authors: Zhang Xingong; Wang Yong
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper considers single-machine rescheduling problems with agreeable job parameters
under deterioration and disruption. Deteriorating jobs mean that the processing time of a job is defined by an increasing function of its starting time. Rescheduling means that, after a set of original jobs has already been scheduled, a new set of jobs arrives and creates a disruption. We consider four cases of minimization of the total tardiness costs with agreeable job parameters under a limit of the disruptions from the original job sequence. We propose polynomial-time algorithms or some dynamic programming algorithms under sequence disruption and time disruption.


---

## Body

## 1. Introduction

Scheduling problems are very important in manufacturing systems. Hence, numerous scheduling problems have been studied for many years. In the classical scheduling theory, job processing times are assumed to be known and fixed from the first job to be processed until the last job to be completed. However, there are many situations in which a job that is processed later consumes more time than the same job when processed earlier. Scheduling in this setting is known as scheduling deteriorating jobs.Significant contributions towards addressing or solving deteriorating job scheduling problems on a single machine include, among others, the following: Browne and Yechiali [1] cited applications concerning the control of queues and communication systems where jobs deteriorate as they await processing. Kunnathur and Gupta [2] and Mosheiov [3] gave several other real-life situations where deteriorating jobs occur. These include the search for an object under worsening weather or performance of medical treatments under deteriorating health conditions. Comprehensive discussion of scheduling problems with time-dependent processing times of jobs can be found in Cheng et al. [4] and Gawiejnowicz [5]. Recently, Biskup and Herrmann [6] observed that the sum of the processing times of the jobs processed before a job contributes to the actual processing time of the job, and they cite equipment wearout (e.g., a drill) as a real-life example of their observation. Wang and Guo [7] considered a single-machine scheduling problem with the effects of learning and deterioration. The goal is to determine an optimal combination of the due date and schedule so as to minimize the sum of earliness, tardiness, and due-date costs. Ng et al. [8] considered a two-machine flow shop scheduling problem with linearly deteriorating jobs to minimize the total completion time. Cheng et al. [9] considered scheduling with deteriorating jobs in which the actual processing time of a job is a function of the logarithm of the total processing time of the jobs processed before it (to avoid the unrealistic situation where the jobs scheduled lately will incur excessively long processing times), and the setup times are proportional to the actual processing times of the already scheduled jobs.Rescheduling involves adjusting a previously planned, possibly optimal, scheduling to account for a disruption. Examples of common disruptions include: the arrival of new orders, order cancelations, changes in order priority, processing delays, changes in release dates, machine breakdowns, and the unavailability of raw materials, personnel, or tools. There are several papers on rescheduling approaches in manufacturing systems. Raman et al. [10] developed a branch-and-bound procedure to reschedule a flexible manufacturing system in the presence of dynamic job arrivals. Church and Uzsoy [11] addressed a similar problem for which they describe periodic rescheduling policies and analyze their error bounds. Jain and Elmaraghy [12] used genetic algorithms to develop heuristic approaches for rescheduling a flexible manufacturing system. Vieira et al. [13] provided an extensive review of rescheduling problems. Yang [14] studied the single-machine rescheduling with new jobs arrivals and processing time compression. Hall and Potts [15] considered the problem of rescheduling of a single machine with newly arrived jobs to minimize the maximum lateness and the total completion time under a limit of the disruption from the original scheduling. Yuan and Mu [16] considered the rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the maximum sequence disruption. Zhao and Tang [17] presented two single-machine rescheduling problems with linear deteriorating jobs under disruption. deteriorating jobs mean that the actual processing time of the job is an increasing function of its starting time. They considered the rescheduling problem to minimize the total completion time under a limit of the disruption from the original scheduling. Hoogeveen et al. [18] tackled several simple setup time configurations yielding different scheduling problems for which they propose optimal polynomial time algorithms or provide NP-hardness proofs. They also present the problem of enumerating the set of strict Pareto optima for the sum of setup times and disruption cost criteria.Based on the motivation of Hall and Potts [15] and Zhao and Tang [17], we consider some rescheduling problems with the criterion minimizing the total tardiness costs under a limit of the disruption from the original schedule in this paper. The rest of the paper is organized as follows. In the next section, we give the problem description. In Section 3, we consider single-machine scheduling problems. The last section is the conclusion.


## 2. Problem Definition and Notation

By the terminology of Hall and Potts [15], our researchful problem can be stated as follows. Let J0={J1,…,Jn0} denote a set of original jobs to be processed non preemptively on a single machine. In the presented model, we assume that these jobs have been scheduled optimally to minimize some classical objective and that π* is an optimal job sequence with no idle time between the jobs. Let JN={Jn0+1,…,Jn0+nN} denote a set of new jobs that arrive together. We assume that these jobs arrive at time zero after a schedule for the jobs of J0 has been determined, but before processing begins. There is no loss of generality in this assumption: if the jobs arrive after time zero, then the fully processed jobs of J0 are removed from the problem; any partly processed jobs are processed to completion, and J0 and n0 are updated accordingly. Let J=J0⋃JN and n=n0+nN. Each job Jj∈J has an integral normal processing time pj and a deteriorating rate b>0; the actual processing time of job Jj is pj(a+bsj), where sj (≥0) is the starting time of job Jj and a (>0) is constant. For any schedule σ of the jobs in J, we define the following variables:sj(σ)
is the time at which jobJj∈J starts its processing in schedule σ.dj(σ) is the due date of job Jj∈J in schedule σ.Cj(σ) is the time at which job Jj∈J is completed in schedule σ.Tj(σ)=max{Cj(σ)-dj,0} is the tardiness value of job Jj∈J.Dj(π*;σ) is the sequence disruptions of job Jj∈J0; that is, if Jj is the xth job in π* and the yth job in σ, respectively, then Dj(π*;σ)=|y-x|.Δj(π*;σ)=|Cj(σ)-Cj(π*)| is the time disruption of job Jj∈J0.When there is no ambiguity, we simplify the above symbols and writesj, djCj, Tj, Dj(π*), and Δj(π*), respectively.We consider only the single-scheduling problems with the following constraints on the amount of disruption, wherek≥0 is a known integer:Dmax(π*)≤k: max{Dj(π*)Jj∈J0}≤k; the maximum sequence disruption of the jobs cannot exceed k.∑‍Dj(π*)≤k: ∑Jj∈J0‍Dj(π*)≤k; the total sequence disruption of the jobs cannot exceed k.Δmax(π*)≤k: max{Δj(π*)Jj∈J0}≤k; the maximum time disruption of the jobs cannot exceed k.∑‍Δj(π*)≤k: ∑Jj∈J0‍Δj(π*)≤k; the total time disruption of the jobs cannot exceed k.Since the1∣∑‍Tj problem is NP-hard in Du and Leung [19], the 1∣Γ≤k∣∑‍Tj problem is also NP-hard, where Γ∈{Dmax(π*),∑‍Dj(π*),Δmax(π*),∑‍Δj(π*)}. In this paper, we consider a special case: the processing time and due date of jobs are agreeable; that is, pi≤pj⇒di≤dj for all jobs Ji and Jj.Using the three-field notation [20], the considered problems can be denoted as1∣pi≤pj⇒di≤dj, Dmax(π*)≤k, pj(a+bsj)∣∑‍Tj,1∣pi≤pj⇒di≤dj, ∑‍Dj(π*)≤k, pj(a+bsj)∣∑‍Tj;1∣pi≤pj⇒di≤dj, Δmax(π*)≤k, pj(a+bsj)∣∑‍Tj;1∣pi≤pj⇒di≤dj, ∑‍Δj(π*)≤k, pj(a+bsj)∣∑‍Tj.


## 3. Minimum Tardiness Problem with Agreeable Job Parameters

We start with the following result by Kononov and Gawiejnowicz [21].Lemma 1.
For the1∣pj(a+bsj)∣Cmax problem, if π={J1,…,Jn} and the starting time of the job J1 is t, then makespan is sequence independent, and
(1)Cmax(π)=t∏i=1n‍(1+bpi)+ab(∏i=1n‍(1+bpi)-1).For notational convenience, we assume that the jobs are indexed by agreeable order; that is,p1≤⋯≤pn0 and d1≤⋯≤dn0. Thus, π*={J1,…,Jn0} with no idle time between jobs. We now show that the EDD or SPT rule applies to serval of the rescheduling problems we consider.Lemma 2.
Problems1∣pi≤pj⇒di≤dj, Dmax(π*)≤k, pj(a+bsj)∣∑‍Tj, and 1∣pi≤pj⇒di≤dj, Δmax(π*)≤k, pj(a+bsj)∣∑‍Tj have an optimal schedule with no idle time between jobs, and(a)
a schedule for problem1∣pi≤pj⇒di≤dj, Dmax(π*)≤k, pj(a+bsj)∣∑‍Tj is feasible if the number of jobs of JN scheduled before the last job of J0 is less than or equal to k;(b)
a schedule for problem1∣pi≤pj⇒di≤dj, Δmax(π*)≤k, pj(a+bsj)∣∑‍Tj is feasible if the total actual processing time of jobs of JN scheduled before the last job of J0 is less than or equal to k.Proof.
The proof is similar to that of Lemma 1 in Hall and Potts [15].Lemma 3.
For problems1∣pi≤pj⇒di≤dj, Γ≤k and pj(a+bsj)∣∑‍Tj, where Γ∈{Dmax(π*),∑‍Dj(π*),Δmax(π*),∑‍Δj(π*)}, there exists an optimal schedule in which the jobs of J0 are sequenced in the EDD or SPT rule as in π*, the jobs of JN are sequenced in the EDD or SPT rule, and there is no idle time between jobs.Proof.
We first analyze the jobs ofJ0. Consider an optimal schedule σ* in which the jobs of J0 are not sequenced in the EDD or SPT rule as in π*. Let Ji be the job with the smallest index that appears later relative to the other jobs of J0 in σ* than in π*, and let Jj(j>i) be the last job of J0 that precedes job Ji in σ*. Because π* is an optimal sequence, pj and dj are agreeable. Assume that the starting time of job Jj in σ* is t0, then Cj(σ*)=t0+pj(a+bt0). Perform an interchange on jobs Jj and Ji, and get a new schedule σ′. In σ′, the starting time of job Ji is t0, then Ci(σ′)=t0+pi(a+bt0)<t0+pj(a+bt0)=Cj(σ*). From Lemma 1, Cj(σ′)=Ci(σ*). Thus, the jobs between job Ji and Jj are completed earlier in σ′ than in σ*. Next, we consider the total tardiness of jobs Ji and Jj in σ′ and in σ*.
The total tardiness of jobsJi and Jj in σ* is as follows:
(2)Ti(σ*)+Tj(σ*)=max{Ci(σ*)-di,0}+max{Cj(σ*)-dj,0}.
The total tardiness of jobsJi and Jj in σ′ is as follows:
(3)Ti(σ′)+Tj(σ′)=max{Ci(σ′)-di,0}+max{Cj(σ′)-dj,0}.
To compare the total tardiness of jobsJi and Jj in σ* and in σ′, we divide it into two cases. In the first case, when Cj(σ*)≤dj, we have Ti(σ*)+Tj(σ*)=max{Ci(σ*)-di,0}. Suppose that neither Ti(σ′) nor Tj(σ′) is zero. Note that this is the most restrictive case since it comprises the case that either one or both Ti(σ′) and Tj(σ′) are zero. From Lemma 1 and pi≤pj, di≤dj, we have {Ti(σ*)+Tj(σ*)}-{Ti(σ′)+Tj(σ′)}=Ci(σ*)-Ci(σ′)-Cj(σ′)+dj=dj-Ci(σ′)≥dj-Cj(σ*)≥0.
In the second case, whenCj(σ*)>dj, we have Ti(σ*)+Tj(σ*)=Ci(σ*)+Cj(σ*)-di-di. Suppose that neither Ti(σ′) nor Tj(σ′) is zero. From Lemma 1 and pi≤pj, di≤dj, we have
(4){Ti(σ*)+Tj(σ*)}-{Ti(σ′)+Tj(σ′)}=Ci(σ*)+Cj(σ*)-Cj(σ′)-Ci(σ′)≥0.
Now, we have proved that the total tardiness of σ′ is less than or equal to that of σ*.
Let the position of jobJi in π* be k1 and let the position of job Jj in π* be k2 and in σ′ be k3. If k3≥k2, then Dj(π*,σ′)=k3-k2, Di(π*,σ*)=k3-k1. Since i<j implies k1<k2, we have Dj(π*,σ′)<Di(π*,σ*). If k3<k2, then Dj(π*,σ′)=k2-k3 and Dj(π*,σ*)=k2-(k3-h), where h is the difference between the position of job Ji and Jj in σ*. So, Dj(π*,σ′)<Dj(π*,σ*). Hence, we have Dmax(π*,σ′)<Dmax(π*,σ*). In either case, because Di(π*,σ′)=Di(π*,σ*)-h and Dj(π*,σ′)≤Dj(π*,σ*)+h. Hence, ∑‍Dj(π*,σ′)≤∑‍Dj(π*,σ*).
Moreover, ifCj(σ′)≥Cj(π*), then Δj(π*,σ′)=Cj(σ′)-Cj(π*). Since Δi(π*,σ*)=Ci(σ*)-Ci(π*)=Cj(σ′)-Ci(π*) and Ci(π*)<Cj(π*); therefore, Δj(π*,σ′)<Δi(π*,σ*). If Cj(σ′)<Cj(π*), then Δj(π*,σ′)=Cj(π*)-Cj(σ′) because Δj(π*,σ*)=Cj(π*)-Cj(σ*), Δj(π*,σ′)<Δj(π*,σ*). Thus, we have Δmax(π*,σ′)<Δmax(π*,σ*). In either case, because Δi(π*,σ′)=Δi(π*,σ*)-h′ and Δj(π*,σ′)≤Δj(π*,σ*)+h′, where h′=Ci(σ*)-Ci(σ′). Then we deduce that ∑‍Δj(π*,σ′)≤∑‍Δj(π*,σ*). Thus, for either problem, σ′ is feasible and optimal. We can show that there exists an optimal schedule in which the jobs of J0 are sequenced in the EDD or SPT order as in π* by finite numbers of repetitions of the argument. A similar interchange argument establishes that the jobs of JN can also be obtained by sequencing in the EDD or SPT order. The same EDD or SPT ordering of the jobs of J0 in π* and an optimal schedule show that there is no idle time in this optimal schedule. Otherwise, removing this idle time maintains feasibility and decreases the total tardiness.We refer to the (EDD, EDD) property when a schedule is constructed using Lemmas2 and 3. We first consider problem 1∣pi≤pj⇒di≤dj, Dmax(π*)≤k, pj(a+bsj)∣∑‍Tj. From Lemmas 2 and 3, there are at most k jobs of JN that can be sequenced before the last job of J0, and these jobs have the smallest due dates.Thus, we propose the following algorithm under the maximum sequence disruption constraint. (see Box 1).Box 1
Input: Givenpj, dj for j=1,…,n; k and π*, where k≤nN.
Indexing: Index the jobs ofJN in the EDD order.
Schedule Construction: Schedule jobs1,…,n0+k in the EDD order in the first n0+k positions.
Schedule jobsn0+k+1,…,n0+nN in EDD order in the final nN-k positions.Algorithm 4.
Consider the following steps.
Step  1. Index the job of JN in the EDD order.
Step  2. Schedule jobs 1,…,n0+k in the EDD rule in the first n0+k position and schedule jobs n0+k+1,…,n0+nN in the EDD order in the final nN-k positions.Theorem 5.
For the1∣pi≤pj⇒di≤dj, Dmax(π*)≤k, pj(a+bsj)∣∑‍Tj problem, Algorithm 4 finds an optimal schedule in O(n+nNlognN) time.Proof.
From Lemmas2 and 3, the constraint Dmax(π*)≤k allows at most k jobs of JN to be sequenced before the final of J0, and these are the jobs of JN with the smallest due dates. Classical schedule theory shows that the jobs of this first group are sequenced in the EDD order, while Lemma 3 establishes that the remaining nN-k jobs of JN are also sequenced in the EDD order.
Next, we note that the Step 1 for the jobs ofJN requires O(nNlognN) time. Step 2 is executed in O(n) time by merging the first k jobs of the EDD ordered jobs of JN with the jobs of J0 as sequenced in π* and then placing the last nN-k jobs of the EDD order ordered jobs of JN at the end of the schedule.Next, we consider problem1∣pi≤pj⇒di≤dj, ∑‍Dj(π*)≤k, pj(a+bsj)∣∑‍Tj. From Lemmas 1, 2, and 3, there is the total sequence disruption of the jobs of JN which is less than or equal to k and can be sequenced before the last job of J0, and these jobs have the smallest due dates. Thus, we propose the following algorithm under the total sequence disruption constraint. (see Box 2).Box 2
Input:   Givenpj, dj for j=1,…,n; k and π*, where k≤n0nN.
Indexing:   Index the jobs ofJN in the EDD order.Letf(i,j,δ) be minimum total tardiness value of a partial schedule for jobs J1,…,Ji and Jn0+1,…,Jn0+j, where the total sequence disruption is equal to δ. The dynamic programming procedure can now be stated as follows.Algorithm 6.
Consider the following steps.
Step  1 (Initialization). Set f(i,j,δ)=0 for (i,j,δ)=(0,0,0) and f(i,j,δ)=∞ for (i,j,δ)≠(0,0,0), i=1,…,n0, j=1,…,nN, i=0,…,k.
Step  2 (Recurrence Relation). 							(5)f(i,j,δ)=min{f(i-1,j,δ-j)+max{Ci-di,0};f(i,j-1,δ)+max{Cn0+j-dn0+j,0},
where Cj denotes the completion time of job Jj.
Step  3 (Optimal Solution). Calculate the optimal solution value min0≤δ≤k{f(n0,nN,δ)}.In the recurrence relation, the first term in the minimization corresponds to the case where the partial schedule ends with jobJi∈J0. Because Jj jobs of JN appear before job Ji in such a partial schedule, the increase in total sequence disruption is equal to j. The second term corresponds to the case where the partial schedule ends with job Jn0+j∈JN.In addition, we demonstrate the result of Algorithm6 in the following example.Example 7.
n
0
=
3, nN=3, t0=0, J0={J1,J2,J3}, JN={J4,J5,J6}, p1=3.2, d1=4, p2=1, d2=2.4, p3=2, d3=3,p4=1.5, d4=3, p5=4, d5=5, p6=3, d6=4.7, a=0.2, b=0.4, and k=5.
Solution: According to Algorithm4 and Lemmas 2 and 3. Because the total sequence disruption of the jobs J1, J2, J3 can not exceed k=5. By dynamic programming algorithm, we obtain job sequence and the total tardiness cost as follows:ifk=0, the optimal sequence is [J2→J3→J1→J4→J6→J5], and the total tardiness cost is 26.8007;ifk=0, the job sequence is [J2→J3→J1→J4→J6→J5], and the total tardiness cost is 26.8007;ifk=1, the job sequence is [J2→J3→J4→J1→J6→J5], and the total tardiness cost is 25.8007;ifk=2, the job sequence is [J2→J4→J3→J1→J6→J5], and the total tardiness cost is 25.8007;ifk=3, the job sequence is [J4→J2→J3→J1→J6→J5], and the total tardiness cost is 25.8007;ifk=4, the job sequence is [J4→J2→J3→J6→J1→J5], and the total tardiness cost is 26.8223;ifk=5, the job sequence is [J4→J2→J6→J3→J1→J5], and the total tardiness cost is 28.5223;
Furthermore, if total sequence disruptionk is equal to 1, 2, 3, then minimizing total tardiness cost is 25.8007, and optimal job sequence is [J2→J3→J4→J1→J6→J5], [J2→J4→J3→J1→J6→J5], and [J4→J2→J3→J1→J6→J5].Theorem 8.
For the1∣pi≤pj⇒di≤dj, ∑‍Dj(π*)≤k, pj(a+bsj)∣∑‍Tj problem, Algorithm 6 finds an optimal schedule in O(n02nN2) time.Proof.
From Lemmas1, 2, and 3, it only remains to enumerate all possible ways of merging the EDD ordered lists of jobs of J0 and JN. Algorithm 6 does so by comparing the cost of all possible state transitions and therefore finds an optimal schedule.
Becausei≤n0, j≤nN and δ≤k≤n0nN, there are O(n02nN2) values of the state variables. Step 1 requires O(nNlognN). Step 2 requires constant time for each set of values of the state variables. Thus, the overall time complexity of Algorithm 6 is O(n02nN2).Now, we consider problem1∣pi≤pj⇒di≤dj, Δmax(π*)≤k, pj(a+bsj)∣∑‍Tj. From Lemmas 1, 2, and 3, the maximum time disruption of jobs of J0 is at most k, and jobs of JN before the last job of J0 have the smallest due dates. Thus, we propose the following algorithm under the maximum time disruption constraint. (see Box 3).Box 3
Input: Givenpj, dj for j=1,…,n; k and π*, where k<Cmax (see Lemma 1).
Indexing: Index the jobs ofJN in the EDD order.Letf(i,j,δ) be minimum total tardiness value of a partial schedule for jobs J1,…,Ji and Jn0+1,…,Jn0+j, where the maximum time disruption is equal to δ. The dynamic programming procedure can now be stated as follows.Algorithm 9.
Consider the following steps.
Step  1 (Initialization). Set f(i,j,δ)=0 for (i,j,δ)=(0,0,0) and f(i,j,δ)=∞ for (i,j,δ)≠(0,0,0), i=1,…,n0, j=1,…,nN, and i=0,…,k.
Step  2 (Recurrence Relation). 							(6)f(i,j,δ)=min{f(i-1,j,δ-Ph)+max{Ci-di,0};f(i,j-1,δ)+max{Cn0+j-dn0+j,0},
where Ph is the sum of actual processing time of the new jobs of JN between Ji-1 and Ji and Cj denotes the completion time of job Jj.
Step  3 (Optimal Solution). Calculate the optimal solution value min0≤δ≤k{f(n0,nN,δ)}.In the recurrence relation, the first term in the minimization corresponds to the case where the partial schedule ends with jobJi∈J0. Because Jj jobs of JN appear before job Ji in such a partial schedule, the increase in the maximum time disruption is equal to Ph. The second term corresponds to the case where the partial schedule ends with job Jn0+j∈JN.Similar to Example7, by Algorithm 9, we have(i)
the maximum time disruptionk is in [1.7237,25.7919]; the job sequence and the total tardiness cost are the same to Example;(ii)
the maximum time disruptionk is in [0,1.7237), the job sequence is [J2→J3→J1→J4→J6→J5], and the total tardiness cost is 26.8007.Theorem 10.
For the1∣pi≤pj⇒di≤dj, Δmax(π*)≤k, pj(a+bsj)∣∑‍Tj problem, Algorithm 9 finds an optimal schedule in O(n0nNCmax+nNlognN) time.Proof.
From Lemmas1, 2, and 3, Δ≤k means that the total actual processing time of the new jobs of JN before the last job of J0 is at most k, and these are the jobs of JN with the smallest due dates. Hence, Algorithm 9 schedules the jobs according to the (EDD, EDD) property.
Becausei≤n0, j≤nN and δ≤k<Cmax, there are O(n0nNCmax) values of the state variables. Step 1 requires O(nNlognN). Step 2 requires constant time for each set of values of the state variables. Thus, the overall time complexity of Algorithm 9 is O(n0nNCmax+nNlognN).Now, we consider problem1∣pi≤pj⇒di≤dj, ∑‍Δj(π*)≤k, pj(a+bsj)∣∑‍Tj. From Lemmas 1, 2, and 3, there is the total time disruption of jobs of JN which is less than or equal to k and can be sequenced before the last job of J0, and these jobs have the smallest due dates. The following dynamic programming algorithm performs an optimal merging of jobs of J0 and JN in a way similar to Algorithm 6. (see Box 4).Box 4
Input: Givenpj, dj for j=1,…,n; k and π*, where k≤n0Cmax.
Indexing: Index the jobs ofJN in the EDD order.Letf(i,j,δ) be minimum total tardiness value of a partial schedule for jobs J1,…,Ji and Jn0+1,…,Jn0+j, where the total time disruption is equal to δ. The dynamic programming procedure can now be stated as follows.Algorithm 11.
Step  1 (Initialization). Set f(i,j,δ)=0 for (i,j,δ)=(0,0,0) and f(i,j,δ)=∞ for (i,j,δ)≠(0,0,0), i=1,…,n0, j=1,…,nN, and i=0,…,k.
Step  2 (Recurrence Relation).(7)f(i,j,δ)=min{f(i-1,j,δ-∑h=n0+1n0+jp[h])+max{Ci-di,0};f(i,j-1,δ)+max{Cn0+j-dn0+j,0},where p[h] is the actual processing time of job Jh; Cj denotes the completion time of job Jj.
Step  3 (Optimal Solution). Calculate the optimal solution value min0≤δ≤k{f(n0,nN,δ)}.In the recurrence relation, the first term in the minimization corresponds to the case where the partial schedule ends with jobJi∈J0. Because Jj jobs of JN appear before job Ji in such a partial schedule, the increase in total time disruption is equal to ∑h=n0+1n0+j‍p[h]. The second term corresponds to the case where the partial schedule ends with job Jn0+j∈JN.Theorem 12.
For the1∣pi≤pj⇒di≤dj,∑‍Δj(π*)≤k, pj(a+bsj)∣∑‍Tj problem, Algorithm 11 finds an optimal schedule in O(n02nNCmax) time.Proof.
The proof of optimality of Algorithm11 is similar to Theorem 8 regarding the time complexity. Because i≤n0, j≤nN, and δ≤k≤n0Cmax, there are O(n02nNCmax) values of the state variables. Step 1 requires O(nNlognN). Similar arguments to those in the proof of Theorem 8 show that the overall time complexity of Algorithm 11 is O(n02nNCmax).


## 4. Conclusions

In this paper, we studied the issue of rescheduling to allow the unexpected arrival of new jobs and took into account the effect of the disruption on a previously planned optimal schedule. The main contribution of this paper is that we develop the machine rescheduling scheduling problems agreeable job parameters under deterioration and disruption. Rescheduling means to schedule the jobs again, together with a set of new jobs. Deteriorating job means that the actual processing time of a job is an increasing function of its starting time. When the processing time and due date of jobs are agreeable, we considered some problems to minimize total tardiness under a limit on two disruption constraints: sequence disruption and time disruption. We proposed polynomial time algorithms or some dynamic programming algorithms for each problem. Future research may stimulate rescheduling models to mitigate the effects of the disruptions that occur frequently in manufacturing practice.



---

*Source: 138240-2013-08-29.xml*