# Due-Window Assignment Scheduling with Variable Job Processing Times

Authors: Yu-Bin Wu; Ping Ji
Journal: The Scientific World Journal
 (2015)

---

## Abstract

We consider a common due-window assignment scheduling problem jobs with variable job processing times on a single machine, where the processing time of a job is a function of its position in a sequence (i.e., learning effect) or its starting time (i.e., deteriorating effect). The problem is to determine the optimal due-windows, and the processing sequence simultaneously to minimize a cost function includes earliness, tardiness, the window location, window size, and weighted number of tardy jobs. We prove that the problem can be solved in polynomial time.


---

## Body

## 1. Introduction

In most scheduling studies, job processing times are treated as constant numbers; however, in many practical situations, job processing times are affected by the learning effects and/or deteriorating (aging) effects. Learning effects and deteriorating (aging) effects are important for production and scheduling problems. For details on this line of the scheduling problems with learning effects (deteriorating effects), the reader is referred to a comprehensive survey by Biskup [1] (Gawiejnowicz [2]). Rudek [3] considered single machine scheduling problems with position-dependent job processing times (i.e., learning and aging effects). For the following objectives, the makespan with release dates, the maximum lateness, and the number of late jobs, they gave some results. J.-B. Wang and M.-Z. Wang [4] and Sun et al. [5] considered flow shop scheduling problems with general position-dependent learning effects. For some regular objective functions, they proposed heuristics. Sun et al. [6] considered flow shop scheduling problems with three special position-dependent learning effects. For the total weighted completion time minimization problem, they proposed heuristics. Lu et al. [7] considered single machine scheduling problems with learning effects and controllable processing times. For two due date assignment methods, they presented a polynomial-time optimization algorithm to minimize a multiobjective cost function.J.-B. Wang and M.-Z. Wang [8] considered common due-window single machine scheduling with learning effects and controllable processing times. For a mule-objective cost function, they presented a polynomial-time optimization algorithm. J.-B. Wang and M.-Z. Wang [9] considered single machine scheduling problems with nonlinear deterioration. They showed that the makespan minimization problem can be solved in polynomial time. J.-B. Wang and M.-Z. Wang [10] considered three-machine flow shop scheduling with deteriorating jobs. For the makespan minimization problem, they proposed a branch-and-bound algorithm and two heuristic algorithms. X.-R Wang and J.-J. Wang [11] considered single machine scheduling problems with deteriorating jobs and convex resource dependent processing times. Xu et al. [12] considered single machine group scheduling with proportional linear deterioration and ready times. For the makespan minimization problem, they gave some results. Cheng et al. [13] considered a single machine common due-window assignment scheduling problem with deteriorating jobs. For a deteriorating maintenance activity, they provided polynomial-time solutions for a multiobjective cost. Yang et al. [14] considered a single machine multiple common due dates assignment resource allocation scheduling problems with general position-dependent deterioration effect. For a multiobjective cost, they proved that the problems can be solved in polynomial time, respectively. Liu et al. [15] considered single-machine common due-window assignment scheduling problem with deteriorating jobs. If the width of the common due-window is a given constant, they proved a mule-objective function cost problem can be solved in polynomial time. J.-B. Wang and C. Wang [16] and Wang et al. [17] considered due-window assignment scheduling problems with learning effects and deteriorating jobs at the same time.The recent paper Li et al. [18] addresses single machine scheduling problem with deteriorating jobs. For common due date assignment (CON) and common flow allowance (i.e., all jobs have slack due date (SLK)) due date assignment methods, they showed that a multiobjective minimization problem can be solved in polynomial time, respectively. In this research, we continue the work of Li et al. [18] but focus on the common due-window assignment (CONW) scheduling problem (Yin et al. [19]). Under the learning effect and deteriorating jobs models, we prove that the CONW due-window assignment scheduling is solvable in polynomial time, respectively.


## 2. Problem Formulation

The following notations will be used throughout the paper:Jj: Job jJ: Set of jobs (i.e., J={J1,J2,…,Jn})Cj: Completion time of job Jjd1: Earliest due dateD: Common due-window sized2: Latest due date =d1+DEj: Earliness of Jj=max⁡{0,d1-Cj}Tj: Tardiness of Jj=max⁡{0,Cj-d2}E: Set of earliest jobs ={Jj∣Cj<d1}T: Set of tardy jobs ={Jj∣Cj>d2}D-: Set of on time jobs (i.e., D-=J∖(E∪T))m: Number of set D- jobs (i.e., m=|D-|)γj: The penalty weight if Jj is tardy (i.e., Jj∈T)F(d1,D,π)=αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj: The total cost function, where α>0, β>0, and θ>0 are the unit due-window starting time, due-window size, and earliness penalties, respectively.Consider a nonpreemptive single machine setting. There aren independent jobs J={J1,J2,…,Jn} available at zero and preemption is not allowed. Let Pj denote the actual processing time for job Jj. In this research, we consider the following models.Job Time-Dependent Deterioration Effect Model (See Li et al. [18]). Consider(1)Pj=aj+bt,where aj, b>0, t are the basic (normal) processing time of Jj, the deteriorating rate, and the starting time of Jj, respectively.Job-Position-Dependent Learning Effect Model (See Biskup [20]). Consider(2)Pj=ajra,where aj, a<0, r are the basic (normal) processing time of Jj, the learning rate, and the position Jj in a processing sequence, respectively.Our task of this paper is to determine the optimal earliest due dated1, the common due-window size D, and a schedule π which minimizes the following objective function:(3)Fd1,D,π=αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj.Then, using the common three-field notation introduced by Graham et al. [21], the corresponding scheduling problems are denoted by(4)1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj,1∣Pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj.


## 3. Optimal Solutions

### 3.1. Job Time-Dependent Deterioration Effect Model

Lemma 1 (Li et al. [18]).
For a given scheduleπ=(J1,J2,…,J[n]), if the starting time of the first job is 0, then C[r]=∑j=1ra[j](1+b)r-j and ∑j=1nCj=∑j=1na[j]∑i=0n-j(1+b)i.Lemma 2.
Ifα>β, an optimal schedule exists in which the due-window starts at time zero.Proof.
Supposeα>β, and d1>0; we shift X units of time to the left. The change in the total cost is given by ΔZ=-αX+βX-θlX, where l denotes the number of early jobs. Cleary, ΔZ<0. Therefore, a shift of d1 (until d1=0) can only decrease the total cost.Lemma 3.
An optimal schedule exists in which the due-window starting time (i.e.,d1), and the due-window completion time (i.e., d2) coincide with job completion times, respectively.Proof.
Suppose that there exists a schedule starting at time zero and containing jobs at thekth and the (k+m)th positions such that Ck<d1<Ck+1,Ck+m<d2<Ck+m+1.When we shiftd2 to Ck+m, the change in the total cost is given by -β(d2-Ck+m).When we shiftd1 to Ck, the change in the total cost is given by (-α+β+kθ)(d1-Ck).When we shiftd1 to Ck+1, the change in the total cost is given by -(-α+β+kθ)(Ck+1-d1).Again, a shift ofd1 to Ck or to Ck+1 does not increase the total cost.
Therefore, an optimal schedule exists such that bothd1 and d2 coincide with job completion times.Lemma 4.
An optimal schedule exists in which the index of the job completed at the due-window starting time isk=(β-α)/θ.Proof.
Using the classical small perturbation technique (see J.-B. Wang and C. Wang [16] and J.-B. Wang and M.-Z. Wang [8]), we measure the change in the total cost when moving d1.
We shiftd1, X units of time to the left, and the effect of the total cost is (5)-αX+βX-θk-1X.We shift d1, X units of time to the right, and the effect of the total cost is (6)αX-βX+θkX.Both expressions (5) and (6) are clearly nonnegative due to the optimality of the original solution.
From-αX+βX-θ(k-1)X≥0 and αX-βX+θkX≥0 we have k≤(β-α/θ)+1 and k≥(β-α)/θ. And from the integrality ofk, it follows that k=(β-α)/θ.Lemma 5.
For the problem1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj, if the job sequence is π=(J1,J2,…,J[n]) and m=|D-|, then the objective function can be expressed as(7)Fd1,D,π,m=∑j=1k+mwjaj+∑j=k+m+1nγj,where (8)wj={(α+kθ)+β[1+bm-1]}1+bk-j-θ∑i=0k-j1+bi,j=1,2,…,k;β1+bk+m-j,j=k+1,k+2,…,k+m.Proof.
By Lemmas1 and 3, we have(9)d1=C[k]=∑j=1ka[j]1+bk-j,(10)D=Ck+m-Ck=∑j=1k+ma[j]1+bk+m-j-∑j=1ka[j]1+bk-j=∑j=1kaj1+bk+m-j+∑j=k+1k+maj1+bk+m-j-∑j=1ka[j]1+bk-j=∑j=1kaj1+bk-j1+bm+∑j=k+1k+maj1+bk+m-j-∑j=1ka[j]1+bk-j=∑j=1kaj1+bk-j[1+bm-1]+∑j=k+1k+maj1+bk+m-j,Fd1,D,π,m=αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj=αCk+β∑j=1kaj1+bk-j[1+bm-1]=αCk+β22+∑j=k+1k+maj1+bk+m-j+θ∑j=1k(C[k]-C[j])+∑Jj∈Tγ[j]=(α+kθ)Ck-θ∑j=1kCj+β∑j=1kaj1+bk-j[1+bm-1]+β∑j=k+1k+ma[j]1+bk+m-j+∑Jj∈Tγ[j]=(α+kθ)∑j=1kaj1+bk-j+β∑j=1ka[j]1+bk-j[1+bm-1]-θ∑j=1kaj∑i=0k-j1+bi+β∑j=k+1k+maj1+bk+m-j+∑j=k+m+1nγ[j]=∑j=1kaj1+bk-j{(α+kθ)+β[1+bm-1]}-θ∑j=1ka[j]∑i=0k-j1+bi+β∑j=k+1k+ma[j]1+bk+m-j+∑j=k+m+1nγj=∑j=1k+mwjaj+∑j=k+m+1nγj.Corollary 6.
Ifm=n-k, then(11)Fd1,D,π,n-k=∑j=1nwjaj,where(12)wj={(α+kθ)+β[1+bm-1]}1+bk-j-θ∑i=0k-j1+bi,j=1,2,…,kβ1+bk+m-j,j=k+1,k+2,…,n.Equation (11) can be viewed as the scalar product of two vectors, wj and a[j], respectively, (j=1,…,n). It is well known (from Hardy et al. [22]) that (11) is minimized by sorting the elements of the wj and a[j] vectors in opposite orders. This procedure can be done in O(nlog⁡n) time. We refer to this rule as the HLP rule in the rest of the paper.Theorem 7.
If the number ofD- jobs is given, then the problem 1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be formulated as an assignment problem.Proof.
We definezjr as a 0/1 variable such that zjr=1 if job Jj is scheduled in position r, and zjr=0, otherwise. We can formulate the problem 1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj as the following assignment problem:(13)APmMin⁡∑j=1n∑r=1nCjrmzjrSubjectto∑r=1nzjr=1,j=1,2,…,n∑j=1nzjr=1,r=1,2,…,nzjr=0or1,j,r=1,2,…,n,where(14)Cjrm=aj∑i=0k-r1+biα+kθ+β1+bm-11+bk-r-θ∑i=0k-r1+bi,r=1,2,…,kajβ1+bk+m-r,r=k+1,k+2,…,k+mγj,β1+bk+m-r,r=k+m+1,…,n.Therefore, based on the above analysis, we can obtain a polynomial algorithm for the problem 1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj.Algorithm 8.Step
0. By Lemma 4, calculate k=(β-α)/θ.Step
1. For m from 0 to n-k-1, solve the above assignment problem AP(m) to obtain a local optimal schedule and the total cost F(m).Step
2. For m=n-k, first calculate the positional weights defined by (12) and assign the n jobs to the corresponding positions according to the HLP rule and then use (11) to evaluate the objective value F(n-k).Step
3. The global optimal schedule is the one with the minimum total cost given by min⁡{Fm∣0≤m≤n-k}.Based on the above analysis, we have the following result.Theorem 9.
The scheduling problem1∣pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be solved by Algorithm 8 in O(n4) time.Proof.
For a givenm, our problem becomes identical to the classical assignment problem and can be solved in O(n3) time. Since 0≤m≤n-k≤n, the overall time requirement of Algorithm 8 is O(n4).Example 10.
Consider the instance with(15)n=5,α=2,β=4,θ=0.5,b=0.3,a1=4,a2=3,a3=6,a4=9,a5=11,γ1=6,γ2=4,γ3=5,γ4=3,γ5=30.Now we apply Algorithm8 to solve Example 10.Step 0. Calculate the index k=(β-α)/θ=(4-2)/0.5=4.Step 1. When m=0, the Cjr0 values can be calculated by (14) and given below:(16)Cjr0=22.778019.060016.200014617.083514.295012.150010.5434.167028.590024.300021551.250542.885036.450031.5362.639552.415044.550038.530.The optimal job sequence is (J2,J1,J3,J5,J4).The optimal objective value isF(0)=101.9435.Step 2. When m=1, the wj values can be calculated by (12):(17)w1=8.3309,w2=6.7930,w3=5.6100,w4=4.7000,w5=4.0000.The optimal job sequence is (J2,J1,J3,J4,J5).The optimal objective value isF(1)=172.1247.Step 3. The global optimal objective is min{F(0),F(1)}=101.9435. The global optimal schedule is (J2,J1,J3,J5,J4).


### 3.2. Job-Position-Dependent Learning Effect Model

By the same way as in the previous subsection, we consider the following scheduling problem:1∣Pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj.Lemma 11.
For a given scheduleπ=(J1,J2,…,J[n]), if the starting time of the first job is 0, then C[r]=∑j=1ra[j]ja and ∑j=1nCj=∑j=1na[j](n+1-j)ja.Lemma 12.
For the problem1∣pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj, if the job sequence is π=(J1,J2,…,J[n]) and m=|D-|, then the objective function can be expressed as(18)Fd1,D,π,m=∑j=1k+mw¯jaj+∑j=k+m+1nγj,where w¯j=(α-θ+θj)ja,βjaj=1,2,…,k;j=k+1,k+2,…,k+m.Proof.
By Lemmas3 and 11, we have(19)Fd,D,π,m=αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj=αCk+β∑j=k+1k+maj1+bn-j+θ∑j=1k(C[k]-C[j])+∑Jj∈Tγ[j]=(α+kθ)Ck-θ∑j=1kCj+β∑j=k+1k+maj1+bn-j+∑Jj∈Tγ[j]=(α+kθ)∑j=1kajja-θ∑j=1kaj(k+1-j)ja+β∑j=k+1k+ma[j]ja+∑j=k+m+1nγ[j]=∑j=1k+mwjaj+∑j=k+m+1nγj.Corollary 13.
Ifm=n-k, then(20)Fd1,D,π,m=∑j=1nw¯jaj,where w¯j=(α-θ+θj)ja,βjaj=1,2,…,k;j=k+1,k+2,…,k+m.Equation (20) can be viewed as the scalar product of two vectors, w¯j and a[j] vectors, respectively. The procedure can be done in O(nlog⁡n) time by the HLP rule.Theorem 14.
If we fix the number ofD- jobs, then the problem 1∣pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be formulated as an assignment problem.Proof.
It is similar to the proof of Theorem7.Again, we can define(21)C-jrm=(α-θ-θr)raaj,r=1,2,…,kβraaj,r=k+1,k+2,…,k+mγj,r=k+m+1,…,n,as the cost of assigning job Jj(j=1,2,…,n) to the rth (r=1,2,…,n) position in the schedule. Then the problem 1∣pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be formulated as the following assignment problem:(22)APmMin⁡∑j=1n∑r=1nC-jrmzjrSubjectto∑r=1nzjr=1,j=1,2,…,n∑j=1nzjr=1,r=1,2,…,nzjr=0or1,j,r=1,2,…,n.Similar to Section3.1, we have the following theorem.Theorem 15.
The scheduling problem1∣pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be solved in O(n4) time.


## 3.1. Job Time-Dependent Deterioration Effect Model

Lemma 1 (Li et al. [18]).
For a given scheduleπ=(J1,J2,…,J[n]), if the starting time of the first job is 0, then C[r]=∑j=1ra[j](1+b)r-j and ∑j=1nCj=∑j=1na[j]∑i=0n-j(1+b)i.Lemma 2.
Ifα>β, an optimal schedule exists in which the due-window starts at time zero.Proof.
Supposeα>β, and d1>0; we shift X units of time to the left. The change in the total cost is given by ΔZ=-αX+βX-θlX, where l denotes the number of early jobs. Cleary, ΔZ<0. Therefore, a shift of d1 (until d1=0) can only decrease the total cost.Lemma 3.
An optimal schedule exists in which the due-window starting time (i.e.,d1), and the due-window completion time (i.e., d2) coincide with job completion times, respectively.Proof.
Suppose that there exists a schedule starting at time zero and containing jobs at thekth and the (k+m)th positions such that Ck<d1<Ck+1,Ck+m<d2<Ck+m+1.When we shiftd2 to Ck+m, the change in the total cost is given by -β(d2-Ck+m).When we shiftd1 to Ck, the change in the total cost is given by (-α+β+kθ)(d1-Ck).When we shiftd1 to Ck+1, the change in the total cost is given by -(-α+β+kθ)(Ck+1-d1).Again, a shift ofd1 to Ck or to Ck+1 does not increase the total cost.
Therefore, an optimal schedule exists such that bothd1 and d2 coincide with job completion times.Lemma 4.
An optimal schedule exists in which the index of the job completed at the due-window starting time isk=(β-α)/θ.Proof.
Using the classical small perturbation technique (see J.-B. Wang and C. Wang [16] and J.-B. Wang and M.-Z. Wang [8]), we measure the change in the total cost when moving d1.
We shiftd1, X units of time to the left, and the effect of the total cost is (5)-αX+βX-θk-1X.We shift d1, X units of time to the right, and the effect of the total cost is (6)αX-βX+θkX.Both expressions (5) and (6) are clearly nonnegative due to the optimality of the original solution.
From-αX+βX-θ(k-1)X≥0 and αX-βX+θkX≥0 we have k≤(β-α/θ)+1 and k≥(β-α)/θ. And from the integrality ofk, it follows that k=(β-α)/θ.Lemma 5.
For the problem1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj, if the job sequence is π=(J1,J2,…,J[n]) and m=|D-|, then the objective function can be expressed as(7)Fd1,D,π,m=∑j=1k+mwjaj+∑j=k+m+1nγj,where (8)wj={(α+kθ)+β[1+bm-1]}1+bk-j-θ∑i=0k-j1+bi,j=1,2,…,k;β1+bk+m-j,j=k+1,k+2,…,k+m.Proof.
By Lemmas1 and 3, we have(9)d1=C[k]=∑j=1ka[j]1+bk-j,(10)D=Ck+m-Ck=∑j=1k+ma[j]1+bk+m-j-∑j=1ka[j]1+bk-j=∑j=1kaj1+bk+m-j+∑j=k+1k+maj1+bk+m-j-∑j=1ka[j]1+bk-j=∑j=1kaj1+bk-j1+bm+∑j=k+1k+maj1+bk+m-j-∑j=1ka[j]1+bk-j=∑j=1kaj1+bk-j[1+bm-1]+∑j=k+1k+maj1+bk+m-j,Fd1,D,π,m=αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj=αCk+β∑j=1kaj1+bk-j[1+bm-1]=αCk+β22+∑j=k+1k+maj1+bk+m-j+θ∑j=1k(C[k]-C[j])+∑Jj∈Tγ[j]=(α+kθ)Ck-θ∑j=1kCj+β∑j=1kaj1+bk-j[1+bm-1]+β∑j=k+1k+ma[j]1+bk+m-j+∑Jj∈Tγ[j]=(α+kθ)∑j=1kaj1+bk-j+β∑j=1ka[j]1+bk-j[1+bm-1]-θ∑j=1kaj∑i=0k-j1+bi+β∑j=k+1k+maj1+bk+m-j+∑j=k+m+1nγ[j]=∑j=1kaj1+bk-j{(α+kθ)+β[1+bm-1]}-θ∑j=1ka[j]∑i=0k-j1+bi+β∑j=k+1k+ma[j]1+bk+m-j+∑j=k+m+1nγj=∑j=1k+mwjaj+∑j=k+m+1nγj.Corollary 6.
Ifm=n-k, then(11)Fd1,D,π,n-k=∑j=1nwjaj,where(12)wj={(α+kθ)+β[1+bm-1]}1+bk-j-θ∑i=0k-j1+bi,j=1,2,…,kβ1+bk+m-j,j=k+1,k+2,…,n.Equation (11) can be viewed as the scalar product of two vectors, wj and a[j], respectively, (j=1,…,n). It is well known (from Hardy et al. [22]) that (11) is minimized by sorting the elements of the wj and a[j] vectors in opposite orders. This procedure can be done in O(nlog⁡n) time. We refer to this rule as the HLP rule in the rest of the paper.Theorem 7.
If the number ofD- jobs is given, then the problem 1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be formulated as an assignment problem.Proof.
We definezjr as a 0/1 variable such that zjr=1 if job Jj is scheduled in position r, and zjr=0, otherwise. We can formulate the problem 1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj as the following assignment problem:(13)APmMin⁡∑j=1n∑r=1nCjrmzjrSubjectto∑r=1nzjr=1,j=1,2,…,n∑j=1nzjr=1,r=1,2,…,nzjr=0or1,j,r=1,2,…,n,where(14)Cjrm=aj∑i=0k-r1+biα+kθ+β1+bm-11+bk-r-θ∑i=0k-r1+bi,r=1,2,…,kajβ1+bk+m-r,r=k+1,k+2,…,k+mγj,β1+bk+m-r,r=k+m+1,…,n.Therefore, based on the above analysis, we can obtain a polynomial algorithm for the problem 1∣Pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj.Algorithm 8.Step
0. By Lemma 4, calculate k=(β-α)/θ.Step
1. For m from 0 to n-k-1, solve the above assignment problem AP(m) to obtain a local optimal schedule and the total cost F(m).Step
2. For m=n-k, first calculate the positional weights defined by (12) and assign the n jobs to the corresponding positions according to the HLP rule and then use (11) to evaluate the objective value F(n-k).Step
3. The global optimal schedule is the one with the minimum total cost given by min⁡{Fm∣0≤m≤n-k}.Based on the above analysis, we have the following result.Theorem 9.
The scheduling problem1∣pj=aj+bt∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be solved by Algorithm 8 in O(n4) time.Proof.
For a givenm, our problem becomes identical to the classical assignment problem and can be solved in O(n3) time. Since 0≤m≤n-k≤n, the overall time requirement of Algorithm 8 is O(n4).Example 10.
Consider the instance with(15)n=5,α=2,β=4,θ=0.5,b=0.3,a1=4,a2=3,a3=6,a4=9,a5=11,γ1=6,γ2=4,γ3=5,γ4=3,γ5=30.Now we apply Algorithm8 to solve Example 10.Step 0. Calculate the index k=(β-α)/θ=(4-2)/0.5=4.Step 1. When m=0, the Cjr0 values can be calculated by (14) and given below:(16)Cjr0=22.778019.060016.200014617.083514.295012.150010.5434.167028.590024.300021551.250542.885036.450031.5362.639552.415044.550038.530.The optimal job sequence is (J2,J1,J3,J5,J4).The optimal objective value isF(0)=101.9435.Step 2. When m=1, the wj values can be calculated by (12):(17)w1=8.3309,w2=6.7930,w3=5.6100,w4=4.7000,w5=4.0000.The optimal job sequence is (J2,J1,J3,J4,J5).The optimal objective value isF(1)=172.1247.Step 3. The global optimal objective is min{F(0),F(1)}=101.9435. The global optimal schedule is (J2,J1,J3,J5,J4).


## 3.2. Job-Position-Dependent Learning Effect Model

By the same way as in the previous subsection, we consider the following scheduling problem:1∣Pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj.Lemma 11.
For a given scheduleπ=(J1,J2,…,J[n]), if the starting time of the first job is 0, then C[r]=∑j=1ra[j]ja and ∑j=1nCj=∑j=1na[j](n+1-j)ja.Lemma 12.
For the problem1∣pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj, if the job sequence is π=(J1,J2,…,J[n]) and m=|D-|, then the objective function can be expressed as(18)Fd1,D,π,m=∑j=1k+mw¯jaj+∑j=k+m+1nγj,where w¯j=(α-θ+θj)ja,βjaj=1,2,…,k;j=k+1,k+2,…,k+m.Proof.
By Lemmas3 and 11, we have(19)Fd,D,π,m=αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj=αCk+β∑j=k+1k+maj1+bn-j+θ∑j=1k(C[k]-C[j])+∑Jj∈Tγ[j]=(α+kθ)Ck-θ∑j=1kCj+β∑j=k+1k+maj1+bn-j+∑Jj∈Tγ[j]=(α+kθ)∑j=1kajja-θ∑j=1kaj(k+1-j)ja+β∑j=k+1k+ma[j]ja+∑j=k+m+1nγ[j]=∑j=1k+mwjaj+∑j=k+m+1nγj.Corollary 13.
Ifm=n-k, then(20)Fd1,D,π,m=∑j=1nw¯jaj,where w¯j=(α-θ+θj)ja,βjaj=1,2,…,k;j=k+1,k+2,…,k+m.Equation (20) can be viewed as the scalar product of two vectors, w¯j and a[j] vectors, respectively. The procedure can be done in O(nlog⁡n) time by the HLP rule.Theorem 14.
If we fix the number ofD- jobs, then the problem 1∣pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be formulated as an assignment problem.Proof.
It is similar to the proof of Theorem7.Again, we can define(21)C-jrm=(α-θ-θr)raaj,r=1,2,…,kβraaj,r=k+1,k+2,…,k+mγj,r=k+m+1,…,n,as the cost of assigning job Jj(j=1,2,…,n) to the rth (r=1,2,…,n) position in the schedule. Then the problem 1∣pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be formulated as the following assignment problem:(22)APmMin⁡∑j=1n∑r=1nC-jrmzjrSubjectto∑r=1nzjr=1,j=1,2,…,n∑j=1nzjr=1,r=1,2,…,nzjr=0or1,j,r=1,2,…,n.Similar to Section3.1, we have the following theorem.Theorem 15.
The scheduling problem1∣pj=ajra∣αd1+βD+θ∑Jj∈EEj+∑Jj∈Tγj can be solved in O(n4) time.


## 4. Conclusions

We have considered the single machine due-window assignment scheduling problem with variable job processing times. The objective is to minimize a linear combination of earliness, tardiness, the window location, window size, and weighted number of tardy jobs. We proposed a polynomial-time algorithm, respectively, for the learning effect and the deteriorating jobs. Obviously, ifa>0 (i.e., deterioration or aging effect) and b<0 (i.e., shortening processing times), then the results of this paper still hold. In future research, we plan to explore more realistic settings, such as group technology scheduling problems, flexible flow shop scheduling problems, and unrelated parallel machines scheduling problems, or optimize other performance measures with variable job processing time.



---

*Source: 740750-2015-03-30.xml*