Single machine scheduling problem with multiple due windows assignment in a group technology

Abstract

We consider group scheduling problem on a single machine with multiple due windows assignment. Jobs are divided into groups in advance according to their processing similarities, and all jobs of the same group are required to be processed contiguously on the machine in order to achieve production efficiency and save time/money resource. A sequence-independent setup time precedes the processing of each group. The goal is to determine the optimal sequence for both groups and jobs, together with an optimal combination of the due windows assignment strategy so as to minimize the total of earliness, tardiness and due windows related costs. We give an $O(n\log n)$ time algorithm for the problem.

1 Introduction

Scheduling problems with due date assignment have attracted attention in recent years due to the just-in-time (JIT) production management. In a JIT system, jobs should be completed as close as possible to their due dates. Completing a job early means having to bear the costs of holding unnecessary inventories, while finishing a job late results in a contractual penalty and a loss of customer goodwill. Kuo and Yang [12] stressed a single machine scheduling problem with a common due-date and deteriorating jobs, in which the job processing time is an increasing function of its starting time. They made a concise analysis of the problem and provided a polynomial time algorithm to solve it. Li et al. [13] studied the problem of scheduling deteriorating jobs and due date assignment on a single machine. They presented some polynomial time algorithms to solve the problem with two due date assignment methods: CON and SLK. Moreover, Chand and Chhajed [1] introduced the problem of simultaneous determination of optimal due dates and optimal schedule for the single machine problem with multiple due dates, they provided an efficient optimal algorithm to solve it. For further research on this topic, the reader may refer to Wang and Wang [23], Yang et al. [27], Yang et al. [28], Fan and Zhao [6] and Zhao et al. [33].

Furthermore, job completions can be accepted without penalty within an interval in time in the JIT system. This time interval is often called the due window. A job completed within the due window is considered to be on time and will not be penalized. However, a job completed prior to or after the due window will be penalized according to their earliness/tardiness. Sidney [19] was among the pioneers, who stressed a single machine scheduling problem with due windows assignment. He assumed that each job has its due window and no job’s due window is allowed to contain the due window of another job. The goal was to find a schedule that minimizes the total costs of earliness and tardiness. Recently, Janiak et al. [9] considered various models of due window assignment scheduling problems on a single machine such that the objective function including the maximum or total earliness and tardiness and the due window parameters is minimized. They constructed polynomial algorithms for the considered problems. Wang and Wang [22] explored a single machine common due window scheduling problem simultaneously with the learning effect and deteriorating jobs considerations. Cheng et al. [4] investigated a common due window assignment scheduling with linear time-dependent deteriorating jobs and a deteriorating maintenance on a single machine setting. They showed that the proposed model is polynomial solvable. Yang et al. [25] first proposed the multiple due windows assignment scheduling problem with controllable processing times, in which $n$ jobs may have distinct $m$ due windows, where $1\le m\le n$. The objective is to determine the optimal due window positions and sizes, the set of jobs assigned to each due window, the optimal job compressions, and the optimal schedule to minimize a total cost function, which consists of the earliness, the tardiness, the processing time compressions, and the due windows related costs. For the detailed research results on scheduling with due window, the reader may refer to Mor and Mosheiov [16], Yin et al. [30], Chen et al. [3], Ji et al. [11], and Yin et al. [31].

Additionally, an important issue of scheduling problems is characterized by the group technology (GT) assumption. The GT method groups products with similar characteristics into families and sets aside groups of machines for their production. Families may be based on size, shape, geometry, manufacturing requirements and so on. Through decades of application, people have found many advantages of GT. For instance, jobs in the same group tend to move through production in a direct route, reducing the manufacturing lead time; changeover among different jobs in the same group is simplified, reducing the costs or time involved (Ji et al. [10], Li et al. [14]). As a realistic example of GT, Conway et al. [5] stressed paint production on a single machine. Customer orders vary in colors, but they can be divided into several major color groups, such as red, blue, and green. Within a color group, red, for example, colors may range from very light to dark red. The setup time of the machine to produce paint in colors of the same group is small and can be neglected, since it is natural to produce paint from lighter to darker colors. While the time to switch the machine from the production of paint of one color group to another color group is substantial, which may include the time to clean the machine and change the tools, and the setup time is color-independent in general. Another example can be found in the metal or wood cutting process, the process need to cut various sizes and shapes of product, the products with similar shape or manufacturing requirements are grouping as a product family and the cutting tools used to process the individual product family are grouping as a machine family. Thus, it is clear that dividing the orders into groups according to their processing similarities can significantly increase the production efficiency. Chen et al. [2] considered single machine scheduling with common due date assignment in a group technology environment. The objective is to find an optimal common due date and an optimal sequence of jobs to minimize the sum of the cost of tardy jobs and the cost related to the common due date. Ng et al. [17] explored group scheduling with controllable setup and processing times, the objective is to minimize the total weighted completion time. Wang et al. [20] studied single machine scheduling problems with GT and deteriorating jobs. The job processing time is a decreasing function of its starting time. The objectives are to minimize the makespan and the total completion time. They provided polynomial time algorithms to solve these problems. Shabtay et al. [18] argued that single machine scheduling with optimal due date assignment and resource allocation in a group technology environment. They gave a polynomial algorithm for the considered problem in which each job has a constant processing time, and when jobs have controllable processing times, the complexity of this problem remains an open question. Ji et al. [10] assessed a single-machine group scheduling and job-dependent due window assignment problem in which each job is assigned an individual due window based on a common flow allowance. The goal is to find the optimal sequence for both groups and jobs, together with the optimal due window assignment, to minimize the total cost that comprises the earliness and tardiness penalties, the due window starting time and due window size costs. Apart from above, the reader may refer to the following literatures for a detailed comprehension of group scheduling problem: Ham et al. [7], Li et al. [14], Yang [26], Yang and Yang [29], Zhu et al. [34], Wang et al. [21], Low and Lin [15], Zhang [32], and Xu et al. [24].

Although the due date and due window assignment in JIT scheduling have been extensively investigated in the literature, there are only a few researches on JIT scheduling problem with multiple due dates, especially multiple due windows assignment. Moreover, the multiple due dates and multiple due windows assignment scheduling problems under a GT restriction have never been explored. The group scheduling problems with due date assignment that jobs within the same group are assigned to a common due date and each job within the same group is assigned to a different due date with no restrictions have been studied by Li et al. [14]. Actually, however, jobs within the same group may have not only one due date because of the different needs of customers or other special reasons. Then to consider the case that jobs within the same group $G_i$ have $z_i$ distinct due dates can meet the actual needs better, where $1\le z_i \le n_i$, and $n_i$ is the number of jobs in group $G_i$. If $z_i =1$, it means that all jobs in the same group have one common due date; if $z_i =n_i$, it indicates that each job within the same group is assigned to a different due date. Obviously it is an extension of Li et al. [14]. This paper will further expand the due date problem into the due window problem. That is, jobs within the same group $G_i$ have $z_i$ distinct due windows, $1\le z_i \le n_i$. The extension allows for greater flexibility in modeling real-life problems. For example, in an order picking operation process, the number of orders to be completed may be too great to realistically justify measurement from a single due window for a single customer. By viewing the order picking operation process as being composed of several discrete segments, each team of orders could be made uniform around its own due window. The orders should be ready at their due window in order to avoid staging delays. Moreover, a higher cost in the form of transship fee generally accompanies a later due window (Yang et al. [25]).

In this paper, we consider scheduling problem on a single machine with multiple due windows assignment in a group technology. We seek to determine the optimal group sequence, the optimal job sequence, and the optimal due windows assignment to minimize the total of earliness, tardiness and the due windows related costs.

The remainder of this paper is organized as follows: In Sect. 2 we introduce the notation and formulate the problem. In Sect. 3 we study the group scheduling problem with multiple due windows assignment. Finally, conclusions are given in the last Section.

2 Problem formulation

The following notations will be used throughout the paper and we will introduce additional notations when needed.

$n:$ :

the total number of jobs;

$m:$ :

the total number of groups, $1\le m\le n$;

$n_i:$ :

the number of jobs in group $G_i$, $i=1,2,\ldots ,m$, and ${\sum }_{i=1}^m {n_i } =n$;

$s_i:$ :

the setup time of group $G_i$;

$p_{ij}:$ :

the processing time of job $J_j$ of group $G_i$;

$p_{i[j]}:$ :

the processing time of job in the $j$th position of group $G_i$, $i=1,2,\ldots ,m,\,j=1,2,\ldots ,n_i;$

$z_i:$ :

the number of due windows assigned to the $n_i$ jobs of group $G_i$, $1\le z_i \le n_i$;

$I_{ik}:$ :

the set of jobs assigned to the $k$th due window in group $G_i$, $k=1,2,\ldots ,z_i , i=1,2,\ldots ,m;$

$n_{ik}:$ :

the number of jobs assigned to the $k$th due window in group $G_i$, i.e., $\left| {I_{ik} } \right| =n_{ik}$ and ${\sum }_{k=1}^{z_i } {n_{ik} } =n_i$;

$N_{ik}:$ :

the total number of jobs assigned to the first $k$ due windows in group $G_i$, i.e., ${\sum }_{j=1}^k {n_{ij} } =N_{ik}$ for $k=1,2,\ldots ,z_i$, $i=1,2,\ldots ,m$, and $N_{i0} =0$.

The problem under consideration is formulated as follows. We are given $n$ independent and non-preemptive jobs that are classified into $m$ groups $G_1 ,G_2 ,\ldots ,G_m$. Each group $G_i$, for $i=1,2,\ldots ,m$, has $n_i$ jobs $\{J_{i1} ,J_{i2} ,\ldots ,J_{in_i } \}$, where ${\sum }_{i=1}^m {n_i } =n$. Jobs of the same group are required to be processed contiguously. A sequence-independent machine setup time $s_i$ precedes the processing of the first job of group $G_i$. All jobs are simultaneously available for processing at time zero.

Let $d_{ik} (\ge 0)$ and $w_{ik} (\ge d_{ik})$ denote the starting time and finishing time of the $k$ th due window in group $G_i$, respectively. $S_{ik} =w_{ik} -d_{ik}$ denotes the size of the $k$ th due window in group $G_i$ for $k=1,2,\ldots ,z_i$, $i=1,2,\ldots ,m$. We assume that the number of distinct due windows $z_i$ assigned to group $G_i$ ($i=1,2,\ldots ,m)$ is given in advance, and $n_{ik}$, for $k=1,2,\ldots ,z_i$, is known. If $z_i =1$, it means that all the jobs in group $G_i$ have one common due window; If $z_i =n_i$, it indicates that there exists $n_i$ distinct due windows for $n_i$ jobs in group $G_i$. The earliness and tardiness of job $J_{ij} \in I_{ik}$ are $E_{ij} =\max \{0,d_{ik} -C_{ij} \}$ and $T_{ij} =\max \{0,C_{ij} -w_{ik} \}$, respectively. The objective is to find the optimal group sequence, the optimal job sequence, and the optimal due window assignment to minimize the following total cost function

$$\begin{aligned} g(\pi )=\sum \nolimits _{i=1}^m {\sum \nolimits _{l=1}^{n_i } {\big (\alpha _i E_{il} +\beta _i T_{il} +\gamma _i d_{il} +\delta _i S_{il} \big )} } \end{aligned}$$

(1)

where $\alpha _i , \beta _i , \gamma _i , \delta _i$ are non-negative parameters representing the unit time costs of earliness, tardiness, due window starting time and due window size, respectively.

Using the three-field notation, the considered problem can be described as

$$\begin{aligned} 1 \left| { GT,MDW } \right| \sum \nolimits _{i=1}^m {\sum \nolimits _{l=1}^{n_i } {\big (\alpha _i E_{il} +\beta _i T_{il} +\gamma _i d_{il} +\delta _i S_{il} \big )} }, \end{aligned}$$

where $MDW$ means the multiple due windows.

3 Group scheduling with multiple due windows

In this section, we study the scheduling problem with multiple due windows assignment under a GT restriction, i.e., $1 \left| { GT,MDW } \right| {\sum }_{i=1}^m {\sum }_{l=1}^{n_i } (\alpha _i E_{il} +\beta _i T_{il} +\gamma _i d_{il} +\delta _i S_{il} )$

3.1 Preliminary results

Some useful lemmas are given in this subsection to solve the group scheduling problem with multiple due windows.

Lemma 1

In an optimal schedule, there exists no idle time between consecutive jobs on the machine and the first job starts at time zero.

Proof

The proof is obvious and omitted. $\square$

Lemma 2

Given two sequences of non-negative numbers $x_i$ and $y_i$, the sum of the products of the corresponding elements ${\sum }_{i=1}^n {x_i } y_i$ is minimized if the sequences are monotonic in the opposite way.

Proof

See Hardy et al. [8]. $\square$

The following Lemma 3 indicates that for an optimal sequence, the jobs assigned to different due windows are mutually disjoint, that is, there is an optimal solution such that $n_{ik}$ consecutive jobs (in positions $N_{i(k-1)} +1$ to $N_{ik} )$ in a sequence $\pi$ are assigned to the $k$ th due window in group $G_i$.

Lemma 3

For any given $d_i =\{d_{i1} ,d_{i2} ,\ldots ,d_{iz_i } \}$, $w_i =\{w_{i1} ,w_{i2} ,\ldots ,w_{iz_i } \}$ in group $G_i$, $i=1,2,\ldots ,m$, and a schedule $\pi$, there exists an optimal $I_i$ such that $I_{ik} =\{J_{i[N_{i(k-1)} +1]} , \quad J_{i[N_{i(k-1)} +2]} ,\ldots ,J_{i[N_{ik} ]} \}$ for $k=1,2,\ldots ,z_i$, where $J_{i[r]}$ is the job scheduled in position $r$ in group $G_i$.

Proof

For any given $d_i$, $w_i$ and $\pi$, $i=1,2,\ldots ,m$, without loss of generality, we assume that in a schedule $S_1 =(\pi _1 , J_k , J_j , \pi _2 )$ job $J_k$ immediately precedes job $J_j$, while in another schedule $S_2 =(\pi _1 , J_j , J_k , \pi _2 )$ jobs $J_k$ and $J_j$ are mutually replaced, where $\pi _1$ and $\pi _2$ denote partial sequences and jobs $J_k$ and $J_j$ are, respectively, scheduled in the $h$ th and $(h+1)$ th position in group $G_i$ in the schedule $S_1$. In addition, we assume that for both schedules $S_1$ and $S_2$, $J_k$ is early for the $(r+1)$ th due window in group $G_i$, and $J_j$ is tardy for the $r$ th due window in group $G_i$, where $J_k \in I_{i(r+1)}$ and $J_j \in I_{ir}$.

Let $C_{il} (S_1 )$ and $C_{il} (S_2 )$ be the completion times of job $J_l$ in group $G_i$ in schedule $S_1$ and $S_2$, respectively. And $S_i (\pi )$ denotes the starting time of group $G_i$. By the definition, the completion times of jobs $J_k$ and $J_j$ in $S_1$ are

$$\begin{aligned} C_{ik} (S_1 )=S_i (\pi )+s_i +\sum \nolimits _{l=1}^{h-1} {p_{i[l]} } +p_k \end{aligned}$$

(2)

and

$$\begin{aligned} C_{ij} (S_1 )=S_i (\pi )+s_i +\sum \nolimits _{l=1}^{h-1} {p_{i[l]} } +p_k +p_j \end{aligned}$$

(3)

Similarly, the completion times of jobs $J_k$ and $J_j$ in $S_2$ are

$$\begin{aligned} C_{ij} (S_2 )=S_i (\pi )+s_i +\sum \nolimits _{l=1}^{h-1} {p_{i[l]} } +p_j \end{aligned}$$

(4)

and

$$\begin{aligned} C_{ik} (S_2 )=S_i (\pi )+s_i +\sum \nolimits _{l=1}^{h-1} {p_{i[l]} } +p_j +p_k \end{aligned}$$

(5)

Then,

$$\begin{aligned} g(S_1 )-g(S_2 )&=\left\{ {\alpha _i \big [d_{i(r+1)} -C_{ik} (S_1 )\big ]+\beta _i \big [C_{ij} (S_1 )-w_{ir}\big ]}\right\} \\&\quad -\left\{ \alpha _i \big [d_{i(r+1)} -C_{ik} (S_2)\big ] +{\beta _i \big [C_{ij} (S_2 )-w_{ir} \big ]} \right\} \\&=\alpha _i p_j +\beta _i p_k \\&>0 \end{aligned}$$

Obviously,

$$\begin{aligned} g(S_1 )>g(S_2 ). \end{aligned}$$

Similarly, the total cost decreases as repeating this interchange argument for the jobs which assigned to the same due window are not sequenced consecutively. This completes the proof. $\square$

Lemma 4

For a given schedule $\pi$, if the due window starting time $d_{ik}$ and finishing time $w_{ik}$ are within the starting and ending times of group $G_i$, then the optimal values of $d_{ik}$ and $w_{ik}$ coincide with some jobs’ completion times of group $G_i$ for $k=1,2,\ldots ,z_i$, $i=1,2,\ldots ,m$.

Proof

Assume that $d_{ik} =S_i (\pi )+s_i +{\sum }_{l=1}^{b_{ik} } {p_{i[l]} }$, $w_{ik} =S_i (\pi )+s_i +{\sum }_{l=1}^{b_{ik} +h_{ik} } {p_{i[l]} }$, $k=1,2,\ldots ,z_i$, $i=1,2,\ldots ,m$, where $b_{ik}$ and $b_{ik} +h_{ik}$ mean the $b_{ik}$ th and $(b_{ik} +h_{ik} )$ th positions of group $G_i$, respectively. We only address $G_i$ here as an example to demonstrate that the result is correct. Consider that there exists an optimal schedule without the stated property, without loss of generality, suppose that there exists $k=r,\;1\le r\le z_i$ such that

$$\begin{aligned} d_{ir} =S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} } {p_{i[l]} } +\Delta _1 , \quad 0\le \Delta _1 \le p_{i[b_{ir} +1]} , \end{aligned}$$

and

$$\begin{aligned} w_{ir} =S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} +h_{ir} } {p_{i[l]} } +\Delta _2 ,\quad 0\le \Delta _2 \le p_{i[b_{ir} +h_{ir} +1]} . \end{aligned}$$

Note that moving $d_{ir}$ and $w_{ir} \quad \Delta$ units of time only change the cost of jobs assigned to the $r$ th due window in group $G_i$.

The total cost of jobs assigned to the $r$ th due window in group $G_i$ as a function of $\Delta _1$ and $\Delta _2$ is given by

$$\begin{aligned} g_{ir} (\Delta _1 ,\Delta _2 )&= \alpha _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {E_{i[l]} } +\beta _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {T_{i[l]} } +\gamma _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {d_{i[l]}}\\&+\delta _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {S_{i[l]} } \end{aligned}$$

We consider each cost component separately as follows:

• (a)
  $$\begin{aligned} \alpha _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {E_{i[l]} }&= \alpha _i \sum \nolimits _{l=N_{i(r-1)} +1}^{b_{ir} } {E_{i[l]} } =\alpha _i \sum \nolimits _{l=N_{i(r-1)} +1}^{b_{ir} } {(d_{ir} } -C_{i[l]} )\\&= \alpha _i \left\{ {\left[ {\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} } {p_{i[l]} +\Delta _1 } } \right) -} \right. } \right. \left. {\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{N_{i(r-1)} +1} {p_{i[l]} } } \right) } \right] \\&\quad +\left[ {\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} } {p_{i[l]} +\Delta _1 } } \right) } \right. -\left. {\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{N_{i(r-1)} +2} {p_{i[l]} } } \right) } \right] \\&\quad +\cdots \\&\quad \left. {+\left[ {\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} } {p_{i[l]} +\Delta _1 } } \right) } \right. -\left. {\left( {S_i (\pi )+s_i +{\sum }_{l=1}^{b_{ir} } {p_{i[l]} } } \right) } \right] } \right\} \\&= \alpha _i \sum \nolimits _{l=N_{i(r-1)} +1}^{b_{ir} } {(l-N_{i(r-1)} -1)p_{i[l]} } +\alpha _i (b_{ir} -N_{i(r-1)} )\Delta _1 \end{aligned}$$
• (b)
  $$\begin{aligned} \beta _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {T_{i[l]} }&= \beta _i \sum \nolimits _{l=b_{ir} +h_{ir} +1}^{N_{ir} } {T_{i[l]} } =\beta _i \sum \nolimits _{l=b_{ir} +h_{ir} +1}^{N_{ir} } ( C_{i[l]} -w_{ir} )\\&= \beta _i \left\{ {\left[ {\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} +h_{ir} +1} {p_{i[l]} } } \right) -} \right. } \right. \left. {\left( {S_i (\pi )+s_i \!+\!\sum \nolimits _{l=1}^{b_{ir} \!+\!h_{ir} } {p_{i[l]} \!+\!\Delta _2 } } \right) } \right] \\&\quad +\left[ {\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} +h_{ir} +2} {p_{i[l]} } } \right) -\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} +h_{ir} } {p_{i[l]} +\Delta _2 } } \right) } \right] \\&\quad +\cdots \\&\quad \left. {+\left[ {\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{N_{ir} } {p_{i[l]} } } \right) -\left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} +h_{ir} } {p_{i[l]} +\Delta _2 } } \right) } \right] } \right\} \\&= \beta _i \sum \nolimits _{l=b_{ir} +h_{ir} +1}^{N_{ir} } {(N_{ir} -l+1)p_{i[l]} } -\beta _i (N_{ir} -b_{ir} -h_{ir} )\Delta _2 \end{aligned}$$
• (c)
  $$\begin{aligned} \gamma _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {d_{i[l]} }&= \gamma _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {d_{ir} }\\&= \gamma _i n_{ir} \left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ir} } {p_{i[l]} +\Delta _1 } } \right) \\&= \gamma _i n_{ir} \sum \nolimits _{l=1}^{b_{ir} } {p_{i[l]} } +\gamma _i n_{ir} \left( {S_i (\pi )+s_i } \right) +\gamma _i n_{ir} \Delta _1 \end{aligned}$$
• (d)
  $$\begin{aligned} \delta _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {S_{i[l]} }&= \delta _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {\big (d_{i[l]} -w_{i[l]}\big )} =\delta _i \sum \nolimits _{l=N_{i(r-1)} +1}^{N_{ir} } {\big (d_{ir} -w_{ir} \big )}\\&=\delta _i n_{ir} \left[ \left( {S_i (\pi )\!+\!s_i \!+\!\sum \nolimits _{l=1}^{b_{ir} +h_{ir} } {p_{i[l]} \!+\!\Delta _2 }}\right) -\left( {S_i (\pi )+s_i }\!+\!\sum \nolimits _{l=1}^{b_{ir} } {p_{i[l]} } \!+\!\Delta _1\right) \right] \\&= \delta _i n_{ir} \sum \nolimits _{l=b_{ir} +1}^{b_{ir} +h_{ir} } {p_{i[l]}} +\delta _i n_{ir} (\Delta _2 -\Delta _1) \end{aligned}$$

Therefore the total cost can be expressed as

$$\begin{aligned} g_{ir} (\Delta _1 ,\Delta _2 )=A\Delta _1 +B\Delta _2 +C, \end{aligned}$$

Where $A=\alpha _i (b_{ir} -N_{i(r-1)} )+\gamma _i n_{ir} -\delta _i n_{ir}$, $B=\delta _i n_{ir} -\beta _i (N_{ir} -b_{ir} -h_{ir} )$, and

$$\begin{aligned} C&= \sum \nolimits _{l=1}^{N_{i(r-1)} } {\gamma _i n_{ir} p_{i[l]} } +\sum \nolimits _{l=N_{i(r-1)} +1}^{b_{ir} } {\left[ {\gamma _i n_{ir} +\alpha _i (l-N_{i(r-1)} -1)} \right] p_{i[l]} }\\&\!+\!\sum \nolimits _{l=b_{ir} +1}^{b_{ir} +h_{ir} } {\delta _i n_{ir} p_{i[l]} } \!+\!\sum \nolimits _{l=b_{ir} +h_{ir} +1}^{N_{ir} } {\beta _i (N_{ir} -l+1)p_{i[l]} } +\gamma _i n_{ir} \left( {S_i (\pi )+s_i } \right) \end{aligned}$$

Clearly, $A,\;B$ and $C$ are independent of $\Delta _1$ and $\Delta _2$. We can see that $f_{ir} (\Delta _1 ,\Delta _2 )$ is a linear function of $\Delta _1$ and $\Delta _2$. Thus we can either decrease $\Delta _1$ and $\Delta _2$ to zero, or increase them to $p_{i[b_{ir} +1]}$ and $p_{i[b_{ir} +h_{ir} 1]}$, respectively, to obtain a lower cost. In any case, we can see that $d_{ik}$ and $w_{ik}$ coincide with some jobs’ completion times of group $G_i$. $\square$

Lemma 5

For any given $I=\{I_{11} ,\ldots ,I_{1z_1 } ,I_{21} ,\ldots ,I_{2z_2 } ,\ldots ,I_{m1} ,\ldots ,I_{mz_m } \}$ and a schedule $\pi$, if the values of $d_{ik}$ and $w_{ik}$ are within the starting time and ending times of group $G_i$, $k=1,2,\ldots ,z_i$, $i=1,2,\ldots ,m$, then there exists optimal due windows such that $d_{ik} =C_{i[b_{ik} ]}$ and $w_{ik} =C_{i[b_{ik} +h_{ik} ]}$, where

$$\begin{aligned} b_{ik} =N_{i(k-1)} +\left\lceil {\frac{n_{ik} (\delta _i -\gamma _i )}{\alpha _i }} \right\rceil \mathrm{{and }}\,\, b_{ik} +h_{ik} =N_{i(k-1)} +\left\lceil {\frac{n_{ik} (\beta _i -\delta _i )}{\beta _i }} \right\rceil . \end{aligned}$$

Proof

This lemma can be easily proved by the standard technique of small perturbations. Without loss of generality, we only consider group $G_i$ here as an example to demonstrate that the result is correct. Suppose that $k=r,\;1\le r\le z_i$, $d_{ir} =C_{i[b_{ir} ]}$ and $w_{ir} =C_{i[b_{ir} +h_{ir} ]}$. The effect of moving $d_{ik} \quad \Delta$ units of time to the left is

$$\begin{aligned} -\alpha _i \big (b_{ir} -N_{i(r-1)} -1\big )\Delta -\gamma _i n_{ir} \Delta +\delta _i n_{ir} \Delta \end{aligned}$$

(6)

The effect of moving $d_{ik} \quad \Delta$ units of time to the right is

$$\begin{aligned} \alpha _i \big (b_{ir} -N_{i(r-1)}\big )\Delta +\gamma _i n_{ir} \Delta -\delta _i n_{ir} \Delta \end{aligned}$$

(7)

Both (6) and (7) are non-negative due to the optimality of the original schedule. Then from $-\alpha _i (b_{ir} -N_{i(r-1)} -1)\Delta -\gamma _i n_{ir} \Delta +\delta _i n_{ir} \Delta \ge 0$ and $\alpha _i (b_{ir} -N_{i(r-1)} )\Delta +\gamma _i n_{ir} \Delta -\delta _i n_{ir} \Delta \ge 0$, we have $b_{ik} \le N_{i(k-1)} +{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }+1$ and $b_{ik} \ge N_{i(k-1)} +{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }$. By Lemma 4, we know that $b_{ik}$ is an integer, therefore, $b_{ik}$ is the smallest integer greater than or equal to $N_{i(k-1)} +\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$, i.e., $b_{ik} =N_{i(k-1)} +\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$. Using the same method, we obtain $b_{ik} +h_{ik} =N_{i(k-1)} +\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$. $\square$

Remarks

For any given $I=\{I_{11} ,\ldots ,I_{1z_1 } ,I_{21} ,\ldots ,I_{2z_2 } ,\ldots ,I_{m1} ,\ldots ,I_{mz_m } \}$ and a schedule $\pi$, if $0<\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil <\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$, we can determine the optimal due window assignments for a group by Lemmas 4 and 5. But the ratios may not meet the above inequality, e.g., for the given parameters, there may exist inequality $\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil \le \left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$, then we need further analysis. Note that $\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil \le \left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$ means ${n_{ik} (\beta _i -\delta _i )}/{\beta _i }{\le n_{ik} (\delta _i -\gamma _i )}/{\alpha _i}$.

Similar to the analysis of Ji et al. [10], we have the following discussion.

• (i) With a shift of $d_{ik}$ (without changing $w_{ik} )$ by $\Delta$ units of time to the right, resulting in a change of total costs of $\Delta g=\alpha _i (b_{ik} -N_{i(k-1)} )\Delta +\gamma _i n_{ik} \Delta -\delta _i n_{ik} \Delta$ . With a shift of $w_{ik}$ (without changing $d_{ik} )$ by $\Delta$ units of time to the right, resulting in a change of total costs of $\Delta g=\delta _i n_{ik} \Delta -\beta _i (N_{ik} -b_{ik} -h_{ik} )\Delta$.

If $b_{ik} +h_{ik} <N_{i(k-1)} +{n_{ik} (\beta _i -\delta _i )}/{\beta _i }$, a shift of $w_{ik}$ by $\Delta$ units of time to the right till $b_{ik} +h_{ik} =N_{i(k-1)} +\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$ can only reduce the total cost. If $b_{ik} < N_{i(k-1)} +{n_{ik} (\beta _i -\delta _i )}/{\beta _i }$, then $b_{ik} <N_{i(k-1)} +{n_{ik} (\beta _i -\delta _i )}/{\beta _i }\le N_{i(k-1)} +{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }$, so a shift of $d_{ik}$ by $\Delta$ units of time to the right till $b_{ik} =N_{i(k-1)} +\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$ can only reduce the total cost.

• (ii) With a shift of $d_{ik}$ (without changing $w_{ik}$) by $\Delta$ units of time to the left, resulting in a change of total costs of $\Delta g=-\alpha _i (b_{ik} -N_{i(k-1)} -1)\Delta -\gamma _i n_{ik} \Delta +\delta _i n_{ik} \Delta$. With a shift of $w_{ik}$ (without changing $d_{ik}$) by $\Delta$ units of time to the left, resulting in a change of total costs of $\Delta g=\beta _i (N_{ik} -b_{ik} -h_{ik} +1)\Delta -\delta _i n_{ik} \Delta$.

If $b_{ik} >N_{i(k-1)} +{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }+1$, a shift of $d_{ik}$ by $\Delta$ units of time to the left till $b_{ik} =N_{i(k-1)} +\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$ can only reduce the total cost. If $b_{ik} +h_{ik} >N_{i(k-1)} + {n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }+1,$ then $b_{ik} +h_{ik} >N_{i(k-1)} +{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }+1\ge N_{i(k-1)} +{n_{ik} (\beta _i -\delta _i )}/{\beta _i }$ $+1,$ so a shift of $w_{ik}$ by $\Delta$ units of time to the left till $b_{ik} +h_{ik} =N_{i(k-1)} +\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$ can only reduce the total cost.

Form (i) and (ii), we can see that

$$\begin{aligned} N_{i(k-1)} +\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil \le b_{ik} \le b_{ik} +h_{ik} \le N_{i(k-1)} +\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil , \end{aligned}$$

if $b_{ik} <b_{ik} +h_{ik}$, a further shift of $d_{ik}$ to the right and a further shift of $w_{ik}$ to the left till $b_{ik} =b_{ik} +h_{ik}$ can only reduce the total cost, which means that $d_{ik} =w_{ik}$,$k=1,2,\ldots ,z_i$. And the multiple due windows assignment problem reduces to the multiple due dates assignment problem. Then we have the following Lemma 6.

Lemma 6

If $\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil \le \left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$ for $i\in \{1,2,\ldots ,m\}$, then the multiple due windows assignment problem reduces to the multiple due dates assignment problem. The optimal due date assignment is given as follows. For any $k=1,2,\ldots ,z_i$,

$$\begin{aligned} D_{ik} =\left\{ \begin{array}{lll} C_{i[b_{ik}]} \quad \mathrm{{where } }~b_{ik} =N_{i(k-1)} +\left\lceil {\frac{n_{ik} (\beta _i -\gamma _i )}{\alpha _i +\beta _i }}\right\rceil \, \mathrm{{ if }}~\beta _i >\gamma _i ,\\ 0 \quad \mathrm{{ otherwise}}.\\ \end{array}\right. \end{aligned}$$

(8)

Where $D_{ik}$ represents the due date of job $J_{ik}$.

Proof

When all jobs belong to a single group and setup time equals to zero, Chand and Chhajed [1] showed that there exists an optimal schedule for $1 \left| { MD } \right| {\sum }_{i=1}^m {\sum }_{J_j \in I_i } (\alpha E_j +\beta T_j +\gamma D_i )$ in which the due date can be assigned according to (8), where $MD$ means the multiple due dates. Because their proof is independent of the job distribution on the time axis, the result can immediately be generalized to the problem $1 \left| { GT,MD } \right| {\sum }_{i=1}^m {{\sum }_{l=1}^{n_i } {(\alpha _i E_{il} +\beta _i T_{il} +\gamma _i D_{il} )} }$. Then the above lemma holds.

From Lemma 6, without loss of generality, we only consider the case $\left\lceil {n_{ik} (\delta _i -\gamma _i )}\right. /\left. {\alpha _i } \right\rceil <\left\lceil {n_{ik} (\beta _i -\delta _i )}/{\beta _i } \right\rceil$ in the following Lemmas 7 and 8. $\square$

Lemma 7

If $\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil \le 0<\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$, the problem becomes a special due window assignment problem, with $d_{ik} =0$, $w_{ik} =S_i (\pi )+s_i +{\sum }_{l=1}^{b_{ik} +h_{ik} } {p_{i[l]} }$, and $b_{ik} +h_{ik} =N_{i(k-1)} +\left\lceil {\frac{n_{ik} (\beta _i -\delta _i )}{\beta _i }} \right\rceil$.

Proof

If $\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil \le 0$, meaning $\delta _i \le \gamma _i$, then a shift of $d_{ik}$ by $\Delta$ units of time to the left will result in a change of the total cost $\Delta f\le 0$, so result $d_{ik}$ can be shifted to the left until it equals time zero. Using the same analytical method of Lemmas 4 and 5, we can get the result about $w_{ik}$. $\square$

Lemma 8

If $\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil <\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil \le 0$ for $i\in \{1,2,\ldots ,m\}$, then the multiple due windows assignment problem also reduces to the multiple due dates assignment problem. And for any $k=1,2,\ldots ,z_i$, the due date $D_{ik} =0$.

Proof

If $\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil <\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil \le 0$, which means $\beta _i \le \delta _i \le \gamma _i$, then a shift of $w_{ik}$ by $\Delta$ units of time to the left until $d_{ik}$ will result in a change of the total cost $\Delta f\le 0$, so $w_{ik}$ can be shifted to $d_{ik}$, and the multiple due windows assignment problem reduces to the multiple due dates assignment problem. Since $\beta _i \le \gamma _i$, according to (8), we can get the result that $D_{ik} =0$, for $k=1,2,\ldots ,z_i$.

From Lemmas 4–8, according to the ratios of $\left\lceil {{n_{ik} (\delta _i \!-\!\gamma _i )}/{\alpha _i }} \right\rceil$ and $\left\lceil {{n_{ik} (\beta _i \!-\!\delta _i )}/{\beta _i }} \right\rceil$, there exist three cases:

• Case 1.1: $0<\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil <\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$. This will be the normal multiple due windows assignment problem, which can be determined by Lemmas 4 and 5.

• Case 1.2: $\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil \le 0<\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$. This is a special multiple due windows assignment problem, which can be determined by Lemma 7.

• Case 1.3: $\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil \le \left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$ or $\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil <\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$ $\le 0.$ The problem reduces to the multiple due dates assignment problem, which can be determined by Lemmas 6 and 8.

$\square$

Lemma 9

For any given sequence $\pi$, the cost function of all jobs within group $G_i$ under the optimal due windows assignment strategy of Case 1.1, denoted by $d_i^*(\pi )=\{d_{i1}^*,d_{i2}^*,\ldots ,d_{iz_i }^*\}$ and $w_i^*(\pi )=\{w_{i1}^*,w_{i2}^*,\ldots ,w_{iz_i }^*\}$, can be expressed as follows:

$$\begin{aligned} g_i \big (\pi ,d_i^*(\pi ),w_i^*(\pi )\big )=\sum \nolimits _{l=1}^{n_i} {w_{il}\,p_{i[l]} } +n_i \gamma _i \big (S_i (\pi )+s_i \big ) \end{aligned}$$

(9)

Where

$$\begin{aligned} w_{il} =\left\{ {{\begin{array}{ll} \alpha _i (l-N_{i(k-1)} -1)+\gamma _i (n_i -N_{i(k-1)} ),&{}\quad N_{i(k-1)} +1\le l\le b_{ik}\\ n_{ik} \delta _i +\gamma _i (n_i -N_{ik} ), &{}\quad b_{ik} +1\le l\le b_{ik} +h_{ik} \\ \beta _i (N_{ik} -l+1)+\gamma _i (n_i -N_{ik} ), &{} \quad b_{ik} +h_{ik} +1\le l\le N_{ik} \end{array} }} \right. \end{aligned}$$

(10)

Proof

Let $\pi$ be a given job sequence, and group $G_i$ with Case 1.1, the optimal $d_{ik}^*$ and $w_{ik}^*$ for $k=1,2,\ldots ,z_i$, can be determined by Lemma 5. Then for any $k\in \{1,2,\ldots ,z_i \}$, we have

$$\begin{aligned} E_{i[l]}&= \sum \nolimits _{j=l+1}^{b_{ik} } {p_{i[j]} }~\mathrm{{ for }}~ N_{i(k-1)} +1\le l\le b_{ik} -1, E_{i[l]} =0~\mathrm{{ for }}~b_{ik} \le l\le N_{ik}.\\ T_{i[l]}&= 0~\mathrm{{ for }}~N_{i(k-1)} +1\le l\le b_{ik} +h_{ik} , \quad T_{i[l]} = \sum \nolimits _{j=b_{ik} +h_{ik} +1}^l {p_{i[j]} }\quad \mathrm{{ for }}~ b_{ik}\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad +h_{ik} +1\le l\le N_{ik}.\\ d_{i[l]}&= d_{ik} =C_{i[b_{ik} ]} =S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ik} } {p_{i[l]} }\quad \mathrm{{ for }}~N_{i(k-1)} +1\le l\le N_{ik}.\\ w_{i[l]}&= w_{ik} =C_{i[b_{ik} +h_{ik} ]} =S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ik} +h_{ik} } {p_{i[l]} }\quad \mathrm{{ for }}~N_{i(k-1)} +1\le l\le N_{ik} .\\ S_{i[l]}&= w_{i[l]} -d_{i[l]} =w_{ik} -d_{ik} =\sum \nolimits _{l=b_{ik} +1}^{b_{ik} +h_{ik} } {p_{i[l]} }~\mathrm{{ for }}~N_{i(k-1)} +1\le l\le N_{ik}. \end{aligned}$$

Then the cost function of all the cost function of all jobs within group $G_i$ can be written as follows:

$$\begin{aligned}&g_i \big (\pi ,d_i^*(\pi ),w_i^*(\pi )\big ) = \sum \nolimits _{k=1}^{z_i } {\sum \nolimits _{l=N_{i(k-1)} +1}^{N_{ik} } {\big (\alpha _i E_{i[l]} +\beta _i T_{i[l]} +\gamma _i d_{i[l]} +\delta _i S_{i[l]} \big )} }\\&\quad = \sum \nolimits _{k=1}^{z_i } {\left[ \sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {\left( {\alpha _i \sum \nolimits _{j=l+1}^{b_{ik} } {p_{i[j]} } } \right) } \right. +\sum \nolimits _{l=b_{ik} +h_{ik} +1}^{N_{ik} } {\left( {\beta _i \sum \nolimits _{j=b_{ik} +h_{ik} +1}^l {p_{i[j]} } } \right) } }\\&\qquad \left. {+n_{ik} \gamma _i \left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{N_{i(k-1)} } {p_{i[l]} +\sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {p_{i[l]} } } } \right) +n_{ik} \delta _i \sum \nolimits _{l=b_{ik} +1}^{b_{ik} +h_{ik} } {p_{i[l]} } } \right] \\&\quad = \sum \nolimits _{k=1}^{z_i } {\left[ {\sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {\alpha _i (l-N_{i(k-1)} -1)p_{i[l]} } } \right. +\sum \nolimits _{l=b_{ik} +h_{ik} +1}^{N_{ik} } {\beta _i (N_{ik} -l} } +1)p_{i[l]}\\&\qquad +n_{ik} \gamma _i \left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{N_{i(k-1)} } {p_{i[l]} } } \right) +n_{ik} \gamma _i \sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {p_{i[l]} } +\left. {n_{ik} \delta _i \sum \nolimits _{l=b_{ik} +1}^{b_{ik} +h_{ik} } {p_{i[l]} } } \right] \\&\quad = \sum \nolimits _{k=1}^{z_i } {\left\{ {\sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {\left[ {\alpha _i (l-N_{i(k-1)} -1)+\gamma _i (n_i -N_{i(k-1)} )} \right] } } \right. p_{i[l]} }\\&\qquad \!+\!\sum \nolimits _{l=b_{ik} +1}^{b_{ik} \!+\!h_{ik} } {\left[ {n_{ik} \delta _i \!+\!\gamma _i (n_i \!-\!N_{ik} )} \right] p_{i[l]} } \left. {+\sum \nolimits _{l=b_{ik} \!+\!h_{ik} +1}^{N_{ik} } {\left[ {\beta _i (N_{ik} -l+1)\!+\!\gamma _i (n_i \!-\!N_{ik} )} \right] p_{i[l]} } } \right\} \\&\qquad +n_i \gamma _i \left( {S_i (\pi )+s_i } \right) \end{aligned}$$

Therefore, the result holds. $\square$

Lemma 10

For any given sequence $\pi$, the cost function of all jobs within group $G_i$ under the optimal due windows assignment strategy of Case 1.2, denoted by $d_i^*(\pi )=\{0,0,\ldots ,0\}$ and $w_i^*(\pi )=\{w_{i1}^*,w_{i2}^*,\ldots ,w_{iz_i }^*\}$, can be expressed as follows:

$$\begin{aligned} g_i \big (\pi ,d_i^*(\pi ),w_i^*(\pi )\big )={\sum }_{l=1}^{n_i } {w_{il} p_{i[l]} } +n_i \delta _i \big (S_i (\pi )+s_i \big ) \end{aligned}$$

(11)

Where,

$$\begin{aligned} w_{il} =\left\{ \begin{array}{ll} n_{ik} \delta _i ,&{} N_{i(k-1)} +1\le l\le b_{ik} +h_{ik}\\ \beta _i (N_{ik} -l+1), &{} b_{ik} +h_{ik} +1\le l\le N_{ik} \end{array}\right. . \end{aligned}$$

(12)

Proof

Let $\pi$ be a given job sequence, and group $G_i$ with Case 1.2, the optimal $d_{ik}^*$ and $w_{ik}^*$ for $k=1,2,\ldots ,z_i$, can be determined by Lemma 7. Then for any $k\in \{1,2,\ldots ,z_i \}$, we have

$$\begin{aligned} E_{i[l]}&= 0~\mathrm{{ for }}~N_{i(k-1)} +1\le l\le N_{ik}.\\ T_{i[l]}&= 0~\mathrm{{ for }}~N_{i(k-1)} +1\le l\le b_{ik} +h_{ik},\\ T_{i[l]}&= {\sum }_{j=b_{ik} +h_{ik} +1}^l {p_{i[j]} } \quad \mathrm{{ for }}~b_{ik} +h_{ik} +1\le l\le N_{ik}.\\ d_{i[l]}&= d_{ik} =0 \quad \mathrm{{ for }}~N_{i(k-1)} +1\le l\le N_{ik}.\\ w_{i[l]}&= w_{ik} =C_{i[b_{ik} +h_{ik} ]} =S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ik} +h_{ik} } {p_{i[l]} } \quad \mathrm{{ for }}~N_{i(k-1)} \!+\!1\!\le \! l \!\le \! N_{ik}.\\ S_{i[l]}&= w_{i[l]} -d_{i[l]} =w_{ik} =S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ik} +h_{ik} } {p_{i[l]} } \quad \mathrm{{ for }}~N_{i(k-1)} \!+\!1\!\le \! l\!\le \! N_{ik}. \end{aligned}$$

Then the cost function of all jobs within group $G_i$ can be written as follows:

$$\begin{aligned}&g_i \big (\pi ,d_i^*(\pi ),w_i^*(\pi )\big )=\sum \nolimits _{k=1}^{z_i } {\sum \nolimits _{l=N_{i(k-1)} +1}^{N_{ik} } {\big (\alpha _i E_{i[l]} +\beta _i T_{i[l]} +\gamma _i d_{i[l]} +\delta _i S_{i[l]} \big )} }\\&\quad =\sum \nolimits _{k=1}^{z_i } {\left[ {\sum \nolimits _{l=b_{ik} +h_{ik} +1}^{N_{ik} } {\left( {\beta _i \sum \nolimits _{j=b_{ik} \!+\!h_{ik} +1}^l {p_{i[j]} } } \right) } \!+\! n_{ik} \delta _i \left( {S_i (\pi )\!+\!s_i +\sum \nolimits _{l=1}^{b_{ik} +h_{ik} } {p_{i[l]} } } \right) } \right] }\\&\quad =\sum \nolimits _{k=1}^{z_i } {\left[ {\sum \nolimits _{l=b_{ik} +h_{ik} +1}^{N_{ik} } {\beta _i \big (N_{ik} -l} } \right. }\!+\!1\big )p_{i[l]} +n_{ik} \delta _i \sum \nolimits _{l=1}^{b_{ik} +h_{ik} } {p_{i[l]} } +\left. {n_{ik} \delta _i \left( {S_i (\pi )+s_i } \right) } \right] \\&\quad =\sum \nolimits _{k=1}^{z_i } {\left[ {\sum \nolimits _{l=1}^{b_{ik} +h_{ik} } {n_{ik} \delta _i p_{i[l]} +\sum \nolimits _{l=b_{ik} +h_{ik} +1}^{N_{ik} } {\beta _i \big (N_{ik} -l} +1\big )p_{i[l]} } } \right] } +n_i \delta _i \left( {S_i (\pi )+s_i } \right) \end{aligned}$$

Therefore, the result holds.

If group $G_i$ is under the optimal due windows assignment strategy of Case 1.3, then the multiple due windows assignment problem of group $G_i$ reduces to the multiple due dates assignment problem, i.e., $\{d_{i1}^*,d_{i2}^*,\ldots ,d_{iz_i }^*\}=d_i^*(\pi )=D_i^*(\pi )=w_i^*(\pi )=\{w_{i1}^*,w_{i2}^*,\ldots ,w_{iz_i }^*\}$. The corresponding objective function $g(\pi ,d(\pi ),w(\pi ))={\sum }_{i=1}^m {{\sum }_{l=1}^{n_i } {(\alpha _i E_{il} +\beta _i T_{il} +\gamma _i d_{il} +\delta _i S_{il} )} }$ is translated into $f(\pi ,D(\pi ))={\sum }_{i=1}^m {{\sum }_{l=1}^{n_i } {(\alpha _i E_{il} +\beta _i T_{il} +\gamma _i D_{il} )} }$. Then we contain the following lemma. $\square$

Lemma 11

For any given sequence $\pi$, the cost function of all jobs within group $G_i$ under the optimal due windows assignment strategy of Case 1.3, denoted by $d_i^*(\pi )=w_i^*(\pi )=D_i^*(\pi )=\{D_{i1}^*,D_{i2}^*,\ldots ,D_{iz_i }^*\}$, can be expressed as follows:

$$\begin{aligned} f_i \big (\pi ,D_i^*(\pi )\big )=\sum \nolimits _{l=1}^{n_i } {w_{il} p_{i[l]} } +n_i \varpi _i \big (S_i (\pi )+s_i \big ) \end{aligned}$$

(13)

where

$$\begin{aligned} \varpi _i&= \min \{\beta _i ,\gamma _i \},\end{aligned}$$

(14)

$$\begin{aligned} w_{il}&= \left\{ \begin{array}{ll} \alpha _i (l-N_{i(k-1)} -1)+\gamma _i (n_i -N_{i(k-1)} ), &{} N_{i(k-1)} +1\le l\le b_{ik}\\ \beta _i (N_{ik} -l+1)+\gamma _i (n_i -N_{ik} ), &{} b_{ik} +1\le l\le N_{ik}\\ \end{array}\right. \mathrm{{ for }} \beta _i >\gamma _i ,\nonumber \\ \end{aligned}$$

(15)

and

$$\begin{aligned} w_{il} =\beta _i (n_i -l+1),\quad 1\le l\le n_i ~\mathrm{{ for }}~\beta _i \le \gamma _i , \end{aligned}$$

(16)

Proof

Let $\pi$ be a given job sequence. By Lemma 6, the optimal due date $D_{ik}^*$ for $k=1,2,\ldots ,z_i$, $i=1,2,\ldots ,m$ can be determined according to (8). We split the proof into two cases with respect to the relation of $\beta _i$ and $\gamma _i$.

Case 2.1: $\beta _i >\gamma _i$. For any $k\in \{1,2,\ldots ,z_i \}$ in this case, we have

$$\begin{aligned} E_{i[l]}&= \sum \nolimits _{j=l+1}^{b_{ik} } {p_{i[j]} }~\mathrm{{ for }}~N_{i(k-1)} +1\le l\le b_{ik} -1~\mathrm{{ and }}~E_{i[l]} =0~\mathrm{{ for }}~b_{ik} \le l\le N_{ik}.\nonumber \\ T_{i[l]}&= 0~\mathrm{{ for }}~N_{i(k-1)} +1\le l\le b_{ik}~\mathrm{{ and }}~ T_{i[l]} =\sum \nolimits _{j=b_{ik} +1}^l {p_{i[j]} }~\mathrm{{ for }}~b_{ik} +1\le l\le N_{ik}.\nonumber \\ D_{i[l]}&= D_{ik} =C_{i[b_{ik} ]} =S_i (\pi )+s_i +\sum \nolimits _{l=1}^{b_{ik} } {p_{i[l]} } ~\mathrm{{ for }}~ N_{i(k-1)} +1\le l\le N_{ik} \end{aligned}$$

(17)

Then the cost function of all jobs within group $G_i$ can be written as follows:

$$\begin{aligned}&f_i \big (\pi ,D_i^*(\pi )\big )=\sum \nolimits _{l=1}^{n_i } {\big (\alpha _i E_{il} +\beta _i T_{il} +\gamma _i D_{il} \big )}\\&\quad =\sum \nolimits _{k=1}^{z_i } {\sum \nolimits _{l=N_{i(k-1)} +1}^{N_{ik} } {\big (\alpha _i E_{i[l]} +\beta _i T_{i[l]} +\gamma _i D_{i[l]} \big )}}\\&\quad =\sum \nolimits _{k=1}^{z_i } {\left[ {\sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {\left( {\alpha _i \sum \nolimits _{j=l+1}^{b_{ik} } {p_{i[j]} } } \right) } } \right. +\sum \nolimits _{l=b_{ik} +1}^{N_{ik} } {\left( {\beta _i \sum \nolimits _{j=b_{ik} +1}^l {p_{i[j]} } } \right) } }\\&\qquad \left. {+n_{ik} \gamma _i \left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{N_{i(k-1)} } {p_{i[l]} +\sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {p_{i[l]} } } } \right) } \right] \\&\quad =\sum \nolimits _{k=1}^{z_i } {\left[ {\sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {\alpha _i \big (l-N_{i(k-1)} -1\big )p_{i[l]} } } \right. +\sum \nolimits _{l=b_{ik} +1}^{N_{ik} } {\beta _i \big (N_{ik} -l+1\big )p_{i[l]}}}\\&\qquad \left. {+n_{ik} \gamma _i \left( {S_i (\pi )+s_i +\sum \nolimits _{l=1}^{N_{i(k-1)} } {p_{i[l]} } } \right) +n_{ik} \gamma _i \sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {p_{i[l]} } } \right] \\&\quad =\sum \nolimits _{k=1}^{z_i } {\left\{ {\sum \nolimits _{l=N_{i(k-1)} +1}^{b_{ik} } {\left[ {\alpha _i \big (l-N_{i(k-1)} -1\big )+\gamma _i \big (n_i -N_{i(k-1)} \big )} \right] } } \right. p_{i[l]}}\\&\qquad \left. {+\sum \nolimits _{l=b_{ik} +1}^{N_{ik} } {\left[ {\beta _i \big (N_{ik} -l+1\big )+\gamma _i \big (n_i -N_{ik} \big )} \right] p_{i[l]} } } \right\} +n_i \gamma _i \left( {S_i (\pi )+s_i } \right) \end{aligned}$$

Therefore, the result retains in this case.

Case 2.2: $\beta _i \le \gamma _i$. For any $k\in \{1,2,\ldots ,z_i \}$ in this case, we have

$$\begin{aligned} E_{i[l]}&= 0~\mathrm{{ for }}~N_{i(k-1)} +1\le l\le N_{ik}.\nonumber \\ T_{i[l]}&= C_{i[l]} =S_i (\pi )+s_i +\sum \nolimits _{j=1}^{N_{i(k-1)} } {p_{i[j]}}\nonumber \\&+\sum \nolimits _{j=N_{i(k-1)} +1}^l {p_{i[j]} }~\mathrm{{ for }}~ N_{i(k-1)} +1\le l\le N_{ik}.\nonumber \\ D_{i[l]}&= D_{ik} =0 ~\mathrm{{ for }}~ N_{i(k-1)} +1\le l\le N_{ik} \end{aligned}$$

(18)

Then the cost function of all jobs within group $G_i$ can be written as follows:

$$\begin{aligned} f_i (\pi ,D_i^*(\pi ))&= \sum \nolimits _{l=1}^{n_i } {\big (\alpha _i E_{il} +\beta _i T_{il} +\gamma _i D_{il} \big )}\\&= \sum \nolimits _{k=1}^{z_i } {\sum \nolimits _{l=N_{i(k-1)} +1}^{N_{ik} } {(\alpha _i E_{i[l]} +\beta _i T_{i[l]} +\gamma _i D_{i[l]} )} }\\&= \sum \nolimits _{k=1}^{z_i } {\sum \nolimits _{l=N_{i(k-1)} +1}^{N_{ik} } {\beta _i \left( {S_i (\pi )+s_i +\sum \nolimits _{j=1}^{N_{i(k-1)} } {p_{i[j]} } +\sum \nolimits _{j=N_{i(k-1)} +1}^l {p_{i[j]} } } \right) }}\\&= \sum \nolimits _{k=1}^{z_i } {\sum \nolimits _{l=N_{i(k-1)} +1}^{N_{ik} } {\beta _i \big (n_i \!-\!N_{ik} \big )p_{i[j]} \!+\!{\sum }_{k=1}^{z_i } {\sum \nolimits _{j=N_{i(k-1)} +1}^{N_{ik} } {\beta _i \big (N_{ik} \!-\!l\!+\!1\big )p_{i[j]}}}}}\\&+\sum \nolimits _{k=1}^{z_i } {\sum \nolimits _{l=N_{i(k-1)} +1}^{N_{ik} } {\beta _i \left( {S_i (\pi )+s_i } \right) }}\\&= \sum \nolimits _{k=1}^{z_i } {\sum \nolimits _{l=N_{i(k-1)} +1}^{N_{ik} } {\beta _i \big (n_i -l+1\big )p_{i[j]} } } +n_i \beta _i \left( {S_i (\pi )+s_i } \right) \end{aligned}$$

Therefore, the result also holds for the second case. $\square$

3.2 A unified optimization algorithm

In this subsection, we will present an $O(n\log n)$ time unified optimization algorithm for the problem $1 \left| {GT,MDW} \right| {\sum }_{i=1}^m {{\sum }_{l=1}^{n_i } {(\alpha _i E_{il} +\beta _i T_{il} +\gamma _i d_{il} +\delta _i S_{il})}}$.

In view of Lemmas 9–11, for any given job sequence $\pi$, the unified cost function under the optimal due windows assignment strategy, denoted by $d^{*}(\pi )=\{d_{11}^*,\ldots ,d_{1z_1 }^*,\ldots ,d_{m1}^*,\ldots ,d_{mz_m }^*\}$ and $w^{*}(\pi )=\{w_{11}^*,\ldots ,w_{1z_1 }^*,\ldots ,w_{m1}^*,\ldots ,w_{mz_m }^*\}$, can be formulated as follows:

$$\begin{aligned} g\big (\pi ,d^{*}(\pi ),w^{*}(\pi )\big )=\sum \nolimits _{i=1}^m {\sum \nolimits _{l=1}^{n_i } {w_{il} p_{i[l]} } } +\sum \nolimits _{i=1}^m {n_i \psi _i \big (S_i (\pi )+s_i \big )} \end{aligned}$$

(19)

where,

$$\begin{aligned} \psi _i =\left\{ \begin{array}{ll} \gamma _i , \quad \mathrm{{ if~group}}~\mathrm { G}_\mathrm{i}~\mathrm{{is~Case}}~1.1\\ \delta _i , \quad \mathrm{if~group}~\mathrm{G}_\mathrm{i}~\mathrm{is~Case}~1.2\\ \varpi _i , \quad \mathrm{if~group}~\mathrm{G}_\mathrm{i}~\mathrm{is~Case}~1.3\\ \end{array}\right. , \varpi _i =\min \{\beta _i ,\gamma _i \}, \end{aligned}$$

and $w_{il} (1\le i\le m, 1\le l\le n_i )$ is defined by (10) for Case 1.1, by (12) for Case 1.2, and by (15) and (16) for Case 1.3.

From (19) we can observe that under an optimal due window assignment policy, the total cost is the sum of $m+1$ separable terms. The first $m$ terms, ${\sum }_{l=1}^{n_i } {w_{il} p_{i[l]} }$ for $i=1,2,\ldots ,m$, is dependent only on the internal job sequence within group $G_i$, while the last term, ${\sum }_{i=1}^m {n_i \psi _i (S_i (\pi )+s_i )}$, is only concerned with the starting time of the group and is independent of the internal job sequence of each group. As a result of this separable characteristic of the objective function, our problem reduces to $m+1$ subproblems. The first $m$ subproblems are to find an optimal job sequence which minimize ${\sum }_{l=1}^{n_i } {w_{il} p_{i[l]} }$ for $i=1,2,\ldots ,m$, while the last subproblem is to find an optimal group sequence which minimizes ${\sum }_{i=1}^m {n_i \psi _i (S_i (\pi )+s_i )}$. Then the following two lemmas are immediately obtained.

Lemma 12

The optimal job sequence within group $G_i$ can be obtained by matching the smallest $w_{il}$ value to the largest $p_{il}$ value, the second smallest $w_{il}$ value to the second largest $p_{il}$ value, and so on.

Proof

It can be easily proved by Lemma 2. $\square$

Lemma 13

In an optimal schedule, the groups are ordered in non-decreasing order of ${(s_i +{\sum }_{l=1}^{n_i } {p_{il} } )}{\big /}{n_i }\psi _i$.

Proof

we prove the result by contradiction. Let $\pi$ be an optimal schedule that does not satisfy the property of the lemma. Then $\pi$ must contain at least two adjacent groups, say $G_j$ followed by $G_k$, such that ${(s_k +{\sum }_{l=1}^{n_i } {p_{kl} } )}{\big /}{n_k }\psi _k <{(s_j +{\sum }_{l=1}^{n_i } {p_{jl} } )}{\big /}{n_j }\psi _j$. Swapping $G_j$ and $G_k$, while leaving the other groups in their original order, we obtain a new schedule ${\pi }'$. Then we have

$$\begin{aligned} S_k (\pi )&= S_j (\pi )+s_j +\sum \nolimits _{l=1}^{n_j } {p_{jl} },\end{aligned}$$

(20)

$$\begin{aligned} S_k ({\pi }')&= S_j (\pi ),\end{aligned}$$

(21)

$$\begin{aligned} S_j ({\pi }')&= S_j (\pi )+s_k +\sum \nolimits _{l=1}^{n_k } {p_{kl} } . \end{aligned}$$

(22)

Because the completion times of jobs processed before (after) $G_j$ and $G_k$ are the same under schedule $\pi$ and ${\pi }'$, the cost function for groups processed before (after) $G_j$ and $G_k$ are not changed. As a consequence, by submitting (20–22) into (19), the difference between the objective values of the two schedules is

$$\begin{aligned}&g\big (\pi ,d^{*}(\pi ),w^{*}(\pi )\big )-g\big ({\pi }',d^{*}({\pi }'),w^{*}({\pi }')\big )\\&\quad =n_k \psi _k \Big (s_j +\sum \nolimits _{l=1}^{n_j } {p_{jl} } \Big )-n_j \psi _j \Big (s_k +\sum \nolimits _{l=1}^{n_k } {p_{kl} } \Big )\\&\quad =n_k n_j \psi _k \psi _j \left( {\frac{s_j +{\sum }_{l=1}^{n_j } {p_{jl} } }{n_j \psi _j }-\frac{s_k +{\sum }_{l=1}^{n_k } {p_{kl} } }{n_k \psi _k }} \right) >0. \end{aligned}$$

This contradicts the optimality of $\pi$, and completes the proof of the lemma.

Based on the above analysis, now we present the following algorithm to solve the $1 \left| { GT,MDW } \right| {\sum }_{i=1}^m {{\sum }_{l=1}^{n_i } {(\alpha _i E_{il} +\beta _i T_{il} +\gamma _i d_{il} +\delta _i S_{il} )} }$ problem. $\square$

Algorithm

Step 1:

Calculate the ratios of $\left\lceil {{n_{ik} (\delta _i -\gamma _i )}/{\alpha _i }} \right\rceil$ and $\left\lceil {{n_{ik} (\beta _i -\delta _i )}/{\beta _i }} \right\rceil$, and according to Lemmas 4–8, determine which case each group is.

Step 2:

For the groups of Case 1.1, calculate $w_{il}$ according to (10), and $b_{ik}$ and $b_{ik} +h_{ik}$ according to Lemma 5. For the groups of Case 1.2, calculate $w_{il}$ according to (12), and $b_{ik} +h_{ik}$ according to Lemma 7. For the groups of Case 1.3, calculate $w_{il}$ according to (15) and (16), and $b_{ik}$ according to Lemma 6 or 8.

Step 3:

Sequence the jobs within each group by Lemma 12 and arrange the groups in non-decreasing order of ${(s_i +{\sum }_{l=1}^{n_i } {p_{il} } )}{\big /}{n_i }\psi _i$ by Lemma 13.

Step 4:

For the groups of Case 1.1, assign the due windows according to Lemma 5. For the groups of Case 1.2, assign the due windows according to Lemma 7. For the groups of Case 1.3, assign the due windows according to Lemma 6 or 8.

To determine the computational complexity of the algorithm, note that Step 1, Step 2 and Step 4 can be performed in linear time; Step 3 requires $O({\sum }_{i=1}^m {n_i } \log n_i +m\log m)$ time. Since ${\sum }_{i=1}^m {n_i } =n$ and $m\le n$, the time complexity of the algorithm is $O(n\log n)$.

Theorem 1

The $1 \left| { GT,MDW } \right| {\sum }_{i=1}^m {{\sum }_{l=1}^{n_i } {(\alpha _i E_{il} +\beta _i T_{il} +\gamma _i d_{il} +\delta _i S_{il} )} }$ problem can be solved by the above algorithm in $O(n\log n)$ time.

4 Conclusions

We considered the problem of the simultaneous determination of multiple due windows assignment and job scheduling on a single machine under a GT restriction, where the objective is to determine an optimal combination of the job schedule and due windows assignment strategy to minimize the total related cost that comprises the earliness, tardiness and the due windows. We presented an $O(n\log n)$ time algorithm for the problem. It would be an interesting and valuable topic to investigate the case where the job processing times are time-dependent or resource-dependent in the future research.