# Optimization for Due-Date Assignment Single-Machine Scheduling under Group Technology

Authors: Li-Yan Wang; Mengqi Liu; Ji-Bo Wang; Yuan-Yuan Lu; Wei-Wei Liu
Journal: Complexity
 (2021)

---

## Abstract

In this paper, the single-machine scheduling problem is studied by simultaneously considering due-date assignment and group technology (GT). The objective is to determine the optimal sequence of groups and jobs within groups and optimal due-date assignment to minimize the weighted sum of the absolute value in lateness and due-date assignment cost, where the weights are position dependent. For the common (CON) due-date assignment, slack (SLK) due-date assignment, and different (DIF) due-date assignment, anOnlogn time algorithm is proposed, respectively, to solve the problem, where n is the number of jobs.


---

## Body

## 1. Introduction

In the manufacturing industry, it is well known that firms can increase production efficiency by adopting the group technology (GT). The group technology is an approach to manufacturing that seeks to improve efficiency in high-volume production by exploiting the similarities of different products and activities in their production (Neufeld et al. [1] and Yang et al. [2]). Through decades of application, people have found many advantages of the group technology. For example, changeover between different jobs in the same group is simplified, reducing the costs or time involved; jobs in the same group spend less time waiting, which results in less work-in-process inventory; jobs in the same group tend to move through production in a direct route, reducing the manufacturing lead time (see the work of Yang and Yang [3], Lu et al. [4], Yin et al. [5], Wang and Liu [6], Wang and Wang [7], Qin et al. [8], Lu et al. [9], Zhang et al. [10], Liu et al. [11], and Wang and Liang [12]).In recent years, the problem of the due-date assignment has been closely focused on by scholars (see the work of Yin et al. [13, 14], Wang et al. [15], and Shabtay [16]). Due to the increasing interest in the Just-In-Time (JIT) system, the issue of schedule allocation is becoming more and more important in practical applications. In the classical scheduling problem, the due date is usually a given constant, while in the actual application of life, the duration of the job is not a fixed constant, but a decision variable. In order to strengthen the global competition and improve the service level for customers, the jobs are required to be processed too early or too late in the JIT system, which leads to the trouble of scheduling problems involving advance and delay costs and the expiration date of the construction period. For the early completion of the job, it means that we have to bear a certain inventory cost, while for the delayed completion of the job, we have to bear the contract penalty, and the customer’s goodwill is damaged (see the work of Li et al. [17], Liu et al. [18], Wang et al. [19]). A lot of literature deals with the problems such as the CON, SLK, and some other due-date assignment methods considering jobs. However, under the group technology, there are relatively few studies on the problem of the assignment of jobs. Li et al. [17] considered three due-date assignment methods under group technology. The objective function is to minimize the weighted sum of earliness, tardiness, due-date assignment, and completion time. For the CON, SLK, and different due-date assignments (DIFs), they proved that the problem can be solved in polynomial time, respectively. Ji et al. [20] studied the single-machine slack due-date window assignment scheduling with group technology. The objective function is to minimize the total cost including the earliness, tardiness, due window starting time, and due window size. They proved that the problem can be solved in Onlogn time.Brucker [21] considered the CON due-date scheduling problem of minimizing the total cost comprising the total weighted absolute lateness value and common due-date (CON) cost, where the weight is position dependent. He proved that the problem can be solved in a time Onlogn. Liu et al. [18] considered the SLK due-date assignment scheduling, and the goal is to minimize the total cost comprising the total weighted absolute lateness value and common flow allowance (SLK) cost, where the weight is a position-dependent weight. They proved that the problem can be solved in a time Onlogn. Wang et al. [19] studied the scheduling problems of single machine resource allocation in job-dependent learning effects. Under the linear and convex resource consumption functions, they proved that the CON and SLK due-date assignment problems can be solved in polynomial time, respectively. Sun et al. [22] considered single-machine scheduling problems on resource allocation, group technology, and learning effect. Under the linear and convex resource consumption functions, they proved that the SLK due-date assignment problem can be solved in polynomial time.According to this study, we consider due-date assignment and scheduling problems with group technology. Under the assumption of group technology, the jobs are classified into groups by exploiting the similarities of different products and activities in their production. In this paper, we proceed to the study Brucker [21], Liu et al. [18], and Wang et al. [19], which is an extension of their work from considering the CON, SLK, and DIF due-date assignment scheduling problems with group technology and position-dependent weights. We organize the rest of the paper as follows: the problem is formulated in Section 2, several results of the optimal solution are introduced in Section 3, and the conclusions are summarized in Section 4.


## 2. Problem Formulation

In the study, the problem can be formally described as follows: there aren independent non-preemption jobs grouped into f groups, i.e., G1,G2,…,Gf. A single machine and all the jobs are available at time zero, and the single machine can handle one job at a time and preemption is not allowed. Let the number of jobs in group Gi be ni, i.e., Ji,1,Ji,2,…,Ji,ni, where Ji,j denotes the job Jj of group Gi, i=1,2,…,f, j=1,2,…,ni and n1+n2+⋯+nf=n. Jobs in the same group are processed consecutively and do not need setup times. Let pij denote the processing time of job Ji,j and si be the sequence-independent machine setup time incurred before the process of the first job of group Gi. Each job Ji,ji=1,2,…,f;j=1,2,…,ni has a due date di,j, which is assignable according to one of the following three due-date assignment methods:(1)
The common (CON) due-date assignment in which all jobs of groupGi are assigned the same due date, i.e., di,j=diopt for i=1,2,…,f and j=1,2,…,ni(2)
The common flow allowance (slack, SLK) assignment in which the due-datedi,j for all jobs of group Gi are assigned an equal flow allowance that is equal to its processing time plus the common flow allowance, i.e., di,j=pi,j+qiopt for i=1,2,…,f and j=1,2,…,ni(3)
The different (DIF) due-date assignments in which the due datedi,j for all jobs of group Gi are assigned a different due date with no restrictions (i=1,2,…,f and j=1,2,…,ni)LetCi,j be the completion time of job Ji,j. The goal is to determine the due date di,j (i.e., the CON diopt, the SLK qiopt, and the DIF di,j) and an optimal sequence π∗ such that the following objective functions are to be minimized:(1)Z1π,Dπ=∑i=1f∑j=1niωijLπi,j+ωi,0diopt,Z2π,Dπ=∑i=1f∑j=1niωi,jLπi,j+ωi,0qiopt,Z3π,Dπ=∑i=1f∑j=1niωi,jLπi,j+ωi,0dπi,j,where ωi,j is the nonnegative weight of the jth position in group Gi (i.e., position-dependent weight, i=1,2,…,f;j=1,2,…,ni), ωi,0 denotes the unit cost of diopt (qiopt and dπi,j), i=1,2,…,f, Dπ=d1,1π,…,d1,n1π;…;df,1π,…,df,nfπ is the due-date assignment vector under schedule π, and Li,j=Ci,j−di,j is the lateness of job Ji,j. Note that Lπi,j=Eπi,j+Tπi,j, where Eπi,j=max0,dπi,j−Cπi,j is the earliness of job Jij, Tπi,j=max0,Cπi,j−dπi,j is the tardiness of job Jij, and πi,j represents the job that is in the jth position of group Gi in π for 1≤k≤ni. By using the three-field notation (see Graham et al. [23]), the problems can be denoted by(2)1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt,1GT,SLK∑i=1f∑j=1niωi,jLπi,j+ωi,0qiopt,1GT,DIF∑i=1f∑j=1niωi,jLπi,j+ωi,0dπi,j,respectively, where GT denotes the group technology.


## 3. Main Results

Lemma 1.
For each of the three due-date assignment methods, there exists an optimal schedule with zero machine idle times.Proof.
It is omitted due to simplicity.Therefore, it is convenient to introduce a dummy jobJi,0 of group Gi for i=1,2,…,f with processing time pi,0=0 and weight ωi,0 which is always scheduled at time 0, i.e., πi,0=0. Consequently, for any given job schedule π, the completion times can be calculated by the following equation:(3)Cπi,j=Siπ+si+∑k=1jpπi,k,where Siπ denotes the starting time of group Gi in schedule π for i=1,2,…,f.Lemma 2.
If the sequence of groups is fixed, for the CON and SLK due-date assignment methods, there exists an optimal sequence with the property thatdiopt (qiopt) coincides with the job completion times of group Gi for i=1,2,…,f.Proof.
Let the sequence of groups be fixed. Consider an optimal sequenceπ in Gi.(a)
First, we prove that the common due-datediopt of group Gi coincides with the completion time of a job of group Gi. Assume that Cπi,ki<diopt<Cπi,ki+1; therefore,(4)Z1iπ,Diπ=∑j=1niωi,jLπi,j+ωi,0diopt,=∑j=1niωi,jCπi,j−diopt+ωi,0diopt,=∑j=1kiωi,jdiopt−Cπi,j+∑j=ki+1niωi,jCπi,j−diopt+ωi,0diopt.Ifdiopt=Cπi,ki, we have(5)Z1i1π,Diπ=∑j=1kiωi,jCπi,ki−Cπi,j+∑j=ki+1niωi,jCπi,j−Cπi,ki+ωi,0Cπi,ki.Ifdiopt=Cπi,ki+1, we have(6)Z1i2π,Diπ=∑j=1kiωi,jCπi,ki+1−Cπi,j+∑j=ki+1niωi,jCπi,j−Cπi,ki+1+ωi,0Cπi,ki+1.Letx=diopt−Cπi,ki>0, y=Cπi,ki+1−diopt>0, then we can obtain that(7)Z1iπ,Diπ−Z1i1π,Diπ,=∑j=1kiωi,jdiopt−Cπi,ki+∑j=ki+1niωi,jCπi,ki−diopt+ωi,0diopt−Cπi,ki,=∑j=0kiωi,jdiopt−Cπi,ki+∑j=ki+1niωi,jCπi,ki−diopt,=x∑j=0kiωi,j−∑j=ki+1niωi,j,(8)Z1iπ,Diπ−Z1i2π,Diπ,=∑j=1kiωi,jdiopt−Cπi,ki+1+∑j=ki+1niωi,jCπi,ki+1−diopt+ωi,0diopt−Cπi,ki+1,=∑j=0kiωi,jdiopt−Cπi,ki+1+∑j=ki+1niωi,jCπi,ki+1−diopt,=−y∑j=0kiωi,j−∑j=ki+1niωi,j.Thus,Z1i1π,Diπ≤Z1iπ,Diπ if ∑j=0kiωi,j≥∑j=ki+1niωi,j and Z1i2π,Diπ≤Z1iπ,Diπ otherwise.(b)
Assume thatCπi,li<qiopt<Cπi,li+1; therefore,(9)Z2iπ=∑j=1niωi,jLπi,j+ωi,0qiopt,=∑j=1niωi,jCπi,j−pπi,j−qiopt+ωi,0qiopt,=∑j=1niωi,jCπi,j−1−qiopt+ωi,0qiopt,=∑j=1li+1ωi,jqiopt−Cπi,j−1+∑j=li+2niωi,jCπi,j−1−qiopt+ωi,0qiopt,where Cπi,0=Siπ+si.
Ifqiopt=Cπi,li, we have(10)Z2i′π=∑j=1li+1ωi,jCπi,li−Cπi,j−1+∑j=li+2niωi,jCπi,j−1−Cπi,li+ωi,0Cπi,li.
Ifqiopt=Cπi,li+1, we have(11)Z2i″π=∑j=1li+1ωi,jCπi,li+1−Cπi,j−1+∑j=li+2niωi,jCπi,j−1−Cπi,li+1+ωi,0Cπi,li+1.
Letx′=qiopt−Cπi,li>0 and y′=Cπi,li+1−qiopt>0; then, we have(12)Z2iπ,Diπ−Z2i′π,Diπ,=∑j=1li+1ωi,jqiopt−Cπi,li+∑j=li+2niωi,jCπi,li−qiopt+ωi,0qiopt−Cπi,li,=∑j=0li+1ωi,jqiopt−Cπi,li+∑j=li+2niωi,jCπi,li−qiopt,=x′∑j=0li+1ωi,j−∑j=li+2niωi,j,Z2iπ,Diπ−Z2i′′π,Diπ,=∑j=1li+1ωi,jqiopt−Cπi,li+1+∑j=li+2niωi,jCπi,li+1−qiopt+ωi,0qiopt−Cπi,li+1,=∑j=0li+1ωi,jqiopt−Cπi,li+1+∑j=li+2niωi,jCπi,li+1−qiopt,=−y′∑j=0li+1ωi,j−∑j=li+2niωi,j.
Thus,Z2i′π,Diπ≤Z2iπ,Diπ if ∑j=0li+1ωi,j≥∑j=li+2niωi,j and Z2i′′π,Diπ≤Z2iπ,Diπ otherwise.
From (a) and (b), this implies thatdiopt (qiopt) is equal to the job completion times of group Gi for i=1,2,…,f.Lemma 3.
For the CON due-date assignment, if the sequence of groups is fixed, for a given scheduleπ, there exists an optimal schedule of group Gi in which diopt=Cπi,ki, where ki is a median for the sequence ωi,0,ωi,1,…,ωi,ni and ∑j=0ki−1ωi,j≤∑j=kiniωi,j and ∑j=0kiωi,j≥∑j=ki+1niωi,j.Proof.
By using the technique of small perturbations, from Lemma2, we assume that diopt=Cπi,ki. Applying (7) and (8) to the cases of moving the common due-date x units of time to the left (right), we have ∑j=kiniωi,j−∑j=0ki−1ωi,j≥0 and ∑j=0kiωi,j−∑j=ki+1niωi,j≥0.Lemma 4.
For the SLK due-date assignment, if the sequence of groups is fixed, for a given scheduleπ, there exists an optimal schedule of group Gi in which qiopt=Cπi,li, where li is a median for the sequence ωi,0,ωi,1,…,ωi,ni and ∑j=0liωi,j≤∑j=li+1niωi,j and ∑j=0li+1ωi,j≥∑j=li+2niωi,j.Proof.
It is similar to the proof of Lemma3.Lemma 5.
For the DIF due-date assignment method, there exists an optimal sequence such thatdπi,j≤Cπi,j.Proof.
We consider the case that contradicts this optimal property. Consider an optimal sequenceπ in Gi, if Cπi,j<dπi,j, and then, the total cost for job Jπi,j is(13)Zπi,j=ωi,jdπi,j−Cπi,j+ωi,0dπi,j.
We shiftdπi,j to the left such that dπi,j=Cπi,j, and we have(14)Z˜πi,j=ωi,0dπi,j<Zπi,j.
Hence, the caseCπi,j<dπi,j is not an optimal due-date assignment. Lemma 5 is proved.Lemma 6.
For the DIF due-date assignment method, letπ be a given sequence, and the optimal due-date dπi,j for job Jπi,j can be obtained as follows:(15)dπi,j=0,ωi,j≤ωi,0,Cπi,j,ωi,j>ωi,0.Proof.
From Lemma5, for job Jπi,j, we have(16)Zπi,j=ωi,jCπi,j−dπi,j+ωi,0dπi,j=ωi,jCπi,j+ωi,0−ωi,jdπi,j.
Obviously, ifωi,j≤ωi,0, dπi,j should be 0, if ωi,j>ωi,0dπi,j should be Cπi,j. Hence, the total cost for job Jπi,j is(17)Zπi,j=ηi,jCπi,j,where ηi,j=minωi,j,ωi,0.For the CON due-date assignment, obviously, the value ofki (i=1,2,…,f) given in Lemma 3 is independent of the job processing times and the job sequence. Therefore, it is optimal for any job sequence within each group. For a given schedule π, diopt=Cπi,ki, and the total cost of all the jobs within Gi for i=1,…,m is given by(18)Z1iπ=∑j=1niωi,jLπi,j+ωi,0diopt,=∑j=1niωi,jCπi,j−diopt+ωi,0diopt,=ωi,0Cπi,ki+∑j=1kiωi,jCπi,ki−Cπi,j+∑j=ki+1niωi,jCπi,j−Cπi,ki,=ωi,0Si+si+∑j=0kiωi,j∑h=j+1kipπi,h+∑j=ki+1niωi,j∑h=ki+1jpπi,h,=∑h=1kipπi,h∑j=0h−1ωi,j+∑h=ki+1nipπi,h∑j=hniωi,j+ωi,0Si+si,=∑j=1niWi,jpπi,j+ωi,0Si+si,where(19)Wi,j=∑h=0j−1ωi,h,j=1,2,…,ki,∑h=jniωi,h,j=ki+1,…,ni.For the SLK due-date assignment, obviously, the value ofli (i=1,2,…,f) given in Lemma 4 is independent of the job processing times and the job sequence. Therefore, it is optimal for any job sequence within each group. For a given schedule π, qiopt=Cπi,li, and the total cost of all the jobs within Gi for i=1,2,…,f is given by(20)Z2iπ=∑j=1niωi,jLπi,j+ωi,0qiopt,=∑j=1niωi,jCπi,j−pπi,j−qiopt+ωi,0qiopt,=∑j=1niωi,jCπi,j−1−qiopt+ωi,0qiopt,=∑j=1niωi,jCπi,j−1−Cπi,li+ωi,0Cπi,li,=∑j=1li+1ωi,jCπi,li−Cπi,j−1+∑j=li+2niωi,jCπi,j−1−Cπi,li+ωi,0Cπi,li,=∑j=0li+1ωi,j∑h=jlipπi,h+∑j=li+2niωi,j∑h=li+1j−1pπi,h+ωi,0Si+si,=∑j=1lipπi,j∑h=0jωi,h+∑j=li+1ni−1pπi,j∑h=j+1niωi,h+ωi,0Si+si,=∑j=1niVi,jpπi,j+ωi,0Si+si,where(21)Vi,j=∑h=0j−1ωi,h,j=1,2,…,li,∑h=j+1niωi,h,j=li+1,…,ni−1,0,j=ni.For the DIF due-date assignment, from Lemma6, the total cost of all the jobs within Gi for i=1,2,…,f is given by(22)Z3iπ=∑j=1niωi,jLπi,j+ωi,0dπi,j,=∑j=1niηi,jCπi,j,=∑j=1niηi,jSi+si+∑h=1jpπi,h,=∑j=1niUi,jpπi,j+Si+si∑j=1niωi,j,where(23)Ui,j=∑h=jniηi,h,h=1,2,…,ni.Obviously, from (18), (20), and (22), the term ∑j=1niWi,jpπi,j∑j=1niVi,jpπi,jand∑j=1niUi,jpπi,j is only concerned with the job processing sequence within group Gi and can be minimized by the HLP rule (see the work of Hardy et al. [24]), i.e., the optimal job sequence within group Gii=1,2,…,f can be obtained by arranging the elements of the Wi,j (Vi,j and Ui,j) and pi,j vectors in opposite orders. The term ωi,0Si+siSi+si∑j=1niωi,j is only dependent on the starting time of the group Gi, and the optimal sequence of the groups G1,G2,…,Gf can be obtained by the following lemma.Lemma 7.
For the problems1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt and 1GT,SLK∑i=1f∑j=1niωi,jLπi,j+ωi,0qiopt, the optimal group sequence can be obtained by arranging the groups in nondecreasing order of θi=si+∑j=1nipi,jωi,0, i=1,2,…,f, respectively. For the problem 1GT,DIF∑i=1f∑j=1niωi,jLπi,j+ωi,0dπi,j, the optimal group sequence can be obtained by arranging the groups in nondecreasing order of θi=si+∑j=1nipi,j∑j=1niωi,j, i=1,2,…,f.Proof.
For the problem1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt, let π and π′ be two sequences where the difference between π and π′ is a pairwise interchange of two adjacent groups Gk and Gl, that is, π=A,Gk,Gl,B and π′=A,Gl,Gk,B, where A and B are partial sequences. To show π dominates π′, it suffices to show that Z1π,Dπ≤Z1π′,Dπ′. We assume that S denotes the completion time of the last job in A, and we have(24)Slπ=S+sk+∑j=1nkpk,j,Skπ′=S+sl+∑j=1nlpl,j.
Suppose that(25)sk+∑j=1nkpk,jωk,0≤sl+∑j=1nlpl,jωl,0,and from (18), we have(26)Z1π,Dπ−Z1π′,Dπ′,=ωk,0S+sk+ωl,0S+sk+∑j=1nkpkj+sl−ωl,0S+sl−ωk,0S+sl+∑j=1nlplj+sk,=ωl,0sk+∑j=1nkpk,j−ωk,0sl+∑j=1nlpl,j≤0.
Therefore,Z1π,Dπ≤Z1π′,Dπ′. This completes the proof of the problem 1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt.
For the problem1GT,SLK∑i=1f∑j=1niωijLπi,j+ωi,0qiopt, the proof can be obtained similarly.
For the problem1GT,DIF∑i=1f∑j=1niωijLπi,j+ωi,0diopt, stemming from the proof of the problem 1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt, we suppose that(27)sk+∑j=1nipk,j∑j=1nkωk,j≤sl+∑j=1nipl,j∑j=1nlωl,j,and from (22), we have(28)Z3π,Dπ−Z3π′,Dπ′,=S+sk∑j=1nkωk,j+S+sk+∑j=1nkpkj+sl∑j=1nlωl,j−S+sl∑j=1nlωl,j−S+sl+∑j=1nlplj+sk∑j=1nkωk,j,=∑j=1nlωl,jsk+∑j=1nkpk,j−∑j=1nkωk,jsl+∑j=1nlpl,j≤0.
Therefore,Z1π,Dπ≤Z1π′,Dπ′. This completes the proof of the problem 1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt.Based on the abovementioned analysis, we can present the following algorithm to solve the problems1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt, 1GT,SLK∑i=1f∑j=1niωi,jLπi,j+ωi,0qiopt, and 1GT,DIF∑i=1f∑j=1niωi,jLπi,j+ωi,0dπi,j.Theorem 1.
The problems1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt, 1GT,SLK∑i=1f∑j=1niωi,jLπi,j+ωi,0qiopt, and 1GT,DIF∑i=1f∑j=1niωi,jLπi,j+ωi,0dπi,j can be solved in Onlogn time, respectively.Proof.
Step 1 and Step 4 need timeOn, respectively. Step 2 needs O∑i=1fnilogni≤Onlogn time. Step 3 needs Oflogf≤Onlogn time ∑i=1fni=nandf<n. Thus, the total time complexity of Algorithm 1 is Onlogn.Algorithm 1:Optimal algorithm.
Step 1: for the problem1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt, we calculate ki of each group according to Lemma 3 and calculate Wi,j according to equation (19). For the problem 1GT,SLK∑i=1f∑j=1niωi,jLπi,j+ωi,0qiopt, we calculate li of each group according to Lemma 4 and calculate Vi,j according to equation (21). For the problem 1GT,DIF∑i=1f∑j=1niωi,jLπi,j+ωi,0dπi,j, we calculate Ui,j according to equation (23).Step 2: we assign the smallestWi,j (Vi,j and Ui,j) value to the job with the largest pi,j value, the second smallest Wi,j (Vi,j and Ui,j) value to the job with the second largest pi,j value, and so on, with ties broken arbitrarily, and then obtain the internal job sequence of each group.Step 3: we arrange the groups in nondecreasing order ofθi by Lemma 7.Step 4: according to Lemma3, we calculate diopt for the problem 1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt. According to Lemma 4, we calculate qiopt for the problem 1GT,SLK∑i=1f∑j=1niωi,jLπi,j+ωi,0qiopt. According to Lemma 6, we calculate di,j for the problem 1GT,DIF∑i=1f∑j=1niωi,jLπi,j+ωi,0dπi,j.Example 1.
We only consider the problem1GT,CON∑i=1f∑j=1niωijLπi,j+ωi,0diopt. Consider n=12,f=3, G1:J1,1,J1,2,J1,3, p1,1=2,p1,2=4,p1,3=6, ω1,1=2,ω1,2=4,ω1,3=3,ω1,0=2,s1=2; G2:J2,1,J2,2,J2,3,J2,4, p2,1=5,p2,2=8,p2,3=4,p2,4=3, ω2,1=3,ω2,2=2,ω2,3=2,ω2,4=3,ω2,0=1,s2=4; and G3:J,,J3,2,J3,3,J3,4,J3,5, p3,1=9,p3,2=4,p3,3=2,p3,4=3,p3,5=7, ω3,1=4,ω3,2=2,ω3,3=5,ω3,4=3,ω3,5=7,ω3,0=5,s3=3.
The solution is as follows:Step 1: we calculatek1=2, W1,1=2,W1,2=4,W1,3=3; k2=2, W2,1=1,W2,2=4,W2,3=5,W2,4=3; and k3=3, W3,1=5,W3,2=9,W3,3=11,W3,4=10,W3,5=7Step 2: sequence of jobs within each group:G1:J1,3⟶J1,1⟶J1,2, G2:J2,2⟶J2,3⟶J2,4⟶J2,1, and G3:J3,1⟶J3,2⟶J3,3⟶J3,4⟶J3,5Step 3:θ1=7, θ2=24, θ3=28/5, and θ3<θ1<θ2; hence, the optimal group sequence is G3,G1,G2Step 4:d3opt=s3+∑j=1k3p3j=18, d1opt=S1+s1+∑j=1k1p1j=28+2+8=38, and d2opt=S2+s2+∑j=1k2p2j=42+4+12=58


## 4. Conclusions

In this paper, we studied the single-machine scheduling problem involving the due-date assignment and job scheduling under the group technology. The due dates are assignable according to one of the following three due-date assignment methods: CON, SLK, and DIF due-date assignment. The objective is to find the optimal due dates of jobs, a sequence for groups, and jobs to minimize a total cost function. We show that the problem can be solved in polynomial time. In future study, we can consider the group scheduling models associated with learning and deteriorating effects. In addition, we can further study the group scheduling with CON and SLK due-date assignment in the flow shop setting.



---

*Source: 6656261-2021-03-05.xml*