<figure><img src="image_1.png" /></figure>

HAL
open science

# Group Scheduling and Due Date Assignment Without Restriction on a Single Machine

Ying Chen, Yongxi Cheng

► To cite this version:

Ying Chen, Yongxi Cheng. Group Scheduling and Due Date Assignment Without Restriction on a Single Machine. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.250-257, 10.1007/978-3-030-85906-0_28. hal-04022112

HAL Id: hal-04022112

https://inria.hal.science/hal-04022112

Submitted on 9 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
Group scheduling and due date assignment
without restriction on a single machine*

Ying Chen¹ and Yongxi Cheng¹,²[0000-0003-0405-5263]

¹ School of Management, Xi’an Jiaotong University, Xi’an 710049, China
gulichenying@stu.xjtu.edu.cn, chengyx@mail.xjtu.edu.cn

² State Key Lab for Manufacturing Systems Engineering, Xi’an 710049, China

**Abstract.** We consider a single machine scheduling problem in which the scheduler decides optimal due dates for different jobs under a group technology environment, in which the jobs are classified into groups in advance due to their production similarities, and jobs in the same group are required to be processed consecutively to achieve efficiency of high-volume production. The goal is to determine an optimal job schedule together with a due date assignment strategy to minimize an objective function that includes earliness, tardiness, due date assignment and flow time costs. The due date assignment is without restriction, that is, it is allowed to assign different due dates to jobs within one group. We present structural results that fully characterize the optimal schedule, and give an optimal $O(n \log n)$ time algorithm for this problem.

**Keywords:** Single machine scheduling · Due date assignment · Group technology

# 1 Introduction

Consider a multinational company exports products to overseas destinations. The products are often adapted to local regulations, require labeling in different languages, or are even modified to meet different electricity and other infrastructure standards. In order to meet different demands, improve the efficiency and reduce costs, the company join orders coming from the same area of the world to be processed together. These orders can be considered as a group of jobs where each job can be assigned a different due date, which is often determined during sales negotiations with the customers. Each job completed ahead of its due date has to be stored and thus an inventory (earliness) cost is incurred, and each job that is not completed by its due date incurs a tardiness cost.

The above scenario forms the due date assignment problem in a group technology (GT) scheduling environment, which has attracted much attention in the past few decades due to the increasing interest in Just-In-Time systems,

* Supported by the National Natural Science Foundation of China under Grant No. 11771346.
together with the current changing of manufacturing industries from mass pro-
duction to customized production with the coming of Industry 4.0 [1, 2]. GT is an
approach to manufacturing and engineering management that seeks to achieve
efficiency in high-volume production, by exploring similarities of different prod-
ucts in their production. After classified into groups, products (jobs) within a
group are consecutively sequenced. Many advantages have been claimed through
the wide applications of group technology, e.g., by Lv et al. [3] and Keshavarz et
al. [4]. When analyzing a group technology scheduling problem, it is commonly
assumed that a job is completed when its processing is finished, irrespective of
when the other jobs in the group may be finished.

Meeting due dates has always been one of the most important objectives in
scheduling and supply chain management. Products which complete processing
prior to their due date often incur earliness costs, which include storage costs,
insurance fees and so on. On the other hand, products completed past their due
date often incur tardiness penalties, e.g., in the form of compensation of cus-
tomers. An increasing number of studies have viewed due date assignment as
part of the scheduling process, motivated by the fact that the due date is often
determined during sales negotiations with the customer. Earlier due dates are
more attractive to customers but may incur higher tardiness cost, while setting
further due dates may result in lost sales. Hence, there is also a cost associated
with the due date assignment. Due to limited production capacity, it is often
unlikely to complete all jobs exactly on their respective due dates. Thus, it is
crucial for manufacturing systems to take into account all associated costs and
develop policies which focus on the aggregate cost.

Research in scheduling with due date assignments was initiated by Seidmann
et al. [5] and Panwalkar et al. [6]. Seidmann et al. [5] analyzed a single machine
non-preemptive scheduling problem where all jobs are available for processing
at time zero. They used a due date assignment method where each job can be
assigned a due date without any restriction, and presented an O(n log n) time
optimization algorithm to determine the set of due dates. Panwalkar et al. [6]
studied a problem where the scheduler has to assign a common due date to all
jobs, to minimize an objective function which is a combination of earliness, tar-
diness, and due date costs. They provided an O(n log n) optimization algorithm
to solve the problem. Li et al. [7] considered a single machine scheduling prob-
lem involving both the due date assignment and job scheduling under a group
technology environment, with three different due date assignment methods. The
objective is to find an optimal combination of the due date assignment strategy
and job schedule, to minimize an objective function that includes earliness, tar-
diness, due date assignment and flow time costs. Shabtay et al. [8] investigated
a due date assignment problem under a group technology environment in which
jobs within a family (group) are restricted to be assigned the same due date,
while the due dates for different families are allowed to be different. The objec-
tive is to find the job schedule and the due date for each group that minimizes an
objective function which includes earliness, tardiness and due date assignment
costs. They also extended the analysis to the case in which the job process-
ing times are resource dependent. Shabtay [9] considered a due date assignment problem where each job may be assigned a different due date whose value cannot exceed a predefined threshold. Bajwa et al. [10] investigated a single machine problem of minimizing the total number of tardy jobs in a GT environment with individual due dates. They proposed a hybrid heuristic approach to solve the problem. Li et al. [11] and Ji et al. [12] considered group scheduling problem on a single machine with multiple due windows assignment.

For the third due date assignment method in [7], the unit due date, earliness, tardiness and flow time costs are the same for jobs within one group. Though classified into groups according to similarities in their production, jobs within one group could be different from each other, and so these unit costs could be different as well. Based on the research gap found, in this paper we consider the group scheduling problem with due date assignment, in which jobs within one group may have different unit due date, earliness, tardiness and flow time costs. Similar to the third due date assignment method in [7], in the problem studied it is allowed to assign different due dates to jobs within one group.

The rest of this paper is organized as follows. In Section 2, we formally describe the group scheduling problem with due date assignment studied in this paper and present some preliminary analysis. In Section 3, structural results of the optimal schedule are presented and an $O(n \log n)$ time optimization algorithm for the problem is given. The paper is concluded in Section 4.

## 2 Problem Formulation

There are $n$ independent and non-preemptive jobs that are classified into $m$ groups $G_1, G_2, \dots, G_m$. Each group $G_i$, for $i = 1, 2, \dots, m$, consists of a set $\{J_{i1}, J_{i2}, \dots, J_{in_i}\}$ of $n_i$ jobs, where $\sum_{i=1}^m n_i = n$. All the groups are given, and jobs within the same group are required to be processed contiguously. A sequence-independent machine setup time $s_i$ precedes the processing of the first job in group $G_i$. All jobs are simultaneously available for processing at time zero. Each job $J_{ij}$ has a normal processing time $p_{ij}$, and jobs within one group are allowed to be assigned different due dates. Let $C_{ij}$ denote the completion time of job $J_{ij}$. The earliness and tardiness of job $J_{ij}$ is given by $E_{ij}=\max\{d_{ij} - C_{ij}, 0\}$ and $T_{ij}=\max\{C_{ij} - d_{ij}, 0\}$. Clearly, $E_{ij}$ and $T_{ij}$ cannot both be positive. Let $\alpha_{ij}, \beta_{ij}, \gamma_{ij}$ and $\theta_{ij}$ be unit due date, earliness, tardiness and flow time costs of job $J_{ij}$, respectively. All $n_i, s_i, p_{ij}, \alpha_{ij}, \beta_{ij}, \gamma_{ij}$ and $\theta_{ij}$ are given parameters.

The objective is to determine a schedule $\pi$ for the group sequence and job sequence within each group $G_i$ for $i = 1, 2, \dots, m$, and a due date assignment vector $d(\pi) = (d_{11}(\pi), d_{12}(\pi), \dots, d_{n_1}(\pi), \dots, d_{m1}(\pi), \dots, d_{mn_m}(\pi))$ specifying the due date for each job $J_{ij}$, to minimize a cost function that includes earliness, tardiness, due date assignment and flow time costs, given by the following equation:

$$Z(\pi, d(\pi)) = \sum_{i=1}^{m} \sum_{j=1}^{n_i} (\alpha_{ij}d_{ij} + \beta_{ij}E_{ij} + \gamma_{ij}T_{ij} + \theta_{ij}C_{ij}).$$
<table><caption>**Table 1.** Notations.</caption><thead><tr><th>Simbol</th><th>Definition</th></tr></thead><tbody><tr><td>G<sub>[i]</sub></td><td>the group scheduled in the i<sup>th</sup> position of a sequence</td></tr><tr><td>J<sub>[i][j]</sub></td><td>the job scheduled in the j<sup>th</sup> position in group G<sub>[i]</sub></td></tr><tr><td>p<sub>[i][j]</sub></td><td>the processing time of job J<sub>[i][j]</sub></td></tr><tr><td>s<sub>[i]</sub></td><td>the setup time for group G<sub>[i]</sub></td></tr><tr><td>d<sub>[i][j]</sub></td><td>the due date assigned to job J<sub>[i][j]</sub></td></tr><tr><td>ψ<sub>[i][j]</sub></td><td>min(α<sub>[i][j]</sub>, γ<sub>[i][j]</sub>)</td></tr><tr><td>P<sub>[i]</sub> = Σ<sup>n<sub>[i]</sub></sup><sub>j=1</sub> p<sub>[i][j]</sub></td><td>the total processing time of all jobs within group G<sub>[i]</sub></td></tr><tr><td>Θ<sub>[i]</sub> = Σ<sup>n<sub>[i]</sub></sup><sub>j=1</sub> θ<sub>[i][j]</sub></td><td>the sum of θ<sub>[i][j]</sub> for all jobs within group G<sub>[i]</sub></td></tr><tr><td>Ψ<sub>[i]</sub> = Σ<sup>n<sub>[i]</sub></sup><sub>j=1</sub> ψ<sub>[i][j]</sub></td><td>the sum of ψ<sub>[i][j]</sub> for all jobs within group G<sub>[i]</sub></td></tr></tbody></table>

Following Graham's et al. [13] three-field notation and the notations used in [7], we denote this problem by $1|GT, DIF| \sum_{i=1}^{m} \sum_{j=1}^{n_i} (\alpha_{ij}d_{ij} + \beta_{ij}E_{ij} + \gamma_{ij}T_{ij} + \theta_{ij}C_{ij})$. Please refer to Table 1 for notations that will be used in this paper.

## 2.1 Preliminary Analysis

The following two lemmas will be used in later analysis. They are easy to verify, we state them without giving proofs.

**Lemma 1.** Fix a schedule $\pi$ for the group sequence and job sequence within every group, the optimal due date assignment vector, $d^*(\pi)$, for problem

$$1|GT, DIF| \sum_{i=1}^{m} \sum_{j=1}^{n_i} (\alpha_{ij}d_{ij} + \beta_{ij}E_{ij} + \gamma_{ij}T_{ij} + \theta_{ij}C_{ij})$$

can be determined as follows:

$$d^*_{[i][j]}(\pi) = \begin{cases} C_{[i][j]}(\pi) & \text{if } \alpha_{[i][j]} < \gamma_{[i][j]} \\ 0 & \text{if } \alpha_{[i][j]} > \gamma_{[i][j]} \\ \text{any value in } [0, C_{[i][j]}(\pi)] & \text{if } \alpha_{[i][j]} = \gamma_{[i][j]} \end{cases}$$

for $i = 1, 2, \dots, m$, and $j = 1, 2, \dots, n_i$.

**Lemma 2.** An optimal schedule does not have idle times.

Given a schedule $\pi$, let $d^*(\pi)$ be an optimal due date assignment as given in Lemma 1, and let $Z_{[i][j]}(\pi, d^*(\pi))$ be the contribution to the objective function from job $J_{[i][j]}$. According to Lemma 1, we can analyze $Z_{[i][j]}(\pi, d^*(\pi))$ according to the following three cases.

Case 1. $\alpha_{[i][j]} > \gamma_{[i][j]}$. According to Lemma 1, in this case we have $d^*(\pi)_{[i][j]} = E_{[i][j]} = 0$ and $T_{[i][j]} = C_{[i][j]}$, for $i = 1, 2, \dots, m$ and $j = 1, 2, \dots, n_i$. Hence,

$$Z_{[i][j]}(\pi, d^*(\pi)) = (\gamma_{[i][j]} + \theta_{[i][j]})C_{[i][j]}.$$
Case 2. $\alpha_{[i][j]} < \gamma_{[i][j]}$. In this case, we have $d^*(\pi)_{[i][j]} = C_{[i][j]}$ and $E_{[i][j]} = T_{[i][j]} = 0$, for $i = 1, 2, \dots, m$ and $j = 1, 2, \dots, n_i$. Hence,

$$Z_{[i][j]}(\pi, d^*(\pi)) = (\alpha_{[i][j]} + \theta_{[i][j]})C_{[i][j]}.$$

Case 3. $\alpha_{[i][j]} = \gamma_{[i][j]}$. Similarly, according to Lemma 1 in this case we have

$$\begin{aligned} Z_{[i][j]}(\pi, d^*(\pi)) &= \alpha_{[i][j]}d_{[i][j]} + \gamma_{[i][j]}(C_{[i][j]} - d_{[i][j]}) + \theta_{[i][j]}C_{[i][j]} \\ &= (\alpha_{[i][j]} + \theta_{[i][j]})C_{[i][j]}. \end{aligned}$$

Recall that $\psi_{[i][j]} = \min(\alpha_{[i][j]}, \gamma_{[i][j]})$, for $i = 1, 2, \dots, m$, and $j = 1, 2, \dots, n_i$. Hence, for all the above three cases $Z_{[i][j]}(\pi, d^*(\pi))$ can be written in a unified way as follows:

$$Z_{[i][j]}(\pi, d^*(\pi)) = (\psi_{[i][j]} + \theta_{[i][j]})C_{[i][j]}.$$

It follows that $Z(\pi, d^*(\pi))$, the objective value of the problem, can be written as

$$Z(\pi, d^*(\pi)) = \sum_{i=1}^{m} \sum_{j=1}^{n_{[i]}} (\psi_{[i][j]} + \theta_{[i][j]}) C_{[i][j]}. \quad (1)$$

## 3 The Optimal Schedule

In this section, we analyze the structure of an optimal schedule for problem $1|GT, DIF| \sum_{i=1}^{m} \sum_{j=1}^{n_i} (\alpha_{ij}d_{ij} + \beta_{ij}E_{ij} + \gamma_{ij}T_{ij} + \theta_{ij}C_{ij})$, and present an $O(n \log n)$ time optimal algorithm for the problem. By Lemma 2, we can restrict our attention to schedules without idle times. Hence, for any given schedule $\pi$, the completion time for job $J_{[i][j]}$ can be calculated by the following equation:

$$C_{[i][j]} = \sum_{k=1}^{i-1} P_{[k]} + \sum_{k=1}^{i} s_{[k]} + \sum_{l=1}^{j} p_{[i][l]}.$$

Thus, by Equ. (1), the objective value can be written as

$$\begin{aligned} Z(\pi, d^*(\pi)) &= \sum_{i=1}^{m} \sum_{j=1}^{n_{[i]}} (\psi_{[i][j]} + \theta_{[i][j]}) C_{[i][j]} \\ &= \sum_{i=1}^{m} \sum_{j=1}^{n_{[i]}} (\psi_{[i][j]} + \theta_{[i][j]}) \left( \sum_{k=1}^{i-1} P_{[k]} + \sum_{k=1}^{i} s_{[k]} + \sum_{l=1}^{j} p_{[i][l]} \right) \\ &= \sum_{i=1}^{m} (\Psi_{[i]} + \Theta_{[i]}) \left( \sum_{k=1}^{i-1} P_{[k]} + \sum_{k=1}^{i} s_{[k]} \right) + \sum_{i=1}^{m} \sum_{j=1}^{n_{[i]}} \sum_{l=1}^{j} (\psi_{[i][j]} + \theta_{[i][j]}) p_{[i][l]}. \end{aligned} \quad (2)$$

From Equ. (2), under an optimal due date assignment, the total cost is the sum of $m + 1$ terms. The first term $\sum_{i=1}^{m} (\Psi_{[i]} + \Theta_{[i]}) (\sum_{k=1}^{i-1} P_{[k]} + \sum_{k=1}^{i} s_{[k]})$ is independent of the internal job sequence with each group, and each of the
remaining $m$ terms, $\sum_{j=1}^{n[i]} \sum_{l=1}^{j} (\psi_{[i][j]} + \theta_{[i][j]}) p_{[i][l]}$, only depends on the internal job sequence within group $G_{[i]}$. As a result of this separable property of the objective function, the problem reduces to $m + 1$ subproblems. We can get the optimal group sequence and job sequence in each group from the following two lemmas.

**Lemma 3.** There exists an optimal group sequence such that the groups are scheduled in non-decreasing order of $\frac{P_u+s_u}{\Psi_u+\Theta_u}$.

*Proof.* Assume that $\pi$ is an optimal schedule which does not satisfy the property of the lemma. Then, $\pi$ must contain two consecutive groups, $G_u$ (we assume that $G_u$ is processed as the $r$th group in $\pi$) followed by $G_v$, such that $\frac{P_u+s_u}{\Psi_u+\Theta_u} > \frac{P_v+s_v}{\Psi_v+\Theta_v}$. We exchange the positions of $G_u$ and $G_v$ (i.e., $G_v$ is now at the $r$th position), and leave all other groups at their original positions in $\pi$. Let $\pi'$ be the resulting schedule. From the above analysis, to compare the objective values between schedules $\pi$ and $\pi'$, we only need to consider the first term in Equ. (2). Hence,

$$ 
\begin{aligned}
& Z(\pi, d^*(\pi)) - Z(\pi', d^*(\pi')) \\
& = (\Psi_u + \Theta_u) \left( \sum_{k=1}^{r-1} P_{[k]} + \sum_{k=1}^{r-1} s_{[k]} + s_u \right) + (\Psi_v + \Theta_v) \left( \sum_{k=1}^{r-1} P_{[k]} + P_u + \sum_{k=1}^{r-1} s_{[k]} + s_u + s_v \right) \\
& \quad - (\Psi_v + \Theta_v) \left( \sum_{k=1}^{r-1} P_{[k]} + \sum_{k=1}^{r-1} s_{[k]} + s_v \right) - (\Psi_u + \Theta_u) \left( \sum_{k=1}^{r-1} P_{[k]} + P_v + \sum_{k=1}^{r-1} s_{[k]} + s_v + s_u \right) \\
& = (\Psi_v + \Theta_v)(P_u + s_u) - (\Psi_u + \Theta_u)(P_v + s_v) \\
& = (\Psi_v + \Theta_v)(\Psi_u + \Theta_u) \left( \frac{P_u + s_u}{\Psi_u + \Theta_u} - \frac{P_v + s_v}{\Psi_v + \Theta_v} \right) \\
& > 0.
\end{aligned}
$$

This contradicts the optimality of $\pi$. The lemma is established. $\square$

<figure><img src="image_4.png" /></figure>

**Lemma 4.** In an optimal schedule, the jobs within group $G_i$ ($i = 1, 2, \dots, m$) are ordered in non-decreasing order of $\frac{p_{ij}}{\psi_{ij}+\theta_{ij}}$.

*Proof.* Once the processing order of the groups is fixed, the first term of Equ. (2) is a constant, and the second term of Equ. (2) can be decomposed into $m$ terms, such that each of these $m$ terms only depends on the internal job processing order within each group, that is, does not depend on the processing order of the groups. Hence, the proof of this lemma follows directly from a standard exchange argument similar to the proof of Lemma 3. $\square$

<figure><img src="image_5.png" /></figure>

## 3.1 An $O(n \log n)$ Time Optimal Algorithm

Now we are ready to present an $O(n \log n)$ time optimal algorithm for problem $1|GT, DIF| \sum_{i=1}^{m} \sum_{j=1}^{n_i} (\alpha_{ij}d_{ij} + \beta_{ij}E_{ij} + \gamma_{ij}T_{ij} + \theta_{ij}C_{ij})$.

**Algorithm 1:**
1. Order the groups in non-decreasing order of $\frac{P_i+s_i}{\Psi_i+\Theta_i}$.

2. Order the jobs within group $G_i$ ($i = 1, 2, \dots, m$) in non-decreasing order of $-\frac{p_{ij}}{\psi_{ij}+\theta_{ij}}$. Let $\pi$ be the schedule obtained.

3. Assign the due dates for jobs according to Lemma 1.

**Theorem 1.** *Algorithm 1 optimally solves $1|GT, DIF| \sum_{i=1}^{m} \sum_{j=1}^{n_i} (\alpha_{ij}d_{ij} + \beta_{ij}E_{ij} + \gamma_{ij}T_{ij} + \theta_{ij}C_{ij})$ in $O(n \log n)$ time.*

*Proof.* The correctness of Algorithm 1 follows from Lemmas 1-4. Determining the group sequence in Step 1 requires $O(max(n, m \log m))$ time. Calculating the job sequence in Step 2 requires $O(\sum_{i=1}^{m} n_i \log n_i)$ time, and Step 3 requires $O(n)$ time. Since $m = O(n)$ and $\sum_{i=1}^{m} n_i = n$, the overall time complexity of the algorithm is $O(n \log n)$. $\square$

# 4 Conclusion

In this paper, we study a single machine scheduling problem in which the scheduler decides optimal due dates for different jobs under a group technology environment. Jobs in the same group are required to be processed consecutively. The goal is to determine an optimal job schedule and a due date assignment strategy to minimize an aggregate cost function, which includes earliness, tardiness, due date assignment and flow time costs. Though classified into groups according to similarities in their production, jobs within one group could be different from each other, and so their unit due date, earliness, tardiness and flow time costs could be different as well. In this paper, we consider the group scheduling problem with due date assignment, in which the above mentioned unit costs of jobs within the same group could be different. The due date assignment is without restriction, that is, it is allowed to assign different due dates to jobs within one group.

We present structural results that fully characterize the optimal schedule, and give an optimal $O(n \log n)$ time algorithm for this problem. As the assumption that the processing times of jobs are constant may not be appropriate for the modeling of many real world industrial processes, one possible future research direction is to take into account time-dependent learning effect for job processing times, in which the actual processing time of a job is affected by the total processing time of jobs preceding it.

# References

1. Vaidya, S., Ambad, P., Bhosle, S.: Industry 4.0 – A Glimpse. Procedia Manufacturing **20**, 233-238 (2018)

2. Dalenogare, L.S., Benitez, G.B., Ayala, N.F., Frank, A.G.: The expected contribution of Industry 4.0 technologies for industrial performance. International Journal of Production Economics **204**, 383-394 (2018)
3. Lv, D., Luo, S., Xue, J., Xu, J., Wang, J.: A note on single machine common flow allowance group scheduling with learning effect and resource allocation. Computers & Industrial Engineering, vol. 151 (2021). https://doi.org/10.1016/j.cie.2020.106941

4. Keshavarz, T., Savelsbergh, M., Salmasi, N.: A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties. Applied Mathematical Modelling **39**(20), 6410-6424 (2015)

5. Seidmann, A., Panwalkar, S.S., Smith, M.L.: Optimal assignment of due-dates for a single processor scheduling problem. International Journal of Production Research **19**(4), 393-399 (1981)

6. Panwalkar, S.S., Smith, M.L., Seidmann, A.: Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research **30**(2), 391-399 (1982)

7. Li, S., Ng, C.T., Yuan, J.: Group scheduling and due date assignment on a single machine. International Journal of Production Economics **130**(2), 230-235 (2011)

8. Shabtay, D., Itskovich, Y., Yedidsion, L., Oron, D.: Optimal due date assignment and resource allocation in a group technology scheduling environment. Computers & Operations Research **37**(12), 2218-2228 (2010)

9. Shabtay, D.: Optimal restricted due date assignment in scheduling. European Journal of Operational Research **252**(1), 79-89 (2016)

10. Bajwa, N., Melouk, S., Bryant, P.: A hybrid heuristic approach to minimize number of tardy jobs in group technology systems. International Transactions in Operational Research **26**(5), 1847-1867 (2019)

11. Li, W., Zhao, C.: Single machine scheduling problem with multiple due windows assignment in a group technology. Journal of Applied Mathematics & Computing **44**, 477-494 (2015)

12. Ji, M., Zhang, X., Tang, X., Cheng, T.C.E., Wei, G., Tan, Y.: Group scheduling with group-dependent multiple due windows assignment. International Journal of Production Research **54**(4), 1244-1256 (2016)

13. Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics **5**, 287-326 (1979)