# Study on Single-Machine Group Scheduling with Due-Window Assignment and Position-Dependent Weights

Authors: Weiguo Liu; Xuyin Wang; Xiaoxiao Wang; Peizhen Zhao
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This article considers a single-machine group scheduling problem with due-window assignment, where the jobs are classified into groups and the jobs in the same group must be processed in succession. The goal is to minimize the weighted sum of lateness and due-window assignment cost, where the weights depend on the position in which a job is scheduled (i.e., position-dependent weights). For the common, slack, and different due-window assignment methods, we prove that the problem can be solved polynomially, i.e., inONlogN time, where N is the number of jobs.


---

## Body

## 1. Introduction

Group scheduling (GS) is an approach, which schedules jobs with similar characteristics close together and reduces tooling changeovers and in-process inventories to improve efficiency in high-volume production (Neufeld et al. [1], Lu et al. [2], Yin et al. [3], and Wang and Liu [4]). Wang and Wang [5] studied the single-machine group scheduling problem with ready times and time-dependent processing times. Under the case of the group setup times and job processing times are proportional linear deterioration functions, they proved that the makespan minimization problem can be solved in polynomial time. He and Sun [6] considered the single-machine group scheduling problem with general deteriorating jobs and learning effects. They proved that the makespan and the sum of completion times minimizations remain solvable in polynomial time. Lu et al. [7] considered the single-machine group scheduling with learning effects and resource allocation. For the makespan minimization subject to limited resource availability, they proved that the problem can be solved in polynomial time under some special cases. For the general case, they proposed heuristic and branch-and-bound algorithms. Zhang et al. [8] studied the single-machine group scheduling with position-dependent processing times. For the makespan and the total completion time minimizations, they proved that the problem can be solved in polynomial time. Liu et al. [9] considered the single-machine group scheduling with the proportional deterioration effect. For the makespan minimization with release times, they proposed heuristic and branch-and-bound algorithms. Huang [10] studied the single-machine group problem with proportional deterioration effects, where the total weighted completion time minimization is the primary criterion and the maximum cost minimization is the secondary criterion. They proved that the problem remains solvable in polynomial time. Wang and Liang [11] and Liang et al. [12] considered the single-machine group scheduling problem with deteriorating jobs and resource allocation. Qin et al. [13] considered the flowshop group scheduling problem with learning effects. For some regular objectives (including the makespan, total completion time, total weighted completion time, and maximum lateness), they proposed heuristics and metaheuristics.On the other hand, due to the increasing interest in the just-in-time (JIT) system, the problem of the due-date assignment has been closely focused on by scholars (Yin et al. [14], Wang et al. [15], and Shabtay [16]). However, under the group technology, there are relatively few studies on the problem of the assignment of jobs. Li et al. [17] studied the single-machine group scheduling with due-date assignment. For the common (CON), slack (SLK), and different (DIF) due-date assignment methods, they proved that the nonregular objective minimization can be solved in polynomial time. Sun et al. [18], Lv et al. [19], and Wang et al. [20] considered single-machine group scheduling problems with resource allocation and learning effect. Under slack due-date assignment and the linear and convex resource consumption functions, Sun et al. [18] gave some results. Lv et al. [19] showed by two counter examples that the results of Sun et al. [18] were incorrect. Under the convex resource allocation, for some special cases, Wang et al. [20] proved that the problem can be solved in polynomial time. For the general case of the problem, Wang et al. [20] proposed the heuristic, tabu search, and branch-and-bound algorithms.Recently, Wang et al. [21] considered the single-machine group scheduling problem with due-date assignment and positional-dependent weights. For the CON, SLK, and DIF due-date assignments, they proved that the problem can be solved in polynomial time. The importance of due-window assignment scheduling is widely recognized for the production company [22–27]. Ji et al. [28] investigated the single-machine group scheduling with slack due-window assignment. They proved that the nonregular objective minimization (including the earliness, tardiness, due-window starting time, and due-window size) can be solved in polynomial time. Li and Zhao [29] studied the single-machine group scheduling problem with multiple due-windows assignment. The objective is to determine an optimal sequence for both groups and jobs, and optimal due-windows such that the total cost of earliness, tardiness, and due-windows assignment is minimized. They showed that the problem can be solved in polynomial time. “The application of problems with positional-dependent weights can be found in many practical settings, such as the busyness of production services often changes with time. The weight of the processing queue can be increased when the production efficiency of a certain period of time needs to be improved. For example, in the Didi taxi dispatching (a similar mode to Uber), orders placed in the morning offer a higher bonus to the driver, which can effectively improve customer satisfaction in these locations by better meeting the needs of customers going to work in the morning [30].” In this article, the results of Wang et al. [21] are extended to the case of the due-window assignment with position-dependent weights (Wang et al. [24], Wang et al. [25], and Wang et al. [31]). In other words, this article studies the group scheduling with the due-window assignment and position-dependent weights, i.e., our model is more general and covers the results of Wang et al. [21], Wang et al. [24], and Wang et al. [25].The rest of the study is organized as follows: in Section2, the model and problem is formulated. In Section 3, we present several results of the optimal solution. In Section 4, some examples are given. In Section 5, the conclusions are summarized.


## 2. Problem Formulation

The notations used throughout this article are tabulated in Table1.Table 1
List of notations.
NotationsDefinitionsNNumber of jobsmNumber of groupsTll=1,2,…,nIndex of jobG˜hh=1,2,…,mIndex of groupnhNumber of groupG˜hTh,lJobTl of group G˜hshSetup time of groupG˜hph,lProcessing time of jobTh,ldh,l′,dh,l″Due-window of jobTh,ldh,l′Due-window starting time of jobTh,ldh,l″Due-window finishing time of jobTh,lDh,l=dh,l″−dh,l′Due-window size of jobTh,lCh,lCompletion time of jobTh,ldh′dh″Starting (finishing) time of common due-window in groupG˜hqh′qh″Common flow allowance of slack due-window in groupG˜hξAn optimal schedule of jobsLh,lLateness penalty of jobTh,lϑh,ll=1,2,…,nhWeight of thelth position in group G˜hϑh,0Unit cost ofdh,l′ϑh,nh+1Unit cost ofDh,lCONDWCommon due-window assignmentSLKDWSlack due-window assignmentDIFDWDifferent due-window assignmentlJob scheduled in thelth positionΦh,lWeight cost oflth position in group G˜hΩhWeight factor of groupG˜hThere areN jobs ready to be processed on a single machine, and all the jobs are divided (grouped) into m groups G˜1,G˜2,…,G˜m in advance. All the jobs are available at time 0 and job preemption is not allowed. Each group G˜h has nh jobs, i.e., Th,1,Th,2,…,Th,nh, where Th,l denotes the job Tl of group G˜h and n1+n2+⋯+nm=Nh=1,2,…,m,l=1,2,…,nh. The jobs in the same group must be processed in succession and do not need setup times, and each group G˜h requires an independent setup time sh. Each job Th,l has a processing time ph,l and a due-window dh,l′,dh,l″, where dh,l′≤dh,l″, dh,l′dh,l″ is the due-window starting (finishing) time of job Th,l in group G˜h, Dh,l=dh,l″−dh,l′ is due-window size, and both dh,l′ and dh,l″ are decision variables. The due-window is assignable according to the following three methods:(1)
The common due-window (CONDW) assignment: all jobs in groupG˜h are assigned the same due-window, i.e., dh,l′=dh′ and dh,l″=dh″h=1,2,…,m,l=1,2,…,nh(2)
The slack due-window (SLKDW) assignment:dh,l′=ph,l+qh′ and dh,l″=ph,l+qh″h=1,2,…,m,l=1,2,…,nh(3)
The different due-window (DIFDW) assignment: the due-windowdh,l′,dh,l″ for all jobs of group G˜h is assigned with no restrictions h=1,2,…,m,l=1,2,…,nhLetCh,l be the completion time of job Th,l. The objective of the study is to determine dh,l′ and dh,l″ (i.e., for CONDW, determine dh′ and dh″; for SLKDW, determine qh′ and qh″; and for DIFDW, determine dh,l′, dh,l″ of all jobs) and an optimal schedule ξ to minimize a cost function that comprises lateness (earliness-tardiness) penalties, due-window starting time, and due-window size costs, i.e.,(1)Fξ,dh,l′,dh,l″=∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l,where ϑh,l is the weight of the lth position in group G˜h (i.e., position-dependent weights, Wang et al. [24], Wang et al. [25], and Wang et al. [31]), ξh,l is the job scheduled in the lth position in group G˜h, ϑh,0 denotes the unit cost of dh,l′, and ϑh,nh+1 denotes the unit cost of Dh,l, and the lateness (earliness-tardiness) of job Tξh,l is(2)Lξh,l=dξh,l′−Cξh,l,fordξh,l′>Cξh,l,0,fordξh,l′≤Cξh,l≤dξh,l″,Cξh,l−dξh,l″,forCξh,l>dξh,l″.By using the three-field notation (Graham etv al. [32]), the problem can be denoted by(3)1GS,A∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l,where A∈CONDW,SLKDW,DIFDW.Procurement sharing of sustainable and regular products: self-competition and sharing incentives.


## 3. Preliminary Results

It is clear that there exists an optimal schedule that starts at time 0 and contains 0 machine idle times.


### 3.1. CONDW Method

Lemma 1.
For a given scheduleξ, the optimal values dh′ and dh″ coincide with the job completion times of group G˜hh=1,2,…,m.Proof.
For the given scheduleξ, under group G˜h, we assume that(4)dh′=Cξh,gh=Sh+sh+∑l=1ghph,l,dh″=Cξh,kh=Sh+sh+∑l=1khph,l,where Sh denotes the starting time of group G˜h, gh and kh mean the ghth and khth positions of group G˜h, respectively gh≤kh. Consider that there exists an optimal schedule without the stated property, i.e., dh′=Sh+sh+∑θ=1ghph,θ+x and dh″=Sh+sh+∑θ=1khph,θ+y, where 0≤x≤ph,gh+1 and 0≤y≤ph,kh+1.
For groupG˜h, the total cost is(5)Fhx,y=∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l=∑l=1ghϑh,ldh′−Cξh,l+∑l=kh+1nhϑh,lCξh,l−dh″+nhϑh,0dh′+nhϑh,nh+1dh″−dh′=∑l=1ghϑh,l∑θ=1ghph,θ+x−∑θ=1lph,θ+∑l=kh+1nhϑh,l∑θ=1lph,θ−∑θ=1khph,θ−y+nhϑh,0Sh+sh+∑θ=1ghph,θ+x+nhϑh,nh+1∑θ=1khph,θ+y−∑θ=1ghph,θ−x=∑l=1ghϑh,l∑θ=l+1ghph,θ+x+∑l=kh+1nhϑh,l∑θ=kh+1lph,θ−y+nhϑh,0Sh+sh+∑θ=1ghph,θ+x+nhϑh,nh+1∑θ=gh+1khph,θ+y−x=∑l=1ghϑh,l∑θ=l+1ghph,θ+∑l=kh+1nhϑh,l∑θ=kh+1lph,θ+nhϑh,0Sh+sh+∑θ=1ghph,θ+nhϑh,nh+1∑θ=gh+1khph,θ+∑l=1ghϑh,l+nhϑh,0−nhϑh,nh+1x+nhϑh,nh+1−∑l=kh+1nhϑh,ly.
From (5), we see that the term Fhx,y is a linear function of x and y; hence, we can either decrease x and y to 0 or increase them to ph,gh+1 and ph,kh+1, respectively, to obtain a lower cost. This completes the proof.Lemma 2.
For a given scheduleξ, the optimal values dh′=Sh+sh+∑l=1ghph,l (where ∑l=0gh−1ϑh,l≤ϑh,nh+1≤∑l=0ghϑh,l) and dh″=Sh+sh+∑l=1khph,l (where ∑l=kh+1nhϑh,l≤ϑh,nh+1≤∑l=khnhϑh,l).Proof.
By the technique of small perturbations, the result can be easily obtained.
For a given scheduleξ, the total cost of all the jobs within G˜hh=1,…,m is(6)Fhξ,dh′,dh″=∑l=1ghϑh,l∑θ=l+1ghph,θ+∑l=kh+1nhϑh,l∑θ=kh+1lph,θ+nhϑh,0Sh+sh+∑θ=1ghph,θ+nhϑh,nh+1∑θ=gh+1khph,θ=∑l=1nhΦh,lph,l+nhϑh,0Sh+sh,where(7)Φh,l=nhϑh,0+∑θ=1l−1ϑh,θ,l=1,2,…,gh,nhϑh,nh+1,l=gh+1,gh+2,…,kh,∑θ=lnhϑh,θ,l=kh+1,kh+2,…,nh.
From (6) and HLP rule (Hardy et al. [33], i.e., the sum of products ∑j=1nxjyj is minimized if the sequence x1,x2,…,xn is ordered nondecreasingly and the sequence y1,y2,…,yn is ordered nonincreasingly, or vice versa, and it is maximized if the sequences are ordered in the same way), minimizing ∑l=1nhΦh,lph,l can be obtained by arranging the elements of the Φh,l and ph,l vectors in opposite orders. The term nhϑh,0Sh+sh is only dependent on the starting time of the group G˜hh=1,…,m.Lemma 3.
For the problem1GS,CONDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, the optimal group sequence can be obtained by arranging the groups in a nondecreasing order of Ωhsh+∑l=1nhph,l/nhϑh,0,h=1,2,…,m.Proof.
By contradiction, letξ=π,G˜f,G˜h,ρ be an optimal schedule, such that(8)sf+∑l=1nfpf,lnfϑf,0>sh+∑l=1nhph,lnhϑh,0,where π and ρ are the partial sequences. We now perform an adjacent pairwise interchange of G˜f and G˜h, leaving all other groups in their original positions, to derive a new schedule ξ′=π,Gh,Gf,ρ. Let B denote the completion time of the last job in π, and it follows that(9)Shξ=B+sf+∑l=1nfpf,l,Sfξ′=B+sh+∑l=1nhph,l,Fξ−Fξ′=nfϑf,0B+sf+nhϑh,0B+sf+∑l=1nfpf,l+sh−nhϑh,0B+sh−nfϑf,0B+sh+∑l=1nhph,l+sf=nhϑh,0sf+∑l=1nfpf,l−nfϑf,0sh+∑l=1nhph,l>0.
This contradicts the optimality ofξ and proves that groups are arranged in a nondecreasing order of Ωh=sh+∑l=1nhph,l/nhϑh,0.
Based on the above analysis, the following algorithm can be proposed to solve the problem1GS,CONDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l.Theorem 1.
The problem1GS,CONDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l can be solved by Algorithm 1 in ONlogN time.Algorithm 1:
Step 1: calculategh and kh by Lemma 2, h=1,2,…,mStep 2: arrange the jobs of each group by the HLP rule (vectorsΦh,l (7) and ph,l)Step 3: by Lemma3, arrange the groups in a nondecreasing order of Ωh=sh+∑l=1nhph,l/nhϑh,0h=1,2,…,mStep 4: according to Lemma2, calculate dh′ and dh″h=1,2,…,mProof.
The correctness of Algorithm1 follows Lemmas 1–3 and the above analysis. Steps 1 and 4 need Om time. Step 2 needs O∑h=1mnhlognh≤ONlogN time. Step 3 needs Omlogm≤ONlogN time m<N. Thus, the total time of Algorithm 1 is ONlogN.


### 3.2. SLKDW Method

Similar to Subsection3.1, we have the following.Lemma 4.
For a given scheduleξ, the optimal values qh′ and qh″ coincide with the job completion times of group G˜hh=1,2,…,m.Lemma 5.
For a given scheduleξ, the optimal values qh′=Sh+sh+∑l=1gh−1ph,l (where ∑l=0gh−1ϑh,l≤ϑh,nh+1≤∑l=0ghϑh,l) and qh″=Sh+sh+∑l=1kh−1ph,l (where ∑l=kh+1nhϑh,l≤ϑh,nh+1≤∑l=khnhϑh,l).
For a given scheduleξ, the total cost of all the jobs within G˜hh=1,…,m is(10)Fhξ,qh′,qh″=∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l=∑l=1ghϑh,ldξh,l′−Cξh,l+∑l=kh+1nhϑh,lCξh,l−dξh,l′′+ϑh,0∑l=1nhdξh,l′+ϑh,nh+1∑l=1nhdξh,l′′−dξh,l′=∑l=1ghϑh,lph,l+qh′−Cξh,l+∑l=kh+1nhϑh,lCξh,l−ph,l−qh″+ϑh,0∑l=1nhph,l+qh′+nhϑh,nh+1qh″−qh′=∑l=1ghϑh,l∑θ=1gh−1ph,θ−∑θ=1l−1ph,θ+∑l=kh+1nhϑh,l∑θ=1l−1ph,θ−∑θ=1kh−1ph,θ+ϑh,0∑l=1nhph,l+nhϑh,0Sh+sh+∑θ=1gh−1ph,θ+nhϑh,nh+1∑θ=1kh−1ph,θ−∑θ=1gh−1ph,θ=∑l=1ghϑh,l∑θ=lgh−1ph,θ+∑l=kh+1nhϑh,l∑θ=khl−1ph,θ+ϑh,0∑l=1nhph,l+nhϑh,0Sh+sh+∑θ=1gh−1ph,θ+nhϑh,nh+1∑θ=ghkh−1ph,θ=∑l=1nhΦh,lph,l+nhϑh,0Sh+sh,where(11)Φh,l=nh+1ϑh,0+∑θ=1lϑh,θ,l=1,2,…,gh−1,ϑh,0+nhϑh,nh+1,l=gh,gh+1,…,kh−1,ϑh,0+∑θ=l+1nhϑh,θ,l=kh,kh+1,…,nh−1ϑh,0,l=nh.
From (10) and Subsection 3.1, the optimal schedule of each group can be obtained by the HLP rule.Lemma 6.
For the problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, the optimal group sequence can be obtained by arranging the groups in a nondecreasing order of Ωh=sh+∑l=1nhph,l/nhϑh,0,h=1,2,…,m.
Based on the above analysis, the following algorithm can be proposed to solve the problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l.Theorem 2.
The problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l can be solved by Algorithm 2 in ONlogN time.Algorithm 2:
Step 1: calculategh and kh by Lemma 5, h=1,2,…,mStep 2: arrange the jobs of each group by the HLP rule (vectorsΦh,l (11) and ph,l)Step 3: by Lemma6, arrange the groups in a nondecreasing order of Ωh=sh+∑l=1nhph,l/nhϑh,0,h=1,2,…,mStep 4: according to Lemma5, calculate qh′ and qh″h=1,2,…,m


### 3.3. DIFDW Method

Lemma 7.
For the DIFDW method, there exists an optimal sequence, such thatdh,l′≤dh,l′≤Ch,l.Proof.
Similar to the proof of Wang et al. [24].Lemma 8.
For the DIFDW method, letξ be a given sequence, and the optimal dξh,j′ and dξh,j″ of job Jξh,j can be given as follows:(1)
Ifminϑh,0,ϑh,l,ϑh,nh+1=ϑh,0, then dξh,j′=dξh,j″=Cξh,j(2)
Ifminϑh,0,ϑh,l,ϑh,nh+1=ϑh,l, then dξh,j′=dξh,j″=0(3)
Ifminϑh,0,ϑh,l,ϑh,nh+1=ϑh,nh+1, then dξh,j′=0,dξh,j″=Cξh,jProof.
Similar to the proof of Wang et al. [24].
From Lemma8, the cost for job Jξh,l is(12)Fξh,l=ψh,lCξh,l,where ψh,l=minϑh,0,ϑh,l,ϑh,nh+1. The total cost of all the jobs within G˜h is(13)Fhξ,dξh,j′,dξh,j″=∑la=1nhψh,lCξh,l=∑l=1nhΦh,lph,l+Sh+sh∑l=1nhψh,l,where(14)Φh,l=nh−l+1ψh,l.
From (13) and Subsection 3.1, the optimal schedule of each group can be obtained by the HLP rule.Lemma 9.
For the problem1GS,DIFDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, the optimal group sequence can be obtained by arranging the groups in a nondecreasing order of Ωh=sh+∑l=1nhph,l/∑l=1nhψh,l,h=1,2,…,m.
Based on the above analysis, the following algorithm can be proposed to solve the problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l.Theorem 3.
The problem1GS,DIFDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l can be solved by Algorithm 3 in ONlogN time.Algorithm 3:
Step 1: arrange the jobs of each group by the HLP rule (vectorsΦh,l (14) and ph,l)Step 2: arrange the groups in a nondecreasing order ofΩh=sh+∑l=1nhph,l/∑l=1nhψh,l,h=1,2,…,mStep 3: according to Lemma8, calculate dξh,j′, dξh,j″, h=1,2,…,m, and j=1,2,…,nh


## 3.1. CONDW Method

Lemma 1.
For a given scheduleξ, the optimal values dh′ and dh″ coincide with the job completion times of group G˜hh=1,2,…,m.Proof.
For the given scheduleξ, under group G˜h, we assume that(4)dh′=Cξh,gh=Sh+sh+∑l=1ghph,l,dh″=Cξh,kh=Sh+sh+∑l=1khph,l,where Sh denotes the starting time of group G˜h, gh and kh mean the ghth and khth positions of group G˜h, respectively gh≤kh. Consider that there exists an optimal schedule without the stated property, i.e., dh′=Sh+sh+∑θ=1ghph,θ+x and dh″=Sh+sh+∑θ=1khph,θ+y, where 0≤x≤ph,gh+1 and 0≤y≤ph,kh+1.
For groupG˜h, the total cost is(5)Fhx,y=∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l=∑l=1ghϑh,ldh′−Cξh,l+∑l=kh+1nhϑh,lCξh,l−dh″+nhϑh,0dh′+nhϑh,nh+1dh″−dh′=∑l=1ghϑh,l∑θ=1ghph,θ+x−∑θ=1lph,θ+∑l=kh+1nhϑh,l∑θ=1lph,θ−∑θ=1khph,θ−y+nhϑh,0Sh+sh+∑θ=1ghph,θ+x+nhϑh,nh+1∑θ=1khph,θ+y−∑θ=1ghph,θ−x=∑l=1ghϑh,l∑θ=l+1ghph,θ+x+∑l=kh+1nhϑh,l∑θ=kh+1lph,θ−y+nhϑh,0Sh+sh+∑θ=1ghph,θ+x+nhϑh,nh+1∑θ=gh+1khph,θ+y−x=∑l=1ghϑh,l∑θ=l+1ghph,θ+∑l=kh+1nhϑh,l∑θ=kh+1lph,θ+nhϑh,0Sh+sh+∑θ=1ghph,θ+nhϑh,nh+1∑θ=gh+1khph,θ+∑l=1ghϑh,l+nhϑh,0−nhϑh,nh+1x+nhϑh,nh+1−∑l=kh+1nhϑh,ly.
From (5), we see that the term Fhx,y is a linear function of x and y; hence, we can either decrease x and y to 0 or increase them to ph,gh+1 and ph,kh+1, respectively, to obtain a lower cost. This completes the proof.Lemma 2.
For a given scheduleξ, the optimal values dh′=Sh+sh+∑l=1ghph,l (where ∑l=0gh−1ϑh,l≤ϑh,nh+1≤∑l=0ghϑh,l) and dh″=Sh+sh+∑l=1khph,l (where ∑l=kh+1nhϑh,l≤ϑh,nh+1≤∑l=khnhϑh,l).Proof.
By the technique of small perturbations, the result can be easily obtained.
For a given scheduleξ, the total cost of all the jobs within G˜hh=1,…,m is(6)Fhξ,dh′,dh″=∑l=1ghϑh,l∑θ=l+1ghph,θ+∑l=kh+1nhϑh,l∑θ=kh+1lph,θ+nhϑh,0Sh+sh+∑θ=1ghph,θ+nhϑh,nh+1∑θ=gh+1khph,θ=∑l=1nhΦh,lph,l+nhϑh,0Sh+sh,where(7)Φh,l=nhϑh,0+∑θ=1l−1ϑh,θ,l=1,2,…,gh,nhϑh,nh+1,l=gh+1,gh+2,…,kh,∑θ=lnhϑh,θ,l=kh+1,kh+2,…,nh.
From (6) and HLP rule (Hardy et al. [33], i.e., the sum of products ∑j=1nxjyj is minimized if the sequence x1,x2,…,xn is ordered nondecreasingly and the sequence y1,y2,…,yn is ordered nonincreasingly, or vice versa, and it is maximized if the sequences are ordered in the same way), minimizing ∑l=1nhΦh,lph,l can be obtained by arranging the elements of the Φh,l and ph,l vectors in opposite orders. The term nhϑh,0Sh+sh is only dependent on the starting time of the group G˜hh=1,…,m.Lemma 3.
For the problem1GS,CONDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, the optimal group sequence can be obtained by arranging the groups in a nondecreasing order of Ωhsh+∑l=1nhph,l/nhϑh,0,h=1,2,…,m.Proof.
By contradiction, letξ=π,G˜f,G˜h,ρ be an optimal schedule, such that(8)sf+∑l=1nfpf,lnfϑf,0>sh+∑l=1nhph,lnhϑh,0,where π and ρ are the partial sequences. We now perform an adjacent pairwise interchange of G˜f and G˜h, leaving all other groups in their original positions, to derive a new schedule ξ′=π,Gh,Gf,ρ. Let B denote the completion time of the last job in π, and it follows that(9)Shξ=B+sf+∑l=1nfpf,l,Sfξ′=B+sh+∑l=1nhph,l,Fξ−Fξ′=nfϑf,0B+sf+nhϑh,0B+sf+∑l=1nfpf,l+sh−nhϑh,0B+sh−nfϑf,0B+sh+∑l=1nhph,l+sf=nhϑh,0sf+∑l=1nfpf,l−nfϑf,0sh+∑l=1nhph,l>0.
This contradicts the optimality ofξ and proves that groups are arranged in a nondecreasing order of Ωh=sh+∑l=1nhph,l/nhϑh,0.
Based on the above analysis, the following algorithm can be proposed to solve the problem1GS,CONDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l.Theorem 1.
The problem1GS,CONDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l can be solved by Algorithm 1 in ONlogN time.Algorithm 1:
Step 1: calculategh and kh by Lemma 2, h=1,2,…,mStep 2: arrange the jobs of each group by the HLP rule (vectorsΦh,l (7) and ph,l)Step 3: by Lemma3, arrange the groups in a nondecreasing order of Ωh=sh+∑l=1nhph,l/nhϑh,0h=1,2,…,mStep 4: according to Lemma2, calculate dh′ and dh″h=1,2,…,mProof.
The correctness of Algorithm1 follows Lemmas 1–3 and the above analysis. Steps 1 and 4 need Om time. Step 2 needs O∑h=1mnhlognh≤ONlogN time. Step 3 needs Omlogm≤ONlogN time m<N. Thus, the total time of Algorithm 1 is ONlogN.


## 3.2. SLKDW Method

Similar to Subsection3.1, we have the following.Lemma 4.
For a given scheduleξ, the optimal values qh′ and qh″ coincide with the job completion times of group G˜hh=1,2,…,m.Lemma 5.
For a given scheduleξ, the optimal values qh′=Sh+sh+∑l=1gh−1ph,l (where ∑l=0gh−1ϑh,l≤ϑh,nh+1≤∑l=0ghϑh,l) and qh″=Sh+sh+∑l=1kh−1ph,l (where ∑l=kh+1nhϑh,l≤ϑh,nh+1≤∑l=khnhϑh,l).
For a given scheduleξ, the total cost of all the jobs within G˜hh=1,…,m is(10)Fhξ,qh′,qh″=∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l=∑l=1ghϑh,ldξh,l′−Cξh,l+∑l=kh+1nhϑh,lCξh,l−dξh,l′′+ϑh,0∑l=1nhdξh,l′+ϑh,nh+1∑l=1nhdξh,l′′−dξh,l′=∑l=1ghϑh,lph,l+qh′−Cξh,l+∑l=kh+1nhϑh,lCξh,l−ph,l−qh″+ϑh,0∑l=1nhph,l+qh′+nhϑh,nh+1qh″−qh′=∑l=1ghϑh,l∑θ=1gh−1ph,θ−∑θ=1l−1ph,θ+∑l=kh+1nhϑh,l∑θ=1l−1ph,θ−∑θ=1kh−1ph,θ+ϑh,0∑l=1nhph,l+nhϑh,0Sh+sh+∑θ=1gh−1ph,θ+nhϑh,nh+1∑θ=1kh−1ph,θ−∑θ=1gh−1ph,θ=∑l=1ghϑh,l∑θ=lgh−1ph,θ+∑l=kh+1nhϑh,l∑θ=khl−1ph,θ+ϑh,0∑l=1nhph,l+nhϑh,0Sh+sh+∑θ=1gh−1ph,θ+nhϑh,nh+1∑θ=ghkh−1ph,θ=∑l=1nhΦh,lph,l+nhϑh,0Sh+sh,where(11)Φh,l=nh+1ϑh,0+∑θ=1lϑh,θ,l=1,2,…,gh−1,ϑh,0+nhϑh,nh+1,l=gh,gh+1,…,kh−1,ϑh,0+∑θ=l+1nhϑh,θ,l=kh,kh+1,…,nh−1ϑh,0,l=nh.
From (10) and Subsection 3.1, the optimal schedule of each group can be obtained by the HLP rule.Lemma 6.
For the problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, the optimal group sequence can be obtained by arranging the groups in a nondecreasing order of Ωh=sh+∑l=1nhph,l/nhϑh,0,h=1,2,…,m.
Based on the above analysis, the following algorithm can be proposed to solve the problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l.Theorem 2.
The problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l can be solved by Algorithm 2 in ONlogN time.Algorithm 2:
Step 1: calculategh and kh by Lemma 5, h=1,2,…,mStep 2: arrange the jobs of each group by the HLP rule (vectorsΦh,l (11) and ph,l)Step 3: by Lemma6, arrange the groups in a nondecreasing order of Ωh=sh+∑l=1nhph,l/nhϑh,0,h=1,2,…,mStep 4: according to Lemma5, calculate qh′ and qh″h=1,2,…,m


## 3.3. DIFDW Method

Lemma 7.
For the DIFDW method, there exists an optimal sequence, such thatdh,l′≤dh,l′≤Ch,l.Proof.
Similar to the proof of Wang et al. [24].Lemma 8.
For the DIFDW method, letξ be a given sequence, and the optimal dξh,j′ and dξh,j″ of job Jξh,j can be given as follows:(1)
Ifminϑh,0,ϑh,l,ϑh,nh+1=ϑh,0, then dξh,j′=dξh,j″=Cξh,j(2)
Ifminϑh,0,ϑh,l,ϑh,nh+1=ϑh,l, then dξh,j′=dξh,j″=0(3)
Ifminϑh,0,ϑh,l,ϑh,nh+1=ϑh,nh+1, then dξh,j′=0,dξh,j″=Cξh,jProof.
Similar to the proof of Wang et al. [24].
From Lemma8, the cost for job Jξh,l is(12)Fξh,l=ψh,lCξh,l,where ψh,l=minϑh,0,ϑh,l,ϑh,nh+1. The total cost of all the jobs within G˜h is(13)Fhξ,dξh,j′,dξh,j″=∑la=1nhψh,lCξh,l=∑l=1nhΦh,lph,l+Sh+sh∑l=1nhψh,l,where(14)Φh,l=nh−l+1ψh,l.
From (13) and Subsection 3.1, the optimal schedule of each group can be obtained by the HLP rule.Lemma 9.
For the problem1GS,DIFDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, the optimal group sequence can be obtained by arranging the groups in a nondecreasing order of Ωh=sh+∑l=1nhph,l/∑l=1nhψh,l,h=1,2,…,m.
Based on the above analysis, the following algorithm can be proposed to solve the problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l.Theorem 3.
The problem1GS,DIFDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l can be solved by Algorithm 3 in ONlogN time.Algorithm 3:
Step 1: arrange the jobs of each group by the HLP rule (vectorsΦh,l (14) and ph,l)Step 2: arrange the groups in a nondecreasing order ofΩh=sh+∑l=1nhph,l/∑l=1nhψh,l,h=1,2,…,mStep 3: according to Lemma8, calculate dξh,j′, dξh,j″, h=1,2,…,m, and j=1,2,…,nh


## 4. Number Examples

Example 1.
For the problem1GS,CONDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, consider n=13,m=3, n1=4,n2=4,n3=5, G˜1: s1=5, p1,1=4, p1,2=3, p1,3=6, p1,4=2, ϑ1,0=2, ϑ1,1=3, ϑ1,2=5, ϑ1,3=4, ϑ1,4=6, ϑ1,5=7; G˜2: s2=3, p2,1=8, p2,2=2, p2,3=7, p2,4=5, ϑ2,0=6, ϑ2,1=7, ϑ2,2=4, ϑ2,3=5, ϑ2,4=2, ϑ2,5=8; G˜3: s3=6, p3,1=14, p3,2=7, p3,3=5, p3,4=10, p3,5=9, ϑ3,0=3, ϑ3,1=6, ϑ3,2=7, ϑ3,3=5, ϑ3,4=8, ϑ3,5=2, and ϑ3,6=12.
From Algorithm1, we have the following.Step 1:g1=2, k1=3, g2=1, k2=2, g3=2, and k3=3Step 2:Φ1,1=8, Φ1,2=11, Φ1,3=28, Φ1,4=6; Φ2,1=24, Φ2,2=32, Φ2,3=7, Φ2,4=2; Φ3,1=15, Φ3,2=21, Φ3,3=60, Φ3,4=10, and Φ3,5=2. The optimal sequence of jobs within each group is G˜1: T1,l⟶T1,2⟶T1,4⟶T1,3; G˜2: T2,4⟶T2,2⟶T2,3⟶T2,1; and G˜3: T3,5⟶T3,2⟶T3,3⟶T3,4⟶T3,1.Step 3:Ω1=5/2, Ω2=25/24, and Ω3=51/15; the optimal group sequence is G˜2⟶G˜1⟶G˜3.Step 4:d2′=8, d2″=10; d1′=37, d1″=39; d3′=67, and d3″=72Example 2.
For the problem1GS,SLKDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, the data are the same as in Example 1.
From Algorithm2, we have the following.Step 1:g1=2, k1=3, g2=1, k2=2, g3=2, and k3=3Step 2:Φ1,1=13, Φ1,2=30, Φ1,3=8, Φ1,4=2; Φ2,1=38, Φ2,2=13, Φ2,3=8, Φ2,4=6; Φ3,1=24, Φ3,2=63, Φ3,3=13, Φ3,4=5, and Φ3,5=3. The optimal sequence of jobs within each group is G˜1: T1,2⟶T1,4⟶T1,1⟶T1,3; G˜2: T2,2⟶T2,4⟶T2,3⟶T2,1; and G˜3: T3,2⟶T3,3⟶T3,5⟶T3,4⟶T3,1.Step 3:Ω1=5/2, Ω2=25/24, and Ω3=51/15; the optimal group sequence is G˜2⟶G˜1⟶G˜3.Step 4:q2′=3, q2″=5; q1′=33, q1″=35; q3′=58, and q3″=63Example 3.
For the problem1GS,DIFDW∑h=1m∑l=1nhϑh,lLξh,l+ϑh,0dξh,l′+ϑh,nh+1Dξh,l, the data are the same as in Example 1.
From Algorithm3, we have the following.Step 1:Φ1,1=8, Φ1,2=6, Φ1,3=4, Φ1,4=2; Φ2,1=24, Φ2,2=12, Φ2,3=10, Φ2,4=2; Φ3,1=15, Φ3,2=12, Φ3,3=9, Φ3,4=6, and Φ3,5=2. The optimal sequence of jobs within each group is G˜1: T1,4⟶T1,2⟶T1,1⟶T1,3; G˜2: T2,2⟶T2,4⟶T2,3⟶T2,1; and G˜3: T3,3⟶T3,2⟶T3,5⟶T3,4⟶T3,1.Step 2:Ω1=5/2, Ω2=25/17, and Ω3=51/14; the optimal group sequence is G˜2⟶G˜1⟶G˜3.Step 3:d2,2′=d2,2″=7, d2,4′=d2,4″=0, d2,3′=d2,3″=0, d2,1′=d2,1″=0; d1,4′=d1,4″=32, d1,2′=d1,2″=35, d1,1′=d1,1″=39, d1,3′=d1,3″=45; d3,3′=d3,3″=56, d3,2′=d3,2″=63, d3,5′=d3,5″=72, d3,4′=d3,4″=82, and d3,1′=d3,1″=0


## 5. Conclusions

We extended the classical single-machine scheduling with the due-window assignment and position-dependent weights to the group technology assumption. For the CONDW, SLKDW, and DIFDW assignment methods, our objective is to minimize a cost function including lateness (earliness-tardiness), starting times, and sizes of due-window. Some properties of the above three assignment methods were given, and three algorithms can be proposed in theONlogN time algorithm. A future extension is to the group scheduling in the flowshop, parallel machines setting, or two-stage assembly flowshop. Other future research may study extending the group scheduling to scenario-dependent processing times (Wu et al. [34–36]) or variable processing times (Wang et al. [37, 38]).



---

*Source: 2232696-2021-08-26.xml*