Scheduling with Resource Allocation, Deteriorating Effect and Group Technology to Minimize Total Completion Time

Abstract

This paper studies a single-machine problem with resource allocation ($RA$) and deteriorating effect ($DE$). Under group technology ($GT$) and limited resource availability, our goal is to determine the schedules of groups and jobs within each group such that the total completion time is minimized. For three special cases, polynomial time algorithms are given. For a general case, a heuristic, a tabu search algorithm, and an exact (i.e., branch-and-bound) algorithm are proposed to solve this problem.

1. Introduction

With the development of economy, the research on the group technology (denoted by $GT$) problem involves a variety of fields, especially in the supply chain management, information processing, computer systems, and other industries (see Ham et al. [1], Wang et al. [2]). Yang [3] and Bai et al. [4] investigated single-machine $GT$ scheduling with learning and deterioration effects. Lu et al. [5] studied the single-machine problem with $GT$ and time-dependent processing times (i.e., time-dependent scheduling), i.e., the processing time of jobs and setup time of groups are time-dependent. For the makespan minimization subject to release dates, they presented a polynomial time algorithm. Wang et al. [6] examined the single-machine problem with $GT$ and shortening job processing times. For the makespan minimization with ready times, they demonstrated that some special cases were optimally solved in polynomial time. Liu et al. [7] studied the single-machine problem with $GT$ and deterioration effects (denoted by $DE$), i.e., the processing time of jobs are time-dependent and setup time of groups are constants. For the makespan minimization with ready times, they proposed a branch-and-bound algorithm. Zhu et al. [8] discussed the single-machine problem with $GT$, resource allocation (denoted by $RA$), and learning effects. For the weighted sum minimization of makespan and total resource consumption, Zhu et al. [8] proved that the problem remains polynomially solvable. In 2018, Zhang et al. [9] discussed the single-machine problem with $GT$ and position-dependent processing times. In 2020, Liao et al. [10] considered the two-competing scheduling problem with $GT$ and learning effects. In 2021, Lv et al. [11] addressed single-machine slack due date assignment problems with $GT$, $RA$, and learning effects. In 2021, Xu et al. [12] investigated the single-machine problem with $GT$, nonperiodical maintenance, and $DE$. For the makespan minimization, they proposed some heuristic algorithms.

Recently, Oron [13] and Li and Wang [14] considered a single-machine scheduling model combining $RA$ and $DE$. Later, Wang et al. [15] discussed a scheduling model combining $GT$, $RA$, and $DE$. Under the single-machine setting, the objective is to minimize the weighted sum of makespan and total resource consumption. Wang et al. [15] showed that some special cases remain polynomially solvable. In 2020, Liang et al. [16] considered the same model as Wang et al. [15] for the general case; they provided heuristic and branch-and-bound algorithms. In 2019, Wang and Liang [17] studied the single-machine problem with $GT$, $RA$, and $DE$ concurrently. For the makespan minimization under the constraint that total resource consumption cannot exceed an upper bound, they proved that some special cases remain polynomially solvable. For the general case, they provided heuristic and branch-and-bound algorithms.

This paper conducts a further study on the problem with $GT$, $RA$, and $DE$, but the objective cost is to minimize the total completion time under the constraint that total resource consumption cannot exceed an upper bound. For three special cases, polynomial algorithms are given. For the general case, upper and lower bounds of the problem are given, then the branch-and-bound algorithm is proposed. In addition, a tabu search algorithm and numerical simulation analysis are given.

The rest of this paper is organized as follows: Section 2 presents a formulation of the problem. Section 3 gives some basic properties. Section 4 studies some special cases. Section 5 considers the general case, and we propose some algorithms to solve this problem. Section 6 presents the numerical simulations. The conclusions are given in Section 7.

2. Problem Statement

The following notation (see

Table 1. Symbols.

Notation	Meaning
$\tilde{n}$ (resp. $\tilde{m}$)	number of jobs (respective groups)
${\mathsf{\Omega }}_h$	group h
${\breve{J}}_{hj}$	job j at group ${\mathsf{\Omega }}_h$
${\tilde{n}}_h$	number of jobs belonging to ${\mathsf{\Omega }}_h$, i.e., ${\sum }_{h=1}^{\tilde{m}}{\tilde{n}}_h=\overline{n}$
${\varsigma }_{hj}$	workload of ${\breve{J}}_{hj}$ (a positive value which represents job parameter)
${\tilde{r}}_{hj}$	amount of resource assigned to ${\breve{J}}_{hj}$
$p_{hj}^{Apt}$	actual processing time of ${\breve{J}}_{hj}$
$o_h$	workload of ${\mathsf{\Omega }}_h$ (a positive value which represents group parameter),
	$h=1,2,\cdots ,\tilde{m}$,
${\tilde{r}}_h$	amount of resource allocated to ${\mathsf{\Omega }}_h$
$s_h^{Apt}$	actual setup time of ${\mathsf{\Omega }}_h$
${\overline{C}}_{hj}$	completion time of ${\breve{J}}_{hj}$
$\left[j\right]$	jth position in a schedule
$\widehat{tct}={\sum }_{i=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\overline{C}}_{ij}$	total completion time
${\overline{\pi }}_{\mathsf{\Omega }}$	group schedule
${\overline{\pi }}_h$	job schedule in ${\mathsf{\Omega }}_h$
$\Pi$	schedule of jobs and groups, i.e., $\Pi =\left({\overline{\pi }}_{\mathsf{\Omega }},{\overline{\pi }}_h|h=1,\cdots ,\tilde{m}\right)$

) will be used throughout this paper. There are $\tilde{n}$ independent jobs. In order to exploit $GT$ in production (see Ji et al. [18]), all the jobs are classified into $\tilde{m}$$\left(\tilde{m}\ge 2\right)$ groups (i.e., ${\mathsf{\Omega }}_1,{\mathsf{\Omega }}_2,\dots ,{\mathsf{\Omega }}_{\tilde{m}}$) in advance according to their processing similarities. All the jobs in the same group must be processed in succession on a single machine. Assume that the single machine and all jobs are available at time zero. Let ${\breve{J}}_{hj}$ be the job j in group ${\mathsf{\Omega }}_h$, and the number of jobs in group ${\mathsf{\Omega }}_h$ is ${\tilde{n}}_h$, i.e., ${\sum }_{h=1}^{\tilde{m}}{\tilde{n}}_h=\tilde{n}$. The actual processing time of ${\breve{J}}_{hj}$ is:

$$p_{hj}^{Apt}={\left(\frac{{\varsigma }_{hj}}{{\tilde{r}}_{hj}}\right)}^{\eta }+\theta t,$$

(1)

where ${\varsigma }_{hj}$ (resp. ${\tilde{r}}_{hj}\ge 0$) is a workload (respective amount of resource) of ${\breve{J}}_{hj}$, $\eta >0$ is a constant, $\theta \ge 0$ is a common deterioration rate, and $t\ge 0$ is its starting time. The actual setup time of ${\mathsf{\Omega }}_h$ is:

$$s_h^{Apt}={\left(\frac{o_h}{{\tilde{r}}_h}\right)}^{\eta }+\mu t,$$

(2)

where $o_h$ (respectively, ${\tilde{r}}_h$) is a workload (amount of resource) of ${\mathsf{\Omega }}_h$, and $\mu \ge 0$ is a common deterioration rate. Obviously, the parameters $\tilde{n},\tilde{m}$, ${\varsigma }_{hj}$, ${\tilde{n}}_h$, $o_h$, $\eta$, $\theta$, and $\mu$ are given in advance, and the resource allocation ${\tilde{r}}_{hj}$ and ${\tilde{r}}_h$ are decision variables. Our goal is to find the optimal group schedule ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$, job schedule ${\overline{\pi }}_h^{*}$$\left(h=1,\cdots ,\tilde{m}\right)$ within ${\mathsf{\Omega }}_h$, and resource allocation $R^{*}$ (i.e., ${\tilde{r}}_{hj}$ and ${\tilde{r}}_h$) such that a total completion time,

$$\widehat{tct}({\overline{\pi }}_{\mathsf{\Omega }},{\overline{\pi }}_h|h=1,\cdots ,\tilde{m},R)={\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\overline{C}}_{hj}$$

(3)

is minimized subject to ${\sum }_{h=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\tilde{r}}_{hj}\le \tilde{V},{\sum }_{h=1}^{\tilde{m}}{\tilde{r}}_h\le \tilde{U}$, where $\tilde{V}$ and $\tilde{U}$ are given constants (there is not any constraint between the ${\tilde{r}}_{hj}$ variables and the ${\tilde{r}}_h$ variables, and ${\sum }_{h=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\tilde{r}}_{hj}$ and ${\sum }_{h=1}^{\tilde{m}}{\tilde{r}}_h$ are independent from each other). By using the three-field notation (see Gawiejnowicz [19]), the problem can be denoted by

$$1\left|p_{hj}^{Apt}={\left(\frac{{\varsigma }_{hj}}{{\tilde{r}}_{hj}}\right)}^{\eta }+\theta t,s_h^{Apt}={\left(\frac{o_h}{{\tilde{r}}_h}\right)}^{\eta }+\mu t,{\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\tilde{r}}_{hj}\le \tilde{V},{\displaystyle \sum _{h=1}^{\tilde{m}}}{\tilde{r}}_h\le \tilde{U},GT\right|\widehat{tct},$$

where 1 denotes the single machine, the middle field is the job and group characteristics, and $\widehat{tct}$ is the objective function (this problem is abbreviated as $P_{\widehat{tct}}$). Wang et al. [15] and Liang et al. [16] considered the problem

$$1\left|p_{hj}^{Apt}={\left(\frac{{\varsigma }_{hj}}{{\tilde{r}}_{hj}}\right)}^{\eta }+\theta t,s_h^{Apt}={\left(\frac{o_h}{{\tilde{r}}_h}\right)}^{\eta }+\mu t,GT\right|{\alpha }_1\times C_{max}+{\alpha }_2{\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\tilde{r}}_{hj}+{\alpha }_3{\displaystyle \sum _{h=1}^{\tilde{m}}}{\tilde{r}}_h,$$

where ${\alpha }_l\ge 0$ ($l=1,2,3$) is a given constant and $C_{max}=max\left\{{\overline{C}}_{hj}\right|h=1,\dots ,\tilde{m};j=1,\dots ,{\tilde{n}}_h\}$. Wang and Liang [17] studied the problem

$$1\left|p_{hj}^{Apt}={\left(\frac{{\varsigma }_{hj}}{{\tilde{r}}_{hj}}\right)}^{\eta }+\theta t,s_h^{Apt}={\left(\frac{o_h}{{\tilde{r}}_h}\right)}^{\eta }+\mu t,{\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\tilde{r}}_{hj}\le \tilde{V},{\displaystyle \sum _{h=1}^{\tilde{m}}}{\tilde{r}}_h\le \tilde{U},GT\right|C_{max}.$$

3. Basic Results

For a given schedule $\Pi$, stemming from Wang et al. [15] and Liang et al. [16], by a mathematical induction, we have

$$\begin{array}{ccc}\hfill {\overline{C}}_{\left[1\right]\left[1\right]}& =& {\left(\frac{o_{\left[1\right]}}{{\tilde{r}}_{\left[1\right]}}\right)}^{\eta }+{\left(\frac{{\varsigma }_{\left[1\right]\left[1\right]}}{{\tilde{r}}_{\left[1\right]\left[1\right]}}\right)}^{\eta }+\theta {\left(\frac{o_{\left[1\right]}}{{\tilde{r}}_{\left[1\right]}}\right)}^{\eta }={\left(\frac{{\varsigma }_{\left[1\right]\left[1\right]}}{{\tilde{r}}_{\left[1\right]\left[1\right]}}\right)}^{\eta }+\left(1+\theta \right){\left(\frac{o_{\left[1\right]}}{{\tilde{r}}_{\left[1\right]}}\right)}^{\eta },\hfill \\ \hfill {\overline{C}}_{\left[1\right]\left[2\right]}& =& {\overline{C}}_{\left[1\right]\left[1\right]}+{\left(\frac{{\varsigma }_{\left[1\right]\left[2\right]}}{{\tilde{r}}_{\left[1\right]\left[2\right]}}\right)}^{\eta }+\theta {\overline{C}}_{\left[1\right]\left[1\right]}\hfill \\ & =& {\left(\frac{{\varsigma }_{\left[1\right]\left[2\right]}}{{\tilde{r}}_{\left[1\right]\left[2\right]}}\right)}^{\eta }+\left(1+\theta \right){\left(\frac{{\varsigma }_{\left[1\right]\left[1\right]}}{{\tilde{r}}_{\left[1\right]\left[1\right]}}\right)}^{\eta }+{\left(1+\theta \right)}^2{\left(\frac{o_{\left[1\right]}}{{\tilde{r}}_{\left[1\right]}}\right)}^{\eta },\hfill \\ & ⋮& \\ \hfill {\overline{C}}_{\left[1\right]\left[{\tilde{n}}_1\right]}& =& {\displaystyle \sum _{j=1}^{{\tilde{n}}_{\left[1\right]}}}{\left(1+\theta \right)}^{{}^{{\tilde{n}}_{\left[1\right]}-j}}{\left(\frac{{\varsigma }_{\left[1\right]\left[j\right]}}{{\tilde{r}}_{\left[1\right]\left[j\right]}}\right)}^{\eta }+{\left(1+\theta \right)}^{{\tilde{n}}_{\left[1\right]}}{\left(\frac{o_{\left[1\right]}}{{\tilde{r}}_{\left[1\right]}}\right)}^{\eta },\hfill \\ \hfill {\overline{C}}_{\left[2\right]\left[1\right]}& =& {\overline{C}}_{\left[1\right]\left[{\tilde{n}}_1\right]}+{\left(\frac{o_{\left[2\right]}}{{\tilde{r}}_{\left[2\right]}}\right)}^{\eta }+\mu {\overline{C}}_{\left[1\right]\left[{\tilde{n}}_1\right]}+{\left(\frac{{\varsigma }_{\left[2\right]\left[1\right]}}{{\tilde{r}}_{\left[2\right]\left[1\right]}}\right)}^{\eta }+\theta \left({\overline{C}}_{\left[1\right]\left[{\tilde{n}}_1\right]}+{\left(\frac{o_{\left[2\right]}}{{\tilde{r}}_{\left[2\right]}}\right)}^{\eta }+\mu {\overline{C}}_{\left[1\right]\left[{\tilde{n}}_1\right]}\right)\hfill \\ & =& {\displaystyle \sum _{j=1}^{{\tilde{n}}_{\left[1\right]}}}\left(1+\mu \right){\left(1+\theta \right)}^{{}^{{}^{{}^{{\tilde{n}}_{\left[1\right]}-j+1}}}}{\left(\frac{{\varsigma }_{\left[1\right]\left[j\right]}}{{\tilde{r}}_{\left[1\right]\left[j\right]}}\right)}^{\eta }+\left(1+\mu \right){\left(1+\theta \right)}^{{\tilde{n}}_{\left[1\right]}+1}{\left(\frac{o_{\left[1\right]}}{{\tilde{r}}_{\left[1\right]}}\right)}^{\eta }\hfill \\ & & +\left(1+\theta \right){\left(\frac{o_{\left[2\right]}}{{\tilde{r}}_{\left[2\right]}}\right)}^{\eta }+{\left(\frac{{\varsigma }_{\left[2\right]\left[1\right]}}{{\tilde{r}}_{\left[2\right]\left[1\right]}}\right)}^{\eta },\hfill \\ \hfill {\overline{C}}_{\left[2\right]\left[2\right]}& =& {\overline{C}}_{\left[2\right]\left[1\right]}+{\left(\frac{{\varsigma }_{\left[2\right]\left[2\right]}}{{\tilde{r}}_{\left[2\right]\left[2\right]}}\right)}^{\eta }+\theta {\overline{C}}_{\left[2\right]\left[1\right]}\hfill \\ & =& {\displaystyle \sum _{j=1}^{{\tilde{n}}_{\left[1\right]}}}\left(1+\mu \right){\left(1+\theta \right)}^{{}^{{\tilde{n}}_{\left[1\right]}-j+2}}{\left(\frac{{\varsigma }_{\left[1\right]\left[j\right]}}{{\tilde{r}}_{\left[1\right]\left[j\right]}}\right)}^{\eta }+\left(1+\mu \right){\left(1+\theta \right)}^{{\tilde{n}}_{\left[1\right]}+2}{\left(\frac{o_{\left[1\right]}}{{\tilde{r}}_{\left[1\right]}}\right)}^{\eta }\hfill \\ & & +{\left(1+\theta \right)}^2{\left(\frac{o_{\left[2\right]}}{{\tilde{r}}_{\left[2\right]}}\right)}^{\eta }+\left(1+\theta \right){\left(\frac{{\varsigma }_{\left[2\right]\left[1\right]}}{{\tilde{r}}_{\left[2\right]\left[1\right]}}\right)}^{\eta }+{\left(\frac{{\varsigma }_{\left[2\right]\left[2\right]}}{{\tilde{r}}_{\left[2\right]\left[2\right]}}\right)}^{\eta },\hfill \\ & ⋮& \\ \hfill {\overline{C}}_{\left[2\right]\left[{\tilde{n}}_2\right]}& =& {\displaystyle \sum _{j=1}^{{\tilde{n}}_{\left[1\right]}}}\left(1+\mu \right){\left(1+\theta \right)}^{{\tilde{n}}_{\left[1\right]}+{\tilde{n}}_{\left[2\right]}-j}{\left(\frac{{\varsigma }_{\left[1\right]\left[j\right]}}{{\tilde{r}}_{\left[1\right]\left[j\right]}}\right)}^{\eta }+\left(1+\mu \right){\left(1+\theta \right)}^{{\tilde{n}}_{\left[1\right]}+{\tilde{n}}_{\left[2\right]}}{\left(\frac{o_{\left[1\right]}}{{\tilde{r}}_{\left[1\right]}}\right)}^{\eta }\hfill \\ & & +{\displaystyle \sum _{j=1}^{{\tilde{n}}_{\left[2\right]}}}{\left(1+\theta \right)}^{{\tilde{n}}_{\left[2\right]}-j}{\left(\frac{{\varsigma }_{\left[2\right]\left[j\right]}}{{\tilde{r}}_{\left[2\right]\left[j\right]}}\right)}^{\eta }+{\left(1+\theta \right)}^{{\tilde{n}}_{\left[2\right]}}{\left(\frac{o_{\left[2\right]}}{{\tilde{r}}_{\left[2\right]}}\right)}^{\eta },\hfill \\ & ⋮& \\ \hfill {\overline{C}}_{\left[\tilde{m}\right]\left[{\tilde{n}}_m\right]}& =& {\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_{\left[h\right]}}}{(1+\mu )}^{\tilde{m}-h}{(1+\theta )}^{{\sum }_{l=h}^{\tilde{m}}{\tilde{n}}_{\left[l\right]}-j}{\left(\frac{{\varsigma }_{\left[h\right]\left[j\right]}}{{\tilde{r}}_{\left[h\right]\left[j\right]}}\right)}^{\eta }\hfill \\ & & +{\displaystyle \sum _{h=1}^{\tilde{m}}}{(1+\mu )}^{\tilde{m}-h}{(1+\theta )}^{{\sum }_{l=h}^{\tilde{m}}{\tilde{n}}_{\left[l\right]}}{\left(\frac{o_{\left[h\right]}}{{\tilde{r}}_{\left[h\right]}}\right)}^{\eta }.\hfill \end{array}$$

According to the above equations, we have

$$\begin{array}{ccc}\widehat{tct}\hfill & =\hfill & {\displaystyle {\sum }_{i=1}^{\tilde{m}}}{\displaystyle {\sum }_{j=1}^{{\tilde{n}}_h}}{\overline{C}}_{\left[i\right]\left[j\right]}\hfill \\ & =\hfill & {\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}\left[{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right]{\left(\frac{{\varsigma }_{\left[i\right]\left[j\right]}}{{\tilde{r}}_{\left[i\right]\left[j\right]}}\right)}^{\eta }\hfill \\ \hfill & \hfill & +{\displaystyle \sum _{h=1}^{\tilde{m}}}\left[{\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right]{\left(\frac{o_{\left[h\right]}}{{\tilde{r}}_{\left[h\right]}}\right)}^{\eta }.\hfill \end{array}$$

(4)

Lemma 1.

For a given schedule Π of $P_{\widehat{tct}}$, the optimal resource allocation $R^{*}\left({\overline{\pi }}_{\mathsf{\Omega }},{\overline{\pi }}_h|h=1,\cdots ,\tilde{m}\right)$ is

$${{\tilde{r}}^{*}}_{\left[h\right]\left[j\right]}=\frac{{\left[{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle {\displaystyle \sum _{k=h+1}^{\tilde{m}}}}{(1+\mu )}^{k-h}{\displaystyle {\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}{\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\eta }\right]}^{\frac{1}{\eta +1}}}{{{\displaystyle {\displaystyle \sum _{h=1}^{\tilde{m}}}}{\displaystyle {\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}}\left[{\displaystyle {\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}}{(1+\theta )}^{l-j}+{\displaystyle {\displaystyle \sum _{k=h+1}^{\tilde{m}}}}{(1+\mu )}^{k-h}{\displaystyle {\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle {\displaystyle \sum _{\xi =h}^k}}{\tilde{n}}_{\left[\xi \right]}}{\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\eta }\right]}^{\frac{1}{\eta +1}}}\times \tilde{V}$$

(5)

for $h=1,\cdots ,\tilde{m};j=1,\cdots ,{\tilde{n}}_i$, and

$${{\tilde{r}}^{*}}_{\left[h\right]}=\frac{{\left[{\displaystyle {\displaystyle \sum _{k=h}^{\tilde{m}}}}{(1+\mu )}^{k-h}{\displaystyle {\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}{\left(o_{\left[h\right]}\right)}^{\eta }\right]}^{\frac{1}{\eta +1}}}{{{\displaystyle \sum _{h=1}^{\tilde{m}}}\left[{\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}{\left(o_{\left[h\right]}\right)}^{\eta }\right]}^{\frac{1}{\eta +1}}}\times \tilde{U}$$

(6)

for $h=1,\cdots ,\tilde{m}$.

Proof. 

Obviously, Equation (4) is a convex function with respect to ${\tilde{r}}_{\left[h\right]\left[j\right]}$ and ${\tilde{r}}_{\left[h\right]}$. It is obvious that in the optimal solution all resources should be consumed, i.e., ${\sum }_{h=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\tilde{r}}_{\left[h\right]\left[j\right]}-\tilde{V}=0$ and ${\sum }_{h=1}^{\tilde{m}}{\tilde{r}}_{\left[h\right]}-\tilde{U}=0$. As in Wang and Liang [17], Shabtay and Kaspi [20], and Wang and Wang [21], for a given schedule, the optimal resource allocation of the problem $P_{\widehat{tct}}$ can be solved by the Lagrange multiplier method. The Lagrangian function is

$$\begin{array}{lll}Q\left(\kappa ,\upsilon ,R\right)& =& {\sum }_{h=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\overline{C}}_{\left[h\right]\left[j\right]}+\kappa \left({\sum }_{h=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\tilde{r}}_{\left[h\right]\left[j\right]}-\tilde{V}\right)+\upsilon \left({\sum }_{h=1}^{\tilde{m}}{\tilde{r}}_{\left[h\right]}-\tilde{U}\right)\\ & =& {\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}\left[{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right]{\left(\frac{{\varsigma }_{\left[h\right]\left[j\right]}}{{\tilde{r}}_{\left[h\right]\left[j\right]}}\right)}^{\eta }\\ & & +{\displaystyle \sum _{h=1}^{\tilde{m}}}\left[{\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right]{\left(\frac{o_{\left[h\right]}}{{\tilde{r}}_{\left[h\right]}}\right)}^{\eta }\\ & +& \kappa \left({\displaystyle {\sum }_{h=1}^{\tilde{m}}}{\displaystyle {\sum }_{j=1}^{\tilde{n}}}{\tilde{r}}_{\left[h\right]\left[j\right]}-\tilde{V}\right)+\upsilon \left({\displaystyle {\sum }_{h=1}^{\tilde{m}}}{\tilde{r}}_{\left[h\right]}-\tilde{U}\right),\end{array}$$

(7)

where $\kappa \ge 0$ and $\upsilon \ge 0$ are the Lagrangian multipliers. Differentiating Equation (7) with respect to ${\tilde{r}}_{\left[h\right]\left[j\right]}$ and $\kappa$, then

$$\begin{array}{ccc}\frac{\partial Q\left(\kappa ,\upsilon ,R\right)}{\partial {\tilde{r}}_{\left[i\right]\left[j\right]}}\hfill & =\hfill & \delta -\eta \left[{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[i\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right]\hfill \\ \hfill & \hfill & \times \frac{{\left({\zeta }_{\left[h\right]\left[j\right]}\right)}^{\eta }}{{\left({\tilde{r}}_{\left[h\right]\left[j\right]}\right)}^{\eta +1}}\hfill \\ \hfill & =\hfill & 0\hfill \end{array}$$

(8)

and

$$\frac{\partial Q\left(\kappa ,\upsilon ,R\right)}{\partial \kappa }={\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\tilde{r}}_{\left[h\right]\left[j\right]}-\tilde{V}=0.$$

(9)

By using Equations (8) and (9), it follows that

$${\tilde{r}}_{\left[h\right]\left[j\right]}={\left[\frac{\eta \left({\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}{\kappa }\right]}^{\frac{1}{(\eta +1)}}\times {\left({\zeta }_{\left[h\right]\left[j\right]}\right)}^{\frac{\eta }{\eta +1}}$$

(10)

and

$${\kappa }^{\frac{1}{\eta +1}}=\frac{{\sum }_{h=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\left[\eta \left({\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-i}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right){\left({\zeta }_{\left[h\right]\left[j\right]}\right)}^{\eta }\right]}^{\frac{1}{\eta +1}}}{\tilde{V}}.$$

(11)

From Equations (10) and (11), then

$$\begin{array}{ccc}\hfill {\tilde{r}}_{\left[h\right]\left[j\right]}^{*}& =& \frac{{\left[{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}{\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\eta }\right]}^{\frac{1}{\eta +1}}}{{{\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}\left[{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}{\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\eta }\right]}^{\frac{1}{\eta +1}}}\times \tilde{V}.\hfill \end{array}$$

Similarly, Equation (6) can be obtained.    □

By Lemma 1, substituting Equations (5) and (6) into $\widehat{tct}={\sum }_{h=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\overline{C}}_{hj}$, we have

$$\begin{array}{lll}\widehat{tct}& =& {\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}\left[{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right]{\left(\frac{{\varsigma }_{\left[h\right]\left[j\right]}}{{\tilde{r}}_{\left[h\right]\left[j\right]}}\right)}^{\eta }\\ & & +{\displaystyle \sum _{h=1}^{\tilde{m}}}\left[{\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right]{\left(\frac{o_{\left[h\right]}}{{\tilde{r}}_{\left[h\right]}}\right)}^{\eta }\\ & =& {\tilde{V}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\left({\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}{\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}\\ & & +{\tilde{U}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}{\left(o_{\left[h\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}.\end{array}$$

(12)

Lemma 2.

For $P_{\widehat{tct}}$, the optimal job schedule ${\overline{\pi }}_h^{*}$ within group ${\mathsf{\Omega }}_h\left(h=1,\cdots ,\tilde{m}\right)$ is the non-decreasing order of ${\zeta }_{h〈j〉}$, i.e., ${\zeta }_{h〈1〉}\le {\zeta }_{h〈2〉}\le \cdots {\zeta }_{h〈{\tilde{n}}_h〉}$.

Proof. 

From Equation (12), for group ${\mathsf{\Omega }}_{\left[h\right]}$, the objective cost is:

$${\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\left({\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}{\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\frac{\eta }{\eta +1}}={\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{x}_{\left[h\right]\left[j\right]}{y}_{\left[h\right]\left[j\right]},$$

where $x_{\left[h\right]\left[j\right]}={\left({\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}$ and $y_{\left[h\right]\left[j\right]}={\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\frac{\eta }{\eta +1}}$. The term $x_{\left[h\right]\left[j\right]}$ is a monotonically decreasing function of j, by the HLP rule (Hardy et al. [22], i.e., the term ${\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{x}_{\left[h\right]\left[j\right]}{y}_{\left[h\right]\left[j\right]}$ is minimized if sequence $x_{\left[h\right]\left[1\right]},x_{\left[h\right]\left[2\right]},\dots ,$$x_{\left[h\right]\left[{\tilde{n}}_h\right]}$ is ordered non-decreasingly and sequence $y_{\left[h\right]\left[1\right]},y_{\left[h\right]\left[2\right]},\dots ,y_{\left[h\right]\left[{\tilde{n}}_h\right]}$ is ordered non-increasingly or vice versa), for the group ${\mathsf{\Omega }}_{\left[h\right]}\left(h=1,\cdots ,\tilde{m}\right)$, if ${\zeta }_{hj}$ is a non-decreasing order, i.e., ${\zeta }_{h〈1〉}\le {\zeta }_{h〈2〉}\le \cdots {\zeta }_{h〈{\tilde{n}}_h〉}$, the result can be obtained.    □

4. Special Cases

By Lemma 2, for group ${\mathsf{\Omega }}_h$, the optimal schedule ${\overline{\pi }}_h^{*}$ is the non-decreasing order of ${\zeta }_{h〈j〉}$, i.e., ${\zeta }_{h〈1〉}\le {\zeta }_{h〈2〉}\le \cdots {\zeta }_{h〈{\tilde{n}}_h〉}$. From Equation (12), let

$$X={\tilde{U}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}{\left(o_{\left[h\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}$$

and

$$Y={\tilde{V}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\left({\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}{\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}.$$

In this section, we study some special cases (i.e., the cases of parameters ${\varsigma }_{hj}$, $o_h$, and ${\tilde{n}}_h$ have some relationship, then X (Y) is minimized or a constant) which can be solved in polynomial time. The special cases stemmingfrom the parameters ${\varsigma }_{hj}$, $o_h$, and ${\tilde{n}}_h$ have some relationship.

4.1. Case 1

If $o_h=o$ and ${\tilde{n}}_h=\frac{\tilde{n}}{\tilde{m}}=\ddot{n}$$(h=1,\cdots ,\tilde{m})$, from Equation (12), it follows that

$$\begin{array}{ccc}& & {\tilde{U}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}{\left(o_{\left[h\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}\hfill \\ & =& {\tilde{U}}^{-\eta }{o}^{\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{\ddot{n}}}{(1+\theta )}^{l+(k-h)\ddot{n}}\right)}^{\frac{1}{\eta +1}}\right)}^{\eta +1}\hfill \end{array}$$

is a constant (i.e., $\tilde{U},o,\eta ,\mu ,\theta ,\ddot{n}$, and $\tilde{m}$ are given constants, and this term is independent of these parameters). Let

$$Y_{h\rho }=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}{\mathsf{\Omega }}_h\mathrm{is}\mathrm{assigned}\mathrm{to}\rho \mathrm{th}\mathrm{position}\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

(13)

and

$${\Theta }_{h\rho }={\displaystyle \sum _{j=1}^{\ddot{n}}}{\left({\displaystyle \sum _{l=j}^{\ddot{n}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=\rho +1}^{\tilde{m}}}{(1+\mu )}^{k-\rho }{\displaystyle \sum _{l=1}^{\ddot{n}}}{(1+\theta )}^{l-j+(k-\rho )\ddot{n}}\right)}^{\frac{1}{\eta +1}}{\left({\varsigma }_{h〈j〉}\right)}^{\frac{\eta }{\eta +1}}.$$

(14)

The optimal group schedule can be translated into the following assignment problem:

$$\begin{array}{ccc}\hfill \mathrm{Min}& & {\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{\rho =1}^{\tilde{m}}}{\mathsf{\Theta }}_{h\rho }{Y}_{h\rho }\hfill \end{array}$$

(15)

$$\begin{array}{ccc}\hfill s.t.& & {\displaystyle \sum _{\rho =1}^{\tilde{m}}}{Y}_{h\rho }=1,h=1,\dots ,\tilde{m},\hfill \end{array}$$

(16)

$$\begin{array}{ccc}& & {\displaystyle \sum _{h=1}^{\tilde{m}}}{Y}_{h\rho }=1,\rho =1,\dots ,\tilde{m},\hfill \end{array}$$

(17)

$$\begin{array}{ccc}& & Y_{h\rho }=0\mathrm{or}1,h,\rho =1,\dots ,\tilde{m}.\hfill \end{array}$$

(18)

Thus, for the special case $o_h=o$ and ${\tilde{n}}_h=\frac{\tilde{n}}{\tilde{m}}=\ddot{n}$$(h=1,\cdots ,\tilde{m})$, the problem $P_{\widehat{tct}}$ can be solved by:

Theorem 1.

If $o_h=o$ and ${\tilde{n}}_h=\frac{\tilde{n}}{\tilde{m}}=\ddot{n}$$\left(h=1,\cdots ,\tilde{m}\right)$, $P_{\widehat{tct}}$ is solvable by Algorithm 1 in $O\left({\tilde{n}}^3\right)$ time.

Algorithm 1: Case 1

Step 1. For group ${\mathsf{\Omega }}_h$$\left(h=1,\dots ,\tilde{m}\right)$, optimal job schedule ${\overline{\pi }}_h^{*}$ can be determined by Lemma 2, i.e., ${\varsigma }_{h〈1〉}\le {\varsigma }_{h〈2〉}\le \cdots {\varsigma }_{h〈{\tilde{n}}_h〉}$. Step 2. Calculate ${\mathsf{\Theta }}_{h\rho }$$\left(h,\rho =1,\dots ,\tilde{m}\right)$, and determine optimal group schedule ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$ by using Equations (15)–(18). Step 3. Optimal resource allocations ${\tilde{r}}_{hj}^{*}$ and ${\tilde{r}}_h^{*}$ are calculated by Equations (5) and (6) (see Lemma 1).

Proof. 

Time of Step 1 is $O\left({\sum }_{h=1}^m\left({\tilde{n}}_{h}log{\tilde{n}}_h\right)\right)\le O(\tilde{n}log\tilde{n})$. Steps 3 needs $O\left(\tilde{n}\right)$ time. For an assignment problem, Step 2 needs $O\left({\tilde{m}}^3\right)\le O\left({\tilde{n}}^3\right)$ time. Thus, the total time is $O\left({\tilde{n}}^3\right)$.    □

4.2. Case 2

If ${\varsigma }_{hj}=\varsigma$ and ${\tilde{n}}_h=\frac{\tilde{n}}{\tilde{m}}=\ddot{n}$, $h=1,\cdots ,\tilde{m}$, $j=1,2,\cdots ,{\tilde{n}}_h$, we have:

Lemma 3.

For $P_{\widehat{tct}}$, if ${\varsigma }_{hj}=\varsigma$ and ${\tilde{n}}_h=\frac{\tilde{n}}{\tilde{m}}=\ddot{n}$$\left(h=1,\cdots ,\tilde{m};j=1,\cdots ,{\tilde{n}}_h\right)$, then the optimal group schedule ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$ is the non-decreasing order of $o_h$, i.e., $o_{\left(1\right)}\le o_{\left(2\right)}\le \dots \le o_{\left(\tilde{m}\right)}$.

Proof. 

From Equation (12), if ${\varsigma }_{hj}=\varsigma$ and ${\tilde{n}}_h=\frac{\tilde{n}}{\tilde{m}}=\ddot{n}$,

$$\begin{array}{ccc}& & {\tilde{V}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\left({\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}{\left({\varsigma }_{\left[h\right]\left[j\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}\hfill \\ & =& {\tilde{V}}^{-\eta }{\varsigma }^{\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{\ddot{n}}}{\left({\displaystyle \sum _{l=j}^{\ddot{n}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{\ddot{n}}}{(1+\theta )}^{l-j+(k-h)\ddot{n}}\right)}^{\frac{1}{\eta +1}}\right)}^{\eta +1}\hfill \end{array}$$

is a constant (i.e., $\tilde{V},\varsigma ,\eta ,\mu ,\theta ,\ddot{n}$, and $\tilde{m}$ are given constants, and this term is independent of these parameters).

From Equation (12) and the above analysis, it can be proved that minimizing $\widehat{tct}$ is equal to minimizing the following expression:

$$\begin{array}{ccc}\hfill & \hfill & {\tilde{U}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}\right)}^{\frac{1}{\eta +1}}{\left(o_{\left[h\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}\hfill \\ \hfill & =\hfill & {\tilde{U}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{\ddot{n}}}{(1+\theta )}^{l-\ddot{n}+{\displaystyle \sum _{\xi =h}^k}\ddot{n}}\right)}^{\frac{1}{\eta +1}}{\left(o_{\left[h\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}\hfill \\ \hfill & =\hfill & {\tilde{U}}^{-\eta }{\left({\displaystyle \sum _{h=1}^{\tilde{m}}}{\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{\ddot{n}}}{(1+\theta )}^{l+(k-h)\ddot{n}}\right)}^{\frac{1}{\eta +1}}{\left(o_{\left[h\right]}\right)}^{\frac{\eta }{\eta +1}}\right)}^{\eta +1}.\hfill \end{array}$$

(19)

Similar to Lemma 2, ${\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{\ddot{n}}}{(1+\theta )}^{l+(k-h)\ddot{n}}\right)}^{\frac{1}{\eta +1}}$ is a monotonically decreasing function of h, and by the HLP rule (Hardy et al. [22]), Equation (19) can be minimized by arranging groups in the non-decreasing order of $o_h$; this completes the proof.    □

Thus, for the special case ${\varsigma }_{hj}=\varsigma$ and ${\tilde{n}}_h=\frac{\tilde{n}}{\tilde{m}}=\ddot{n}$$\left(i=1,\cdots ,\tilde{m};j=1,\cdots ,{\tilde{n}}_h\right)$, the problem $P_{\widehat{tct}}$ can be solved by:

Theorem 2.

If ${\varsigma }_{hj}=\varsigma$ and ${\tilde{n}}_h=\frac{\tilde{n}}{\tilde{m}}=\ddot{n}$ $\left(h=1,\cdots ,\tilde{m}\right)$, $P_{\widehat{tct}}$ is solvable by Algorithm 2 in $O(\tilde{n}log\tilde{n})$ time.

Algorithm 2: Case 2

Step 1. For group ${\mathsf{\Omega }}_h$$\left(h=1,\cdots ,\tilde{m}\right)$, optimal job schedule can be obtained in any order. Step 2. Optimal group schedule ${\pi }_{\mathsf{\Omega }}^{*}$ is the non-decreasing order of $o_h$. Step 3. Optimal resource allocations ${\tilde{r}}_{hj}^{*}$ and ${\tilde{r}}_h^{*}$ are calculated by Equations (5) and (6) (see Lemma 1).

4.3. Case 3

For any groups ${\mathsf{\Omega }}_x$ and ${\mathsf{\Omega }}_y$, if $o_x\le o_y$ implies ${\tilde{n}}_x\ge {\tilde{n}}_y$, we have:

Lemma 4.

For any groups ${\mathsf{\Omega }}_x$ and ${\mathsf{\Omega }}_y$ of $P_{\widehat{tct}}$, if $o_x\le o_y$ implies ${\tilde{n}}_x\ge {\tilde{n}}_y$, the optimal group schedule ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$ is non-decreasing order of $o_h$.

Proof. 

Similar to the proof of Liang et al. [6] (see Equation (12)).    □

For this special case, i.e., for any groups ${\mathsf{\Omega }}_x$ and ${\mathsf{\Omega }}_y$, if $o_x\le o_y$ implies ${\tilde{n}}_x\ge {\tilde{n}}_y$, $P_{\widehat{tct}}$ can be solved by:

Theorem 3.

For any groups ${\mathsf{\Omega }}_x$ and ${\mathsf{\Omega }}_y$, if $o_x\le o_y$ implies ${\tilde{n}}_x\ge {\tilde{n}}_y$, $P_{\widehat{tct}}$ is solvable by Algorithm 3 in $O\left(\tilde{n}log\tilde{n}\right)$ time.

Algorithm 3: Case 3

Step 1. For group ${\mathsf{\Omega }}_h$$\left(h=1,\dots ,\tilde{m}\right)$, the optimal job schedule ${\overline{\pi }}_h^{*}$ can be determined by Lemma 2, i.e., ${\varsigma }_{h〈1〉}\le {\varsigma }_{h〈2〉}\le \cdots {\varsigma }_{h〈{\tilde{n}}_h〉}$. Step 2. The optimal group schedule ${\pi }_{\mathsf{\Omega }}^{*}$ is the non-decreasing order of $o_h$. Step 3. The optimal resource allocations ${\tilde{r}}_{hj}^{*}$ and ${\tilde{r}}_h^{*}$ are calculated by Equations (5) and (6) (see Lemma 1).

5. A General Case

For $P_{\widehat{tct}}$, we cannot find a polynomially optimal algorithm, and the complexity of determining the optimal group schedule is still an open problem; we conjecture that this problem is NP-hard. Thus, $B\&B$ (i.e., branch-and-bound, where we need a lower bound and a upper bound) and heuristic algorithms might be a good way to solve $P_{\widehat{tct}}$.

5.1. Upper Bound

For the $\widehat{tct}$ minimization, any feasible solution can be proposed as a upper bound (denoted by $UB$). Similar to Section 3, the group sorting method can be used as the heuristic and then this solution is improved by using the pairwise interchange method.

For a better comparison, an alternative or complementary to Algorithm 4 is proposed, a tabu search (denoted by $\overbrace{ts}$) algorithm (i.e., Algorithm 5) can be used to solve $P_{\widehat{tct}}$.    

Algorithm 4: Upper Bound

Step 1. For group ${\mathsf{\Omega }}_h$$\left(h=1,\cdots ,\tilde{m}\right)$, an internal optimal job schedule ${\pi }_h^{*}$ (Lemma 2) is: ${\varsigma }_{h〈1〉}\le {\varsigma }_{h〈2〉}\le \cdots {\varsigma }_{h〈{\tilde{n}}_h〉}$. Step 2. Groups are scheduled by the non-decreasing order of $o_h$, i.e., $o_{\left(1\right)}\le o_{\left(2\right)}\le \dots \le o_{\left(\tilde{m}\right)}$. Step 3. Groups are scheduled by the non-increasing order of ${\tilde{n}}_h$, i.e., ${\tilde{n}}_{<<1>>}\ge {\tilde{n}}_{<<2>>}\ge \cdots \ge {\tilde{n}}_{<<\tilde{m}>>}$. Step 4. From Steps 2 and 3, the smallest value $\widehat{tct}$ (see Equation (12)) is selected as an original group schedule ${\overline{\pi }}_{\mathsf{\Omega }}$. Step 5. Set $k=1$. Step 6. Set $s=k+1$. Step 7. The new group schedule can be obtained by exchanging the kth and sth groups (denoted as ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$), and when $\widehat{tct}$ of ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$ is smaller than ${\overline{\pi }}_{\mathsf{\Omega }}$, ${\overline{\pi }}_{\mathsf{\Omega }}$ is updated by ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$. Step 8. If $s<\tilde{m}$, then set $s=s+1$, go to step 7. Step 9. If $k<\tilde{m}-1$, then set $k=k+1$, go to step 6; otherwise, STOP. Output the group schedule ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$ of the best group schedule found by the heuristic algorithm and its objective value $\widehat{tct}$. Step 10. According to Lemma 1, calculate the resource allocation by Equations (5) and (6).

Algorithm 5: $\overbrace{ts}$

Step 1. For group ${\mathsf{\Omega }}_h\left(h=1,\cdots ,\tilde{m}\right)$, an internal optimal job schedule ${\pi }_h^{*}$ can be obtained by Lemma 2, i.e., ${\varsigma }_{h〈1〉}\le {\varsigma }_{h〈2〉}\le \cdots {\varsigma }_{h〈{\tilde{n}}_h〉}$. Step 2. Let the tabu list be empty and the iteration number be zero. Step 3. Choose an initial group schedule by the Steps 2–4 of Algorithm 4, calculate its value $\widehat{tct}$ (see Equation (12)) and set the current group schedule as the best solution ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$. Step 4. Search the associated neighborhood of the current group schedule and resolve if there is a group schedule ${\overline{\pi }}_{\mathsf{\Omega }}^{**}$ with the smallest objective value in associated neighborhood and it is not in the tabu list, where the neighborhood is generated by the random exchange of any two groups. Step 5. If $\widehat{tct}\left({\overline{\pi }}_{\mathsf{\Omega }}^{**}\right)<\widehat{tct}\left({\overline{\pi }}_{\mathsf{\Omega }}^{*}\right)$, then let ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$= ${\overline{\pi }}_{\mathsf{\Omega }}^{**}$. Update the tabu list and the iteration number. Step 6. If there is not a group schedule in associated neighborhood but it is not in the tabu list or the maximum number of iterations is reached, output the local optimal group schedule ${\overline{\pi }}_{\mathsf{\Omega }}$ and $\widehat{tct}\left({\overline{\pi }}_{\mathsf{\Omega }}\right)$. Otherwise, update tabu list and go to Step 4. Step 7. According to Lemma 1, calculate the resource allocation by Equations (5) and (6).

5.2. Lower Bound

Let ${\overline{\pi }}_{\mathsf{\Omega }}=\left({\overline{\pi }}_{\mathsf{\Omega }p},{\overline{\pi }}_{\mathsf{\Omega }u}\right)$ be a group schedule, where ${\overline{\pi }}_{\mathsf{\Omega }p}$ (respectively ${\overline{\pi }}_{\mathsf{\Omega }u}$) is the scheduled (respectively unscheduled) part, and there are r groups in ${\overline{\pi }}_{\mathsf{\Omega }p}$. From Equation (12) and Lemma 4, the lower bound (denoted by $LB$) of $P_{\widehat{tct}}$ is

$$\begin{gathered} LB={\tilde{V}}^{-\eta }{\left(\begin{array}{c}{\displaystyle \sum _{h=1}^r}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\left(\begin{array}{c}{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+{\displaystyle \sum _{k=h+1}^r}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-j-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}+\hfill \\ {\displaystyle \sum _{k=r+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{<<k>>}}}{(1+\theta )}^{l-j-{\tilde{n}}_{<<k>>}+{\displaystyle \sum _{\xi =h}^r}{\tilde{n}}_{\left[\xi \right]}+{\displaystyle \sum _{\xi =r+1}^k}{\tilde{n}}_{<<\xi >>}}\hfill \end{array}\right)}^{\frac{1}{\eta +1}}{\left({\varsigma }_{\left[h\right]〈j〉}\right)}^{\frac{\eta }{\eta +1}}\hfill \\ +{\displaystyle \sum _{h=r+1}^{\tilde{m}}}{\displaystyle \sum _{j=1}^{{\tilde{n}}_h}}{\left(\begin{array}{c}{\displaystyle \sum _{l=j}^{{\tilde{n}}_{\left[h\right]}}}{(1+\theta )}^{l-j}+\hfill \\ {\displaystyle \sum _{k=h+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{<<k>>}}}{(1+\theta )}^{l-j-{\tilde{n}}_{<<k>>}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{<<\xi >>}}\hfill \end{array}\right)}^{\frac{1}{\eta +1}}{\left({\varsigma }_{\left(h\right)〈j〉}\right)}^{\frac{\eta }{\eta +1}}\hfill \end{array}\right)}^{\eta +1} \\ +{\tilde{U}}^{-\eta }{\left(\begin{array}{c}{\displaystyle \sum _{h=1}^r}{\left(\begin{array}{c}{\displaystyle \sum _{k=h}^r}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{\left[k\right]}}}{(1+\theta )}^{l-{\tilde{n}}_{\left[k\right]}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{\left[\xi \right]}}+\hfill \\ {\displaystyle \sum _{k=r+1}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{<<k>>}}}{(1+\theta )}^{l-{\tilde{n}}_{<<k>>}+{\displaystyle \sum _{\xi =h}^r}{\tilde{n}}_{\left[\xi \right]}+{\displaystyle \sum _{\xi =r+1}^k}{\tilde{n}}_{<<\xi >>}}\hfill \end{array}\right)}^{{}^{\frac{1}{\eta +1}}}{\left(o_{\left[h\right]}\right)}^{\frac{\eta }{\eta +1}}\hfill \\ {\displaystyle \sum _{h=r+1}^{\tilde{m}}}{\left({\displaystyle \sum _{k=h}^{\tilde{m}}}{(1+\mu )}^{k-h}{\displaystyle \sum _{l=1}^{{\tilde{n}}_{<<k>>}}}{(1+\theta )}^{l-{\tilde{n}}_{<<k>>}+{\displaystyle \sum _{\xi =h}^k}{\tilde{n}}_{<<\xi >>}}\right)}^{\frac{1}{\eta +1}}{\left(o_{\left(h\right)}\right)}^{\frac{\eta }{\eta +1}}\hfill \end{array}\right)}^{\eta +1}, \end{gathered}$$

(20)

where ${\varsigma }_{h〈1〉}\le {\varsigma }_{h〈2〉}\le \cdots {\varsigma }_{h〈{\tilde{n}}_h〉}$, $o_{(r+1)}\le o_{(r+2)}\le \dots \le o_{\left(\tilde{m}\right)}$ and ${\tilde{n}}_{<<r+1>>}\ge {\tilde{n}}_{<<r+2>>}\ge \cdots \ge {\tilde{n}}_{<<\tilde{m}>>}$ (remark: $o_{\left(h\right)}$ and ${\tilde{n}}_{<<h>>}$ ($h=r+1,\dots ,\tilde{m}$) do not necessarily correspond to identical group).

From the $UB$ (see Algorithm 4) and $LB$ (see Equation (20)), a standardized $B\&B$ algorithm can be given.

6. Computational Result

A series of computational experiments were performed to evaluate the effectiveness of the $UB$, $B\&B$, and $\overbrace{ts}$ algorithms, and the $\overbrace{ts}$ algorithm was terminated after 2000 iterations. The proposed algorithms were coded in the C++ language and performed on a desktop computer with CPUInter^®Corei5-10500 3.10 GHz, 8 GB RAM on Windows^® 10 operating system. The following parameters were randomly generated: ${\zeta }_{hj}$ is uniformly distributed in $\left[1,100\right]$; $o_h$ is uniformly distributed in $\left[1,50\right]$; $\theta$ and $\mu$ are uniformly distributed in $\left(0,0.5\right)$, $\left(0.5,1\right)$; $\tilde{U}=\tilde{V}=500$; $\tilde{n}=100,150,200,250,300$; $\tilde{m}=12,13,14,15,16$ (at least one job per group); $\eta =2$. For each combination ($\tilde{n}$, $\tilde{m}$, and $\theta \left(\mu \right)$), there were 10 randomly generated replicas and the maximum $\widehat{cpu}$ time for each instance was set to 3600 s. For the $B\&B$ algorithm, average and maximum $\widehat{cpu}$ time (in seconds), and average and maximum node numbers were given. The error bound of $UB$ and $\overbrace{ts}$ algorithms is given by:

$$\frac{\widehat{tct}\left(Y\right)-\widehat{tct}\left(Opt\right)}{\widehat{tct}\left(Opt\right)},$$

where $Y\in \left\{UB,\overbrace{ts}\right\}$, $\widehat{tct}\left(Y\right)$ is a value $\widehat{tct}$ by Y, and $\widehat{tct}\left(Opt\right)$ is an optimal value by a $B\&B$ algorithm. The computational results are given in

Table 2. Results of algorithms for $\theta ,\mu \sim \left(0,0.5\right)$.

		$\mathit{B}\&\mathit{B}$-$\widehat{\mathit{cpu}}$ (s)		Node Number of $\mathit{B}\&\mathit{B}$		$\mathit{UB}$-$\widehat{\mathit{cpu}}$ (s)		Error Bound of $\mathit{UB}$		$\overbrace{\mathit{ts}}$-$\widehat{\mathit{cpu}}$ (s)		Error Bound of $\overbrace{\mathit{ts}}$
$\tilde{\mathit{n}}$	$\tilde{\mathit{m}}$	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max
	12	135.024	221.776	1,809,907.670	2,159,443	0.016	0.017	0.000095	0.000187	20.779	20.851	3.834449	7.624277
	13	487.759	689.564	3,549,270.333	5,082,238	0.026	0.027	0.000156	0.000268	27.917	27.931	1.732993	2.020046
100	14	922.643	1522.268	13,107,200.333	15,310,034	0.039	0.040	0.000801	0.000857	36.547	36.851	2.649336	3.713691
	15	2194.031	2700.565	27,285,725.333	29,086,172	0.06	0.066	0.000958	0.001559	46.688	46.716	2.817131	3.046495
	16	3600	3600	31,359,296.667	35,393,226	0.089	0.091	0	0	59.426	59.502	4.264297	5.401098
	12	207.987	342.972	2,341,793.000	3,117,957	0.018	0.019	0.000027	0.000078	20.801	21.24	1.514108	1.621744
	13	542.599	801.597	6,761,302.333	9,380,526	0.024	0.025	0	0	27.637	27.713	1.385886	2.443091
150	14	945.239	1546.23	12,394,620.667	16,056,940	0.038	0.039	0.000023	0.000062	36.417	36.447	2.669022	3.621472
	15	2253.448	2792.626	21,252,555.333	28,365,609	0.058	0.059	0.000044	0.000083	46.842	46.884	2.305773	2.829561
	16	3600	3600	3,216,807.333	35,946,209	0.084	0.086	0.000078	0.000165	59.635	59.732	2.348701	3.032307
	12	244.069	401.384	2,977,588.333	4,496,930	0.019	0.024	0	0	20.679	20.701	1.159309	1.440431
	13	603.216	898.287	7,165,875.333	9,493,651	0.025	0.026	0.000035	0.000071	27.631	27.626	1.273332	1.786464
200	14	998.154	1702.5569	10,620,850.667	18,113,633	0.039	0.04	0	0	36.339	36.386	1.895725	2.250205
	15	2256.669	2899.45	25,283,619.350	29,882,329	0.058	0.059	0.000336	0.000512	46.892	46.941	1.741518	2.476327
	16	3600	3600	30406061.000	34993966	0.083	0.084	0	0	59.634	59.691	2.173201	3.408911
	12	315.999	511.48	4,632,641.000	7,187,564	0.018	0.019	0.000726	0.000937	20.606	20.611	0.849315	1.063118
	13	649.96	998.95	7,359,686.667	9,993,712	0.026	0.026	0.000012	0.000053	27.674	27.727	1.177795	1.975853
250	14	1052.236	1798.635	10,615,423.970	15,492,118	0.038	0.040	0.000225	0.000429	35.369	36.441	2.132518	5.285686
	15	2348.584	3022.158	23,198,516.333	26,916,519	0.061	0.063	0	0	46.182	46.886	2.195878	3.378249
	16	3600	3600	31,985,126.350	39,841,545	0.085	0.087	0.000047	0.000096	59.642	60.662	1.080341	2.231895
	12	372.965	602.478	6,529,516.270	8,874,654	0.019	0.021	0.000264	0.000418	20.228	21.678	2.132238	3.441628
	13	700.648	1096.126	9,534,255.360	10,346,347	0.028	0.029	0	0	27.432	28.344	3.041866	4.726763
300	14	1125.267	1900.597	18,285,356.330	20,378,676	0.042	0.043	0.000241	0.000358	35.636	36.359	2.508975	3.354484
	15	2411.266	3098.486	23,166,586.555	29,786,776	0.061	0.063	0.000074	0.000085	45.856	46.612	1.456993	2.018688
	16	3600	3600	33,064,597.980	36,268,497	0.086	0.088	0	0	59.202	60.342	2.665422	3.625572

and

Table 3. Results of algorithms for $\theta ,\mu \sim \left(0.5,1\right)$.

		$\mathit{B}\&\mathit{B}$-$\widehat{\mathit{cpu}}$ (s)		Node Number of $\mathit{B}\&\mathit{B}$		$\mathit{UB}$-$\widehat{\mathit{cpu}}$ (s)		Error Bound of $\mathit{UB}$		$\overbrace{\mathit{ts}}$-$\widehat{\mathit{cpu}}$ (s)		Error Bound of $\overbrace{\mathit{ts}}$
$\tilde{\mathit{n}}$	$\tilde{\mathit{m}}$	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max	Mean	Max
	12	111.759	203.165	1,772,325.333	2,006,440	0.018	0.022	0.000342	0.000361	20.636	20.663	2.151314	2.733541
	13	514.284	720.05	5,192,266.570	8,375,900	0.036	0.057	0.000023	0.000097	27.71	27.724	2.302026	2.604564
100	14	899.152	1511.534	10,440,786.667	15,534,053	0.041	0.044	0.000056	0.000089	38.454	41.59	3.211589	4.194101
	15	2231.154	2691.187	21,511,386.670	28,404,113	0.062	0.071	0	0	47.426	47.484	3.053645	3.928604
	16	3600	3600	32,304,624.333	34,845,329	0.086	0.087	0.000154	0.000203	60.495	60.688	4.714135	6.396946
	12	197.605	301.479	2,269,584.670	3,575,833	0.017	0.018	0.000977	0.000995	20.896	20.912	1.417686	1.890114
	13	570.153	807.542	6,764,995.435	10,027,994	0.025	0.026	0.000089	0.0000138	28.125	28.213	1.023524	1.151338
150	14	966.147	1632.498	10,816,813.000	17,165,408	0.039	0.04	0.000135	0.000185	36.918	36.995	1.383139	1.714258
	15	2265.154	2823.396	64,825,309.666	20,264,395	0.07	0.094	0	0	47.613	47.704	1.918044	3.053374
	16	3600	3600	33,081,125.000	38,287,571	0.086	0.091	0.000235	0.000304	59.542	59.622	2.339585	3.275121
	12	251.663	412.269	3,364,810.333	4,354,750	0.016	0.017	0.000322	0.000358	20.588	20.619	0.679119	1.162433
	13	632.148	910.214	7,692,721.250	12,135,354	0.038	0.064	0.000014	0.000039	27.675	27.737	0.843637	0.974668
200	14	1021.267	1741.637	10,359,758.667	18,262,014	0.040	0.041	0	0	36.342	37.353	1.094559	1.495353
	15	2303.264	2935.348	24,840,981.000	29,871,474	0.057	0.058	0.000055	0.000083	46.872	46.91	1.243455	1.642072
	16	3600	3600	36,074,135.333	39,275,374	0.083	0.084	0	0	59.671	59.794	1.942357	2.492556
	12	310.286	507.549	3,193,303.333	5,195,728	0.017	0.018	0	0	20.627	20.651	0.578495	1.212256
	13	669.297	1032.756	7,887,726.555	13,510,556	0.025	0.026	0.000327	0.000449	27.716	28.722	0.971304	1.540024
250	14	1077.954	1901.25	11,022,935.550	20,161,905	0.042	0.043	0.000087	0.000126	38.265	41.688	1.464696	2.107542
	15	2363.186	3102.583	24,480,723.980	32,108,671	0.08	0.092	0.000355	0.000421	47.464	48.424	1.073162	1.436231
	16	3600	3600	35,416,920.000	37,899,764	0.092	0.096	0.000039	0.000058	60.474	61.622	1.607212	2.647154
	12	372.261	611.365	4,028,462.640	6,779,955	0.021	0.022	0.000022	0.000073	20.858	21.996	0.770591	1.264125
	13	726.314	1143.348	8,899,027.570	13,410,513	0.036	0.057	0	0	28.135	29.234	1.661815	2.354942
300	14	1132.706	2008.646	14,693,257.000	23,608,109	0.059	0.061	0.0000068	0.000112	36.936	38.599	0.702051	1.018678
	15	2546.264	3348.345	30,358,453.333	35,337,815	0.084	0.085	0	0	47.341	48.502	1.670674	2.166306
	16	3600	3600	35,362,523.000	39,764,582	0.086	0.092	0.000034	0.000086	58.245	60.262	1.247154	1.626366

. From Table 2 and Table 3, it is easy to see that the $B\&B$ can solve up to 300 jobs in a reasonable amount of time, and $UB$ performs very well compared to $\overbrace{ts}$ in terms of error bound. When $\tilde{n}\le 300$, the maximum error bound is less than $0.001559$ (i.e., relative error $\le 0.1559\%$).

7. Conclusions

This paper investigated the group problem with deterioration effects and resource allocation. The goal was to determine ${\overline{\pi }}_{\mathsf{\Omega }}^{*}$, ${\overline{\pi }}_h^{*}$$\left(h=1,\cdots ,\tilde{m}\right)$ in ${\mathsf{\Omega }}_h$ and $R^{*}$ such that $\widehat{tct}$ is minimized under ${\sum }_{i=1}^{\tilde{m}}{\sum }_{j=1}^{{\tilde{n}}_h}{\tilde{r}}_{ij}\le \tilde{V}$ and ${\sum }_{i=1}^{\tilde{m}}{\tilde{r}}_i\le \tilde{U}$. For some special cases, we demonstrated that this problem remains polynomially solvable. For the general case, we proposed some algorithms to solve this problem. As a future extension, it is interesting to deal with group scheduling with two scenarios based on processing times (see Wu et al. [23]) and delivery times (see Qian and Zhan [24]).