Group Technology Scheduling with Due-Date Assignment and Controllable Processing Times

Abstract

This paper investigates common (slack) due-date assignment single-machine scheduling with controllable processing times within a group technology environment. Under linear and convex resource allocation functions, the cost function minimizes scheduling (including the weighted sum of earliness, tardiness, and due-date assignment, where the weights are position-dependent) and resource-allocation costs. Given some optimal properties of the problem, if the size of jobs in each group is identical, the optimal group sequence can be obtained via an assignment problem. We then illustrate that the problem is polynomially solvable in $O\left({\wp }^3\right)$ time, where ℘ is the number of jobs.

1. Introduction

Classical scheduling problems consider fixed job processing times. However, scheduling problems with controllable processing times ($\widetilde{CPT}$, i.e., resource allocation) have received extensive attention (see Lu et al. [1], Liu et al. [2]). In 2018, Li and Wang [3] studied single-machine scheduling with deteriorating jobs and $\widetilde{CPT}$. For the general linear deterioration function, they proved that the weighted sum minimization of the makespan and total resource consumption costs can be solved in polynomial time. Lu and Liu [4] delved into single-machine scheduling with $\widetilde{CPT}$ and position-dependent workloads. For scheduling and total resource consumption costs, they performed bicriterion analysis for the problem. In 2019, Geng et al. [5], and Sun et al. [6] investigated two-machine flow-shop problems with learning effects and $\widetilde{CPT}$. Under common due-date assignment and no-wait constraints, Geng et al. [5] proved that irregular objective minimization is solved in polynomial time. Under slack due-date assignment and no-wait constraints, Sun et al. [6] proved that irregular objective minimization is solved in polynomial time. In 2020, Liu and Jiang [7] studied scheduling with learning effects and $\widetilde{CPT}$ on a two-machine no-wait flow-shop setting. Under common and slack due date assignments, they provided bicriterion analysis for scheduling and resource-consumption costs. In 2021, Lu et al. [8] considered a single-machine due-date assignment problem with $\widetilde{CPT}$ and learning effects. Zhao [9], and Lv and Wang [10] revisited no-wait flow-shop problems with learning effects and $\widetilde{CPT}$. Under a slack (different) due-window assignment, Zhao [9] (Lv and Wang [10]) performed bicriterion analysis of scheduling (including earliness–tardiness penalties, due-window starting times, and the due-window size of all jobs) and resource-consumption costs. Zhao [9], and Lv and Wang [10] proved that several scheduling and resource-consumption costs can be solved in polynomial time. In 2022, Tian [11] addressed single-machine due-window assignment scheduling with $\widetilde{CPT}$. Under linear and convex resource allocation functions, the objective is to minimize generalized earliness and tardiness penalties. For common and slack due-window assignments, they demonstrated that the problem could be solved in polynomial time. In 2023, Wang et al. [12] explored single-machine scheduling with $\widetilde{CPT}$. Under linear and convex resource allocation functions, the objective was to minimize the weighted sum of general earliness–tardiness and resource-consumption costs where weights are position-dependent. They demonstrated that the problem was polynomially solvable.

In addition, the study of group technology ($GT$) is very important (see Liu [13]). In 2018, Wang et al. [14] considered single-machine scheduling with shortened job processing times. Under $GT$ and ready times, they proved that some special cases of the makespan minimization could be solved in polynomial time. In 2019, Huang [15] scrutinized the scheduling with deteriorating jobs and $GT$, and proved that bicriterion single-machine minimization is polynomially solvable, where primary (secondary) criterion is the total weighted completion time (maximal cost). Liu et al. [16] focused on single-machine scheduling $GT$ and deterioration effects. For makespan minimization with ready times, they proposed heuristic and branch-and-bound algorithms, and tested them via randomly instances. In 2021, Wang et al. [17] examined single-machine scheduling with $GT$ and due-date assignment. For common, slack, and different due-date assignments, they proved that irregular objective minimization could be solved in $O\left(n\log n\right)$ time, where n is the number of jobs. In 2022, Wang et al. [18] investigated single-machine scheduling with $GT$ and a shortened proportional linear processing time. For the general problem of makespan minimization, they proposed a heuristic algorithm and a branch-and-bound algorithm to solve the problem. In 2023, Chen et al. [19] scrutinized the single-machine problem with $GT$ and a controllable learning effect. In due-window assignments, the objective is to minimize the total cost comprising due-window related penalties and investment costs. They proved that the problem could be solved in polynomial time.

To our knowledge, scheduling with $GT$ and $\widetilde{CPT}$ are concurrently widely reflected in real production (see Shabtay et al. [20], Zhu et al. [21], Wang et al. [22]). Wang and Liang [23], and Liang et al. [24] explored single-machine scheduling with $GT$, convex $\widetilde{CPT}$, and deterioration effects. In 2023, Yan et al. [25] studied single-machine scheduling with $GT$ and $\widetilde{CPT}$. Under learning effects and limited resource availability, the goal is to minimize the total completion time. These authors proved that some special cases of the problem could be solved in polynomial time. For a general case of the problem, they also proposed heuristic and branch-and-bound algorithms. Chen et al. [26] worked on single-machine scheduling with $GT$ and $\widetilde{CPT}$. In different due-date assignments and for a special case, they proved that the problem could be solved in polynomial time. In view of the importance of $GT$ and $\widetilde{CPT}$, in this article, we continue the work of the concurrent single-machine scheduling with $GT$ and $\widetilde{CPT}$ for a common due-date assignment (${\Xi }_{CON}$; for details, see Gordon et al. [27]) and slack due-date assignment (${\Xi }_{SLK}$; see Gordon et al. [28], Liu et al. [29]). Our objective is to minimize the sum of scheduling (including the weighted sum of earliness, tardiness, and due-date assignments where weights are position-dependent ($\widetilde{PDW}$; see Wang et al. [30], and Wang et al. [31])) and resource-allocation costs. This paper’s contributions are as follows:

• We scrutinize the single-machine due-date assignment problem with the group technology and controllable processing times.
• Under ${\Xi }_{CON}$, and ${\Xi }_{SLK}$, the goal is to minimize the sum of scheduling (including the weighted sum of earliness, tardiness, and due-date assignment, where weights are $\widetilde{PDW}$) and resource-allocation costs.
• The optimal properties of a special case are presented, and we prove that the problem could be solved in polynomial time.

The rest of this article is organized as follows: In Section 2, we present the model. In Section 3 and Section 4, we analyze the linear and convex resource functions, respectively. In Section 5, a numerical example is presented. In Section 6, we conclude the paper.

2. Problem Formulation

A set of ℘ jobs to be processed on a single-machine are divided into ℵ groups $\widetilde{G_1},\widetilde{G_2},\dots ,\widetilde{G_{\aleph }}$, where a number of jobs belong to group $\widetilde{G_i}$ is ${\wp }_i$ and ${\wp }_1+{\wp }_2+\dots +{\wp }_{\aleph }=\wp$. All jobs and the machine are available at Time 0. Machine setup time $\widetilde{s_i}$ is incurred before the jobs are processed in $\widetilde{G_i}$. There is not setup time between jobs in the same group, and jobs within each group must be processed consecutively. Let $J_{ih}$ be the hth job in $\widetilde{G_i}$, $i=1,\dots ,\aleph ;h=1,\dots ,{\wp }_i$. For a linear resource function, the actual processing time of $J_{ih}$ is

$$p_{ih}=a_{ih}-b_{ih}{u}_{ih},0\le u_{ih}\le {\overline{u}}_{ih}<\frac{a_{ih}}{b_{ih}},$$

(1)

where $a_{ih}$ and $b_{ih}$ are the normal processing time and positive compression rate of job $J_{ih}$, respectively (the normal processing time means that the processing time without any resource allocation), $u_{ih}$ is the amount of a nonrenewable resource allocated to $J_{ih}$, and ${\overline{u}}_{ih}$ denotes the maximal amount of the resource allocated to $J_{ih}$. For a convex resource function,

$$p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },$$

(2)

where ${\theta }_{ih}$ is a workload of $J_{ih}$ ($\ell >0$ is a given constant).

Let $C_{ih}=$ and $d_{ih}$ be the completion time and due date, respectively, of $J_{ih}$ in $\widetilde{G_i}$. For the ${\Xi }_{CON}$ assignment, we assumed that $d_{ih}=d_i$; for the ${\Xi }_{SLK}$ assignment, we assumed that $d_{ih}=p_{ih}+q_i$, where $q_i$ denotes common flow allowance for $\widetilde{G_i}$. Let $E_{ih}=\max \{0,d_{ih}-C_{ih}\}$ and $T_{ih}=\max \{0,C_{ih}-d_{ih}\}$ denote the earliness and tardiness, respectively, of job $J_{ih}$. Let $\left[r\right]$ be a scheduled job (group) in the rth position, $J_{i\left[r\right]}$ a scheduled job in the rth position in $\widetilde{G_i}$. Our goal was to find group sequence $\varrho$ and internal job sequence ${\phi }_i$ within $\widetilde{G_i}$, the set of due-dates $\tilde{\mathbf{d}}=\{d_1,d_2,\dots ,d_m\}$ (flow allowances $\tilde{\mathbf{q}}=\{q_1,q_2,\dots ,q_m\}$) and the resource allocation $\tilde{\mathbf{u}}=\left\{u_{ih}\right|i=1,\dots ,\aleph ;h=1,2,\dots ,{\wp }_i\}$ such that cost function

$$\begin{array}{cc}\hfill H(\varrho ,{\phi }_i|i=1,\dots ,\aleph ,\tilde{\mathbf{d}}/\tilde{\mathbf{q}},\tilde{\mathbf{u}})& =\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+\gamma d_i/q_i)+\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{g}_{ih}{u}_{ih}\hfill \\ \hfill & =\sum _{i=1}^m\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i)\hfill \end{array}$$

(3)

is minimized, where ${\alpha }_{ih}$ and ${\beta }_{ih}$ are position-dependent weights for earliness and tardiness costs, i.e., ${\alpha }_{ih}$ and ${\beta }_{ih}$ are not related to job $J_{ih}$, but to position h in group $\widetilde{G_i}$, $\gamma \ge 0$ is a given constant, and $g_{ih}$ is the cost of one unit of the allocated resource to job $J_{ih}$. With three field notations, this problem is denoted as follows:

$$1\left|p_{ih}=a_{ih}-b_{ih}{u}_{ih},{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i)$$

(4)

and

$$1\left|p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i)$$

(5)

where 1 stands for the single-machine, field $\{p_{ih},{\Xi }_{CON}/{\Xi }_{SLK},GT,PDW\}$ denotes the characteristics of jobs and groups, and ${\sum }_{i=1}^{\aleph }{\sum }_{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i)$ is the cost function. The notations and symbols used in this article are listed in

Table 1. Symbols.

Symbol	Definition
℘ (resp. ℵ)	number of jobs (resp. groups)
$\widetilde{G_i}$	group i, $i=1,\cdots ,\aleph$
${\wp }_i$	Number of jobs in $\widetilde{G_i}$
$J_{ih}$	Job h in $\widetilde{G_i}$
$a_{ih}$ and $b_{ih}$	Normal processing time and compression rate, respectively, of $J_{ih}$
${\theta }_{ih}$	Workload of $J_{ih}$
$u_{ih}$ and ${\overline{u}}_{ih}$	Amount and maximal amount, respectively, of the assigned resource to $J_{ih}$
$p_{ih}$	Actual processing time of $J_{ih}$
$\widetilde{s_i}$	setup time of $\widetilde{G_i}$
$C_{ih}$ and $d_{ih}$	Completion time and due date, respectively, of $J_{ih}$
$E_{ih}$ and $T_{ih}$	Earliness and tardiness, respectively, of $J_{ih}$
$d_i$ and $q_i$	Common due date and flow allowance, respectively, of $\widetilde{G_i}$
${\alpha }_{ih}$ and ${\beta }_{ih}$)	Position-dependent weights of earliness and tardiness, respectively, in the hth position in $\widetilde{G_i}$
$g_{ih}$	Unit resource cost for $J_{ih}$

.

3. Linear Resource Function

There exists an optimal sequence that does not include idle machine times. Let ${\tilde{S}}_i$ be the starting time of $\widetilde{G_i}$, for a given job sequence ${\phi }_i$ within $\widetilde{G_i}$; completion times of $J_{i\left[h\right]}$ is

$$C_{i\left[h\right]}={\tilde{S}}_i+\widetilde{s_i}+\sum _{l=1}^h{p}_{i\left[l\right]}$$

(6)

Lemma 1.

For a given job sequence ${\phi }_i$ and resource allocation within group $\widetilde{G_i}$, under ${\Xi }_{CON}$ and ${\Xi }_{SLK}$ assignments, if the values of $d_i$ and $q_i$, respectively, are within the starting and ending times of $\widetilde{G_i}$, there exists an optimal value at which $d_i$ and $q_i$ are equal to the completion time of some job ($i=1,\dots ,\aleph$).

Proof. 

For the ${\Xi }_{CON}$ assignment, it was assumed that $C_{i\left[k_i\right]}<d_i<C_{i[k_i+1]}$, where $k_i$ is the $k_i$th position of group $\widetilde{G_i}$, we have

$$\begin{array}{cc}\hfill H_i& =\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i)\hfill \\ \hfill & =\sum _{h=1}^{k_i}{\alpha }_{ih}{E}_{i\left[h\right]}+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}{T}_{i\left[h\right]}+\sum _{h=1}^{{\wp }_i}{g}_{ih}{u}_{ih}+\gamma {\wp }_i{d}_i\hfill \\ \hfill & =\sum _{h=1}^{k_i}{\alpha }_{ih}(d_i-C_{i\left[h\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-d_i)+\sum _{h=1}^{{\wp }_i}{g}_{ih}{u}_{ih}+\gamma {\wp }_i{d}_i\hfill \end{array}$$

(7)

If $d_i=C_{i\left[k_i\right]}$,

$$H_i^{\prime }=\sum _{h=1}^{k_i}{\alpha }_{ih}(C_{i\left[k_i\right]}-C_{i\left[h\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-C_{i\left[k_i\right]})+\sum _{h=1}^{{\wp }_i}{g}_{ih}{u}_{ih}+\gamma {\wp }_i{C}_{i\left[k_i\right]}$$

(8)

If $d_i=C_{i[k_i+1]}$,

$$H_i^{″}=\sum _{h=1}^{k_i}{\alpha }_{ih}(C_{i[k_i+1]}-C_{i\left[h\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-C_{i[k_i+1]})+\sum _{h=1}^{{\wp }_i}{g}_{ih}{u}_{ih}+\gamma {\wp }_i{C}_{i[k_i+1]}$$

(9)

Then

$$\begin{array}{cc}\hfill H_i-H_i^{\prime }& =\sum _{h=1}^{k_i}{\alpha }_{ih}(d_i-C_{i\left[k_i\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[k_i\right]}-d_i)+\gamma {\wp }_i(d_i-C_{i\left[k_i\right]})\hfill \\ \hfill & =(d_i-C_{i\left[k_i\right]})\left(\gamma {\wp }_i+\sum _{h=1}^{k_i}{\alpha }_{ih}-\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}\right)\hfill \end{array}$$

(10)

and

$$\begin{array}{cc}\hfill H_i-H_i^{″}& =\sum _{h=1}^{k_i}{\alpha }_{ih}(d_i-C_{i[k_i+1]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i[k_i+1]}-d_i)+\gamma {\wp }_i(d_i-C_{i[k_i+1]})\hfill \\ \hfill & =(d_i-C_{i[k_i+1]})\left(\gamma {\wp }_i+\sum _{h=1}^{k_i}{\alpha }_{ih}-\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}\right)\hfill \end{array}$$

(11)

Thus, if $C_{i\left[k_i\right]}<d_i<C_{i[k_i+1]}$ and $\gamma {\wp }_i+{\sum }_{h=1}^{k_i}{\alpha }_{ih}-{\sum }_{h=k_i+1}^{{\wp }_i}{\beta }_{ih}\ge 0$, we have $H_i-H_i^{\prime }\ge 0$; if $\gamma {\wp }_i+{\sum }_{h=1}^{k_i}{\alpha }_{ih}-{\sum }_{h=k_i+1}^{{\wp }_i}{\beta }_{ih}\le 0$, we have $H_i-H_i^{\prime }\ge 0$, hence, we can see that $d_i$ coincides with some job completion time of $\widetilde{G_i}$.

For the ${\Xi }_{SLK}$ method, this result can be similarly obtained. □

Lemma 2.

For a given job sequence ${\phi }_i$ within $\widetilde{G_i}$, under ${\Xi }_{CON}/{\Xi }_{SLK}$ assignment, there exists an optimal $d_i=C_{i\left[k_i\right]}/\left(q_i=C_{i[k_i-1]}\right)$ where $k_i$ satisfies the following inequality: ${\sum }_{h=k_i+1}^{{\wp }_i}{\beta }_{ih}-{\sum }_{h=1}^{k_i}{\alpha }_{ih}\le \gamma {\wp }_i\le {\sum }_{h=k_i}^{{\wp }_i}{\beta }_{ih}-{\sum }_{h=1}^{k_i-1}{\alpha }_{ih}$.

Proof. 

For the ${\Xi }_{CON}$ assignment, from Lemma 1, it was assumed that $d_i=C_{i\left[k_i\right]}$; we then have

$$H_i=\sum _{h=1}^{k_i}{\alpha }_{ih}(C_{i\left[k_i\right]}-C_{i\left[h\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-C_{i\left[k_i\right]})+\sum _{h=1}^{n_i}{g}_{ih}{u}_{ih}+\gamma {\wp }_i{C}_{i\left[k_i\right]}$$

(12)

With the technique of small perturbations, if $d_i=C_{i\left[k_i\right]}+\epsilon$ ($\epsilon \gg 0$),

$$H_i^{\prime }=\sum _{h=1}^{k_i}{\alpha }_{ih}(C_{i\left[k_i\right]}+\epsilon -C_{i\left[h\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-C_{i\left[k_i\right]}-\epsilon )+\sum _{h=1}^{n_i}{g}_{ih}{u}_{ih}+\gamma {\wp }_i(C_{i\left[k_i\right]}+\epsilon )$$

(13)

if $d_i=C_{i\left[k_i\right]}-\epsilon$,

$$H_i^{″}=\sum _{h=1}^{k_i-1}{\alpha }_{ih}(C_{i\left[k_i\right]}-\epsilon -C_{i\left[h\right]})+\sum _{h=k_i}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-C_{i\left[k_i\right]}+\epsilon )+\sum _{h=1}^{{\wp }_i}{g}_{ih}{u}_{ih}+\gamma {\wp }_i(C_{i\left[k_i\right]}-\epsilon )$$

(14)

$$H_i-H_i^{\prime }=-\epsilon \left(\gamma {\wp }_i+\sum _{h=1}^{k_i}{\alpha }_{ih}-\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}\right)\le 0$$

(15)

$$H_i-H_i^{″}=\epsilon \left(\gamma {\wp }_i+\sum _{h=1}^{k_i-1}{\alpha }_{ih}-\sum _{h=k_i}^{{\wp }_i}{\beta }_{ih}\right)\le 0$$

(16)

Hence, $k_i$ satisfies $\gamma {\wp }_i+{\sum }_{h=1}^{k_i}{\alpha }_{ih}-{\sum }_{h=k_i+1}^{{\wp }_i}{\beta }_{ih}\ge 0$ and $\gamma {\wp }_i+{\sum }_{h=1}^{k_i-1}{\alpha }_{ih}-{\sum }_{h=k_i}^{{\wp }_i}{\beta }_{ih}\le 0$, i.e., ${\sum }_{h=k_i+1}^{{\wp }_i}{\beta }_{ih}-{\sum }_{h=1}^{k_i}{\alpha }_{ih}\le \gamma {\wp }_i\le {\sum }_{h=k_i}^{{\wp }_i}{\beta }_{ih}-{\sum }_{h=1}^{k_i-1}{\alpha }_{ih}$.

For the ${\Xi }_{SLK}$ assignment, the result can similarly be obtained. □

Remark 1.

If $k_i$ does not satisfy inequality ${\sum }_{h=k_i+1}^{{\wp }_i}{\beta }_{ih}-{\sum }_{h=1}^{k_i}{\alpha }_{ih}\le \gamma {\wp }_i\le {\sum }_{h=k_i}^{{\wp }_i}{\beta }_{ih}-{\sum }_{h=1}^{k_i-1}{\alpha }_{ih}$, we can set $k_i=0$.

For the ${\Xi }_{CON}$ assignment, from Equation (6), Lemma 2, and $d_i=C_{i\left[k_i\right]}={\tilde{S}}_i+\widetilde{s_i}+{\sum }_{l=1}^{k_i}{p}_{i\left[l\right]}$, we have

$$\begin{array}{cc}\hfill H\left({\Xi }_{CON}\right)& =\sum _{i=1}^{\aleph }\left(\sum _{h=1}^{k_i}{\alpha }_{ih}(d_i-C_{i\left[h\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-d_i)+\gamma {\wp }_i{d}_i+\sum _{h=1}^{{\wp }_i}{g}_{i\left[h\right]}{u}_{i\left[h\right]}\right)\hfill \\ \hfill & =\sum _{i=1}^{\aleph }\left(\sum _{h=1}^{k_i}{\alpha }_{ih}(C_{i\left[k_i\right]}-C_{i\left[h\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-C_{i\left[k_i\right]})+\gamma {\wp }_i{C}_{i\left[k_i\right]}+\sum _{h=1}^{{\wp }_i}{g}_{i\left[h\right]}{u}_{i\left[h\right]}\right)\hfill \\ \hfill & =\sum _{i=1}^{\aleph }\left(\sum _{h=1}^{k_i}{\alpha }_{ih}\left(\sum _{l=1}^{k_i}{p}_{i\left[l\right]}-\sum _{l=1}^h{p}_{i\left[l\right]}\right)+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}\left(\sum _{l=1}^h{p}_{i\left[l\right]}-\sum _{l=1}^{k_i}{p}_{i\left[l\right]}\right)\right)\hfill \\ \hfill & +\gamma \sum _{i=1}^{\aleph }{\wp }_i\left({\tilde{S}}_i+\widetilde{s_i}+\sum _{l=1}^{k_i}{p}_{i\left[l\right]}\right)+\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{g}_{i\left[h\right]}{u}_{i\left[h\right]}\hfill \\ \hfill & =\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{\xi }_{ih}{p}_{i\left[h\right]}+\gamma \sum _{i=1}^{\aleph }{\wp }_i\left({\tilde{S}}_i+\widetilde{s_i}\right)+\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{g}_{i\left[h\right]}{u}_{i\left[h\right]}\hfill \end{array}$$

(17)

where

$${\xi }_{ih}=\left\{\begin{array}{cc}\sum _{l=1}^{h-1}{\alpha }_{il}+\gamma n_i,\hfill & h=1,2,\dots ,k_i,\hfill \\ \sum _{l=h}^{n_i}{\beta }_{il},\hfill & h=k_i+1,k_i+2,\dots ,{\wp }_i.\hfill \end{array}\right.$$

(18)

For the ${\Xi }_{SLK}$ assignment, from Equation (6), Lemma 2, and $q_i=C_{i[k_i-1]}={\tilde{S}}_i+\widetilde{s_i}+{\sum }_{l=1}^{k_i-1}{p}_{i\left[l\right]}$, we have

$$\begin{array}{cc}\hfill H\left({\Xi }_{SLK}\right)& =\sum _{i=1}^{\aleph }\left(\sum _{h=1}^{k_i}{\alpha }_{ih}(d_{i\left[h\right]}-C_{i\left[h\right]})+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-d_{i\left[h\right]})+\gamma {\wp }_i{q}_i+\sum _{h=1}^{{\wp }_i}{g}_{i\left[h\right]}{u}_{i\left[h\right]}\right)\hfill \\ \hfill & =\sum _{i=1}^{\aleph }\sum _{h=1}^{k_i}{\alpha }_{ih}(p_{i\left[h\right]}+C_{i[k_i-1]}-C_{i\left[h\right]})+\sum _{i=1}^{\aleph }\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}(C_{i\left[h\right]}-p_{i\left[h\right]}-C_{i[k_i-1]})\hfill \\ \hfill & +\sum _{i=1}^{\aleph }\gamma {\wp }_i{C}_{i[k_i-1]}+\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{g}_{i\left[h\right]}{u}_{i\left[h\right]}\hfill \\ \hfill & =\sum _{i=1}^{\aleph }\left(\sum _{h=1}^{k_i}{\alpha }_{ih}\left(\sum _{l=1}^{k_i-1}{p}_{i\left[l\right]}-\sum _{l=1}^{h-1}{p}_{i\left[l\right]}\right)+\sum _{h=k_i+1}^{{\wp }_i}{\beta }_{ih}\left(\sum _{l=1}^{h-1}{p}_{i\left[l\right]}-\sum _{l=1}^{k_i-1}{p}_{i\left[l\right]}\right)\right)\hfill \\ \hfill & +\gamma \sum _{i=1}^{\aleph }{\wp }_i\left({\tilde{S}}_i+\widetilde{s_i}+\sum _{l=1}^{k_i-1}{p}_{i\left[l\right]}\right)+\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{g}_{i\left[h\right]}{u}_{i\left[h\right]}\hfill \\ \hfill & =\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{\xi }_{ih}{p}_{i\left[h\right]}+\gamma \sum _{i=1}^{\aleph }{\wp }_i\left({\tilde{S}}_i+\widetilde{s_i}\right)+\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{g}_{i\left[h\right]}{u}_{i\left[h\right]}\hfill \end{array}$$

(19)

where

$${\xi }_{ih}=\left\{\begin{array}{cc}\sum _{l=1}^h{\alpha }_{il}+\gamma n_i,\hfill & h=1,2,\dots ,k_i-1,\hfill \\ \sum _{l=h+1}^{n_i}{\beta }_{il},\hfill & h=k_i,k_i+1,\dots ,{\wp }_i-1,\hfill \\ 0,\hfill & h={\wp }_i.\hfill \end{array}\right.$$

(20)

Since $k_i$ values are independent of $\varrho$ and ${\phi }_i$ ($i=1,\dots ,\aleph$), from Lemmas 1 and 2, if $p_{ih}=a_{ih}-b_{ih}{u}_{ih}$, the cost objective can be expressed:

$$\begin{array}{cc}\hfill H({\Xi }_{CON}/{\Xi }_{SLK})& =\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{a}_{\left[i\right]\left[h\right]}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)+\gamma \sum _{i=1}^{\aleph }\left({\wp }_{\left[i\right]}\times \sum _{r=1}^i\widetilde{s_{\left[r\right]}}\right)\hfill \\ \hfill & +\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}\left(g_{\left[i\right]\left[h\right]}-b_{\left[i\right]\left[h\right]}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)\right)u_{\left[i\right]\left[h\right]}\hfill \end{array}$$

(21)

where for the ${\Xi }_{CON}$ assignment,

$${\xi }_{\left[i\right]h}=\left\{\begin{array}{cc}\sum _{l=1}^{h-1}{\alpha }_{\left[i\right]l}+\gamma {\wp }_{\left[i\right]},\hfill & h=1,2,\dots ,k_i,\hfill \\ \sum _{l=h}^{n_i}{\beta }_{\left[i\right]l},\hfill & h=k_i+1,k_i+2,\dots ,{\wp }_i.\hfill \end{array}\right.$$

(22)

For the ${\Xi }_{SLK}$ assignment,

$${\xi }_{\left[i\right]h}=\left\{\begin{array}{cc}\sum _{l=1}^h{\alpha }_{\left[i\right]l}+\gamma {\wp }_{\left[i\right]},\hfill & h=1,2,\dots ,k_i-1,\hfill \\ \sum _{l=h+1}^{{\wp }_i}{\beta }_{\left[i\right]l},\hfill & h=k_i,k_i+1,\dots ,{\wp }_i-1,\hfill \\ 0,\hfill & h={\wp }_i.\hfill \end{array}\right.$$

(23)

Lemma 3.

In the given group sequence and job sequence within each group, optimal resource allocation ${\tilde{\mathbf{u}}}^{*}(\varrho ,{\phi }_1,\dots ,{\phi }_{\aleph })$ is

$$u_{\left[i\right]\left[h\right]}^{*}=\left\{\begin{array}{cc}{\overline{u}}_{\left[i\right]\left[h\right]},\hfill & \hfill \mathrm{if}{g}_{\left[i\right]\left[h\right]}-b_{\left[i\right]\left[h\right]}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)<0,\\ u_{\left[i\right]\left[h\right]}\in [0,{\overline{u}}_{\left[i\right]\left[h\right]}],\hfill & \hfill \mathrm{if}{g}_{\left[i\right]\left[h\right]}-b_{\left[i\right]\left[h\right]}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)=0,\\ 0,\hfill & \hfill \mathrm{if}{g}_{\left[i\right]\left[h\right]}-b_{\left[i\right]\left[h\right]}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)>0.\end{array}\right.$$

(24)

Proof. 

Let the derivative of Equation (21) with respect to $u_{\left[i\right]\left[j\right]}$ be equal to 0, and the result can be obtained. □

For a given group order $\varrho$, from Equation (21), ${\sum }_{i=1}^{\aleph }{\sum }_{h=1}^{{\wp }_i}{a}_{\left[i\right]\left[h\right]}\left({\xi }_{\left[i\right]h}+\gamma {\sum }_{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)$

$+{\sum }_{i=1}^{\aleph }{\sum }_{h=1}^{{\wp }_i}\left(g_{\left[i\right]\left[h\right]}-b_{\left[i\right]\left[h\right]}\left({\xi }_{\left[i\right]h}+\gamma {\sum }_{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)\right)u_{\left[i\right]\left[h\right]}$ is dependent only on the internal job sequence, while term $\gamma {\sum }_{i=1}^{\aleph }\left({\wp }_{\left[i\right]}\times {\sum }_{r=1}^i\widetilde{s_{\left[r\right]}}\right)$ is independent of the internal job sequence within each group. Now, we prove that the optimal sequence within each group can be obtained with the following lemma.

Lemma 4.

Given group order ϱ, optimal job sequence ${\phi }_i^{*}\left(\varrho \right)$ within $\widetilde{G_i}\left(\varrho \right)$ is obtained in $O\left({\wp }_i^3\right)$ time.

Proof. 

For a given $\widetilde{G_{\left[i\right]}}$, let $x_{jh}^{\left[i\right]}$ be a binary variable, i.e., if $J_{\left[i\right]j}$ in $\widetilde{G_{\left[i\right]}}$ is assigned to hth position, $x_{jh}^{\left[i\right]}=1$; otherwise, $x_{jh}^{\left[i\right]}=0$, $j,h=1,\dots ,{\wp }_{\left[i\right]}$. Let

$${\vartheta }_{jh}^{\left[i\right]}=\left\{\begin{array}{c}{g}_{\left[i\right]j}{\overline{u}}_{\left[i\right]j}+(a_{\left[i\right]j}-b_{\left[i\right]j}{\overline{u}}_{\left[i\right]j})\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left(n_{\left[r\right]}\right)\right),\hfill \\ \mathrm{if}{g}_{\left[i\right]j}-b_{\left[i\right]j}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)\le 0;\hfill \\ a_{\left[i\right]j}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left(n_{\left[r\right]}\right)\right),\hfill \\ \mathrm{if}{g}_{\left[i\right]j}-b_{\left[i\right]j}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)>0.\hfill \end{array}\right.$$

(25)

As in Wang et al. [22], optimal job sequence ${\phi }_i^{*}\left(\varrho \right)$ can be obtained with the assignment problem ($\widetilde{AP}$):

$$\mathrm{Min}\sum _{j=1}^{{\wp }_{\left[i\right]}}\sum _{h=1}^{{\wp }_{\left[i\right]}}{\vartheta }_{jh}^{\left[i\right]}{x}_{jh}^{\left[i\right]}$$

(26)

$$\mathrm{s}.\mathrm{t}.$$

$$\sum _{j=1}^{{\wp }_{\left[i\right]}}{x}_{jh}^{\left[i\right]}=1,h=1,\dots ,{\wp }_{\left[i\right]},$$

(27)

$$\sum _{h=1}^{{\wp }_{\left[i\right]}}{x}_{jh}^{\left[i\right]}=1,j=1,\dots ,{\wp }_{\left[i\right]},$$

(28)

$$x_{jh}^{\left[i\right]}\in \{0,1\},j,h=1,\dots ,{\wp }_{\left[i\right]}.$$

(29)

The above $\widetilde{AP}$ is solvable in $O\left(n_{\left[i\right]}^3\right)$ time; hence, determining the total complexity of ${\phi }_i\left(\varrho \right)$ ($i=1,\dots ,\aleph$) is bounded by ${\sum }_{i=1}^{\aleph }O\left({\wp }_{\left[i\right]}^3\right)=O\left({\wp }^3\right).$ □

For

$$1\left|p_{ih}=a_{ih}-b_{ih}{u}_{ih},{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i),$$

from Lemmas 1–4, the complexity of determining the optimal group sequence is still an open problem, so we discuss a special case, i.e., ${\wp }_i=\widehat{N}$, $i=1,\dots ,\aleph$.

Lemma 5.

For

$$1\left|p_{ih}=a_{ih}-b_{ih}{u}_{ih},{\Xi }_{CON}/{\Xi }_{SLK},GT,PDW\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i),$$

if ${\wp }_i=\widehat{N}$ ($i=1,\dots ,\aleph$), the optimal group sequence ${\varrho }^{*}$ is obtained by $\widetilde{AP}$ in $O\left({\wp }^3\right)$ time.

Proof. 

From Equation (21), cost function (3) is determined by both the group and job sequences. Optimal job sequence ${\phi }_i^{*}$ can be obtained with Lemma 4, and the cost function with ${\phi }_i^{*}$ is just dependent on the ith group position in $\varrho$. In $n_i=\widehat{N}$ ($i=1,\dots ,\aleph$), term $\gamma {\sum }_{i=1}^{\aleph }\left({\wp }_{\left[i\right]}\times {\sum }_{r=1}^i\widetilde{s_{\left[r\right]}}\right)=\gamma \widehat{N}{\sum }_{i=1}^{\aleph }\left[(\aleph -i+1)\widetilde{s_{\left[r\right]}}\right]$. Let $y_{ir}$ be a binary variable. If group $\widetilde{G_i}$ is assigned to rth position, $y_{ir}=1$; otherwise, $y_{ir}=0$, $i,r=1,\cdots ,\aleph$. Let

$${\chi }_{ir}=\left\{\begin{array}{c}\sum _{j=1}^{\widehat{N}}\left(g_{i\left[j\right]}{\overline{u}}_{i\left[j\right]}+(a_{i\left[j\right]}-b_{i\left[j\right]}{\overline{u}}_{i\left[j\right]})\left({\xi }_{ij}+\gamma (\aleph -r)\widehat{N}\right)\right)+\gamma \widehat{N}(\aleph -r+1)\widetilde{s_i},\hfill \\ \mathrm{if}{g}_{i\left[j\right]}-b_{i\left[j\right]}\left({\xi }_{ij}+\gamma (\aleph -r)\widehat{N}\right)\le 0;\hfill \\ \sum _{j=1}^{\widehat{N}}\left(a_{i\left[j\right]}\left({\xi }_{ij}+\gamma (\aleph -r)\widehat{N}\right)\right)+\gamma \widehat{N}(\aleph -r+1)\widetilde{s_i},\hfill \\ \mathrm{if}{g}_{i\left[j\right]}-b_{i\left[j\right]}\left({\xi }_{\left[i\right]j}+\gamma (\aleph -r)\widehat{N}\right)>0.\hfill \end{array}\right.$$

(30)

As in Shabtay et al. [20], optimal group sequence ${\varrho }^{*}$ was obtained with the following $\widetilde{AP}$:

$$\mathrm{Min}\sum _{i=1}^{\aleph }\sum _{r=1}^{\aleph }{\chi }_{ir}{y}_{ir}$$

(31)

$$\mathrm{s}.\mathrm{t}.$$

$$\sum _{i=1}^{\aleph }{y}_{ir}=1,r=1,\dots ,\aleph ,$$

(32)

$$\sum _{r=1}^{\aleph }{y}_{ir}=1,i=1,\dots ,\aleph ,$$

(33)

$$y_{ir}\in \{0,1\},i,r=1,\dots ,\aleph .$$

(34)

The above $\widetilde{AP}$ is solvable in $O\left({\aleph }^3\right)\le O\left({\wp }^3\right)$ time. □

Via Lemmas 1–5 and the above analysis, for ${\wp }_i=\widehat{N}$ ($i=1,\dots ,\aleph$), the following algorithm (i.e., Algorithm 1) is presented to solve

$$1\left|p_{ih}=a_{ih}-b_{ih}{u}_{ih},{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i).$$

Theorem 1.

If ${\wp }_i=\widehat{N}$ ($i=1,\dots ,\aleph$), Algorithm 1 solves

$$1|p_{ih}=a_{ih}-b_{ih}{u}_{ih},{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i)$$

in $O\left({\wp }^3\right)$ time.

Algorithm 1: Linear resource function

Step 1. Calculate $k_i$ by Lemma 2.

Step 2. For each possible position of each group in $\varrho$, calculate ${\vartheta }_{jh}^{\left[i\right]}$ with Equation (25) for $j,h=1,\dots ,\widehat{N}$, where for the ${\Xi }_{CON}$ assignment, ${\xi }_{\left[i\right]h}$ is given by Equation (22), and for the ${\Xi }_{SLK}$ assignment, ${\xi }_{\left[i\right]h}$ is given by Equation (23).

Step 3. Solve $\widetilde{AP}$ (26)–(29) to find internal job sequence ${\phi }_{ir}^{*}$ within $\widetilde{G_i}$ if this group is assigned to the rth position in $\varrho$.

Step 4. Calculate ${\chi }_{ir}$ with Equation (30) with ${\phi }_{ir}^{*}$ for $i,r=1,\dots ,\aleph$.

Step 5. Solve $\widetilde{AP}$ (31)–(34) to find optimal sequences ${\varrho }^{*}$ and ${\phi }_i^{*}$.

Step 6. Compute optimal resource allocation $u_{ih}^{*}({\varrho }^{*},{\phi }_1^{*},\dots ,{\phi }_{\aleph }^{*})$ with Equation (24).

Step 7. For the ${\Xi }_{CON}$ and ${\Xi }_{SLK}$ assignments, calculate $d_i^{*}=C_{i\left[k_i\right]}$ and $q_i^{*}=C_{i[k_i-1]}$, respectively, with Lemma 2.

Proof. 

With Lemmas 1–5, the correctness of Algorithm 1 can be confirmed. Steps 1, 6, and 7 need $O(\wp )$ time; Steps 2 and 3 need $O\left({\wp }^3\right)$ time; Steps 4 and 5 need $O\left({\aleph }^3\right)\le O\left({\wp }^3\right)$ time. Thus, the total computational time is $O\left({\wp }^3\right)$. □

4. Convex Resource Function

Similar to Section 3, for problem

$$1\left|p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i),$$

we have

$$\begin{array}{cc}\hfill H({\Xi }_{CON}/{\Xi }_{SLK})& =\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right){\left(\frac{{\theta }_{\left[i\right]\left[h\right]}}{u_{\left[i\right]\left[h\right]}}\right)}^{\ell }+\gamma \sum _{i=1}^{\aleph }\left({\wp }_{\left[i\right]}\times \sum _{r=1}^i\widetilde{s_{\left[r\right]}}\right)\hfill \\ \hfill & +\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}{g}_{\left[i\right]\left[h\right]}{u}_{\left[i\right]\left[h\right]},\hfill \end{array}$$

(35)

where for the ${\Xi }_{CON}$ assignment, ${\xi }_{\left[i\right]h}$ is given by Equation (22), and for the ${\Xi }_{SLK}$ assignment, ${\xi }_{\left[i\right]h}$ is given by Equation (23), $i,h=1,\dots ,{\wp }_i$.

Lemma 6.

Under the given group and job sequences

$$1\left|p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i),$$

the optimal resource allocation ${\tilde{\mathbf{u}}}^{*}(\varrho ,{\phi }_1,\dots ,{\phi }_{\aleph })$ is

$$u_{\left[i\right]\left[h\right]}^{*}={\left(\frac{\ell \left({\xi }_{\left[i\right]h}+\gamma {\sum }_{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)}{g_{\left[i\right]\left[h\right]}}\right)}^{\frac{1}{\ell +1}}\times {\left({\theta }_{\left[i\right]\left[h\right]}\right)}^{\frac{\ell }{\ell +1}},$$

(36)

where for the ${\Xi }_{CON}$ assignment, ${\xi }_{\left[i\right]h}$ is given by Equation (22), and for the ${\Xi }_{SLK}$ assignment, ${\xi }_{\left[i\right]h}$ is given by Equation (23), $i,h=1,\dots ,{\wp }_i$.

Proof. 

From Equation (35), H is a convex function of $u_{\left[i\right]\left[h\right]}$; hence, let

$$\frac{\partial H}{\partial u_{\left[i\right]\left[h\right]}}=g_{\left[i\left]\right[h\right]}-\ell \left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)\right)\frac{{\left({\theta }_{\left[i\right]\left[h\right]}\right)}^{\ell }}{{\left(u_{\left[i\right]\left[h\right]}\right)}^{\ell +1}}=0,$$

and the result of Equation (36) can be obtained. □

By ubstituting Equation (36) into Equation (35), it follows that

$$\begin{array}{cc}\hfill H(\varrho ,{\phi }_1,\dots ,{\phi }_{\aleph },{\tilde{\mathbf{u}}}^{*})& =\left({\ell }^{\frac{-\ell }{\ell +1}}+{\ell }^{\frac{1}{\ell +1}}\right)\sum _{i=1}^{\aleph }\sum _{j=1}^{{\wp }_{\left[i\right]}}{\left({\xi }_{\left[i\right]h}+\gamma \sum _{r=i+1}^m\left({\wp }_{\left[r\right]}\right)\right)}^{\frac{1}{\ell +1}}{\left(g_{\left[i\right]\left[h\right]}{\theta }_{\left[i\right]\left[h\right]}\right)}^{\frac{\ell }{\ell +1}}\hfill \\ \hfill & +\gamma \sum _{i=1}^{\aleph }\left({\wp }_{\left[i\right]}\times \sum _{r=1}^i\widetilde{s_{\left[r\right]}}\right)\hfill \end{array}$$

(37)

For the ${\Xi }_{CON}$ assignment, let

$${\xi }_{ih}=\left\{\begin{array}{ccc}\sum _{l=1}^{h-1}{\alpha }_{il}+\gamma {\wp }_i,\hfill & & h=1,\dots ,k_i,\hfill \\ \sum _{l=h}^{n_i}{\beta }_{il},\hfill & & h=k_i+1,k_i+2,\dots ,{\wp }_i,\hfill \end{array}\right.$$

(38)

For the ${\Xi }_{SLK}$ assignment, let

$${\xi }_{ih}=\left\{\begin{array}{ccc}\sum _{l=1}^h{\alpha }_{il}+\gamma n_{\left[i\right]},\hfill & & h=1,\dots ,k_i-1,\hfill \\ \sum _{l=h+1}^{n_i}{\beta }_{il},\hfill & & h=k_i,k_i+1,\dots ,{\wp }_i-1,\hfill \\ 0,\hfill & & h={\wp }_i.\hfill \end{array}\right.$$

(39)

Lemma 7.

Given group order ϱ, optimal job sequence ${\phi }_i^{*}$ ($i=1,\dots ,\aleph$) within $\widetilde{G_i}$ can be obtained by matching the smallest and second smallest ${\xi }_{ih}$ to the job with the largest and second largest $g_{ih}{\theta }_{ih}$, respectively, and so on.

Proof. 

From Equation (37), $\left({\ell }^{\frac{-\ell }{\ell +1}}+{\ell }^{\frac{1}{\ell +1}}\right)$ is a given constant, $\gamma {\sum }_{r=i+1}^{\aleph }\left({\wp }_{\left[r\right]}\right)$ and $\gamma {\sum }_{i=1}^{\aleph }$$\left({\wp }_{\left[i\right]}\times {\sum }_{r=1}^i\widetilde{s_{\left[r\right]}}\right)$ are independent of the internal job sequence within each group. According to Hardy et al. [32], the optimal job sequence for $\widetilde{G_i}$ is obtained by matching the smallest and second smallest ${\xi }_{ih}$ to the job with the largest and second largest $g_{ih}{\theta }_{ih}$, respectively, and so on. □

For

$$1\left|p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i),$$

the complexity of finding the optimal group sequence is still an open problem, but for the special case ${\wp }_i=\widehat{N}$, $i=1,\dots ,\aleph$, the optimal ${\varrho }^{*}$ is obtained in $O\left({\wp }^3\right)$ time.

Lemma 8.

For

$$1\left|p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i),$$

if ${\wp }_i=\widehat{N}$ ($i=1,\dots ,\aleph$), the optimal group sequence ${\varrho }^{*}$ can be determined with $\widetilde{AP}$ in $O\left({\wp }^3\right)$ time.

Proof. 

Similar to Lemma 5, from Equation (37), let

$${\chi }_{ir}=\left({\ell }^{\frac{-\ell }{\ell +1}}+{\ell }^{\frac{1}{\ell +1}}\right)\sum _{h=1}^{\widehat{N}}{\left({\xi }_{ih}+\gamma \widehat{N}(\aleph -r)\right)}^{\frac{1}{\ell +1}}{\left(g_{i\left[h\right]}{\theta }_{i\left[h\right]}\right)}^{\frac{\ell }{\ell +1}}+\gamma \widehat{N}(\aleph -r+1)\widetilde{s_i},$$

(40)

The optimal group sequence ${\varrho }^{*}$ can be obtained with $\widetilde{AP}$ (31)–(34), where ${\chi }_{ir}$ is given by Equation (40). □

Similarly, for $n_i=\widehat{N}$ ($i=1,\dots ,\aleph$), the following algorithm (i.e., Algorithm 2) is presented to solve

$$1\left|p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },CON,GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i).$$

Theorem 2.

If ${\wp }_i=\widehat{N}$ ($i=1,\dots ,\aleph$), Algorithm 2 solves

$$1|p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i)$$

in $O\left({\wp }^3\right)$ time.

Algorithm 2: Convex resource function

Step 1. Calculate $k_i$ by Lemma 2.

Step 2. For each group $\widetilde{G_i}$ ($i=1,\dots ,\aleph$), Lemma 7 is used to obtain internal job sequence ${\phi }_i^{*}$, where for the ${\Xi }_{CON}$ assignment, ${\xi }_{ih}$ is given by Equation (38), and for the ${\Xi }_{SLK}$ assignment, ${\xi }_{ih}$ is given by Equation (39), $i=1,\dots ,\aleph ,h=1,\dots ,{\wp }_i$.

Step 3. ${\chi }_{ir}$ is computed with Equation (40) with ${\phi }_i^{*}$ for $i,r=1,\dots ,\aleph$.

Step 4. Solve $\widetilde{AP}$ (31)–(34) to determine the optimal group sequence ${\varrho }^{*}$.

Step 5. Compute optimal resource allocation $u_{ih}^{*}({\varrho }^{*},{\phi }_1^{*},\dots ,{\phi }_{\aleph }^{*})$ with Equation (36).

Step 6. For the ${\Xi }_{CON}$ and ${\Xi }_{SLK}$ assignments, calculate $d_i^{*}=C_{i\left[k_i\right]}$ and $q_i^{*}=C_{i[k_i-1]}$, respectively, using Lemma 2.

5. An Example

We only considered the ${\Xi }_{CON}$ assignment problem where $\wp =15$, $\aleph =3$, ${\wp }_1={\wp }_2={\wp }_3=5,$ $\ell =2,\gamma =4$, $\widetilde{s_1}=2,\widetilde{s_2}=3,\widetilde{s_3}=1$; the parameters of job $J_{ih}$ ($i=1,2,3;h=1,\dots ,5$) are given in

Table 2. Job parameters.

$\widetilde{{\mathit{G}}_{\mathit{i}}}$	$\widetilde{{\mathit{G}}_1}$					$\widetilde{{\mathit{G}}_2}$					$\widetilde{{\mathit{G}}_3}$
$J_{ih}$	$J_{11}$	$J_{12}$	$J_{13}$	$J_{14}$	$J_{15}$	$J_{21}$	$J_{22}$	$J_{23}$	$J_{24}$	$J_{25}$	$J_{31}$	$J_{32}$	$J_{33}$	$J_{34}$	$J_{35}$
$a_{ih}$	14	15	13	16	11	13	16	17	18	17	16	19	23	21	18
$b_{ih}$	2	3	3	1	2	2	3	4	5	3	4	4	5	6	3
${\overline{u}}_{ih}$	4	3	4	10	5	6	5	4	3	5	3	4	4	3	5
${\theta }_{ih}$	15	13	9	10	17	15	11	19	20	9	16	15	21	15	18
$g_{ih}$	4	5	6	2	7	3	6	5	3	4	5	7	8	9	11

, ${\alpha }_{ih}$ and ${\beta }_{ih}$ of $\widetilde{PDW}$ ($i=1,2,3;j=1,\dots ,5$) are presented in

Table 3. Position-dependent weights.

$\widetilde{{\mathit{G}}_{\mathit{i}}}$	$\widetilde{{\mathit{G}}_1}$					$\widetilde{{\mathit{G}}_2}$					$\widetilde{{\mathit{G}}_3}$
${\alpha }_{ih}$	6	4	8	6	10	8	10	9	10	13	9	14	10	16	11
${\beta }_{ih}$	10	11	14	8	12	13	12	15	11	14	16	17	11	18	12

.

For problem

$$1\left|p_{ih}=a_{ih}-b_{ih}{u}_{ih},{\Xi }_{CON},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i),$$

from Algorithm 1 and Lemma 2, $8+12-(6+4+8)=2\le 4\times 5\le 14+8+12-(6+4)=24$; hence $k_1=3$. Similarly, $k_2=3,k_3=2$. Values ${\vartheta }_{jh}^{\left[1\right]}$ are given in

Table 4. Values ${\vartheta }_{jh}^{\left[1\right]}$ for $\widetilde{G_1}$ (bold numbers are the optimal solution).

	$\mathit{h}=1$	$\mathit{h}=2$	$\mathit{h}=3$	$\mathit{h}=4$	$\mathit{h}=5$
$J_{11}$	376	412	436	376	328
$J_{12}$	375	411	435	375	327
$J_{13}$	84	90	94	84	76
$J_{14}$	380	416	440	380	332
$J_{15}$	95	101	105	95	87

when $\widetilde{G_1}$ was scheduled at the rth position. Table 4 shows that the optimal job sequence was ${\phi }_{11}^{*}=\{J_{11}\to J_{13}\to J_{15}\to J_{12}\to J_{14}\}$, similarly, ${\phi }_{12}^{*}=\{J_{11}\to J_{13}\to J_{15}\to J_{12}\to J_{14}\}$, ${\phi }_{13}^{*}=\{J_{11}\to J_{13}\to J_{15}\to J_{12}\to J_{14}\}$; For group $\widetilde{G_2}$, we have ${\phi }_{21}^{*}=\{J_{25}\to J_{21}\to J_{22}\to J_{23}\to J_{24}\}$, ${\phi }_{22}^{*}=\{J_{25}\to J_{21}\to J_{22}\to J_{23}\to J_{24}\}$, ${\phi }_{23}^{*}=\{J_{25}\to J_{21}\to J_{22}\to J_{23}\to J_{24}\}$; For group $\widetilde{G_3}$, we have ${\phi }_{31}^{*}=\{J_{32}\to J_{33}\to J_{34}\to J_{35}\to J_{31}\}$, ${\phi }_{32}^{*}=\{J_{32}\to J_{33}\to J_{34}\to J_{35}\to J_{31}\}$, ${\phi }_{33}^{*}=\{J_{32}\to J_{33}\to J_{34}\to J_{35}\to J_{31}\}$.

According to Step 4 of Algorithm 1, the values of ${\chi }_{ir}$ are given in

Table 5. Values ${\chi }_{ir}$ of the linear problem (bold numbers are the optimal solution).

	$\mathit{r}=1$	$\mathit{r}=2$	$\mathit{r}=3$
$\widetilde{G_1}$	1398	958	518
$\widetilde{G_2}$	758	538	318
$\widetilde{G_3}$	1265	925	585

. From Table 5, we have ${\varrho }^{*}=\{\widetilde{G_2}\to \widetilde{G_3}\to \widetilde{G_1}\}$. The optimal jobs sequences are ${\phi }_{21}^{*}=\{J_{25}\to J_{21}\to J_{22}\to J_{23}\to J_{24}\}$, ${\phi }_{32}^{*}=\{J_{32}\to J_{33}\to J_{34}\to J_{35}\to J_{31}\}$, and ${\phi }_{13}^{*}=\{J_{11}\to J_{13}\to J_{15}\to J_{12}\to J_{14}\}$. The optimal resource allocations corresponding to the sequence are $u_{25}^{*}={\overline{u}}_{25}=5,u_{21}^{*}={\overline{u}}_{21}=6,u_{22}^{*}={\overline{u}}_{22}=5,u_{23}^{*}={\overline{u}}_{23}=4,u_{24}^{*}={\overline{u}}_{24}=3,u_{32}^{*}={\overline{u}}_{32}=4,u_{33}^{*}={\overline{u}}_{33}=4,u_{34}^{*}={\overline{u}}_{34}=3,u_{35}^{*}={\overline{u}}_{35}=5,u_{31}^{*}={\overline{u}}_{31}=3,u_{11}^{*}={\overline{u}}_{11}=4,u_{13}^{*}={\overline{u}}_{13}=4,u_{15}^{*}={\overline{u}}_{15}=5,u_{12}^{*}={\overline{u}}_{12}=3,u_{14}^{*}={\overline{u}}_{14}=10$. The optimal due-dates are $d_1^{*}=C_{22}=7,d_2^{*}=C_{34}=18$, and $d_3^{*}=C_{13}=38$.

Similarly, for problem

$$1\left|p_{ih}={\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell },{\Xi }_{CON},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i),$$

$k_1=3,k_2=3,k_3=2$. According to Lemma 7, for $i=1$, the optimal job sequence is ${\phi }_1^{*}=\{J_{11}\to J_{13}\to J_{14}\to J_{12}\to J_{15}\}$, for $i=2$, the optimal sequence is ${\phi }_2^{*}=\{J_{22}\to J_{21}\to J_{25}\to J_{24}\to J_{23}\}$, for $i=3$, the optimal sequence is ${\phi }_3^{*}=\{J_{33}\to J_{34}\to J_{31}\to J_{32}\to J_{35}\}$. According to Equation (40), the values of ${\chi }_{ir}$ are shown in

Table 6. Values ${\chi }_{ir}$ of the convex problem (bold numbers are the optimal solution).

	$\mathit{r}=1$	$\mathit{r}=2$	$\mathit{r}=3$
$\widetilde{G_1}$	690.1632	576.7474	492.4878
$\widetilde{G_2}$	751.6441	622.7040	465.1836
$\widetilde{G_3}$	1043.3726	910.8574	724.1781

, where we have ${\varrho }^{*}=\{\widetilde{G_1},\widetilde{G_2},\widetilde{G_3}\}$. The optimal values of resource allocation corresponding to the sequence are $u_{11}^{*}=18.8988,u_{13}^{*}=12.1237,u_{14}^{*}=19.1293,u_{12}^{*}=15.9477,u_{15}^{*}=16.2534,u_{22}^{*}=11.7285,u_{21}^{*}=19.3098,u_{25}^{*}=13.2931,u_{24}^{*}=22.8943,u_{23}^{*}=16.9961,u_{33}^{*}=13.0158,u_{34}^{*}=11.3185,u_{31}^{*}=16.1322,u_{32}^{*}=12.4474,u_{35}^{*}=26.3904$. The optimal due dates are $d_1^{*}=C_{14}=3.4544,d_2^{*}=C_{25}=10.0560$, and $d_3^{*}=C_{34}=17.4282$.

6. Conclusions

In this article, we investigated single-machine group technology scheduling with $\widetilde{CPT}$. Under ${\Xi }_{CON}/{\Xi }_{SLK}$ assignments, the goal is to find the job and group sequences, resource allocation, and due-date assignment, such that the sum of scheduling and resource-allocation costs is minimized. For ${\wp }_i=\widehat{N}$ ($i=1,\dots ,\aleph$), we demonstrated that this problem is polynomially solvable. Future work could explore job (or flow) shop problems (see Guo et al. [33], and Karacan et al. [34]) with group technology and controllable processing times to study the general version of

$$1\left|p_{ih},{\Xi }_{CON}/{\Xi }_{SLK},GT,\widetilde{PDW}\right|\sum _{i=1}^{\aleph }\sum _{h=1}^{{\wp }_i}({\alpha }_{ih}{E}_{i\left[h\right]}+{\beta }_{ih}{T}_{i\left[h\right]}+g_{ih}{u}_{ih}+\gamma d_i/q_i),$$

where $p_{ih}\in \left\{a_{ih}-b_{ih}{u}_{ih},{\left(\frac{{\theta }_{ih}}{u_{ih}}\right)}^{\ell }\right\}$ (e.g., the proposed cuckoo search algorithm of Xie et al. [35]). Future work could also consider problems regarding maintenance activity (see Wu et al. [36]).