1 Introduction

We study a single machine group scheduling problem with due date assignment and resource allocation. By grouping various products with similar designs and/or production processes, one could increase the efficiency for high-volume production. The utilization of group technology has many advantages, as reported in, e.g., Liu et al. (2014), Keshavarz et al. (2015), Qin et al. (2016) and Wang et al. (2021). Many studies view due date assignment as part of the scheduling decision, since due dates are often determined during sales negotiations. Setting further due dates may defer customers from placing orders, which often results in lost sales, hence a cost is associated with the due date assignment. In addition, products completed processing before their due dates usually incur earliness costs such as storage cost or insurance fees. On the other hand, products completed after their due dates usually incur tardiness penalties such as compensation for customers. In practice, usually it is unlikely to complete all jobs exactly on their due dates, thus for many manufacturing systems all the above mentioned costs are relevant and should be considered (Seidmann et al. 1981; Panwalkar et al. 1982; Shabtay 2016).

Seidmann et al. (1981) and Panwalkar et al. (1982) initiated the study of scheduling problems with due date assignment. Seidmann et al. (1981) studied a single machine scheduling problem where jobs are allowed to be assigned different due dates, and presented an \(O(n\log n)\) time algorithm to solve the problem. Panwalkar et al. (1982) analyzed a scheduling problem where all jobs are required to be assigned a common due date, and an \(O(n\log n)\) time algorithm is presented. Li et al. (2011) studied a single machine group scheduling problem considering three different due date assignment methods. The objective is to minimize an aggregate cost including earliness, tardiness, due date assignment and flow time costs. Li and Zhao (2015) and Ji et al. (2016) studied single machine group scheduling problems with multiple due windows assignment. Bajwa et al. (2019) studied a single machine group scheduling problem to minimize the number of tardy jobs, in which jobs are allowed to be assigned different due dates.

For many modern industrial processes the job processing times are affected by the allocation of certain resource such as fuel or manpower. Shabtay et al. (2010) investigated a group scheduling problem with due date assignment, and extended the study to the case where job processing times are resource dependent. Lv et al. (2021) studied a single machine common flow allowance group scheduling problem with learning effect, and two resource allocation functions are considered. Yin et al. (2014) studied single machine group scheduling problems with learning effect, deteriorating jobs and resource allocation.

To the best of our knowledge, there is no research on group scheduling with resource allocation and due date assignment, in which jobs in the same group could have different due dates assigned and different unit costs (including due date, earliness, tardiness, and resource allocation costs). We will fill the research gap in this paper. An application of our considered scheduling problem is presented as follows. In modern manufacturing, products exported to overseas destinations from a multinational company are often adapted to local regulations, or modified to meet different electricity or other infrastructure standards. In order to improve production efficiency and reduce cost, companies usually join orders with the same processing standards to be processed together. These orders can be considered as a group of jobs and each job of the same group can be assigned a different duedate, since the orders of the same group may come from different customers or areas, and they may own different unit costs. Moreover, the actual processing time of an order can often be compressed if additional resources (e.g., money, fuel, or manpower) are allocated.

The remainder of this paper is structured in the following manner. In Sect. 2, we give a formal description of the scheduling problem that will be studied in this paper. Several preliminary results are presented in Sect. 3. In Sect. 4, properties of the optimal solutions are presented, and for the special case where the size of every group is the same and the minimum of the due date assignment cost and the tardiness cost for each job is identical, for both convex and bounded linear resource consumption functions, an \(O(n^3)\) time algorithm is presented, where n is the total number of jobs. Numerical examples are presented in Sect. 5, and we conclude our paper in Sect. 6.

2 Problem formulation

There are n jobs \(J_1, J_2,\ldots , J_n\) to be processed on a single machine, and the jobs are partitioned into m groups in advance. Let the ith group be \(G_i=\{J_{i1},J_{i2},\ldots ,J_{in_i}\}\), where \(n_i\) is the number of jobs in \(G_i\), for \(i=1,2,\ldots , m\). Hence, \(\sum _{i=1}^{m}n_i=n\). The jobs are non-preemptive, and it is required that jobs in the same group are processed contiguously. For each group \(G_i\), prior to the processing of the first job in \(G_i\), a machine setup time \(s_i\) is required, which does not depend on the job sequence in the group. It is permissible to assign different due dates to jobs in the same group. Let \(d_{ij}\) and \(C_{ij}\) be the due date and completion time of job \(J_{ij}\), respectively. Then, the earliness of job \(J_{ij}\) is \(E_{ij}\)=max{\(d_{ij}-C_{ij}\), 0}, and the tardiness of job \(J_{ij}\) is \(T_{ij}\)=max{\(C_{ij}-d_{ij}\), 0}.

Table 1 Notations
Full size table

In practical manufacturing systems, the actual processing times of jobs are often controllable by allocating a continuous resource, and this relationship is characterized by the resource consumption function. Two different types of resource consumption functions have been widely used in literature (see, e.g., Shabtay et al. 2010). One is a convex function \(p_{ij}(u_{ij})=(\frac{w_{ij}}{u_{ij}})^r\), where \(u_{ij}\) is the amount of resource allocated to \(J_{ij}\), \(w_{ij}\) denotes the workload of \(J_{ij}\), and \(r>0\) is a constant. The second resource consumption function is a bounded linear function \(p_{ij}(u_{ij})=\overline{p_{ij}}-a_{ij}u_{ij}\), where \(\overline{p_{ij}}\) is the non-compressed processing time of job \(J_{ij}\), \(u_{ij}\) is the amount of resource allocated to \(J_{ij}\), and \(a_{ij}\) is the positive compression rate. The value of \(u_{ij}\) is within the range \(0\le u_{ij}\le \overline{u_{ij}} \le \frac{\overline{p_{ij}}}{a_{ij}}\), where \(\overline{u_{ij}}\) is the upper bound on the amount of resource which can be allocated to the job.

Our objective is finding a schedule \(\pi \) for the group sequence and job sequence in every group, a due date assignment

$$\begin{aligned} d(\pi )=(d_{11}(\pi ),\ldots ,d_{1n_1}(\pi ),\ldots ,d_{m1}(\pi ),\ldots ,d_{mn_m}(\pi )) \end{aligned}$$

for all jobs, and a resource allocation vector

$$\begin{aligned} u(\pi )=(u_{11}(\pi ),\ldots ,u_{1n_1}(\pi ),\ldots ,u_{m1}(\pi ),\ldots ,u_{mn_m}(\pi )) \end{aligned}$$

specifying the amount of resource allocated to each job, to minimize the following aggregate cost function

$$\begin{aligned} Z(\pi ,d(\pi ),u(\pi ))=\sum _{i=1}^{m}\sum _{j=1}^{n_i}\left( \alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}\right) , \end{aligned}$$

which includes earliness, tardiness, due date assignment and resource allocation costs. Here \(\alpha _{ij}\), \(\beta _{ij}\), \(\gamma _{ij}\) and \(v_{ij}\) are positive parameters representing the unit due date, earliness, tardiness and resource allocation costs for \(J_{ij}\), respectively. Parameters \(n_i\), \(s_i\), \(\alpha _{ij}\), \(\beta _{ij}\), \(\gamma _{ij}\) and \(v_{ij}\) are all given.

Using the three-field notation of Graham et al. (1979), we denote our problem with the convex and linear resource consumption functions by

$$\begin{aligned} 1|GT, DIF, CONV|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}) \end{aligned}$$

and

$$\begin{aligned} 1|GT, DIF, LIN|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}), \end{aligned}$$

respectively, where GT represents group technology, DIF indicates that jobs within the same group are allowed to be assigned different due dates, CONV indicates that the resource consumption function adopted is convex, and LIN indicates that the resource consumption function adopted is bounded linear. The notations used in this paper are listed in Table 1.

3 Preliminary analysis

First, we present two lemmas that will be useful for later analysis.

Lemma 3.1

For problem

$$\begin{aligned} 1|GT, DIF, X|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}),~~~ X\in \{CONV, LIN\}, \end{aligned}$$

given a schedule \(\pi \), the optimal due date assignment \(d^*(\pi )\) can be calculated by the following rule: For \(i=1,2,\ldots ,m\), and \(j=1,2,\ldots ,n_i\), if \(\alpha _{[i][j]}< \gamma _{[i][j]}\) then \(d^*_{[i][j]}(\pi )=C_{[i][j]}(\pi )\), if \(\alpha _{[i][j]}> \gamma _{[i][j]}\) then \(d^*_{[i][j]}(\pi )=0\), and if \(\alpha _{[i][j]}= \gamma _{[i][j]}\) then \(d^*_{[i][j]}(\pi )\) can be any value in interval \([0, C_{[i][j]}(\pi )]\).

Proof

Since the due date assignment vector only affects the first three terms in the objective function, and by the definition of the earliness and tardiness of a job given in Sect. 2, that is, \(E_{ij}\)=max{\(d_{ij}-C_{ij}\), 0} and \(T_{ij}\)=max{\(C_{ij}-d_{ij}\), 0}, the lemma follows immediately. \(\square \)

Lemma 3.2

There exists an optimal schedule with zero machine idle times for problem

$$\begin{aligned} 1|GT, DIF, X|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}),~~~ X\in \{CONV, LIN\} \end{aligned}$$

Proof

We omit the proof here because it is similar with the proof to Lemma 3.1 in Li et al. (2011). \(\square \)

For a schedule \(\pi \) and its corresponding optimal due date assignment \(d^*(\pi )\) determined in Lemma 3.1, let \(Z_{[i][j]}(\pi ,d^*(\pi ),u(\pi ))\) denote the contribution to the objective function from \(J_{[i][j]}\), and let \(\psi _{[i][j]}\)=min(\(\alpha _{[i][j]}\), \(\gamma _{[i][j]}\)), for \(i=1,2,\ldots , m\), and \(j=1,2,\ldots ,n_i\). By Lemma 3.1 and the same analysis as in Sect. 3 in Chen and Cheng (2021), we can write \(Z_{[i][j]}(\pi ,d^*(\pi ),u(\pi ))\) in the following unified way:

$$\begin{aligned} Z_{[i][j]}(\pi ,d^*(\pi ),u(\pi ))=\psi _{[i][j]}C_{[i][j]}+v_{[i][j]}u_{[i][j]}. \end{aligned}$$

Hence, we can write the objective function of our problem, \(Z(\pi ,d^*(\pi ),u(\pi ))\), as follows

$$\begin{aligned} Z(\pi ,d^*(\pi ),u(\pi ))=\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\big (\psi _{[i][j]}C_{[i][j]}+v_{[i][j]}u_{[i][j]}\big ). \end{aligned}$$
(1)

4 The optimal schedule

We first analyze the optimal schedule for

$$\begin{aligned} 1|GT, DIF, X|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}), ~~~X\in \{CONV, LIN\}. \end{aligned}$$

According to Lemma 3.2, we only consider schedules with no idle time. Thus, for any job \(J_{[i][j]}\), we have the following formula for its completion time:

$$\begin{aligned} C_{[i][j]}&=\sum _{k=1}^{i-1}P_{[k]}+\sum _{k=1}^{i}s_{[k]}+\sum _{\ell =1}^{j}p_{[i][\ell ]}\\&=\sum _{k=1}^{i-1}\sum _{\ell =1}^{n_{[k]}}p_{[k][\ell ]}+\sum _{k=1}^{i}s_{[k]}+\sum _{\ell =1}^{j}p_{[i][\ell ]}. \end{aligned}$$

Next, we calculate the objective function based on Eq. (1) and the above equalities.

$$\begin{aligned}{} & {} Z(\pi ,d^*(\pi ),u(\pi ))\\{} & {} \quad =\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\big (\psi _{[i][j]}C_{[i][j]}+v_{[i][j]}u_{[i][j]}\big )\\{} & {} \quad =\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\psi _{[i][j]}\left( \sum _{k=1}^{i-1}\sum _{\ell =1}^{n_{[k]}}p_{[k][\ell ]}+\sum _{k=1}^{i}s_{[k]}+\sum _{\ell =1}^{j}p_{[i][\ell ]}\right) +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}v_{[i][j]}u_{[i][j]}\\{} & {} \quad =\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\psi _{[i][j]}\left( \sum _{k=1}^{i}s_{[k]}\right) +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}v_{[i][j]}u_{[i][j]}+\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\psi _{[i][j]}\left( \sum _{k=1}^{i-1}\sum _{\ell =1}^{n_{[k]}}p_{[k][\ell ]}\right) \\{} & {} \qquad +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\psi _{[i][j]}\left( \sum _{\ell =1}^{j}p_{[i][\ell ]}\right) . \end{aligned}$$

We rewrite the first, the third and the fourth term in the above formula. For the first term,

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\psi _{[i][j]}\left( \sum _{k=1}^{i}s_{[k]}\right) =\sum _{i=1}^{m}\left( \sum _{j=1}^{n_{[i]}}\psi _{[i][j]}\right) \left( \sum _{k=1}^{i}s_{[k]}\right) =\sum _{i=1}^{m}\Psi _{[i]} \left( \sum _{k=1}^{i}s_{[k]}\right) , \end{aligned}$$

for the third term,

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\psi _{[i][j]}\left( \sum _{k=1}^{i-1}\sum _{\ell =1}^{n_{[k]}}p_{[k][\ell ]}\right)= & {} \sum _{i=1}^{m}\Psi _{[i]}\left( \sum _{k=1}^{i-1}\sum _{\ell =1}^{n_{[k]}}p_{[k][\ell ]}\right) \\= & {} \sum _{i=1}^{m}\sum _{k=1}^{i-1}\left( \Psi _{[i]}\sum _{\ell =1}^{n_{[k]}}p_{[k][\ell ]}\right) \\= & {} \sum _{i=1}^{m}\left( \sum _{k=i+1}^{m}\Psi _{[k]}\right) \left( \sum _{\ell =1}^{n_{[i]}}p_{[i][\ell ]}\right) \\= & {} \sum _{i=1}^{m}\left( \sum _{k=i+1}^{m}\Psi _{[k]}\right) \left( \sum _{j=1}^{n_{[i]}}p_{[i][j]}\right) \\= & {} \sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\left( \sum _{k=i+1}^{m}\Psi _{[k]}\right) p_{[i][j]}, \end{aligned}$$

and for the fourth term,

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\psi _{[i][j]}\left( \sum _{\ell =1}^{j}p_{[i][\ell ]}\right) =\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\left( \sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) p_{[i][j]}. \end{aligned}$$

By combining the above, it follows that

$$\begin{aligned}{} & {} Z(\pi ,d^*(\pi ),u(\pi ))\nonumber \\{} & {} \quad =\sum _{i=1}^{m}\Psi _{[i]} \left( \sum _{k=1}^{i}s_{[k]}\right) +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}v_{[i][j]}u_{[i][j]}+\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\left( \sum _{k=i+1}^{m}\Psi _{[k]}\right) p_{[i][j]} \nonumber \\{} & {} \qquad +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\left( \sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) p_{[i][j]}\nonumber \\{} & {} \quad =\sum _{i=1}^{m}\Psi _{[i]} \left( \sum _{k=1}^{i}s_{[k]}\right) +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}v_{[i][j]}u_{[i][j]}+\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\left( \sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) p_{[i][j]}. \nonumber \\ \end{aligned}$$
(2)

Next, we analyze the optimal schedule for convex and bounded linear resource consumption functions, respectively.

4.1 Optimal schedule for problem \(1|GT, DIF, CONV|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij})\)

By \(p_{ij}(u_{ij})=\left( \frac{w_{ij}}{u_{ij}}\right) ^r\) and Eq. (2), we have

$$\begin{aligned} Z(\pi ,d^*(\pi ),u(\pi ))&=\sum _{i=1}^{m}\Psi _{[i]}\left( \sum _{k=1}^{i}s_{[k]}\right) +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\left( \sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) \nonumber \\&\quad \times \left( \frac{w_{[i][j]}}{u_{[i][j]}}\right) ^r+\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}v_{[i][j]}u_{[i][j]}. \end{aligned}$$
(3)

Lemma 4.1

For problem

$$\begin{aligned} 1|GT, DIF, CONV|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}), \end{aligned}$$

given a schedule \(\pi \) for the group sequence and job sequence within each group, assume that the due date assignment vector \(d^*(\pi )\) is adopted, then the following formula gives the optimal resource allocation with respect to \(\pi \)

$$\begin{aligned} u_{[i][j]}^*(\pi )=w_{[i][j]}^{r/{(r+1)}}\times \left( \frac{r\big (\sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\big )}{v_{[i][j]}}\right) ^{1/{(r+1)}}. \end{aligned}$$
(4)

Proof

The objective function in Eq. (3) can be viewed as a function in \(u_{[i][j]}\)’s, and each variable \(u_{[i][j]}\) is only in the following summation consisting of two terms

$$\begin{aligned} v_{[i][j]}u_{[i][j]}+\left( \sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) \left( \frac{w_{[i][j]}}{u_{[i][j]}}\right) ^r. \end{aligned}$$

Hence, taking derivative of the above formula with respect to \(u_{[i][j]}\) and equating it to zero give the formula in Eq. (4). Note that the above formula is convex in \(u_{[i][j]}\), it follows that Eq. (4) indeed gives the optimal value for \(u_{[i][j]}\). \(\square \)

Let \(\theta _{ij}=(w_{ij} v_{ij})^{r/{(r+1)}}\), for \(i=1,2,\ldots , m\), and \(j=1,2,\ldots ,n_i\). Plugging Eq. (4) into Eq. (3) gives the following formula for the objective value when the resource allocation and the due date assignment are both optimal, under a given schedule \(\pi \) for the group sequence and job sequence within each group.

$$\begin{aligned} \begin{aligned}&Z(\pi ,d^*(\pi ),u^*(\pi ))=\sum _{i=1}^{m}\Psi _{[i]}\left( \sum _{k=1}^{i}s_{[k]}\right) \\&\quad +\big (r^{1/{(r+1)}}+r^{-r/{(r+1)}}\big )\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\theta _{[i][j]} \left( \sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) ^{1/{(r+1)}}. \end{aligned} \end{aligned}$$
(5)

In order to determine the optimal job sequence within each group, the following lemmas will be used.

Lemma 4.2

(Hardy et al. 1967) The sum of products of two sequences \(x_i\) and \(y_i\), \(\sum _i x_iy_i\), attains its maximum (minimum) value if sequences \(x_i\) and \(y_i\) are monotonic in the same (opposite) sense.

Lemma 4.3

For each \(i=1,2,\ldots ,m\), the optimal job sequence in \(G_i\) is in non-decreasing order of \(\theta _{ij}\), where \(\theta _{ij}=(w_{ij} v_{ij})^{r/{(r+1)}}\).

Proof

In Eq. (5), \(\sum _{i=1}^{m}\Psi _{[i]}\left( \sum _{k=1}^{i}s_{[k]}\right) \) and \(\sum _{k=i+1}^{m}\Psi _{[k]}\) do not depend on job sequences in groups. Moreover, \(r^{1/{(r+1)}}+r^{-r/{(r+1)}}\) is a constant as r is a positive constant parameter. Since \(\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\) is monotonically decreasing in j, by Lemma 4.2, the lemma follows. \(\square \)

Lemma 4.3 gives the optimal job sequence in every group. To solve the original problem, it remains to calculate the optimal group sequence that minimizes Eq. (5). Next, we consider a special case where the size of each group is the same, and we use \(\overline{n}\) to denote this size. In addition, \(\psi _{ij}=\overline{\psi }\) is identical for every job.

Define \(x_{i\ell }=1\) if group \(G_i\) is assigned to position \(\ell \) in \(\pi \), and \(x_{i\ell }=0\) otherwise. According to Lemma 6 in Chen and Cheng (2021), for this special case, the optimal group sequence can be calculated in \(O(m\times \max (n,m^2))\) time by solving the following linear assignment problem in \(x_{i\ell }\).

$$\begin{aligned} (P1)~~~&\min ~ \sum _{i=1}^{m} \sum _{\ell =1}^{m} t_{i\ell }\times x_{i\ell } \\ {\textit{s.t.}}~~~&\sum _{\ell =1}^{m}x_{i\ell } =1,~~~~\text{ for }~ i=1,2,\ldots ,m.\\&\sum _{i=1}^{m}x_{i\ell } =1,~~~~\text{ for }~ \ell =1,2,\ldots ,m.\\&x_{i\ell }\in \{0, 1\},~~~~\text{ for }~i,\ell =1,2,\ldots ,m. \end{aligned}$$

In the above,

$$\begin{aligned} \begin{aligned} t_{i\ell }&=\overline{\Psi }(m-\ell +1)s_i+\left( r^{1/{(r+1)}}+r^{-r/{(r+1)}}\right) \\ {}&\quad \times \sum _{j=1}^{\overline{n}}\theta _{i[j]} \left( (m-\ell )\overline{\Psi }+(\overline{n}-j+1)\overline{\psi } \right) ^{1/{(r+1)}}, \end{aligned} \end{aligned}$$
(6)

where \(\overline{\Psi }=\overline{n}\overline{\psi }\).

The following algorithm, Algorithm 1, optimally solves this special case, i.e., problem

$$\begin{aligned} 1|GT, DIF, CONV, n_i=\overline{n}, \psi _{ij}=\overline{\psi }|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}). \end{aligned}$$
figure a

Theorem 4.4

Algorithm 1 optimally solves \(1|GT, DIF, CONV, n_i=\overline{n}, \psi _{ij}=\overline{\psi }|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij})\) in \(O(n^3)\) time.

Proof

The correctness of Algorithm 1 is established by Lemmas 3.1, 3.2, and 4.1, together with Lemma 6 in Chen and Cheng (2021). Next we analyze its time complexity. Since \(\sum _{i=1}^{m}n_i=n\), calculating all the optimal job sequences within the m groups in Step 1 requires \(O(\sum _{i=1}^{m}n_i\log n_i)=O(n\log n)\) time. By Lemma 6 in Chen and Cheng (2021), Step 2 requires \(O(m\times \max (n,m^2))=O(n^3)\) time, where the equality holds because \(m=O(n)\). It requires O(n) time to calculate the optimal resource allocation in Step 3, and requires O(n) time to calculate the optimal due dates in Step 4. Therefore, Algorithm 1 runs in \(O(n^3)\) time. \(\square \)

4.2 Optimal schedule for problem \(1|GT, DIF, LIN|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij})\)

First, the following lemma to determine the optimal resource allocation with respect to a given schedule \(\pi \) (for the group sequence and job sequence within each group) is presented.

Lemma 4.5

For problem

$$\begin{aligned} 1|GT, DIF, LIN|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}), \end{aligned}$$

given a schedule \(\pi \) for the group sequence and job sequence within each group, assume that the due date assignment vector \(d^*(\pi )\) is adopted, then the optimal resource allocation with respect to \(\pi \) can be determined by

$$\begin{aligned} u^*_{[i][j]}(\pi )=\left\{ \begin{array}{rcl} 0\,, &{} &{} {~~~if~\eta _{[i][j]}< 0 }\\ \text{ any } \text{ value } \text{ in } [0, \overline{u_{[i][j]}}]\,,&{} &{} {~~~if~\eta _{[i][j]}=0}\\ \overline{u_{[i][j]} }\,, &{} &{}{~~~if~\eta _{[i][j]}>0 } \end{array} \right. \end{aligned}$$
(7)

where \(\eta _{[i][j]}=\sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}-\frac{v_{[i][j]}}{a_{[i][j]}}\), for \(i=1,2,\ldots ,m\) and \(j=1,2,\ldots ,n_i\).

Proof

By \(p_{ij}(u_{ij})=\overline{p_{ij}}-a_{ij}u_{ij}\), we rewrite Eq. (2) as follows

$$\begin{aligned} \begin{aligned} Z(\pi ,d^*(\pi ),u(\pi ))&=\sum _{i=1}^{m}\Psi _{[i]}\left( \sum _{k=1}^{i}s_{[k]}\right) +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\left( \sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) \overline{p_{[i][j]}}\\&\quad +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\left( v_{[i][j]}-a_{ij}\left( \sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) \right) u_{[i][j]}. \end{aligned} \end{aligned}$$

From the above formula for the objective value, for a given schedule \(\pi \), the first two terms are constants, and the objective value can be viewed as a linear function in \(u_{[i][j]}\)’s. Moreover, each variable \(u_{[i][j]}\) only appears in the following term

$$\begin{aligned} \left( v_{[i][j]}-a_{ij}\left( \sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}\right) \right) u_{[i][j]}. \end{aligned}$$

Since all \(a_{[i][j]}\)’s are given positive parameters, if \(\eta _{[i][j]}<0\) then no resource should be allocated to job \(J_{[i][j]}\); if \(\eta _{[i][j]}>0\) then job \(J_{[i][j]}\) should be allocated the maximum amount of resource allowed; and if \(\eta _{[i][j]}=0\), any feasible amount should be optimal. The lemma is established. \(\square \)

To determine the optimal job sequence within each group, we consider a special case where \(\psi _{ij}=\psi _i\) is identical for all jobs in the same group \(G_i\), for \(i=1,2,\ldots ,m\). We will show that, for any given group sequence, in this case the optimal job sequence within each group can be obtained via solving a linear assignment problem, as described in the following lemma.

Lemma 4.6

Given a group sequence, for the case where \(\psi _{ij}=\psi _i\) for all jobs \(J_{ij}\) in group \(G_i\), for each \(i=1,2,\ldots ,m\), the optimal job sequence within group \(G_i\) can be determined in \(O(n_i^3)\) time, and all optimal job sequences for the m groups can be determined in \(O(n^3)\) time.

Proof

Rewrite \(p_{ij}(u_{ij})=\overline{p_{ij}}-a_{ij}u_{ij}\) as \(u_{ij}=\frac{\overline{p_{ij}}-p_{ij}}{a_{ij}}\), and plug it into Eq. (2) for the objective function, we obtain

$$\begin{aligned} Z(\pi ,d^*(\pi ),u(\pi ))=\sum _{i=1}^{m}\Psi _{[i]}\left( \sum _{k=1}^{i}s_{[k]}\right) +\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\frac{\overline{p_{[i][j]}}}{a_{[i][j]}}v_{[i][j]}+\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\eta _{[i][j]}p_{[i][j]}, \end{aligned}$$
(8)

where \(\eta _{[i][j]}=\sum _{k=i+1}^{m}\Psi _{[k]}+\sum _{\ell =j}^{n_{[i]}}\psi _{[i][\ell ]}-\frac{v_{[i][j]}}{a_{[i][j]}}.\)

When the group sequence is given, both the first term \(\sum _{i=1}^{m}\Psi _{[i]}\left( \sum _{k=1}^{i}s_{[k]}\right) \) and the second term \(\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\frac{\overline{p_{[i][j]}}}{a_{[i][j]}}v_{[i][j]}\) in Eq. (8) are constants. Hence, to determine the optimal job sequence within each group, we only need to consider the last term \(\sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\eta _{[i][j]}p_{[i][j]}\) in Eq. (8).

Since for each i, \(\psi _{ij}=\psi _i\) for \(j=1,2,\ldots ,n_i\), it follows that \(\eta _{[i][j]}\) in Eq. (8) can be rewritten as \(\eta _{[i][j]}=\sum _{k=i+1}^{m}\Psi _{[k]}+(n_{[i]}-j+1)\psi _{[i]}-\frac{v_{[i][j]}}{a_{[i][j]}}\). Define

$$\begin{aligned} \eta _{[i]rs}=\sum _{k=i+1}^{m}\Psi _{[k]}+(n_{[i]}-s+1)\psi _{[i]}-\frac{v_{[i]r}}{a_{[i]r}}, \end{aligned}$$
(9)

for \(i=1,2,\ldots ,m\) and \(r,s=1,2,\ldots ,n_{[i]}\), which is the penalty if job \(J_{[i]r}\) is assigned to position s in group \(G_{[i]}\).

According to the optimal resource allocation in Eq. (7), and by \(p_{ij}(u_{ij})=\overline{p_{ij}}-a_{ij}u_{ij}\), we obtain the optimal processing time of job \(J_{[i]r}\) if it is scheduled in the sth position in group \(G_{[i]}\), as follows:

$$\begin{aligned} p_{[i]rs}=\left\{ \begin{array}{lll} \overline{p_{[i]r} }\,, &{} &{} {~~~\text{ if }~\eta _{[i]rs}< 0 }\\ \text{ Any } \text{ value } \text{ in } [\overline{p_{[i]r} }-a_{[i]r}\times \overline{u_{[i]r}}, ~~\overline{p_{[i]r}}]\,,&{} &{} {~~~\text{ if }~\eta _{[i]rs}=0}\\ \overline{p_{[i]r} }-a_{[i]r}\times \overline{u_{[i]r}}\,, &{} &{}{~~~\text{ if }~\eta _{[i]rs}>0 } \end{array} \right. \end{aligned}$$
(10)

Let \(w_{[i]rs}\) be the minimum cost incurred from assigning job \(J_{[i]r}\) to position s in group \(G_{[i]}\). Then \(w_{[i]rs}\) can be expressed as follows:

$$\begin{aligned} w_{[i]rs}=\eta _{[i]rs} \times p_{[i]rs}=\left\{ \begin{array}{lll} \eta _{[i]rs} \times \overline{p_{[i]r} }\,, &{} &{} {~~~\text{ if }~\eta _{[i]rs}< 0 }\\ 0\,,&{} &{} {~~~\text{ if }~\eta _{[i]rs}=0}\\ \eta _{[i]rs} \times \big (\overline{p_{[i]r} }-a_{[i]r}\times \overline{u_{[i]r}} \big )\,, &{} &{}{~~~\text{ if }~\eta _{[i]rs}>0 } \end{array} \right. \end{aligned}$$
(11)

Similar to problem P1, let us define \(x_{[i]rs}=1\) if job \(J_{[i]r}\) is assigned to position s in group \(G_{[i]}\) and \(x_{[i]rs}=0\) otherwise. For a given group sequence, the problem of determining optimal positions for the \(n_{[i]}\) jobs in group \(G_{[i]}\) can be formulated as the following linear assignment problem:

$$\begin{aligned} (P2)~~~&\min ~ \sum _{r=1}^{n_{[i]}} \sum _{s=1}^{n_{[i]}} w_{[i]rs}\times x_{[i]rs} \\ {\textit{s.t.}}~~~&\sum _{s=1}^{n_{[i]}}x_{[i]rs} =1,~~~~\text{ for }~ r=1,2,\ldots ,n_{[i]}.\\&\sum _{r=1}^{n_{[i]}}x_{[i]rs} =1,~~~~\text{ for }~ s=1,2,\ldots ,n_{[i]}.\\&x_{[i]rs}\in \{0, 1\},~~~~\text{ for }~r,s=1,2,\ldots ,n_{[i]}. \end{aligned}$$

Since the linear assignment problem can be solved in cubic time, the optimal job sequence within each group \(G_i\) can be determined in \(O(n_i^3)\) time, and by \(\sum _{i=1}^{m}n_i=n\), all optimal job sequences for the m groups can be determined in \(O(n_{1}^3)+O(n_{2}^3)+\cdots +O(n_{m}^3)=O(n^3)\) time. \(\square \)

To obtain the optimal group sequence, we further consider a special case which is the same as that in Sect. 4.1, that is the number of jobs within each group is the same, i.e., \(n_i=\overline{n}=n/m\) for \(i=1,2,\ldots ,m\), and \(\psi _{ij}=\overline{\psi }\) is identical for \(i=1,2,\ldots ,m\) and \(j=1,2,\ldots ,\overline{n}\).

Lemma 4.7

When \(n_i=n/m=\overline{n}\) for \(i=1,2,\ldots ,m\), and \(\psi _{ij}=\overline{\psi }\) is identical for \(i=1,2,\ldots ,m\) and \(j=1,2,\ldots ,\overline{n}\), the optimal group sequence can be determined in \(O(n^3)\) time.

Proof

Since \(n_1=n_2=\cdots =n_m=n/m=\overline{n}\), and \(\psi _{ij}=\overline{\psi }\) is identical for \(i=1,2,\ldots ,m\) and \(j=1,2,\ldots ,\overline{n}\), recall that \(\Psi _{i}=\sum _{j=1}^{n_{i}}\psi _{ij}\), it follows that the value of \(\Psi _i\) for each group is identical, i.e., \(\Psi _1=\Psi _2=\cdots =\Psi _m=\overline{n}\overline{\psi }=\overline{\Psi }\).

Let \(t_{i\ell }'\) be the minimal cost contributed to the objective function from assigning group \(G_i\) to position \(\ell \). We will show how to determine the three additive terms of \(t_{i\ell }'\) based on the three terms in the objective function as in Eq. 8).

Since \(\Psi _1=\Psi _2=\cdots =\Psi _m=\overline{\Psi }\), the first term in Eq. (8) can be rewritten as

$$\begin{aligned} \sum _{i=1}^{m}\Psi _{[i]}\left( \sum _{k=1}^{i}s_{[k]}\right) =\overline{\Psi }\sum _{i=1}^{m}\sum _{k=1}^{i}s_{[k]}=\overline{\Psi }\sum _{\ell =1}^{m}\sum _{k=1}^{\ell }s_{[k]}=\overline{\Psi }\sum _{\ell =1}^{m}(m-\ell +1)s_{[\ell ]}, \end{aligned}$$

which indicates that the first additive term of \(t_{i\ell }'\) is \(\overline{\Psi }(m-\ell +1)s_{i}\).

The second term in Eq. (8) can be rewritten as

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{n_{[i]}}\frac{\overline{p_{[i][j]}}}{a_{[i][j]}}v_{[i][j]}=\sum _{i=1}^{m}\sum _{j=1}^{n_{i}}\frac{\overline{p_{ij}}}{a_{ij}}v_{ij}=\sum _{i=1}^{m}\sum _{j=1}^{\overline{n}}\frac{\overline{p_{ij}}}{a_{ij}}v_{ij}, \end{aligned}$$

which is a constant, that is, does not depend on schedule \(\pi \). Hence, the second additive term of \(t_{i\ell }'\) is \(\sum _{j=1}^{\overline{n}}\frac{\overline{p_{ij}}}{a_{ij}}v_{ij}\).

By Eq. (9), the positional penalty of assigning job \(J_{[\ell ]r}\) to position s in group \(G_{[\ell ]}\) can be rewritten as

$$\begin{aligned} \eta _{[\ell ]rs}=(m-\ell )\overline{\Psi }+(\overline{n}-s+1)\overline{\psi }-\frac{v_{[\ell ]r}}{a_{[\ell ]r}}, \end{aligned}$$
(12)

for \(\ell =1,2,\ldots ,m\) and \(r,s=1,2,\ldots ,\overline{n}\). From the above formula, if group \(G_i\) is assigned to position \(\ell \) in \(\pi \), then this penalty is \(\eta _{[\ell ]rs}=(m-\ell )\overline{\Psi }+(\overline{n}-s+1)\overline{\psi }-\frac{v_{ir}}{a_{ir}},\) which depends on \(\ell \), the position that group \(G_{i}\) is assigned to in schedule \(\pi \), and s, the position that job \(J_{ir}\) is assigned to within group \(G_{i}\) in \(\pi \). That is, this penalty is independent of the positions of other groups, and the job sequences within other groups. Similarly, by Eq. (10), the optimal processing time of job \(J_{[\ell ]r}\) (i.e., \(J_{ir}\)) if it is scheduled in the sth position within group \(G_{[\ell ]}\) (i.e., \(G_{i}\)) only depends on \(\eta _{[\ell ]rs}\) given above, and given parameters of job \(J_{ir}\) (to be specific, \(\overline{p_{ir}}\), \(a_{ir}\), and \(\overline{u_{ir}}\)). Hence, if \(G_i\) is assigned to position \(\ell \), by applying Lemma 4.6, we can determine in \(O(\overline{n}^3)\) time an optimal job sequence within group \(G_i\) and the corresponding minimum cost \(Z_{i\ell }^{*}\), which is the optimal value of the corresponding linear assignment problem P2.

From the above, for each \(i,\ell =1,2,\ldots ,m\), \(t_{i\ell }'=\overline{\Psi }(m-\ell +1)s_{i}+\sum _{j=1}^{\overline{n}}\frac{\overline{p_{ij}}}{a_{ij}}v_{ij}+Z_{i\ell }^{*}\) can be determined in \(O(\overline{n}^3)\) time, hence the overall complexity of determining all values \(t_{i\ell }'\) for \(i,\ell =1,2,\ldots ,m\) is \(m^2\times O(\overline{n}^3)\), which is \(O(n^3/m)=O(n^3)\) since \(\overline{n}=n/m\).

Let us now define \(x_{i\ell }=1\) if group \(G_i\) is assigned to position \(\ell \) in \(\pi \) and \(x_{i\ell }=0\) otherwise. The problem of determining the optimal positions for the m groups in \(\pi \) can be formulated as the following linear assignment problem:

$$\begin{aligned} (P3)~~~&\min ~ \sum _{i=1}^{m} \sum _{\ell =1}^{m} t_{i\ell }'\times x_{i\ell } \\ {\textit{s.t.}}~~~&\sum _{\ell =1}^{m}x_{i\ell } =1,~~~~\text{ for }~ i=1,2,\ldots ,m.\\&\sum _{i=1}^{m}x_{i\ell } =1,~~~~\text{ for }~ \ell =1,2,\ldots ,m.\\&x_{i\ell }\in \{0, 1\},~~~~\text{ for }~i,\ell =1,2,\ldots ,m. \end{aligned}$$

Since the linear assignment problem can be solved in \(O(m^3)\) time, the overall complexity of determining the optimal group sequence for this special case is \(O(n^3)+O(m^3)=O(n^3)\), which establishes the lemma. \(\square \)

Now we are ready to present Algorithm 2, which optimally solves problem \(1|GT, DIF, LIN, n_i=\overline{n}, \psi _{ij}=\overline{\psi }|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij})\).

figure b

Theorem 4.8

Algorithm 2 optimally solves \(1|GT, DIF, LIN, n_i=\overline{n}, \psi _{ij}=\overline{\psi } |\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij})\) in \(O(n^3)\) time.

Proof

The correctness of Algorithm 2 is established by Lemmas 3.1, 3.2, and 4.5–4.7. Step 1 requires \(O(n^3)\) time by Lemma 4.7, Step 2 requires \(O(n^3)\) time by Lemma 4.6, and calculating the optimal resource allocation and due date assignment vector in Steps 3 and 4 both require O(n) time. Therefore, Algorithm 2 runs in \(O(n^3)\) time. \(\square \)

5 Numerical examples

In this section, we illustrate applying Algorithms 1 and 2 to problems

$$\begin{aligned} 1|GT, DIF, CONV, n_i=\overline{n}, \psi _{ij}=\overline{\psi }|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}) \end{aligned}$$

and

$$\begin{aligned} 1|GT, DIF, LIN, n_i=\overline{n}, \psi _{ij}=\overline{\psi } |\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij}), \end{aligned}$$

respectively, with parameters \(n=12, m=4, n_i=\overline{n}=3, r=1\), and those presented in Table 2.

From Table 2, we can see that \(\psi _{ij}=\min (\alpha _{ij},\,\gamma _{ij})=\overline{\psi }=2\), and \(\Psi _i=\overline{n}\overline{\psi }=\overline{\Psi }=6\), for \(i=1,2,3,4\) and \(j=1,2,3\).

Table 2 Parameters for the numerical examples
Full size table

5.1 Convex resource consumption function

We use Algorithm 1 to solve the above given instance of problem \(1|GT, DIF, CONV, n_i=\overline{n}, \psi _{ij}=\overline{\psi }|\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij})\).

Step 1. Compute \(\theta _{ij}\)’s by \(\theta _{ij}=(w_{ij} v_{ij})^{r/{(r+1)}}\).

 

i, j

1

2

3

\(\theta _{ij}\)=

1

\(\sqrt{10}\)

\(\sqrt{6}\)

\(\sqrt{8}\)

2

\(\sqrt{8}\)

\(\sqrt{15}\)

\(\sqrt{12}\)

3

\(\sqrt{15}\)

\(\sqrt{8}\)

\(\sqrt{9}\)

4

\(\sqrt{6}\)

\(\sqrt{15}\)

\(\sqrt{12}\)

By Lemma 4.3, the optimal job sequences in the four groups can be determined as follows.

$$\begin{aligned} G_1: \{J_{12},~ J_{13},~ J_{11}\};~~~ G_2: \{J_{21},~ J_{23},~ J_{22}\};~~~ G_3: \{J_{32},~ J_{33},~ J_{31}\};~~~ G_4: \{J_{41},~ J_{43},~ J_{42}\}. \end{aligned}$$

Step 2. Compute \(t_{i\ell }\)’s by Eq. (6).

 

\(i,\ell \)

1

2

3

4

\(t_{i\ell }\)=

1

174.817

139.076

100.748

56.258

2

166.850

134.696

99.414

56.667

3

210.496

166.983

120.478

66.811

4

235.137

185.480

132.788

72.811

Compute the optimal group sequence by solving problem P1, the result is \(\{G_2,~ G_1,~ G_3,~ G_4\}\). Hence, the resulting schedule is \(\pi =\{J_{21},J_{23},J_{22},J_{12},J_{13},J_{11},J_{32},J_{33},J_{31},J_{41},J_{43},J_{42}\}\).

Step 3. Use Eq. (4) to compute the optimal resource allocation \(u^*(\pi )\).

 

i, j

1

2

3

\(u_{[i][j]}^*(\pi )\)=

1

3.464

5.416

3.464

2

5.196

2.828

5.916

3

4.899

3.162

2.191

4

2

1.155

1.826

Step 4. By \(p_{ij}(u_{ij})=(\frac{w_{ij}}{u_{ij}})^r\), the actual processing times of all jobs can be calculated as follows.

 

i, j

1

2

3

\(p_{[i][j]}(u^*)\)=

1

0.577

0.739

0.866

2

0.577

0.707

0.845

3

0.816

0.949

1.369

4

1

1.732

2.739

Based on the above matrix of actual processing times of all jobs and by Lemma 3.1, assign to jobs the following optimal due dates.

 

i, j

1

2

3

\(d_{[i][j]}^*(\pi )\)=

1

0

4.316

5.182

2

9.759

10.466

11.311

3

17.127

18.076

19.445

4

0

28.177

30.916

5.2 Linear resource consumption function

We use Algorithm 2 to solve the above given instance of problem \(1|GT, DIF, LIN, n_i=\overline{n}, \psi _{ij}=\overline{\psi } |\sum _{i=1}^{m}\sum _{j=1}^{n_i}(\alpha _{ij}d_{ij}+\beta _{ij}E_{ij}+\gamma _{ij}T_{ij}+v_{ij}u_{ij})\).

Step 1. Compute \(t_{i\ell }'\)’s by Lemma 4.7.

 

\(i,\ell \)

1

2

3

4

\(t_{i\ell }'\)=

1

430

332

226

94

2

510

396

282

116

3

418

322

226

108

4

505

388

265

110

Compute the optimal group sequence by solving problem P3, the result is \(\{G_3, G_1, G_4, G_2\}\).

Step 2. For the above obtained group sequence, for each position i, calculate the values of \(w_{[i]rs}\) in Eq. (11) for \(r,s=1,2,3\). We illustrate the results for \(i=1\) as follows.

 

r, s

1

2

3

\(w_{[1]rs}\)=

1

14

12

10

2

38

34

30

3

20

10

0

Compute the optimal job sequences in four groups by solving problem P2 as in Lemma 4.6. The optimal schedule \(\pi \) is determined as \(\pi =\{J_{31},J_{32},J_{33},J_{13},J_{12},J_{11},J_{41},J_{42},J_{43},J_{23},J_{22},J_{21}\}\).

Step 3. Use Eq. (7) to compute the optimal resource allocation \(u^*(\pi )\).

 

i, j

1

2

3

\(u_{[i][j]}^*(\pi )\)=

1

8

15

20

2

10

0

10

3

15

0

0

4

0

0

0

Step 4. By \(p_{ij}(u_{ij})=\overline{p_{ij}}-a_{ij}u_{ij}\), the actual processing times of all jobs can be calculated as follows.

 

i, j

1

2

3

\(p_{[i][j]}(u^*)\)=

1

1

2

5

2

2

5

6

3

1.5

5

10

4

7

8

12

Based on the above matrix of actual processing times of all jobs and by Lemma 3.1, assign to jobs the following optimal due dates.

 

i, j

1

2

3

\(d_{[i][j]}^*(\pi )\)=

1

6

8

13

2

19

24

30

3

0

42.5

52.5

4

62.5

70.5

0

6 Conclusion

A single machine group scheduling problem with due date assignment and resource allocation is investigated. Jobs in the same group are allowed to have different due dates. The job processing times are resource dependent, and both convex and bounded linear resource consumption functions are considered. The aim is minimizing an aggregate cost which takes into account earliness, tardiness, due date assignment and resource allocation costs, by finding a group schedule, due date assignment and resource allocation for all jobs. For both resource consumption functions, we present properties of the optimal solutions, and for the special case where the size of every group is the same and the minimum of the due date assignment cost and the tardiness cost for each job is identical, we present an algorithm to optimally solve the problem in \(O(n^3)\) time.

As the actual processing time of jobs may be shortened due to learning over time, one possible future research direction is to take into account the learning effect. Also, it is worthwhile to consider the group scheduling problem with resource allocation in the flow shop setting.