# Optimization for Due-Window Assignment Scheduling with Position-Dependent Weights

Authors: Li-Yan Wang; Dan-Yang Lv; Bo Zhang; Wei-Wei Liu; Ji-Bo Wang
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

This paper considers a single-machine due-window assignment scheduling problem with position-dependent weights, where the weights only depend on their position in a sequence. The objective is to minimise the total weighted penalty of earliness, tardiness, due-window starting time, and due-window size of all jobs. Optimal properties of the problem are given, and then, a polynomial-time algorithm is provided to solve the problem. An extension to the problem is offered by assuming general position-dependent processing time.


---

## Body

## 1. Introduction

Conventionally, in scheduling theory, due-windows are job-dependent either if they are dictated by the customer (i.e., given constants) or they are decision variables (i.e., due-window assignment). A due-window for jobJi is defined by a due-window starting time di1 and a due-window finishing time di′, i.e., the due-window di1,di′, and the due-window size is Di=di′−di1. In the just-in-time (JIT) production methodology and scheduling theory, setting proper due-windows is challenging (see Gong et al. [1], Janiak et al. [2], and Geng et al. [3]). In the literature, three very popular due-window assignment methods are studied:Common due-window (CON-DW) assignment method (Liman et al. [4, 5]): all jobs are assigned a common due-window, i.e., all the jobs have a common due-window d1,d′, where di1=d1, di′=d′, the due-window size of all the jobs is D=d′−d1, and both d1 and D are decision variables. In the literature, most studies considered the CON-DW assignment method, e.g., Mosheiov and Sarig [6] addressed a minmax CON-DW assignment problem, the objective of which is to minimise the largest cost among earliness, tardiness, due-window starting time, and due-window size. They proved that the single-machine and two-machine flow-shop problems can be solved in polynomial time. They also proved that the cases of parallel identical machines and uniform machines are NP-hard. Yin et al. [7] considered the batch delivery scheduling problem with an assignable common due-window on a single machine. Yin et al. [8] studied the single-machine scheduling problem with CON-DW assignment and batch delivery cost. Liu et al. [9] considered the single-machine CON-DW assignment scheduling problem with deteriorating jobs. For the weighted sum of earliness, tardiness, and due-window location penalty minimization, they proposed a polynomial-time algorithm to solve the problem. Wang and Wang [10] considered the single-machine resource allocation scheduling problem with learning effect and CON-DW assignment.Slack due-window (SLK-DW) assignment method (Mosheiov and Oron [11]) is di1=pi+q1, di′=pi+q′, and Di=di′−di1=q′−q1=D, where pi is the normal processing time of job Ji and q1 and D are decision variables. Wang et al. [12] considered the single-machine SLK-DW assignment scheduling problem with deteriorating jobs and learning effect. Ji et al. [13] considered the single-machine SLK-DW assignment scheduling problem with group technology. Yin et al. [14], Yin et al. [15], and Wang et al. [16] considered SLK-DW assignment scheduling problems with resource allocation (controllable processing time). Mor and Mosheiov [17] considered SLK-DW assignment proportionate flow-shop scheduling problems.Different due-windows’ (DIF-DW) assignment method: it is assumed that the jobJi has a due-window di1,di′, where di1≥0 and di′≥0di1≤di′ denote the starting time and finishing time of the due-window, respectively. The due-window size of the job Ji is Di=di′−di1, and both di1 and Di are decision variables. Wang et al. [12] considered DIF-DW assignment scheduling problems with deteriorating jobs and learning effect.In a recent paper, Wang et al. [18] considered CON-DW and SLK-DW assignment methods with position-dependent weights, i.e., the weight does not correspond with the job but with the position in which some job is scheduled. They proved that both these due-window assignment methods with position-dependent weights can be solved in polynomial time, respectively. “The scheduling with due-window assignment has many real-world applications. For example, the due-window might reflect an assembly environment in which the components of the product should be ready within a time interval in order to avoid staging delays or a shop where several jobs constitute a single customer’s order. It is clear that a wide due-window increases the supplier’s production and delivery flexibility. However, a large due-window and delaying job completion reduce the supplier’s competitiveness and customer service level” (Yang et al. [19]). It is natural and interesting to continue the work of Wang et al. [18] but study the DIF-DW assignment scheduling problem with position-dependent weights. The contributions of this paper are given as follows: (1) the structural properties of scheduling problems are derived; (2) the total weighted penalty of earliness, tardiness, due-window starting time, and due-window size of all jobs’ minimization can be solved in polynomial time; and (3) it is further extended the model to the case with general position-dependent processing time. We refer the reader to the survey of Janiak et al. [2] on the scheduling problems with (CON-DW, SLK-DW, and DIF-DW) due-windows.The remainder of the paper is organized as follows. In Section2, we formulate the problem. Section 3 gives some results and an optimal policy for the proposed problem. An extension of the proposed problem is given in Section 4. Finally, the conclusion and future work are given.


## 2. Problem Description

A set ofn jobs N˜=J1,J2,…,Jn needs to be processed on a single machine. All the independent jobs are available at time zero, and preemption is not allowed. For a given sequence, we assume that job Ji has a due-window di1,di′, where di1≥0 (di′≥0) denote the starting time (finishing time) of the due-window, di1≤di′. The due-window size of job Ji is defined by Di=di′−di1, and di1 and Di of all jobs are decision variables. The normal processing time of job Ji is denoted by pi (i.e., the processing time without being influenced by any factor), i=1,2,…,n. For a given sequence, let Ci be the completion time of job Ji. The aim is to find the optimal starting time of the due-windows, the size of the due-windows, and the sequence of jobs δ such that the following measure is minimized:(1)Zdi1,Di,δi=∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi,where δi denotes the job scheduled in the ith position, ψi>0 (i=1,2,…,n) denote a position-dependent weight (i.e., weight ψi does not correspond with the job but with the position in which some job is scheduled), ψ0 (ψn+1) is the unit cost of dδi1 (Dδi), Lδi is the earliness-tardiness of job Jδi (i=1,2,…,n), and(2)Lδi=dδi1−Cδi,fordδi1>Cδi,0,fordδi1≤Cσi≤dδi′,Cδi−dδi′,forCδi>dδi′.Using the three-field notation (Graham et al. [20]), the problem studied here is 1DIF−DW∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi. Wang et al. [18] considered single-machine scheduling problems with common due-window (CON-DW) and slack due-window (SLK-DW) assignments. They proved that the problems 1CON−DW∑i=1nψiLδi+ψ0d1+ψn+1D and 1SLK−DW∑i=1nψiLδi+ψ0q1+ψn+1D can be solved in Onlogn time, respectively.


## 3. Main Results

Obviously, there exists an optimal sequenceδ∗ without any machine idle time between the processing of jobs, and the first job in the sequence starts at time zero.Lemma 1.
There exists an optimal sequence such thatdδi1≤dδi′≤Cδi.Proof.
We consider two cases that contradict this optimal property:Case i: ifdδi1≤Cδi<dδi′, then the total cost for job Jδi is(3)zδi=ψ0dδi1+ψn+1dδi′−dδi1.We shiftdδi′ to the left such that dδi′=Cδi, and we have(4)z˜δi=ψ0dδi1+ψn+1Cδi−dδi1<zδi.Hence, Case i is not an optimal due-window assignment.Case ii: ifCδi<dδi1≤dδi′, then the total cost for job Jδi is(5)zδi=ψidδi1−Cδi+ψ0dδi1+ψn+1dδi′−dδi1.
We shiftdδi1 and dδi′ to the left such that dδi1=dδi′=Cδi, and we have(6)z˜δi=ψ0Cδi<zδi.
Hence, Case ii is not an optimal due-window assignment.
To summarise, we havedδi1≤dδi′≤Cδi.Lemma 2.
For a given sequenceδ, the optimal due-window locations dδi1 and dδi′ for job Jδi can be obtained as follows:(1)
Whenminψi,ψ0,ψn+1=ψi, then set dδi1=dδi′=0(2)
Whenminψi,ψ0,ψn+1=ψ0, then set dδi1=dδi′=Cδi(3)
Whenminψi,ψ0,ψn+1=ψn+1, then set dδi1=0 and dδi′=CδiProof.
(1)
Whenminψi,ψ0,ψn+1=ψi and dδi1=dδi′=0, we have zδi=ψiCδiFrom Lemma1, we consider the following two cases:Case i: ifdδi1≤Cδi≤dδi′, then the total cost for job Jδi is z˜δi=ψ0dδi1+ψn+1dδi′−dδi1≥ψidδi1+ψidδi′−dδi1=ψidδi′≥ψiCδi=zδiCase ii: ifdδi1≤dδi′≤Cδi, then the total cost for job Jδi is z˜δi=ψiCδi−dδi′+ψ0dδi1+ψn+1dδi′−dδi1≥ψiCδi−dδi′+ψidδi1+ψidδi′−dδi1=ψiCδi=zδi
To summarise, ifminψi,ψ0,ψn+1=ψi, then set dδi1=dδi′=0.
Similarly, cases (2) and (3) can be proved.Lemma 3.
For a given sequenceδ, the optimal due-window locations dδi1 and dδi′ for job Jδi can be obtained as follows:(1)
Whenψi=ψ0<ψn+1, then set dδi1=dδi′=Cδj, where j=0,1,…,i(2)
Whenψi=ψn+1<ψ0, then set dδi1=0,dδi′=Cδj, where j=0,1,…,i(3)
Whenψ0=ψn+1<ψi, then set dδi1=Cδj and dδi′=Cδi, where j=0,1,…,i(4)
Whenψ0=ψn+1=ψi, then set dδi1=Cδj1 and dδi′=Cδj2, where j1=0,1,…,i and j2=j1,j1+1,…,iProof.
The proof is similar to the proof of Lemma2.Lemma 4.
The optimal sequence of the problem1DIF−DW∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi can be obtained by sequencing the jobs in a nondecreasing order of pi, i.e., the smallest processing time (SPT) first rule.Proof.
From Lemmas1–3, the objective function ∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi can be transformed into the following three cases: (1) ∑i=1nψiCδi; (2) ψ0Cδi; and (3) ψn+1Cδi. For all the three cases, it is easy to verify (by the pairwise interchange method) that sequencing the jobs in a nondecreasing order of pi is optimal.
LetA=iminψi,ψ0,ψn+1=ψi,i=1,2,…,n∪iψi=ψ0<ψn+1,i=1,2,…,n∪iψi=ψn+1<ψ0,i=1,2,…,n∪iψi=ψ0=ψn+1,i=1,2,…,n, B=iminψi,ψ0,ψn+1=ψ0,i=1,2,…,n∪iψ0=ψn+1<ψi,i=1,2,…,n, and C=iminψi,ψ0,ψn+1=ψn+1,i=1,2,…,n; then,(7)Zdi1,Di,δ=∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi=∑i∈Aψi∑j=1ipδj+∑i∈Bψi∑j=1ipδj+∑i∈Cψi∑j=1ipδj=∑i=1nψi′∑j=1ipδj=∑i=1npδi∑j=inψi′=∑i=1nλipδi,where(8)ψi′=ψi,i∈A,ψ0,i∈B,ψn+1,i∈C.
And(9)λi=∑j=inψi′.Remark 1.
Obviously,λi=∑j=inψi′ is a decreasing function on i; from Hardy et al. [21], the optimal sequence can be obtained by the SPT rule, and it is the same as Lemma 4.
From Lemmas1–4, a polynomial-time algorithm can be proposed for the 1DIF−DW∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi problem.Algorithm 1:
Step 1: obtain the optimal sequence by the SPT rule (see Lemma4)Step 2: calculate the completion time of each job under the optimal sequence, and determine the optimal due-window locationsdδi1 and dδi′ for each job according to Lemmas 2 and 3Step 3: obtain the optimal due-window size by settingDδi=dδi′−dδi1 (i=1,2,…,n), and calculate the objective function ∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi by equation (7)Theorem 1.
Algorithm1 solves the problem 1DIF−DW∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi in Onlogn time.Proof.
Optimality can be guaranteed by Lemmas1–4. In Algorithm 1, Step 1 needs Onlogn time by the SPT rule; Steps 2 and 3 can be performed in On time. Thus, the total time for Algorithm 1 is Onlogn.
In order to illustrate Algorithm1 for the problem 1DIF−DW∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi, we present the following instance.Table 1
Results of the optimal due-window location.
JobJδiJobJδidδi1dδi′Jδ1J10dδi1=0dδ1′ = 0Jδ2J1dδ21=Cδ2=29dδ2′=Cδ2=29Jδ3J5dδ31=0dδ3′ = 0Jδ4J2dδ41=Cδ4=66dδ4′=Cδ4=66Jδ5J7dδ51∈Cδii=0,1,2,3,4,5 i.e., dδ51∈0,14,29,46,66,87dδ5′=dδ51Jδ6J4dδ61=Cδ6=111dδ6′=Cδ6=111Jδ7J8dδ71=Cδ7=136dδ7′=Cδ7=136Jδ8J3dδ81=0dδ8′ = 0Jδ9J9dδ91=Cδ9=189dδ9′=Cδ9=189Jδ10J6dδ101=0dδ10′ = 0Example 1.
The data are as follows:n=10,p1=15,p2=20,p3=26,p4=24,p5=17,p6=28,p7=21,p8=25,p9=27,p10=14, ψ0=14,ψ1=7,ψ2=20,ψ3=12,ψ4=24,ψ5=14,ψ6=22,ψ7=15,ψ8=8,ψ9=19,ψ10=12,andψ11=50.
Now, we can solve the problem1DIFW∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi according to Algorithm 1 as follows:Step 1: according to Lemma4, the optimal sequence is δ∗=J10,J1,J5,J2,J7,J4,J8,J3,J9,J6Step 2: for the optimal sequenceδ∗=J10,J1,J5,J2,J7,J4,J8,J3,J9,J6, the completion time of all jobs is C10=14,C1=29,C5=46,C2=66,C7=87,C4=111,C8=136,C3=162,C9=189,andC6=217, and the optimal due-window locations dδi1 and dδi′ for each job are given in Table 1Step 3: the optimal due-window sizes areDδi=0 (i=1,2,…,10), λ1=123, λ2=116, λ3=102, λ4=90, λ5=76, λ6=62, λ7=48, λ8=34, λ9=26, and λ10=12, and the objective function is Z=∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi=∑i=1nλipδi=13202.


## 4. An Extension

In this section, the problem1DIF−DW∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi is extended to a setting of general position-dependent processing time. Let piA be the actual processing time of Ji; under the general position-dependent processing time setting, the actual processing time of Ji is piA=θi,r if it is assigned to position r, i,r=1,…,n. Thus, the input for the problem contains a matrix of n×n job-position values. Biskup [22] introduced a job-independent learning effect model in which piA=θi,r=pirα, where α≤0 is the learning index (see also Wang et al. [23]). Mosheiov and Sidney [24] introduced job-dependent learning effects, i.e., piA=θi,r=pirαi, where αi≤0 is the job-dependent learning index of job Ji. Wang et al. [25] introduced truncated job-dependent learning effects, i.e., piA=θi,r=pimaxrαi,β, where 0<β<1 is a truncation parameter. We refer the reader to the survey of Azzouz et al. [26] on scheduling problems with learning effects.From (7), we have(10)Zdi1,Di,δ=∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi=∑i=1nλiθi,r,where λi are given by (9).From (10), the optimal sequence of the problem 1DIF−DW,piA=θi,r∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi can be obtained by solving the following assignment problem:(11)Min∑i=1n∑r=1nλrθi,rxir,s.t.∑i=1nxir=1,r=1,…,n,∑r=1nxir=1,i=1,…,n,where λr,r=1,…,n, are given by (9), and(12)xir=1,if jobJiis assigned to positionr,0,otherwise.Based on the above analysis, the solution procedure of the problem1DIF−DW,piA=θi,r∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi can be summarized as follows.Algorithm 2:
Step 1: solve assignment problem (11) to obtain the optimal sequenceStep 2: calculate the completion time of each job under the optimal sequence, and determine the optimal due-window locationsdδi1 and dδi′ for each job according to Lemmas 2 and 3Step 3: obtain the optimal due-window size by settingDδi=dδi′−dδi1 (i=1,2,…,n), and calculate the objective function ∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi by assignment problem (11)Theorem 2.
Algorithm2 solves the problem 1DIF−DW,piA=θi,r∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi in On3 time.Proof.
Optimality is guaranteed by Lemmas1–3 and the above analysis. In Algorithm 2, Step 1 needs On3 time by the SPT rule; Steps 2 and 3 can be performed in On time. Thus, the total time for Algorithm 2 is On3. In order to illustrate Algorithm 2 for the problem 1DIF−DW,piA=θi,r∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi, we present the following instance.Example 2.
The data are as follows:n=8, ψ0=14,ψ1=8,ψ2=18,ψ3=12,ψ4=24,ψ5=10,ψ6=20,ψ7=15,ψ8=7,andψ9=21. The job-dependent processing time is given in Table 2.


## 5. Conclusion and Future Work

This study addressed the due-window (DIF-DW) assignment scheduling problem under the consideration of position-dependent weights. The goal is to determine the optimal sequence, the optimal due-window location, and size such that the total penalty (including the earliness, tardiness, due-window starting time, and due-window size of all jobs) is minimized. It was proved that the problem can be solved in polynomial time. The proposed model was also extended to the general position-dependent processing time, and the polynomial-time solution was provided. Further extensions are considering the above problems in the setting ofm-machine flow-shop and m-identical (unrelated) parallel machines (Hsu and Liao [27]), studying the scheduling with two-agent resource-dependent release time (Liu and Duan [28]), or investigating scheduling with rate-modifying activity under deterioration effect (Xue and Zhang [29]).Table 2
Date of Example2.
Jir12345678J1671156221321J2814781117126J39111332710128J41722191059137J5168151411171314J6181731148231520J7151218198162113J81317241618161315Step 1: by (9), we have λ1=93, λ2=85, λ3=71, λ4=59, λ5=45, λ6=35, λ7=21, and λ8=7. According to assignment problem (11), the optimal sequence is δ∗=J3,J5,J2,J1,J6,J4,J8,J7.Step 2: for the optimal sequenceδ∗=J3,J5,J2,J1,J6,J4,J8,J7, the completion time of all jobs is C3=9,C5=17,C2=24,C1=29,C6=37,C4=46,C8=59,andC7=72, and the optimal due-window locations dδi1 and dδi′ for each job are given in Table 3.Step 3: the optimal due-window sizes areDδi=0 (i=1,2,…,8), and the objective function is Z=∑i=1nψiLδi+ψ0dδi1+ψn+1Dδi=3348.Table 3
Results of the optimal due-window location.
JobJδiJobJδidδi1dδi′Jδ1J3dδ11=0dδ1′ = 0Jδ2J5dδ21=Cδ2=17dδ2′=Cδ2=17Jδ3J2dδ31=0dδ3′ = 0Jδ4J1dδ41=Cδ4=29dδ4′=Cδ4=29Jδ5J6dδ51=0dδ5′=0Jδ6J4dδ61=Cδ6=46dδ6′=Cδ6=46Jδ7J8dδ71=Cδ7=59dδ7′=Cδ7=59Jδ8J7dδ81=0dδ8′ = 0



---

*Source: 9746538-2020-07-22.xml*