# Solution Algorithms for Single-Machine Group Scheduling with Learning Effect and Convex Resource Allocation

Authors: Wanlei Wang; Jian-Jun Wang; Ji-Bo Wang
Journal: Complexity
 (2021)

---

## Abstract

This paper deals with a single-machine resource allocation scheduling problem with learning effect and group technology. Under slack due-date assignment, our objective is to determine the optimal sequence of jobs and groups, optimal due-date assignment, and optimal resource allocation such that the weighted sum of earliness and tardiness penalties, common flow allowances, and resource consumption cost is minimized. For three special cases, it is proved that the problem can be solved in polynomial time. To solve the general case of problem, the heuristic, tabu search, and branch-and-bound algorithms are proposed.


---

## Body

## 1. Introduction

In the conventional scheduling models and problems, it is generally assumed that the job processing times are constants, but in practice, examples can be found to illustrate that the job processing times are not necessarily constants (Shabtay and Steiner [1], Biskup [2], and Azzouz et al. [3]). More recently, Zhu et al. [4] considered resource allocation single-machine scheduling problems with learning effects and group technology. For the linear and convex resource allocation models, they proved that problem of minimizing the weighted sum of makespan and total resource cost can be solved in polynomial time. Lu et al. [5] revisited the same model with Zhu et al. [4], but they considered the case of resource availability is limited. For the makespan minimization subject to limited resource availability, they proposed heuristic and branch-and-bound algorithms. Sun et al. [6] and Lv et al. [7] worked on single-machine scheduling group problems with learning effects and resource allocation. Under the slack (SLK) due-date assignment, for the linear weighted sum of scheduling cost and resource consumption cost minimization, Sun et al. [6] proved that the problem can be solved in polynomial time. However, Lv et al. [7] showed that the results of Sun et al. [6] are incorrect by two counter-examples, and Lv et al. [7] also provided the corrected results under a special case. In this paper, we will consider the same model with Sun et al. [6] and Lv et al. [7], i.e., three popular features in the recent years: group technology, resource allocation, and learning effect. The contributions of this study are given as follows: (1) we study the SLK assignment single-machine group scheduling problem along with learning effect and convex resource allocation; (2) the optimal properties are provided for the total cost (including earliness, tardiness, common flow allowances, and resource consumption cost) minimization; (3) we propose the heuristic, tabu search, and branch-and-bound algorithms to solve the problem.The reminder of this paper is organized as follows. In Section2, the relevant literature review is presented. The problem statement is presented in Section 3. Section 4 gives some properties of the problem. In Section 5, some special cases are discussed. In Section 6, for the general case, solution algorithms are proposed. Finally, the conclusions are given in Section 7.


## 2. Literature Review

In this section, we restrict our literature review to papers that study scheduling problems with learning effects, resource allocation, and/or group technology.In manufacturing environments, after learning, the time required for workers (machines) to process some jobs is decreasing, which causes scheduling problems with learning effects (Biskup [2]). Wang et al. [8] considered the flow shop problem with a learning effect. Under two-machine and release dates, the goal is to minimize the weighted sum of makespan and total completion time. They proposed a branch-and-bound algorithm and a multiobjective memetic algorithm to solve the problem. Wang et al. [9] considered flow shop problems with truncated learning effects. For the makespan and total weighted completion time minimizations, they proposed heuristics and branch-and-bound algorithms. Yan et al. [10] and Wang et al. [11] studied single-machine scheduling problems with learning effects and release times. Sun et al. [12] investigated flow shop problem with general position weighted learning effects. For the total weighted completion time minimization, they proposed some heuristics and a branch-and-bound algorithm to solve the problem.In addition, scheduling problems with resource allocation (controllable processing times) have also attracted considerable interest from researchers (Shabtay and Steiner [1]), that is, the scheduler can control processing times of jobs by allocating a common continuously nonrenewable resource. Kayvanfar et al. [13, 14] considered single-machine scheduling with controllable processing times. For the total tardiness and earliness minimization, Kayvanfar et al. [13] proposed a mathematical model and three heuristic techniques; Kayvanfar et al. [14] proposed a drastic hybrid heuristic algorithm. Lu and Liu [15] considered single machine scheduling problems with resource allocation and position-dependent workloads. They proposed a bicriteria analysis for the scheduling cost and total resource consumption cost. Tsao et al. [16] considered energy-efficient single-machine scheduling problem with controllable processing time. Under differential electricity pricing, they proposed a mixed-integer programming model and a fuzzy control approach. Mor et al. [17] considered single-machine scheduling problems with resource-dependent processing times. For a large set of that the scheduling criterion can be represented as one that includes positional penalties; they proposed heuristic algorithms to solve the problems. Kayvanfar et al. [18] considered unrelated parallel machines scheduling problem with controllable processing times. For the linear weighted sum of tardiness, earliness, jobs compressing and expanding costs, and makespan minimization, they proposed a mixed integer programming model and some heuristics. Zarandi and Kayvanfar [19] considered a biobjective identical parallel machines scheduling problem with controllable processing times. The goal is to simultaneously minimize total cost of tardiness and earliness as well as compression and expansion costs of job processing times and makespan. They proposed two multiobjective evolutionary algorithms to solve the biobjective problem. Kayvanfar et al. [20] studied identical parallel machine scheduling problem with controllable processing times. For the linear weighted sum of tardiness, earliness, and job compressions/expansion cost minimization, they proposed a mixed integer linear programming model and some heuristic algorithms to solve the problem.A third possible aspect is that scheduling problems with group technology (GT, see studies by Mosier et al. [21] and Webster and Baker [22]), that is, GT is an approach to manufacturing that seeks to improve efficiency in high-volume production by exploiting the similarities of different products and activities in their production (see studies by Yang and Yang [23] and Ji et al. [24]). Xu et al. [25] and Liu et al. [26] considered single-machine group scheduling with deteriorating jobs and ready times. For the makespan minimization, Xu et al. [25] proved that some special cases can be solved in polynomial time; for the general case, Liu et al. [26] proposed a branch-and-bound algorithm. Li and Zhao [27] considered single machine scheduling problem with group technology. Under multiple due windows assignment, they proved that the total cost (including earliness, tardiness, and due windows) minimization can be solved in polynomial time. Zhang and Xie [28] studied the single machine scheduling problem with position dependent processing times. Under group technology and ready times, for the makespan minimization, they proved that a special case can be solved in polynomial time. Ji and Li [29] studied single-machine group scheduling with variable job processing times (including resource allocation, learning effects, and deteriorating jobs). They proved that two versions of problem can be solved in polynomial time. Zhang et al. [30] considered single-machine group scheduling problems with position-dependent processing times. They proved that the makespan and the total completion time minimization can be solved in polynomial-time algorithm, respectively. Muştu, and Eren [31]) studied the single-machine scheduling problem with sequence-independent setup times and time-dependent learning and forgetting effects. They proved that the makespan minimization is ordinary NP-hard, and they also proposed an integer nonlinear programming and a dynamic programming to solve the problem. Extensive surveys of different scheduling models and problems with group technology can be found in studies by Allahverdi [32] and Neufeld et al. [33].More recently, Wang et al. [34] and Lu et al. [35] delved into single-machine resource allocation scheduling problems with learning effects. He et al. [36] considered the single-machine resource allocation scheduling with truncated job-dependent learning effect. Under linear and convex resource allocations, polynomial time algorithms are developed to solve the problem. Li et al. [37] considered single-machine scheduling with general job-dependent learning curves and controllable processing times. They proved that some regular and nonregular objective minimizations can be solved in polynomial time. Wang et al. [38] considered single-machine scheduling with truncated learning effects and resource allocation. For total weighted flow time cost and total resource consumption cost, they provided a bicriteria analysis. Geng et al. [39] and Sun et al. [40] investigated two-machine no-wait flow shop scheduling with resource allocation and learning effect. For the common due date assignment, Geng et al. [39] proved that two versions of the scheduling criteria and resource consumption cost can be solved in polynomial time. For the slack due-date assignment, Sun et al. [40] proved that three versions of the scheduling criteria and resource consumption cost can be solved in polynomial time. Liu and Jiang [41] explored due-date assignment scheduling problems with job-dependent learning effects and convex resource allocation. Zhang et al. [30] considered single-machine group scheduling problems with position-dependent learning effects. They proved that the makespan and total completion time minimizations can be solved in polynomial time algorithm. Wang and Liang [42] and Liang et al. [43] investigated single-machine resource allocation scheduling with deteriorating jobs and group technology. Liao et al. [44] studied a two-competing group parallel machines scheduling problem with truncated job-dependent learning effects. Under serial-batching machines, for the makespan minimization, they proposed a greedy algorithm.To the best of our knowledge, apart from the recent papers of Sun et al. [6] and Lv et al. [7], the single-machine slack due-date assignment scheduling problem with resource allocation, group technology, and learning effects has not been investigated. In this paper, we consider the same model as in Sun et al. [6] and Lv et al. [7], but with the tabu search and branch-and-bound algorithms to solve the problem.


## 3. Problem Formulation

We haven jobs grouped into f groups (i.e., G1,G2,…,Gf) to be processed by a single machine, where the number of jobs in the group Gii=1,2,…,f is mi, i.e., ∑i=1fmi=n. Each group Gii=1,2,…,f has an independent setup time si and contains mi jobs which are processed consecutively. Let Ji,j be the j th job in group Gi, i=1,2,…,f, j=1,2,…,mi, i.e., group Gi has jobs Ji,1,Ji,2,…,Ji,mi. Let Ji,j be the job in the i th group position and j th internal job position. As in the study by Liang et al. [43], if the job Ji,j is scheduled in r th position in group Gi, the actual processing time of job Ji,j is(1)pi,jA=pi,jrai,jui,jη,where η is a constant positive parameter, pi,j is the normal processing time of job Ji,j, ai,j≤0 is the learning rate (see the study by Biskup [2]) of job Ji,j, ui,j≥ui′>0, ui′ is the minimal resource allocation to the jobs of group Gi (if ui,j is close to zero, pi,jA will be close to infinity, which is not realistic; hence, we set ui,j≥ui′>0). Let Ci,j (di,j) be the completion time (due-date) of job Ji,j. For the slack (SLK) due-date assignment, we assume that the due-date of job Ji,j is di,j=pi,jA+qi, where qi is the common flow allowance for group Gi and qi is a decision variable. Let Ei,j=maxdi,j−Ci,j,0 (Ti,j=maxCi,j−di,j,0) be the earliness (tardiness) of job Ji,j; our goal is to find the optimal group sequence πG∗, job sequence πi∗i=1,2,…,f within group Gi, and resource allocation such that the following cost is minimized:(2)∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j,where αi, βi, and γi are the nonnegative parameters of group Gi and νi,j represents the per unit cost of the resource ui,j allocated to job Ji,j. Using the three-field classification (see the studies by Shabtay and Steiner [1], Biskup [2], and Azzouz et al. [3]), the problem can be denoted as(3)1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j,where GT denotes the group technology and CRA represents the convex function of resource allocation (1).


## 4. Some Properties

Obviously, an optimal sequence exists that starts at time zero and without any machine idle time between all the jobs. Similar to the study by Adamopoulos and Pappis [45], we have the following.Lemma 1.
IfCi,j≤di,j⟹Ci,j−1≤di,j−1, i=1,2,…,f;j=1,2,…,mi.
IfCi,j≥di,j⟹Ci,j+1≥di,j+1, i=1,2,…,f;j=1,2,…,mi.Lemma 2.
For the problem1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, there exists an optimal schedule such that the optimal value of qi coincides with the job completion time of the group Gi, i.e., qi=Ci,ki−1=Si+si+∑j=1ki−1pi,jA, where(4)ki=minmi,max0,miβi−γiαi+βi,and Si is the starting time of group Gi.Lemma 3 (see [43]).
For a given sequenceπ, the optimal resource allocation is(5)ui,j∗=maxui,j,ui′,where(6)ui,j=ηαij+∑h=ifmhγhνi,j1/η+1pi,jjai,jη/η+1,i=1,…,f;j=1,…,ki−1,ηβimi−jνi,j1/η+1pi,jjai,jη/η+1,i=1,…,f;j=ki,…,mi.
From the study by Liang et al. [43], we have(7)∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j=∑i=1f∑h=ifmhγhsi+η1/η+1+η−η/η+1∑i=1f∑j=1ki−1αij+∑h=ifmhγh1/η+1νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑i=1f∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1.Lemma 4 (see [43]).
For the problem1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, if the sequence of groups is given by πG=G1,G2,…,Gf, the optimal job sequence in the group Gii=1,2,…,f can be obtained by the following assignment problem (AP-i):(8)AP−iMin∑j=1mi∑h=1miϑi,j,hxi,j,h,(9)s.t.∑h=1mixi,j,h=1,i=1,2,…,f;j=1,2,…,mi,(10)∑j=1mixi,j,h=1,i=1,2,…,f;h=1,2,…,mi,(11)xi,j,h=0or1,where(12)ϑi,j,h=η1/η+1+η−η/η+1αih+∑l=ifmlγl1/η+1νi,jpi,jhai,jη/η+1,i=1,2,…,f;j=1,2,…,mi;h=1,2,…,ki−1η1/η+1+η−η/η+1βimi−h1/η+1νi,jpi,jhai,jη/η+1,i=1,2,…,f;j=1,2,…,mi;h=ki,ki+1,…,mi.Lemma 5.
The term∑i=1f∑h=ifmhγhsi is minimized if s1≤s2≤⋯≤sf.Proof.
It is similar to the proof of Liang et al. [43].Lemma 6.
If the optimal job sequence within each group is given, the term,(13)η1/η+1+η−η/η+1∑i=1f∑j=1ki−1αij+∑h=ifmhγh1/η+1νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑i=1f∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1,is minimized if m1γ1≥m2γ2≥⋯≥mfγf.Proof.
By using simple group interchanging technique, the result can be easily obtained.


## 5. Polynomial Time Solvable Cases

### 5.1. Case 1

As in the study by Liao et al. [44], if the groups have agreeable conditions, i.e., if si≤sh implies miγi≥mhγh for all groups Gi and Gh, the problem 1GT,si,CRA,SLK,si≤sh⟹miγi≥mhγh∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j can be solved in polynomial time.Lemma 7 (see [44]).
For the problem1GT,si,CRA,SLK,si≤sh⟹miγi≥mhγh∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, if the groups have agreeable conditions, i.e., if si≤sh implies miγi≥mhγh for all groups Gi and Gh, then the optimal group sequence πG∗ can be obtained by sequencing groups in nondecreasing order of si, or equivalently, the optimal group sequence πG∗ can be obtained by sequencing groups in nonincreasing order of miγi.For the problem1GT,si,Con,si≤sh⟹miγi≥mhγh∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the optimal solution algorithm is given as follows:Theorem 1 (see [44]).
The problem,(14)1GT,si,CRA,SLK,si≤sh⟹miγi≥mhγh∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j,can be solved by Algorithm 1 in On3 time.Algorithm 1:Optimal solution for Case 1.
Step 1. Calculateki by using (4), i=1,2,…,f.Step 2. The optimal sequence between groups is arranged in nondecreasing order ofsi.Step 3. The jobs in each group are arranged according to the assignment problemAP (Lemma 4).Step 4. Calculate the optimal resource allocationuij∗ according to (5).Step 5. Calculate the optimal common flow allowanceqi=Ci,ki−1 and the corresponding optimal objective function ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j by using (7).


### 5.2. Case 2

In this subsection, a special case will be considered, i.e., ifsi=s, miγi=mγ¯, for i=1,2,…f.Lemma 8.
For the problem1GT,si,CRA,SLK,si=s,miγi=mγ¯∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the optimal group sequence πG∗ can be obtained by an assignment problem.Proof.
From Lemma4, the sequence πi∗i=1,2,…,f within the group Gi can be obtained. For the group Gi, if si=s, and miγi=mγ¯i=1,2,…,f, from (7), we have(15)∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j=ff+1smγ¯2+η1/η+1+η−η/η+1∑i=1f∑j=1ki−1αij+f−i+1mγ¯1/η+1νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑i=1f∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1.
Letxi,r=1, if group Gi is assigned to position r, and xi,r=0 otherwise. For ff+1smγ¯/2 is a constant, hence the optimal group sequence πG∗ can be obtained by an assignment problem (AP-G):(16)AP−GMin∑i=1f∑r=1fϑi,rxi,rs.t.∑r=1fxi,r=1,i=1,2,…,f,∑i=1fxi,r=1,r=1,2,…,f,xi,r=0or1,where the optimal sequence of group Gi is πi∗=Ji,1,Ji,2,…,Ji,mi (by Lemma 4), and(17)ϑi,r=η1/η+1+η−η/η+1∑j=1ki−1αij+f−r+1mγ¯1/η+1νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1.
For the problem1GT,si,CRA,SLK,si=s,miγi=mγ¯∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the optimal solution algorithm is given as follows:Theorem 2.
The problem,(18)1GT,si,CRA,SLK,si=s,miγi=mγ¯∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j,can be solved by Algorithm 2 in On3 time.Algorithm 2:Optimal solution for Case 2.
Step 1. Calculateki by using (4), i=1,2,…,f.Step 2. The optimal sequence between groups can be obtained by Lemma8.Step 3. The jobs in each group are arranged according to the assignment problemAP (Lemma 4).Step 4.Calculate the optimal resource allocationui,j∗ according to (5).Step 5. Calculate the optimal common flow allowanceqi=Ciki−1 and the corresponding optimal objective function ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j by using (7).Proof.
Time complexity of Step 1 isOn; time complexity of Step 2 is Oflogf time. Step 3 needs ∑i=1fOmi3≤On3 time. Steps 4-5 need On time, respectively. Thus, the total time complexity of Algorithm 2 is On3 time.


### 5.3. Case 3

In this subsection, it is assumed that the number of groupsf is a given constant.Theorem 3.
For the1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j problem, an optimal schedule can be solved in Of!n3 time, i.e., the problem 1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j can be solved in polynomial time if f is a given constant.Proof.
From Lemma4, if the schedule of groups is given, then an optimal schedule can be obtained in ∑i=1fOni3≤On3 time. Obviously, there are f! possible group schedules, hence an optimal schedule can be solved in Of!n3 time.
Based on Theorem2, an algorithm can be proposed to solve the problem 1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j.


## 5.1. Case 1

As in the study by Liao et al. [44], if the groups have agreeable conditions, i.e., if si≤sh implies miγi≥mhγh for all groups Gi and Gh, the problem 1GT,si,CRA,SLK,si≤sh⟹miγi≥mhγh∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j can be solved in polynomial time.Lemma 7 (see [44]).
For the problem1GT,si,CRA,SLK,si≤sh⟹miγi≥mhγh∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, if the groups have agreeable conditions, i.e., if si≤sh implies miγi≥mhγh for all groups Gi and Gh, then the optimal group sequence πG∗ can be obtained by sequencing groups in nondecreasing order of si, or equivalently, the optimal group sequence πG∗ can be obtained by sequencing groups in nonincreasing order of miγi.For the problem1GT,si,Con,si≤sh⟹miγi≥mhγh∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the optimal solution algorithm is given as follows:Theorem 1 (see [44]).
The problem,(14)1GT,si,CRA,SLK,si≤sh⟹miγi≥mhγh∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j,can be solved by Algorithm 1 in On3 time.Algorithm 1:Optimal solution for Case 1.
Step 1. Calculateki by using (4), i=1,2,…,f.Step 2. The optimal sequence between groups is arranged in nondecreasing order ofsi.Step 3. The jobs in each group are arranged according to the assignment problemAP (Lemma 4).Step 4. Calculate the optimal resource allocationuij∗ according to (5).Step 5. Calculate the optimal common flow allowanceqi=Ci,ki−1 and the corresponding optimal objective function ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j by using (7).


## 5.2. Case 2

In this subsection, a special case will be considered, i.e., ifsi=s, miγi=mγ¯, for i=1,2,…f.Lemma 8.
For the problem1GT,si,CRA,SLK,si=s,miγi=mγ¯∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the optimal group sequence πG∗ can be obtained by an assignment problem.Proof.
From Lemma4, the sequence πi∗i=1,2,…,f within the group Gi can be obtained. For the group Gi, if si=s, and miγi=mγ¯i=1,2,…,f, from (7), we have(15)∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j=ff+1smγ¯2+η1/η+1+η−η/η+1∑i=1f∑j=1ki−1αij+f−i+1mγ¯1/η+1νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑i=1f∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1.
Letxi,r=1, if group Gi is assigned to position r, and xi,r=0 otherwise. For ff+1smγ¯/2 is a constant, hence the optimal group sequence πG∗ can be obtained by an assignment problem (AP-G):(16)AP−GMin∑i=1f∑r=1fϑi,rxi,rs.t.∑r=1fxi,r=1,i=1,2,…,f,∑i=1fxi,r=1,r=1,2,…,f,xi,r=0or1,where the optimal sequence of group Gi is πi∗=Ji,1,Ji,2,…,Ji,mi (by Lemma 4), and(17)ϑi,r=η1/η+1+η−η/η+1∑j=1ki−1αij+f−r+1mγ¯1/η+1νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1.
For the problem1GT,si,CRA,SLK,si=s,miγi=mγ¯∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the optimal solution algorithm is given as follows:Theorem 2.
The problem,(18)1GT,si,CRA,SLK,si=s,miγi=mγ¯∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j,can be solved by Algorithm 2 in On3 time.Algorithm 2:Optimal solution for Case 2.
Step 1. Calculateki by using (4), i=1,2,…,f.Step 2. The optimal sequence between groups can be obtained by Lemma8.Step 3. The jobs in each group are arranged according to the assignment problemAP (Lemma 4).Step 4.Calculate the optimal resource allocationui,j∗ according to (5).Step 5. Calculate the optimal common flow allowanceqi=Ciki−1 and the corresponding optimal objective function ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j by using (7).Proof.
Time complexity of Step 1 isOn; time complexity of Step 2 is Oflogf time. Step 3 needs ∑i=1fOmi3≤On3 time. Steps 4-5 need On time, respectively. Thus, the total time complexity of Algorithm 2 is On3 time.


## 5.3. Case 3

In this subsection, it is assumed that the number of groupsf is a given constant.Theorem 3.
For the1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j problem, an optimal schedule can be solved in Of!n3 time, i.e., the problem 1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j can be solved in polynomial time if f is a given constant.Proof.
From Lemma4, if the schedule of groups is given, then an optimal schedule can be obtained in ∑i=1fOni3≤On3 time. Obviously, there are f! possible group schedules, hence an optimal schedule can be solved in Of!n3 time.
Based on Theorem2, an algorithm can be proposed to solve the problem 1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j.


## 6. General Case

For the general case of the problem1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the complexity is an open question. Hence, the heuristic algorithm and branch-and-bound (B&B) algorithm might be a good way to solve the problem.


### 6.1. Heuristic Algorithm

From Lemma4, the optimal job sequence within the same group can be obtained, and the optimal resource allocation of a given schedule can be obtained by Lemma 3. In this subsection, we apply the well-known heuristic procedure from the study by Nawaz et al. [46], and the following heuristic algorithm can be proposed.


### 6.2. Tabu Search Algorithm

Tabu search (TS) algorithm is a metaheuristic algorithm first proposed by Glover [47]. In this subsection, tabu search (TS) is used to find a near-optimal solution (Xu et al. [48]). The initial sequence used in the TS algorithm is chosen by the nondecreasing order of si, and the maximum number of iterations for the TS algorithm is set at 100f, where f is the number of groups. As in the study by Wu et al. [49], the implementation of the TS algorithm is given as follows:


### 6.3. A Lower Bound

LetπG=πGS,πGU be a sequence of groups in which πGS is the scheduled part, and πGU is a unscheduled part. Assume that there are g groups in πGS; from (7), it is noticed that the terms,(19)∑i=g+1f∑h=ifmhγhsi,η1/η+1+η−η/η+1∑i=g+1f∑j=1ki−1αij+∑h=ifmhγh1/η+1νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑i=g+1f∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1,can be minimized by Lemmas 5–6. Hence, the lower bound can be obtained by the following formula:(20)LB=∑i=1g∑h=igmhγh+∑h=g+1fmhγhsi+∑i=g+1f∑h=ifmhγhsi+η1/η+1+η−η/η+1∑i=1g∑j=1ki−1αij+∑h=igmhγh+∑h=g+1fmhγh1/η+1×νi,jpi,jjai,jη/η+1+∑i=g+1f∑j=1ki−1αij+∑h=igmhγh+∑h=g+1fmhγh1/η+1×νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑i=1g∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1+∑i=g+1f∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1,where sg+1≤sg+2≤⋯≤sf and mg+1γg+1≥mg+2γg+2≥⋯≥mfγf (note that si and miγi (i=g+1,r+2,…,f) do not necessarily correspond to the same group).


### 6.4. Branch-and-Bound (B&B) Algorithm

The branch-and-bound (B&B) algorithm search follows a depth-first strategy; this algorithm assigns groups in a forward manner starting from the first position (assign a group to a node).


### 6.5. An Example for B&B Algorithm

Consider an example in which there are 13 jobs belonging to 5 groupsG1=J11,J12, G2=J21,J22,J23, G3=J31,J32,J33, G4=J41,J42, and G5=J51,J52,J53. The processing times of each job, learning rate, and setup time of each group and other parameters are shown in Tables 1 and 2.Table 1
Numerical parameters.
siαiβiγiui′G131211G251211G371211G441211G561211Table 2
Numerical parameters.
η=1J11J12J21J22J23J31J32J33J41J42J51J52J53pi,j4653547763285ai,j−0.16−0.21−0.22−0.12−0.24−0.23−0.32−0.31−0.15−0.17−0.19−0.2−0.26νi,j5476863425645From Algorithm3 (HA), the initial sequence is G1,G2,G4,G5,G3, and the objective function value (upper bound) is ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j=295.8274. According to Algorithm 4 (B&B algorithm), the following search tree can be obtained, which is represented by Figure 1. The numbers in Figure 1 represent the lower bound values, and G0 is defined as the level 0.Algorithm 3: HA.
(1)
Input:ki⟵ using equation (4) for i=1,2,…,f; the internal job sequence πi∗⟵ using Lemma 4 for each group Gi, i=1,2,…,f.(2)
Output: the suboptimal resource allocationui,j∗, suboptimal common flow allowance qi=, Ciki−1, and corresponding objective function value ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+, ∑i=1f∑j=1miνi,jui,j.3)
For eachπi∗, groups are scheduled by the nondecreasing order of si, i=1,2,…,f;(4)
For eachπi∗, groups are scheduled by the nonincreasing order of miγi, i=1,2,…,f;(5)
From Step 3 and Step 4, the smallest objective function value∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi, +∑i=1f∑j=1miνi,jui,j is selected as the original group sequence πG;(6)
Pick the two groups from the first and second position of the list of Step 5 and find the best sequence for these two groups by calculating∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j for the two possible sequences. Do not change the relative positions of these two groups with respect to each other in the remaining steps of the algorithm. Set i=3;(7)
Pick the group in theith position of the list generated in Step 5 and find the best sequence by placing it at all possible i positions in the partial sequence found in the previous step, without changing the relative positions to each other of the already assigned groups. The number of enumerations at this step equals i;(8)
Ifi>f, then stop(9)
Otherwise,(10)
i⟵i+1, and return to Step 7;(11)
Calculate the suboptimal resource allocationui,j∗ according to (5). Calculate the suboptimal common flow allowance qi=Ciki−1 and the corresponding optimal objective function ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j by using (7).Algorithm 4: B&B algorithm.
Step 1. Finding the upper bound: use Algorithm3 to obtain an initial solution for the problem.Step 2. Bounding: calculate the lower bound (see (8)) for the node. If the lower bound for an unfathomed partial schedule of groups is larger than or equal to the value of the objective function of the initial solution, eliminate the node and all the nodes following it in the branch. Calculate the objective function value of the completed schedule; if it is less than the initial solution, replace it as the new solution; otherwise, eliminate it.Step 3. Termination: continue until all nodes have been explored.Figure 1
Search tree of the B&B algorithm for the example (× denotes pruning).At level 1, i.e.,g=1, for group G1, from formula (8), the lower bound is(21)LBG1=2×1+3×1+3×1+3×1+2×1×3+3×1+3×1+3×1+2×1×4+3×1+3×1+2×1×5+3×1+2×1×6+2×1×7+2×2×2−11/2×4×51/2+2×3−11/2×3×61/2+2×3−21/2×5×7×2−0.221/2+2×3−11/2×3×71/2+2×3−21/2×6×4×2−0.231/2+2×3−11/2×6×21/2+2×3−21/2×5×5×2−0.261/2+2×2−11/2×2×61/2=279.8274.The calculation process of lower bounds of the remaining node is similar to that of this node. From Figure1, the optimal sequences are G1,G2,G4,G5,G3, G1,G2,G5,G4,G3, and G5,G1,G2,G4,G3, and the optimal value of objective function is ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j=295.8274.


### 6.6. Computational Experiments

An enumeration algorithm (i.e., Algorithm5), heuristic algorithm (i.e., Algorithm 3), TS algorithm (i.e., Algorithm 6), and B&B algorithm (i.e., Algorithm 4) were programmed in C++ and carried out on a CPU Intel Core i5-8250U 1.4 GHz PC with 8.00 GB RAM. The number of jobs and groups n=50,100,150,200 and f = 8, 9, 10, 11, 12 were tested, and each group must contain at least one job. The parameters setting can be obtained as follows: si, vi,j, αi,βi, and γi were drawn from a discrete uniform distribution in [1, 10]; pi,j were drawn from a discrete uniform distribution in [1, 100]; ai,j were drawn from a uniform distribution in [−0.1, −1]; and η=2. To avoid the contingency, each problem instance was conducted 20 times, setting the maximum CPU time per instance at 3600 seconds. The percentage relative error of the solution produced by Algorithms 3 and 6 is calculated as(22)ZAi−Z∗Z∗×100%,where i=4,5, ZAi, and Z∗ are the objective function values ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j generated by Algorithm 1 and Algorithm 4, respectively.Algorithm 5:Optimal solution for Case 3.
Step 1. Calculateki by using (4), i=1,2,…,f.Step 2. The jobs in each group are arranged according to the assignment problemAP (Lemma 4).Step 3. List all the group schedules.Step 4. For each group schedule, calculate the corresponding objective value∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j.Step 5. Comparing all the objective values∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the minimum one is optimal, and its corresponding schedule is the optimal sequence of the problem 1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j.Algorithm 6: TS.
Step 1. Let the tabu list be empty and the iteration number be zero.Step 2. Set the initial sequence of the TS algorithm, calculate its objective function, and set the current sequence as the best solutionπ∗.Step 3. Search the associated neighborhood of the current sequence and resolve if there is a sequenceπ∗∗ with the smallest objective function in associated neighborhood and it is not in the tabu list.Step 4. Ifπ∗∗ is better than π∗, then let π∗=π∗∗. Update the tabu list and the iteration number.Step 5. If there is not a sequence in associated neighborhood but it is not in the tabu list or the maximum number of iterations is reached, then output the final sequence. Otherwise, update tabu list and go to Step 3.On the other hand, “A3-CPU time (s)” (“A4-CPU time (s),” “A5-CPU time (s),” and “A6-(B&B) CPU time (s)”) as the running time of Algorithm5 (Algorithms 3–4) is defined. The results are summarized in Table 3. From Table 3, it is easy to find that the maximum relative error percentage of Algorithm 3 is less than 6.1% for n≤200, and performance of Algorithm 3 (i.e., the heuristic algorithm) performs very well in terms of the relative error percentages. Moreover, Table 3 shows that the mean CPU time (s) for the enumeration algorithm (i.e., Algorithm 5) is larger than the B&B algorithm (i.e., Algorithm 4).Table 3
Results of Algorithms.
A3-CPU time (s)A4 (HA)-CPU time (s)A5 (TS)-CPU time (s)A6 (B&B)-CPU time (s)Error percentage ofError percentage ofAlgorithm A4 (%)Algorithm A5 (%)nfMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMax83.9715.5820.0320.0910.0220.05227.38232.4222.5615.0719.97210.063928.36234.6520.0530.1230.0430.19439.02957.8751.3612.6225.96221.0445010104.129130.9940.0480.1210.0520.35442.34498.6730.9611.1427.65120.212111000.2211089.4810.0540.2820.1150.35291.898583.1311.2721.8314.03314.32112360036000.0610.8230.1330.491173.384875.4194.1126.0325.84128.40284.2298.2290.0340.0920.0330.19132.12539.0091.3712.6327.2849.792943.34550.8120.0320.1120.0420.19439.24545.6731.8541.9834.08230.12510010264.826406.5410.0440.2140.6510.42336.30469.6953.1143.8355.64123.164111997.84136000.0520.2920.6910.78466.647300.2132.8123.0514.91423.81512360036000.0760.6510.1460.802195.528893.5231.3431.6926.96121.57387.85119.3310.0330.1120.0340.41540.55449.0692.7813.7426.46220.744957.82589.0710.0430.2550.0470.32452.41782.5211.5611.95210.18439.16315010329.781497.3620.0450.2910.0660.694109.697209.8712.0522.9317.32219.972113193.32236000.0570.3310.0950.911159.225323.7453.1314.0526.91327.33112360036000.0710.9920.1390.684243.252904.0322.6633.0549.77128.324811.86132.8810.0420.2120.0470.30951.85969.6720.7811.5164.42118.714998.651122.3250.0470.2150.0590.57574.957194.6341.1811.8445.52122.60520010475.841779.5630.0510.4210.0670.688193.577488.5812.7243.1148.82116.34511360036000.0610.9850.1010.691296.335723.3161.6412.9546.60126.12512360036000.0791.4310.1390.704435.2291012.5321.7732.2658.22328.108


## 6.1. Heuristic Algorithm

From Lemma4, the optimal job sequence within the same group can be obtained, and the optimal resource allocation of a given schedule can be obtained by Lemma 3. In this subsection, we apply the well-known heuristic procedure from the study by Nawaz et al. [46], and the following heuristic algorithm can be proposed.


## 6.2. Tabu Search Algorithm

Tabu search (TS) algorithm is a metaheuristic algorithm first proposed by Glover [47]. In this subsection, tabu search (TS) is used to find a near-optimal solution (Xu et al. [48]). The initial sequence used in the TS algorithm is chosen by the nondecreasing order of si, and the maximum number of iterations for the TS algorithm is set at 100f, where f is the number of groups. As in the study by Wu et al. [49], the implementation of the TS algorithm is given as follows:


## 6.3. A Lower Bound

LetπG=πGS,πGU be a sequence of groups in which πGS is the scheduled part, and πGU is a unscheduled part. Assume that there are g groups in πGS; from (7), it is noticed that the terms,(19)∑i=g+1f∑h=ifmhγhsi,η1/η+1+η−η/η+1∑i=g+1f∑j=1ki−1αij+∑h=ifmhγh1/η+1νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑i=g+1f∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1,can be minimized by Lemmas 5–6. Hence, the lower bound can be obtained by the following formula:(20)LB=∑i=1g∑h=igmhγh+∑h=g+1fmhγhsi+∑i=g+1f∑h=ifmhγhsi+η1/η+1+η−η/η+1∑i=1g∑j=1ki−1αij+∑h=igmhγh+∑h=g+1fmhγh1/η+1×νi,jpi,jjai,jη/η+1+∑i=g+1f∑j=1ki−1αij+∑h=igmhγh+∑h=g+1fmhγh1/η+1×νi,jpi,jjai,jη/η+1+η1/η+1+η−η/η+1∑i=1g∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1+∑i=g+1f∑j=kimiβimi−j1/η+1νi,jpi,jjai,jη/η+1,where sg+1≤sg+2≤⋯≤sf and mg+1γg+1≥mg+2γg+2≥⋯≥mfγf (note that si and miγi (i=g+1,r+2,…,f) do not necessarily correspond to the same group).


## 6.4. Branch-and-Bound (B&B) Algorithm

The branch-and-bound (B&B) algorithm search follows a depth-first strategy; this algorithm assigns groups in a forward manner starting from the first position (assign a group to a node).


## 6.5. An Example for B&B Algorithm

Consider an example in which there are 13 jobs belonging to 5 groupsG1=J11,J12, G2=J21,J22,J23, G3=J31,J32,J33, G4=J41,J42, and G5=J51,J52,J53. The processing times of each job, learning rate, and setup time of each group and other parameters are shown in Tables 1 and 2.Table 1
Numerical parameters.
siαiβiγiui′G131211G251211G371211G441211G561211Table 2
Numerical parameters.
η=1J11J12J21J22J23J31J32J33J41J42J51J52J53pi,j4653547763285ai,j−0.16−0.21−0.22−0.12−0.24−0.23−0.32−0.31−0.15−0.17−0.19−0.2−0.26νi,j5476863425645From Algorithm3 (HA), the initial sequence is G1,G2,G4,G5,G3, and the objective function value (upper bound) is ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j=295.8274. According to Algorithm 4 (B&B algorithm), the following search tree can be obtained, which is represented by Figure 1. The numbers in Figure 1 represent the lower bound values, and G0 is defined as the level 0.Algorithm 3: HA.
(1)
Input:ki⟵ using equation (4) for i=1,2,…,f; the internal job sequence πi∗⟵ using Lemma 4 for each group Gi, i=1,2,…,f.(2)
Output: the suboptimal resource allocationui,j∗, suboptimal common flow allowance qi=, Ciki−1, and corresponding objective function value ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+, ∑i=1f∑j=1miνi,jui,j.3)
For eachπi∗, groups are scheduled by the nondecreasing order of si, i=1,2,…,f;(4)
For eachπi∗, groups are scheduled by the nonincreasing order of miγi, i=1,2,…,f;(5)
From Step 3 and Step 4, the smallest objective function value∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi, +∑i=1f∑j=1miνi,jui,j is selected as the original group sequence πG;(6)
Pick the two groups from the first and second position of the list of Step 5 and find the best sequence for these two groups by calculating∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j for the two possible sequences. Do not change the relative positions of these two groups with respect to each other in the remaining steps of the algorithm. Set i=3;(7)
Pick the group in theith position of the list generated in Step 5 and find the best sequence by placing it at all possible i positions in the partial sequence found in the previous step, without changing the relative positions to each other of the already assigned groups. The number of enumerations at this step equals i;(8)
Ifi>f, then stop(9)
Otherwise,(10)
i⟵i+1, and return to Step 7;(11)
Calculate the suboptimal resource allocationui,j∗ according to (5). Calculate the suboptimal common flow allowance qi=Ciki−1 and the corresponding optimal objective function ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j by using (7).Algorithm 4: B&B algorithm.
Step 1. Finding the upper bound: use Algorithm3 to obtain an initial solution for the problem.Step 2. Bounding: calculate the lower bound (see (8)) for the node. If the lower bound for an unfathomed partial schedule of groups is larger than or equal to the value of the objective function of the initial solution, eliminate the node and all the nodes following it in the branch. Calculate the objective function value of the completed schedule; if it is less than the initial solution, replace it as the new solution; otherwise, eliminate it.Step 3. Termination: continue until all nodes have been explored.Figure 1
Search tree of the B&B algorithm for the example (× denotes pruning).At level 1, i.e.,g=1, for group G1, from formula (8), the lower bound is(21)LBG1=2×1+3×1+3×1+3×1+2×1×3+3×1+3×1+3×1+2×1×4+3×1+3×1+2×1×5+3×1+2×1×6+2×1×7+2×2×2−11/2×4×51/2+2×3−11/2×3×61/2+2×3−21/2×5×7×2−0.221/2+2×3−11/2×3×71/2+2×3−21/2×6×4×2−0.231/2+2×3−11/2×6×21/2+2×3−21/2×5×5×2−0.261/2+2×2−11/2×2×61/2=279.8274.The calculation process of lower bounds of the remaining node is similar to that of this node. From Figure1, the optimal sequences are G1,G2,G4,G5,G3, G1,G2,G5,G4,G3, and G5,G1,G2,G4,G3, and the optimal value of objective function is ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j=295.8274.


## 6.6. Computational Experiments

An enumeration algorithm (i.e., Algorithm5), heuristic algorithm (i.e., Algorithm 3), TS algorithm (i.e., Algorithm 6), and B&B algorithm (i.e., Algorithm 4) were programmed in C++ and carried out on a CPU Intel Core i5-8250U 1.4 GHz PC with 8.00 GB RAM. The number of jobs and groups n=50,100,150,200 and f = 8, 9, 10, 11, 12 were tested, and each group must contain at least one job. The parameters setting can be obtained as follows: si, vi,j, αi,βi, and γi were drawn from a discrete uniform distribution in [1, 10]; pi,j were drawn from a discrete uniform distribution in [1, 100]; ai,j were drawn from a uniform distribution in [−0.1, −1]; and η=2. To avoid the contingency, each problem instance was conducted 20 times, setting the maximum CPU time per instance at 3600 seconds. The percentage relative error of the solution produced by Algorithms 3 and 6 is calculated as(22)ZAi−Z∗Z∗×100%,where i=4,5, ZAi, and Z∗ are the objective function values ∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j generated by Algorithm 1 and Algorithm 4, respectively.Algorithm 5:Optimal solution for Case 3.
Step 1. Calculateki by using (4), i=1,2,…,f.Step 2. The jobs in each group are arranged according to the assignment problemAP (Lemma 4).Step 3. List all the group schedules.Step 4. For each group schedule, calculate the corresponding objective value∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j.Step 5. Comparing all the objective values∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j, the minimum one is optimal, and its corresponding schedule is the optimal sequence of the problem 1GT,si,CRA,SLK∑i=1f∑j=1miαiEi,j+βiTi,j+γiqi+∑i=1f∑j=1miνi,jui,j.Algorithm 6: TS.
Step 1. Let the tabu list be empty and the iteration number be zero.Step 2. Set the initial sequence of the TS algorithm, calculate its objective function, and set the current sequence as the best solutionπ∗.Step 3. Search the associated neighborhood of the current sequence and resolve if there is a sequenceπ∗∗ with the smallest objective function in associated neighborhood and it is not in the tabu list.Step 4. Ifπ∗∗ is better than π∗, then let π∗=π∗∗. Update the tabu list and the iteration number.Step 5. If there is not a sequence in associated neighborhood but it is not in the tabu list or the maximum number of iterations is reached, then output the final sequence. Otherwise, update tabu list and go to Step 3.On the other hand, “A3-CPU time (s)” (“A4-CPU time (s),” “A5-CPU time (s),” and “A6-(B&B) CPU time (s)”) as the running time of Algorithm5 (Algorithms 3–4) is defined. The results are summarized in Table 3. From Table 3, it is easy to find that the maximum relative error percentage of Algorithm 3 is less than 6.1% for n≤200, and performance of Algorithm 3 (i.e., the heuristic algorithm) performs very well in terms of the relative error percentages. Moreover, Table 3 shows that the mean CPU time (s) for the enumeration algorithm (i.e., Algorithm 5) is larger than the B&B algorithm (i.e., Algorithm 4).Table 3
Results of Algorithms.
A3-CPU time (s)A4 (HA)-CPU time (s)A5 (TS)-CPU time (s)A6 (B&B)-CPU time (s)Error percentage ofError percentage ofAlgorithm A4 (%)Algorithm A5 (%)nfMeanMaxMeanMaxMeanMaxMeanMaxMeanMaxMeanMax83.9715.5820.0320.0910.0220.05227.38232.4222.5615.0719.97210.063928.36234.6520.0530.1230.0430.19439.02957.8751.3612.6225.96221.0445010104.129130.9940.0480.1210.0520.35442.34498.6730.9611.1427.65120.212111000.2211089.4810.0540.2820.1150.35291.898583.1311.2721.8314.03314.32112360036000.0610.8230.1330.491173.384875.4194.1126.0325.84128.40284.2298.2290.0340.0920.0330.19132.12539.0091.3712.6327.2849.792943.34550.8120.0320.1120.0420.19439.24545.6731.8541.9834.08230.12510010264.826406.5410.0440.2140.6510.42336.30469.6953.1143.8355.64123.164111997.84136000.0520.2920.6910.78466.647300.2132.8123.0514.91423.81512360036000.0760.6510.1460.802195.528893.5231.3431.6926.96121.57387.85119.3310.0330.1120.0340.41540.55449.0692.7813.7426.46220.744957.82589.0710.0430.2550.0470.32452.41782.5211.5611.95210.18439.16315010329.781497.3620.0450.2910.0660.694109.697209.8712.0522.9317.32219.972113193.32236000.0570.3310.0950.911159.225323.7453.1314.0526.91327.33112360036000.0710.9920.1390.684243.252904.0322.6633.0549.77128.324811.86132.8810.0420.2120.0470.30951.85969.6720.7811.5164.42118.714998.651122.3250.0470.2150.0590.57574.957194.6341.1811.8445.52122.60520010475.841779.5630.0510.4210.0670.688193.577488.5812.7243.1148.82116.34511360036000.0610.9850.1010.691296.335723.3161.6412.9546.60126.12512360036000.0791.4310.1390.704435.2291012.5321.7732.2658.22328.108


## 7. Conclusions

In this paper, we studied the single-machine resource allocation scheduling problem with learning effect and group technology. The goal is to determine the optimal sequence of jobs and groups, the optimal common flow allowances, and the optimal resource allocation such that the weighted sum of the scheduling cost and the resource allocation cost is minimized. For some special cases (i.e., casessi≤sh⟹miγi≥mhγh, si=s,miγi=mγ¯, and f is a given constant), it was shown that the problem can be solved in polynomial time. For the general case of the problem, the heuristic, tabu search, and B&B algorithms were proposed. The results show that the maximum relative percentage error of the proposed heuristic algorithm (i.e., Algorithm 3) from optimal solutions is less than 6.1% for all sizes of instances.Further research may focus on the extensions of this model to more complicated machine setting (such as flow shop and/or parallel machines) or study other nonregular objective functions (such as due-window assignment scheduling problems with position-dependent weights, see the study by Wang et al. [50]).



---

*Source: 6615824-2021-03-03.xml*