# Due-Window Assignment and Scheduling with Multiple Rate-Modifying Activities under the Effects of Deterioration and Learning

Authors: Zhanguo Zhu; Linyan Sun; Feng Chu; Ming Liu
Journal: Mathematical Problems in Engineering
 (2011)

---

## Abstract

This paper discusses due-window assignment and scheduling with multiple rate-modifying activities. Multiple types of rate-modifying activities are allowed to perform on a single machine. The learning effect and job deterioration are also integrated concurrently into the problem which makes the problem more realistic. The objective is to find jointly the optimal location to perform multiple rate-modifying activities, the optimal job sequence, and the optimal location and size of the due window to minimize the total earliness, tardiness, and due-window-related costs. We propose polynomial time algorithms for all the cases of the problem under study.


---

## Body

## 1. Introduction

With the complexity of the manufacturing activities more researchers focus on variants of classical scheduling problems that reflect the reality, such as learning effect, rate-modifying activity, deteriorating effects, and due-window assignment.The phenomenon of the actual job processing times decreasing due to repetition of tasks by workers is known as the learning effect. Learning effect has received considerable attention in management science since it is first discovered by Wright [1]. However, the analysis of scheduling problems with learning effects is relatively recent. Biskup [2] and Cheng and Wang [3] were among the pioneers. Biskup [2] proposed a learning effect formulation which implied that learning primarily takes place as a result of repeating “processing time independent” operations and proved that with the introduction of learning to job processing times some cases of scheduling problems remain polynomially solvable. Mosheiov and Sidney [4] extended the setting of learning effect to the case of being job dependent. They proposed a new learning model in which the actual processing time of job j is pjr=pjraj if it is scheduled in position r, where aj is a job-dependent negative parameter and pj is the normal processing time. They also provided polynomial time solutions for several classical objective functions based on this realistic assumption. Koulamas and Kyparisis [5] studied single-machine and two machine flowshop scheduling with general learning functions and obtained some results on single-machine and special cases of two-machine. Wang et al. [6] studied single machine scheduling problem considering both learning effect and discounted costs. Kuo and Yang [7] introduced a time-independent learning effect into the single-machine group scheduling problems and provided two polynomial time algorithms to solve the problems of two different objectives.More researchers focus on the topic of rate-modifying activity (RMA) since Lee and Leon [8] first presented this model. In scheduling problems, production rate can be changed by inserting this activity into the job sequence and no jobs are processed during the duration of this activity. Zhao et al. [9] studied two parallel machines scheduling problems in which each machine has a rate-modifying activity. They provided a polynomial algorithm for the total completion time minimization problem and a pseudopolynomial time dynamic programming for the total weighted completion time minimization problem under agreeable ratio condition. Lodree and Geiger [10] addressed a scheduling problem with a rate-modifying activity under simple linear deterioration and proposed an optimal policy to schedule the RMA in the middle of the task sequence under certain conditions. Ji and Cheng [11] studied scheduling with multiple rate-modifying activities. Different from the above literature, they discussed the case that there are multiple different types of rate-modifying activities on each machine. They proved that all the cases of the problem are polynomially solvable. S.-J. Yang and D.-L. Yang [12] analyzed scheduling problems with several maintenance activities. However, they considered three types of aging/deteriorating effects, respectively, and the objective is to minimize the total completion time.Scheduling with deteriorating jobs, first introduced by J. N. D. Gupta and S. K. Gupta [13], and Browne and Yechiali [14], has received extensive attention in recent years. Deterioration discussed here means the actual job processing time is dependent on its normal processing time and actual starting time. Mosheiov [15] first investigated scheduling problem with the simple linear deteriorating jobs. Ng et al. [16] discussed three scheduling problems with deteriorating jobs to minimize the total completion time. Mosheiov [17], Lee et al. [18], and Sun et al. [19] studied job-shop scheduling problem with deteriorating jobs in different settings of environment. Gawiejnowicz [20] studied two scheduling problems with proportionally deteriorating jobs and they showed that these problems are both NP complete in ordinary sense or strong sense. Ji and Cheng [21] considered parallel machine scheduling problem with simple linear deterioration assumption. They proposed a polynomial time approximation scheme for the objective of minimizing total completion time. Wang and Sun [22] discussed the linear deterioration of job processing times and setup time in the context of group scheduling. Moreover, many studies devoted to scheduling problems with deteriorating jobs and learning effects such as Lee [23], Wang and Cheng [24], Cheng et al. [25], and Yang and Kuo [26].As an important issue in modern manufacturing system, due window assignment has also received increasing attention. Distinct from due-date assignment (please see Gordon et al. [27], and Biskup and Simons [28]), due-window assignment allows a time internal and no penalized cost are incurred if the jobs are completed within this internal. Otherwise, related earliness and tardiness are taken into account according to the positions of jobs before/after due-window. Liman et al. [29] considered the single machine scheduling problem with common due-window which is an extension of former earliness-tardiness scheduling problem. They proposed a polynomial algorithm to find the optimal size, location of the window, and an optimal sequence to minimize the cost function. Mosheiov and Sarig [30] studied a single machine scheduling problem with due-window and a maintenance activity. They introduced a polynomial time solution to schedule the jobs, the due-window and the maintenance activity. Yang et al. [31] considered due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance. In their study, they proposed a model with a deteriorating maintenance and provided polynomial time solutions. Zhao and Tang [32] investigated due-window assignment and scheduling with a rate-modifying activity under the assumption of deteriorating jobs that the processing time of a job is a linear function of its starting time. They proposed an O(n4) algorithm to solve the problem optimally, where n is the number of jobs.In this paper, we discuss single-machine scheduling problem with due-window assignment and multiple rate-modifying activities which is an extension of the work by Mosheiov and Sarig [30], Ji and Cheng [11], and Yang et al. [31]. In addition, learning effect, and job deterioration are also integrated concurrently into the problem which makes the problem more realistic. To our best knowledge, it is the first work that integrates due-window assignment, multiple rate-modifying activities, learning effect and job deterioration simultaneously. This paper is organized as follows. The problem is formulated in Section 2. Section 3 provides preliminary results related. An optimal policy is given in Section 4. The last section concludes this paper.


## 2. Problem Formulation

The problem we study can be stated as follows. There are givenn independent and nonpreemptive jobs to be processed on a single machine. Each job j is available for processing at time 0 and has a normal processing time pj, for j=1,2,…,n. J[r] (r=1,2,…,n) denotes the job scheduled in the rth position. Similar to Yang and Kuo [26], we assume the model of learning and deteriorating effect is a combination of the job-dependent learning effect model by Mosheiov and Sidney [4] and the linear deterioration model by Mosheiov [33]. So the actual processing time of job j with learning effect and deteriorating effect if it is scheduled in the rth position in a sequence is given by pjA=pj(r)aj+bsj, for j,r=1,2,…,n, where aj≤0 is the job-dependent learning index of job j,b>0 is the deterioration rate. sj is the starting time of job j. In addition, we assume multiple rate-modifying activities are allowed on the machine to improve its production efficiency throughout the whole scheduling horizon. The lth rate-modifying activity with constant duration tl is in il, if it is scheduled immediately after the completion of J[il], l=1,2,…,u, as in Figure 1. If job j is processed in position r just after any rate-modifying activity l, its actual processing time becomes pjA=θjlpj(r)aj+bsj, where 0<θjl≤1 is job-dependent modifying rate. For a given schedule π, Cj=Cj(π) denotes the completion time of job j,  j=1,2,…,n. In our problem all jobs are assumed to have a common due window. Let d1 and d2 denote the starting time and the finishing time of the due window, respectively. Let D=d2-d1 denote the due-window size. Ej=max{0,d1-Cj} denotes the earliness of job j, j=1,2,…,n. Tj=max{0,Cj-d2} denotes the tardiness of job j, j=1,2,…,n. Further, let α>0,  β>0,  γ>0 and δ>0 be the per time unit penalties for earliness, tardiness and due-window starting and due-window size, respectively. The objective is to determine the optimal due-window starting time d1, the due-window size, the position to schedule multiple rate-modifying activities and to find a schedule π which minimizes the following cost function:(2.1)f(d1,D,π)=Z=∑j=1n(αEj+βTj+γd1+δD).
We focus on the situation that there are two rate-modifying activities (l=1,2) first, and then extend it to multiple rate-modifying activities (l≥3).Figure 1
Structure of a schedule containingn jobs and two rate-modifying activities.Following the three-field notation of Graham et al. [34], we denote our problems as 1|DJLE,2RM|∑j=1n(αEj+βTj+γd1+δD) with two rate-modifying activities (2RM) and 1|DJLE,MRM|∑j=1n(αEj+βTj+γd1+δD) with multiple rate-modifying activities (l≥3) (MRM), where DJLE means “deteriorating jobs and learning effect”.


## 3. Preliminary Works

In this section, some useful preliminary works are given. For the situation there are two rate-modifying activities, we assume the position of thelth rate-modifying activity on machine is il, l=1,2 and they satisfy 1≤i1≤i2≤n. So for any schedule (see Figure 1), we have the following actual processing times for jobs J[1],J[2],…,J[n] which are discussed in three parts: (J[1],J[2],…,J[i1]), (J[i1+1],J[i1+2],…,J[i2]), and (J[i2+1],J[i2+2],…,J[n]).Note that the starting time ofJ[1], s[1] is equal to 0, the stating time of J[2], s[2] is equal to the completion time of J[1] which is just p[1]A, and the stating time of J[3], s[3] is equal to the completion time of J[2] which is just p[1]A+p[2]A,(3.1)p[1]A=p[1](1)a[1],p[2]A=p[2](2)a[2]+bs[2]=p[2](2)a[2]+bC[1]=p[2](2)a[2]+bp[1](1)a[1],p[3]A=p[3](3)a[3]+bs[3]=p[3](3)a[3]+bC[2]=p[3](3)a[3]+b(p[1]A+p[2]A)=p[3](3)a[3]+bp[2](2)a[2]+b(1+b)p[1](1)a[1],p[4]A=p[4](4)a[4]+bp[3](3)a[3]+b(1+b)p[2](2)a[2]+b(1+b)2p[1](1)a[1],⋮
From above analysis, we obtain the following general expression of actual processing time for jobs J[1],J[2],…,J[i1]:(3.2)p[j]A=p[j](j)a[j]+b∑h=1j-1(1+b)j-1-hp[h](h)a[h],j=1,…,i1.
For further analysis of actual processing times of other jobs, we provide the actual processing time of job J[i1] as(3.3)p[i1]A=p[i1](i1)a[i1]+b∑h=1i1-1(1+b)i1-1-hp[h](h)a[h].
Note that bs[i1]=p[i1]A-p[i1](i1)a[i1], bs[i1+1]=p[i1]+1A-θ[i1+1]1p[i1+1](i1+1)a[i1+1] according to the expressions of actual processing times of jobs in Section 2, and the starting time of job J[i1+1], s[i1+1] is equal to the sum of the completion time of job J[i1] and the duration of the first rate-modifying activity, which is C[i1]+t1. Moreover C[i1]=p[i1]A+s[i1], so(3.4)p[i1+1]A=θ[i1+1]1p[i1+1](i1+1)a[i1+1]+bs[i1+1]=θ[i1+1]1p[i1+1](i1+1)a[i1+1]+b(C[i1]+t1)=θ[i1+1]1p[i1+1](i1+1)a[i1+1]+b(t1+p[i1]A+s[i1])=θ[i1+1]1p[i1+1](i1+1)a[i1+1]+bt1+bp[i1]A+bs[i1]=θ[i1+1]1p[i1+1](i1+1)a[i1+1]+bt1+bp[i1]A+p[i1]A-p[i1](i1)a[i1]=θ[i1+1]1p[i1+1](i1+1)a[i1+1]+bt1+(b+1)p[i1]A-p[i1](i1)a[i1]=θ[i1+1]1p[i1+1](i1+1)a[i1+1]+bt1+bp[i1](i1)a[i1]+b(b+1)∑h=1i1-1(1+b)i1-1-hp[h](h)a[h]=θ[i1+1]1p[i1+1](i1+1)a[i1+1]+bp[i1](i1)a[i1]+b∑h=1i1-1(1+b)i1-hp[h](h)a[h]+bt1,p[i1+2]A=θ[i1+2]1p[i1+2](i1+2)a[i1+2]+bs[i1+2]=θ[i1+2]1p[i1+2](i1+2)a[i1+2]+bC[i1+1]=θ[i1+2]1p[i1+2](i1+2)a[i1+2]+b(p[i1+1]A+s[i1+1])=θ[i1+2]1p[i1+2](i1+2)a[i1+2]+bp[i1+1]A+bs[i1+1]=θ[i1+2]1p[i1+2](i1+2)a[i1+2]+bp[i1+1]A+p[i1+1]A-θ[i1+1]1p[i1+1](i1+1)a[i1+1]=θ[i1+2]1p[i1+2](i1+2)a[i1+2]+(b+1)p[i1+1]A-θ[i1+1]1p[i1+1](i1+1)a[i1+1]=θ[i1+2]1p[i1+2](i1+2)a[i1+2]+bθ[i1+1]1p[i1+1](i1+1)a[i1+1]+b(b+1)p[i1](i1)a[i1]+b(b+1)∑h=1i1-1(1+b)i1-hp[h](h)a[h]+b(b+1)t1=θ[i1+2]1p[i1+2](i1+2)a[i1+2]+bθ[i1+1]1p[i1+1](i1+1)a[i1+1]+b(b+1)p[i1](i1)a[i1]+b∑h=1i1-1(1+b)i1+1-hp[h](h)a[h]+b(b+1)t1,⋮
We obtain the following general expression of actual processing time for jobs J[i1+1],J[i1+2],…,J[i2]:(3.5)p[j]A=θ[j]1p[j](j)a[j]+b∑h=1i1(1+b)j-1-hp[h](h)a[h]+b∑h=i1+1j-1(1+b)j-1-hθ[h]1p[h](h)a[h]+b(1+b)j-i1-1t1,j=i1+1,…,i2,p[i2]A=θ[i2]1p[i2](i2)a[i2]+b∑h=1i1(1+b)i2-1-hp[h](h)a[h]+b∑h=i1+1i2-1(1+b)i2-1-hθ[h]1p[h](h)a[h]+b(1+b)i2-i1-1t1,p[i2+1]A=θ[i2+1]2p[i2+1](i2+1)a[i2+1]+bt2+bθ[i2]1p[i2](i2)a[i2]+b∑h=1i1(1+b)i2-hp[h](h)a[h]+b∑h=i1+1i2-1(1+b)i2-hθ[h]1p[h](h)a[h]+b(1+b)i2-i1t1,⋮
Similarly, the general expression of actual processing time for jobs J[i2+1],J[i2+2],…,J[n] is as follows:(3.6)p[j]A=θ[j]2p[j](j)a[j]+b∑h=1i1(1+b)j-1-hp[h](h)a[h]+b∑h=i1+1i2(1+b)j-1-hθ[h]1p[h](h)a[h]+b∑h=i2+1j-1(1+b)j-1-hθ[h]2p[h](h)a[h]+b(1+b)j-i1-1t1+b(1+b)j-i2-1t2,j=i2+1,…,n.
We present that some properties of an optimal solution for the common due-window assignment problem proved by Mosheiov and Sarig [30] still hold for the problem discussed in this paper.Lemma 3.1.
An optimal schedule exists in which the due-window starts and finishes at certain job completion times.Proof.
For any given job sequence (π=J[1],J[2],…,J[k],…,J[k+m],…,J[n]), we set C[k]<d1<C[k+1] and C[k+m]<d2<C[k+m+1], where kth and (k+m)th are positions in sequence π and satisfy 0≤k≤(k+m)≤n (see Figure 2). Considering the relative location of due-window and two rate-modifying activities, there are six cases altogether, that is, i1≤i2≤k, k≤i1≤i2≤k+m, k+m≤i1≤i2, i1≤k&&k+m≤i2, i1≤k&&k≤i2≤k+m, and k≤i1≤k+m&&k+m≤i2. For simplification of description, we only investigate the case i1≤i2≤k in this part, and the proofs of other cases are similar. In addition, we set φ1=d1-C[k],φ2=d2-C[k+m] and clearly 0≤φ1≤p[k+1]A and 0≤φ2≤p[k+m+1]A.
As described in (2.1), the total cost function includes four parts: the earliness cost, the tardiness cost, the due-window starting time cost, and the due-window size cost.
For jobj of a schedule π, we denote the earliness cost by ZjE, where j=k,k-1,…,1. 							(3.7)ZkE=αφ1,Zk-1E=α[φ1+p[k]A],Zk-2E=α[φ1+p[k]A+p[k-1]A],⋮Zi2+1E=α[φ1+p[k]A+p[k-1]A+⋯p[i2+2]A],Zi2E=α[φ1+p[k]A+p[k-1]A+⋯p[i2+1]A+t2],Zi2-1E=α[φ1+p[k]A+p[k-1]A+⋯p[i2+1]A+t2+p[i2]A],Zi2-2E=α[φ1+p[k]A+p[k-1]A+⋯p[i2+1]A+t2+p[i2]A+p[i2-1]A],⋮Zi1+1E=α[φ1+p[k]A+p[k-1]A+⋯p[i2+1]A+t2+p[i2]A+p[i2-1]A+⋯+p[i1+2]A],Zi1E=α[φ1+p[k]A+p[k-1]A+⋯p[i2+1]A+t2+p[i2]A+p[i2-1]A+⋯+p[i1+1]A+t1],Zi1-1E=α[φ1+p[k]A+p[k-1]A+⋯p[i2+1]A+t2+p[i2]A+p[i2-1]A+⋯+p[i1+1]A+t1+p[i1]A],⋮,Z1E=α[φ1+p[k]A+p[k-1]A+⋯p[i2+1]A+t2+p[i2]A+p[i2-1]A+⋯+p[i1+1]A+t1+p[i1]A+⋯+p[2]A].
For job j of a schedule π, we denote the tardiness cost by ZjT, where j=k+m+1,k+m+2,…,n,
(3.8)Zk+m+1T=β[p[k+m+1]A-φ2],Zk+m+2T=β[p[k+m+1]A+p[k+m+2]A-φ2],⋮ZnT=β[p[k+m+1]A+p[k+m+2]A+⋯+p[n]A-φ2].
The due-window starting time cost denoted by Zd1 can be expressed as
(3.9)Zd1=nγ[φ1+p[k]A+p[k-1]A+⋯p[i2+1]A+t2+p[i2]A+p[i2-1]A+⋯+p[i1+1]A+t1+p[i1]A+⋯+p[2]A+p[1]A].
The due-window size cost denoted by ZD can be expressed as
(3.10)ZD=nδ[p[k+1]A+⋯+p[k+m]A+φ2-φ1].
For simplifying the total cost function, let
(3.11)wj={α(j-1)+γn,j=1,…,i1,α(j-1)+γn,j=i1+1,…,i2,α(j-1)+γn,j=i2+1,…,k,δn,j=k+1,…,k+m,β(n-j+1),j=k+m+1,…,n.
The total cost can be represented as
(3.12)Z=[nγ+αk-nδ]φ1+[δn+β(k+m)-βn]φ2+G,
whereG=[b∑j=i1+1nwj(1+b)j-i1-1+nγ+αi1]t1+[b∑j=i2+1nwj(1+b)j-i2-1+nγ+αi2]t2+∑j=k+m+1n[β(n-j+1)+b∑h=j+1n(1+b)h-j-1(β(n-h+1))]θ[j]2p[j](j)a[j]+∑j=k+1k+m[nδ+b∑h=j+1n(1+b)h-j-1nδ]θ[j]2p[j](j)a[j]+∑j=i2+1k[nγ+α(j-1)+b∑h=j+1n(1+b)h-j-1(α(h-1)+γn)]θ[j]2p[j](j)a[j]+∑j=i1+1i2[nγ+α(j-1)+b∑h=j+1n(1+b)h-j-1(α(h-1)+γn)]θ[j]1p[j](j)a[j]+∑j=1i1[nγ+α(j-1)+b∑h=j+1n(1+b)h-j-1(α(h-1)+γn)]p[j](j)a[j].
From (3.12), we know that the total cost includes three items: [nγ+αk-nδ]φ1, [δn+β(k+m)-βn]φ2, and G. It is easy to find that G>0 based on the expression of G. So the minimization of the total cost depends on the values of [nγ+αk-nδ]φ1 and [δn+β(k+m)-βn]φ2. Because of φ1 and φ2 are independent of the coefficients. So we discuss the minimization problem in the following four different cases.(1)
If[nγ+αk-nδ]≥0 and [δn+β(k+m)-βn]≥0, then φ1=0 and φ2=0.(2)
If[nγ+αk-nδ]≤0 and [δn+β(k+m)-βn]≤0, then φ1=p[k+1]A=θ[k+1]2p[k+1](k+1)a[k+1]+b∑h=1i1(1+b)k-hp[h](h)a[h]b∑h=i1+1i2(1+b)k-hθ[h]1p[h](h)a[h]+b∑h=i2+1k(1+b)k-hθ[h]2p[h](h)a[h]+b(1+b)k-i1t1+b(1+b)k-i2t2, and φ2=p[k+m+1]A=θ[k+m+1]2p[k+m+1](k+m+1)a[k+m+1]+b∑h=1i1(1+b)k+m-hp[h](h)a[h]+b∑h=i1+1i2(1+b)k+m-hθ[h]1p[h](h)a[h]+b∑h=i2+1k+m(1+b)k+m-hθ[h]2p[h](h)a[h]+b(1+b)k+m-i1t1+b(1+b)k+m-i2t2.(3)
If[nγ+αk-nδ]≥0 and [δn+β(k+m)-βn]≤0, then φ1=0 and φ2=p[k+m+1]A=θ[k+m+1]2p[k+m+1](k+m+1)a[k+m+1]+b∑h=1i1(1+b)k+m-hp[h](h)a[h]+b∑h=i1+1i2(1+b)k+m-hθ[h]1p[h](h)a[h]+b∑h=i2+1k+m(1+b)k+m-hθ[h]2p[h](h)a[h]+b(1+b)k+m-i1t1+b(1+b)k+m-i2t2.(4)
If[nγ+αk-nδ]≤0 and [δn+β(k+m)-βn]≥0, then φ1=p[k+1]A=θ[k+1]2p[k+1](k+1)a[k+1]+b∑h=1i1(1+b)k-hp[h](h)a[h]+b∑h=i1+1i2(1+b)k-hθ[h]1p[h](h)a[h]+b∑h=i2+1k(1+b)k-hθ[h]2p[h](h)a[h]+b(1+b)k-i1t1+b(1+b)k-i2t2 and φ2=0.So, from the analysis, we say that an optimal schedule exists in which the due window starts and finishes at certain job completion times.Figure 2
Structure of a schedule considering due-window.By Lemma3.1, the the due-window starting time d1 and finishing time d2 are denoted with k and k+m as the indices of the jobs completed at them, respectively, that is, C[k]=d1 and C[k+m]=d2. Moreover, we also provide another property of an optimal solution for the scheduling problem with learning effect and multiple rate-modifying activities.Lemma 3.2.
For the problem1|DJLE,2RM|∑j=1n(αEj+βTj+γd1+δD), there exists an optimal schedule in which d1=C[k] and d2=C[k+m], where k=⌈n(δ-γ)/α⌉ and (k+m)=⌈n(β-δ)/β⌉.Proof.
The proof is similar to that of Mosheiov and Sarig [30].Lemma 3.3.
For the problem1|DJLE,MRM|∑j=1n(αEj+βTj+γd1+δD), there also exists an optimal schedule in which d1=C[k] and d2=C[k+m], where k=⌈n(δ-γ)/α⌉ and (k+m)=⌈n(β-δ)/β⌉.Proof.
The proof is similar to Lemma3.2.


## 4. An Optimal Solution Policy

In this section, we show that problems1|DJLE,2RM|∑j=1n(αEj+βTj+γd1+δD) and 1|DJLE,MRM|∑j=1n(αEj+βTj+γd1+δD) can be both solved in polynomial times.Theorem 4.1.
The1|DJLE,2RM|∑jn(αEj+βTj+γd1+δD) problem can be solved in O(n2+3)time.Proof.
For two rate-modifying activities, there are six cases altogether, that is,i1≤i2≤k, k≤i1≤i2≤k+m, k+m≤i1≤i2, i1≤k&&k+m≤i2, i1≤k&&k≤i2≤k+m, and k≤i1≤k+m&&k+m≤i2.Case 1 (i1,i2<k).
If two different rate-modifying activities are performed before the due window, from the preliminary works, the total cost can be given by(4.1)Z=[b∑j=i1+1nwj(1+b)j-i1-1+nγ+αi1]t1+[b∑j=i2+1nwj(1+b)j-i2-1+nγ+αi2]t2+∑j=k+m+1n[β(n-j+1)+b∑h=j+1n(1+b)h-j-1(β(n-h+1))]θ[j]2p[j](j)a[j]+∑j=k+1k+m[nδ+b∑h=j+1n(1+b)h-j-1nδ]θ[j]2p[j](j)a[j]+∑j=i2+1k[nγ+α(j-1)+b∑h=j+1n(1+b)h-j-1(α(h-1)+γn)]θ[j]2p[j](j)a[j]+∑j=i1+1i2[nγ+α(j-1)+b∑h=j+1n(1+b)h-j-1(α(h-1)+γn)]θ[j]1p[j](j)a[j]+∑j=1i1[nγ+α(j-1)+b∑h=j+1n(1+b)h-j-1(α(h-1)+γn)]p[j](j)a[j].
By substituting (3.11) into above total cost function again, we have
(4.2)Z=∑j=1i1[wj+b∑h=j+1n(1+b)h-j-1wh]p[j](j)a[j]+∑j=i1+1i2[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]1p[j](j)a[j]+∑j=i2+1n[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]2p[j](j)a[j]+[b∑j=i1+1nwj(1+b)j-i1-1+nγ+αi1]t1+[b∑j=i2+1nwj(1+b)j-i2-1+nγ+αi2]t2.Case 2 (k≤i1,i2≤(k+m)).
if two different rate-modifying activities are performed in the due window, similar to the analysis of Case1, the total cost can be given by
(4.3)Z=∑j=1n(αEj+βTj+γd1+δD)=∑j=1i1[wj+b∑h=j+1n(1+b)h-j-1wh]p[j](j)a[j]+∑j=i1+1i2[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]1p[j](j)a[j]+∑j=i2+1n[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]2p[j](j)a[j]+[b∑j=i1+1nwj(1+b)j-i1-1+nδ]t1+[b∑j=i2+1nwj(1+b)j-i2-1+nδ]t2.Case 3 ((k+m)≤i1,i2).
if two different rate-modifying activities are performed after the due window, similar to the analysis of Case1, the total cost can be given by
(4.4)Z=∑j=1n(αEj+βTj+γd1+δD)=∑j=1i1[wj+b∑h=j+1n(1+b)h-j-1wh]p[j](j)a[j]+∑j=i1+1i2[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]1p[j](j)a[j]+∑j=i2+1n[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]2p[j](j)a[j]+[b∑j=i1+1nwj(1+b)j-i1-1+β(n-i1)]t1+[b∑j=i2+1nwj(1+b)j-i2-1+β(n-i2)]t2.Case 4 ((i1≤k)&&(k+m≤i2)).
If one rate-modifying activities is performed before the due-window and the other is after the due-window, similar to the analysis of Case1, the total cost can be given by
(4.5)Z=∑j=1n(αEj+βTj+γd1+δD)=∑j=1i1[wj+b∑h=j+1n(1+b)h-j-1wh]p[j](j)a[j]+∑j=i1+1i2[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]1p[j](j)a[j]+∑j=i2+1n[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]2p[j](j)a[j]+[b∑j=i1+1nwj(1+b)j-i1-1+nγ+αi1]t1+[b∑j=i2+1nwj(1+b)j-i2-1+β(n-i2)]t2.Case 5 ((i1≤k)&&(k≤i2≤k+m)).
if one rate-modifying activities is performed before the due window and the other is in the due window, similar to the analysis of Case1, the total cost can be given by
(4.6)Z=∑j=1n(αEj+βTj+γd1+δD)=∑j=1i1[wj+b∑h=j+1n(1+b)h-j-1wh]p[j](j)a[j]+∑j=i1+1i2[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]1p[j](j)a[j]+∑j=i2+1n[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]2p[j](j)a[j]+[b∑j=i1+1nwj(1+b)j-i1-1+nγ+αi1]t1+[b∑j=i2+1nwj(1+b)j-i2-1+nδ]t2.Case 6 ((k≤i1≤k+m)&&(k+m≤i2)).
if one rate-modifying activities is performed in the due window and the other is after the due window, similar to the analysis of Case1, the total cost can be given by
(4.7)Z=∑j=1n(αEj+βTj+γd1+δD)=∑j=1i1[wj+b∑h=j+1n(1+b)h-j-1wh]p[j](j)a[j]+∑j=i1+1i2[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]1p[j](j)a[j]+∑j=i2+1n[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]2p[j](j)a[j]+[b∑j=i1+1nwj(1+b)j-i1-1+nδ]t1+[b∑j=i2+1nwj(1+b)j-i2-1+nγ+αi2]t2. In the following discussion, for simplification we still take only one case into consideration, that is, Case 3. we define variables xjr, for j=1,2,…,n,  r=1,2,…,n. xjr=1, if job j is scheduled in position r,=0, otherwise.
Let(4.8)Bjr={(wr+b∑h=r+1n(1+b)h-r-1wh)p[j](r)a[j],r=1,…,i1,(wr+b∑h=r+1n(1+b)h-r-1wh)θ[j]1p[j](r)a[j],r=i1+1,…,i2,(wr+b∑h=r+1n(1+b)h-r-1wh)θ[j]2p[j](r)a[j],r=i2+1,…,n.
The problem can be formulated as follows:
(4.9)Min⁡∑j=1n∑r=1nBjrxjr+[b∑j=i1+1nwj(1+b)j-i1-1+β(n-i1)]t1+[b∑j=i2+1nwj(1+b)j-i2-1+β(n-i2)]t2subject to∑r=1nxjr=1,j=1,2,…,n,∑j=1nxjr=1,r=1,2,…,n,xjr=1or0,j=1,2,…,n,r=1,2,…,n.
The first set of constraints guarantees each job j is scheduled only once, the second set of constraints guarantees each position r is taken by only one job, and the third constraints means the variable xjr is binary. For given positions i1 and i2, the problem is transferred to the following assignment problem
(AP)Min⁡∑j=1n∑r=1nBjrxjrsubjectto∑r=1nxjr=1,j=1,2,…,n,∑j=1nxjr=1,r=1,2,…,n,xjr=1or0,j=1,2,…,n,r=1,2,…,n.
The assignment problem can be solved in O(n3) time (see, e.g., Papadimitriou and Steiglitz [35] and Brucker [36]). However, i1 and i2 may be any value of 1⋯n for all cases, so the complexity of Case 2 is O(n3+2)=O(n5) and Theorem 4.1 holds.Theorem 4.2.
The1|JDLE,MRM|∑jn(αEj+βTj+γd1+δD) problem can be solved in O(n3+u)time.Proof.
When there existu different rate-modifying activities, we take the case (k+m)≤i1<i2<i3⋯<iu as an example, and the proofs of other cases are similar. We can formulate the problem as follows:
(4.10)Z=∑jn(αEj+βTj+γd1+δD)=∑j=1i1[wj+b∑h=j+1n(1+b)h-j-1wh]p[j](j)a[j]+∑j=i1+1i2[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]1p[j](j)a[j]+∑j=i2+1n[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]2p[j](j)a[j]+⋯+∑j=iu+1n[wj+b∑h=j+1n(1+b)h-j-1wh]θ[j]up[j](j)a[j]+[b∑j=i1+1nwj(1+b)j-i1-1+β(n-i1)]t1+[b∑j=i2+1nwj(1+b)j-i2-1+β(n-i2)]t2+⋯+[b∑j=i2+1nwj(1+b)j-iu-1+β(n-iu)]tu.
Let(4.11)Qjr={(wr+b∑h=r+1n(1+b)h-r-1wh)p[j](r)a[j],r=1,…,i1,(wr+b∑h=r+1n(1+b)h-r-1wh)θ[j]1p[j](r)a[j],r=i1+1,…,i2,(wr+b∑h=r+1n(1+b)h-r-1wh)θ[j]2p[j](r)a[j],r=i2+1,…,i3,⋮(wr+b∑h=r+1n(1+b)h-r-1wh)θ[j]up[j](r)a[j],r=iu+1,…,n.
The problem can be transformed to the following form after introducing variable xjr defined as above:
(4.12)Min⁡∑j=1n∑r=1nQjrxjr+∑l=1u[b∑j=i1+1nwj(1+b)j-i1-1+β(n-iu)]tlsubjectto∑r=1nxjr=1,j=1,2,…,n,∑j=1nxjr=1,r=1,2,…,n,xjr=1or0,j=1,2,…,n,r=1,2,…,n.
For given positions i1, i2,…,iu, the last item in the objective function is constant. So the above minimization is equivalent to minimizing the following assignment problem:
(BP)Min⁡∑j=1n∑r=1nQjrxjrsubjectto∑r=1nxjr=1,j=1,2,…,n,∑j=1nxjr=1,r=1,2,…,n,xjr=1or0,j=1,2,…,n,r=1,2,…,n.
Since i1,i2,…,iu may be any value of  1⋯n, the number of (1,…,n) vectors is bounded by (n+1)u. The complexity of the problem is O(n3+u) for all cases and Theorem 4.2 holds.The polynomial time algorithm to solve1|DJLE,2RM|∑j=1n(αEj+βTj+γd1+δD) problem optimally is as follows.Algorithm 1.
We have the following steps.Step 1.
Assign the optimal due-window starting timed1* and finishing time d2* at the completion time of the kth and (k+m)th job specifically, where k=⌈n(δ-γ)/α⌉, (k+m)=⌈n(β-δ)/β⌉.Step 2.
For (i2=1,iu≤n,iu++) and for (i1=1,i1≤n,i1++).
Calculate the weightBjr with (4.8).
Solve the classical assignment problem (AP) and get the total cost.Step 3.
Obtain the optimal schedule with minimum total cost.The polynomial time algorithm to solve1|DJLE,MRM|∑j=1n(αEj+βTj+γd1+δD) problem optimally is as follows.Algorithm 2.
We have the following steps.Step 1.
Assign the optimal due-window starting timed1* and finishing time d2* at the completion time of the kth and (k+m)th job specifically, where k=⌈n(δ-γ)/α⌉, (k+m)=⌈n(β-δ)/β⌉.Step 2.
For (iu=1,iu≤n,iu++), for (iu-1=1,iu-1≤n,iu-1++),…,  and for (i1=1,i1≤n,i1++).
Calculate the weightQjr, for j=1,2,…,n; r=1,2,…,n.
Solve the classical assignment problem (BP) and get the total cost.Step 3.
Obtain the optimal schedule with minimum total cost.From the above description, it is easy to conclude that Algorithms1 and 2 take O(n5) time and O(n3+u) time, respectively.


## 5. Conclusions

In this paper, we consider a single machine scheduling problem with due-window assignment and multiple rate-modifying activities in the settings of learning effect and deteriorating jobs. We introduce anO(n3+u) solution algorithm for u different types of rate-modifying activities considering the objective to find jointly the optimal location to perform multiple rate-modifying activities, the optimal job sequence, and the optimal location and size of the due window to minimize the total earliness, tardiness, and due-window-related costs. Further research may investigate problems with multimachine settings and deteriorating rate-modifying activities.



---

*Source: 151563-2011-05-10.xml*