# Parallel-Machine Scheduling with DeJong’s Learning Effect, Delivery Times, Rate-Modifying Activity, and Resource Allocation

Authors: Li Sun; Bin Wu; Lei Ning
Journal: Shock and Vibration
 (2021)

---

## Abstract

We investigate parallel-machine scheduling with past-sequence-dependent (p-s-d) delivery times, DeJong’s learning effect, rate-modifying activity, and resource allocation. Each machine has a rate-modifying activity. We consider two versions of the problem to minimize the sum of the total completion times, the total absolute deviation of job completion times, and the total resource allocation and the sum of the total waiting times, the total absolute deviation of job waiting times, and the total resource allocation, respectively. The problems under our present model can be solved in polynomial time.


---

## Body

## 1. Introduction

In practice, a finite amount of resource usually is allocated to a job to control its actual processing, which is the so-called scheduling problem with controllable processing times. Researchers in this case have to make two decisions−job sequence and resource allocation simultaneously−which is different from common scheduling problems. These kinds of scheduling problems have attracted a great deal of attention in the last three decades since Vickson. Vickson [1] initiated this field. The resource allocation function usually has two forms including a linear function and a convex function. Liu and Feng [2] address two-machine flowshop scheduling problems in which the processing time of a job is a function of its position in the sequence and its resource allocation. Zhu et al. [3]investigate scheduling problems with a deteriorating and resource-dependent maintenance activity. They show that all the considered problems are polynomially solvable. Liu et al. [4] consider a parallel-machine scheduling problem to minimize the sum of resource consumption and outsourcing cost. Liu et al. [5] consider single-machine scheduling problems which determine the optimal job schedule, due-window location, and resource allocation simultaneously.In industrial production, machine unavailability periods are very common which is first studied by Lee and Leon. [6]. Motivated by this phenomenon, scheduling with a rate-modifying activity becomes a popular topic in the last decade. Zhu et al. [7] addresses a single-machine scheduling problem with resource allocation and a rate-modifying activity simultaneously. Ji et al. [8] consider single-machine scheduling with a common due-window and a deteriorating rate-modifying activity. Polynomial-time solution algorithms are provided for the corresponding problems. Yang and Yang [9] investigate parallel-machine scheduling problems with multiple rate-modifying activities. Zhu et al. [3] study single-machine scheduling problems with a deteriorating and resource-dependent maintenance activity. Luo [10] addresses a single-machine scheduling problem with a deteriorating rate-modifying activity to minimize the number of tardy jobs. He proposed an optimal polynomial time algorithm. Yu [11] considers an optimal single-machine scheduling with linear deterioration rate and rate-modifying activities.In modern industry, the manufacturing environment has a great impact onjobs′ processing times. Such an extra time for eliminating the adverse effects between the main processing and the delivery of a job is viewed as a past-sequence-dependent (p-s-d) delivery time. Koulamas and Kyparisis [12] first introduced p-s-d delivery time into scheduling problem. Liu et al. [13] considered the problem of single-machine scheduling with p-s-d delivery times, which was introduced in Koulamas and Kyparisis [12]. Liu [14] introduced identical parallel-machine scheduling with p-s-d delivery times and the learning effect. Shen and Wu [15] studied single-machine scheduling with p-s-d delivery times and general learning effects.The workers can acquire experience and improve the production efficiency continuously, and this phenomenon−first discussed by Wright [16]−is called the learning effect in the literature [17]. Wu et al. [18] study some single-machine scheduling problems with elapsed-time-based and position-based learning and forgetting effects. More recent papers that consider scheduling with learning effect include Rostami et al. [19], Zhang et al. [20], Yin et al. [21], Zhang and Wang [22], Toksari and Arik [23], Jiang et al. [24], Cheng et al. [25], Pei et al. [26], Mustu and Eren [27], and Liu and Feng. [2]. The above scheduling model with the position-based learning effect suffers a drawback that job’s actual processing time is close to zero when the job’s position is sufficiently large in a schedule. Scheduling problem with DeJong’s learning effect is proposed, which overcomes the shortcomings in Wright’s learning model. Okoowski and Gawiejnowicz [28] consider a parallel-machine scheduling problem with DeJong’s learning effect and makespan objective. Ji et al. [29] consider a learning model in scheduling based on DeJong’s learning effect. Ji et al. [30] consider parallel-machine scheduling with deteriorating jobs and DeJong’s learning effect. They show minimizing the total completion time is polynomially solvable and minimizing the makespan is NP-hard. Throughout the paper, we will consider parallel-machine scheduling problem with DeJong’s learning effect.Scheduling problems concerning multimachine production environments are encountered in many modern manufacturing processes. To the best of our knowledge, scheduling with p-s-d delivery times, DeJong’s learning effect, rate-modifying activity, and resource allocation has not been studied in the literature. In this paper, we study two versions of such problems under linear and convex resource consumption and show the problems are polynomially solvable. The remaining part of this paper is organized as follows. In Section2, we formulate the problem and present some notation and one lemma. We introduce two versions of the problem to minimize the sum of the total completion times, the total absolute deviation of job completion times, and the total resource allocation and the sum of the total waiting times, the total absolute deviation of job waiting times, and the total resource allocation in Section 3. In Section 4, we conclude the paper.


## 2. Problem Formulation

There are a set ofn independent and non-pre-emptive jobs simultaneously available for processing and m identical parallel machines. Each machine can handle one job at a time. With the assumption that m<n throughout the paper, since the problem is trivial, if m≥n, let pijpijA be the normal (actual) processing time of job Jij and pirpirA be the normal (actual) processing time of job Jir if it is scheduled in the rth position on machine Mi in a sequence. In view of the study of DeJong’s learning model for scheduling, we adopt it in our paper as follows: pirA=pirM+1−Mrair, where air is a nonpositive learning index and air<0. It is easy to know that if M=0, the model reduces to the classical learning model.In this paper, we will consider the situation of repairing or upgrading the machine that one rate-modifying activity is allowed on each machine throughout the scheduling to improve the machines production efficiency which is denoted by RMA. A rate-modifying activity (RMA) can be applied to the machine so as to change (usually to decrease) the normal processing times of the jobs. The timepij of processing job Jij changes after the RMA to λijpij. The machine will revert to its initial condition, and the learning effect will start anew after the rate-modifying activity. Suppose ni is the number of jobs located on machine Mi and ki is the position of the rate-modifying activity on machine Mi. In this paper, we consider two resource consumption functions.A linear resource consumption function:(1)pirA=pirM+1−Mrair−biruir,before rate-modifying activity and(2)pirA=λirpirM+1−Mr−kiair−biruir,after rate-modifying activity, where λir is the modifying rate to job Jir with 0<λir≤1, uir is the amount of the resource allocated to job Jir with 0≤uir≤u¯ir<λirpir/bir, and bir is the positive compression rate of job Jir.A convex resource consumption function:(3)pirA=pirM+1−Mrairuirv,before rate-modifying activity and(4)pirA=λirpirM+1−Mr−kiairuirv,after rate-modifying activity, where v is a positive constant. The rate-modifying activity duration is a linear function of its starting time which is represented by ft=β+σt, where β>0 is the basic rate-modifying activity time, σ>0 is a rate-modifying activity factor, and t is the starting time of the rate-modifying activity operation. The starting time of the rate-modifying activity is not known in advance, and it can be scheduled immediately after completing the processing of any job.As in [12], the processing of job Jir must be followed by the p-s-d delivery time qir, which can be calculated as(5)qi1=0,qir=γWir=γ∑l=1r−1pilA,before rate-modifying activity and(6)qir=γWir=γ∑l=1r−1pilA+ft,after rate-modifying activity, where γ≥0 is a normalizing constant and Wir denotes the waiting time of job Jir. As usual, the postprocessing operation of any job Jil modelled by its delivery time qil is performed off-line. Hence, it is not affected by the availability of the machine, and it can be implemented immediately upon completion of the main operation, and we have(7)Ci1=pi1,Cij=Wij+pijA+qij=1+γWij+pijA,where Cij denotes the completion time of job Jij.Let denote the p-s-d delivery time byqpsd. In addition, we denote TADCi the total absolute deviation of job completion times and TADWi the total absolute deviation of job waiting times on machine Mi, i.e., TADCi=∑l=1ni∑k=lniCil−Cik and TADWi=∑l=1ni∑k=lniWil−Wik. Let TCi indicates the job’s total processing times on machine Mi and TWi indicates the job’s total waiting times on machine Mi, i.e., TCi=∑r=lniCir and TWi=∑r=lniWir. We will try to find the optimal job sequence, the optimal RMA, and the optimal resource consumption such that the following cost functions are minimized:(8)Z1=α1∑i=1mTCi+δ1∑i=1mTADCi+∑i=1m∑j=1niGijuij,Z2=α2∑i=1mTWi+δ2∑i=1mTADWi+∑i=1m∑j=1niGijuij,where α1,α2,δ1,δ2>0 represent the per unit time contribution for the total processing time, the total waiting time, the total absolute deviation of job completion times, and the total absolute deviation of job waiting times on machine Mi with α1>0, α2>0, δ1>0, and δ2>0. Gij is the per unit time cost associated with resource allocation. Let DJLR denote DeJong’s learning effect and linear resource consumption and DJCR denote DeJong’s learning effect and convex resource consumption. Using the three-field notation introduced by Graham et al., for scheduling problems, we denote the two versions of the problems as(9)Pmqpsd,DJLR,RMAZ,Pmqpsd,DJCR,RMAZ,Z∈Z1,Z2.We first present some notation and one lemma before the main results. On machineMi, if the number of jobs ni and the position of the job preceding the rate-modifying activity ki are known in advance, then the job’s completion times and the job’s waiting times on machine Mi are as follows:(10)Wi1=0,Ci1=pi1A,…,Wiki=pi1A+⋯+piki−1A,Ciki=1+γpi1A+pi2A+⋯+piki−1A+pikiA,ft=β+σpi1A+pi2A+⋯+pikiA,Wiki+1=β+1+σpi1A+⋯+pikiA,Ciki+1=1+γβ+1+σpi1A+⋯+pikiA+piki+1A,…,Wini=β+1+σpi1A+⋯+pikiA+piki+1A…+pini−1A,Cini=1+γβ+1+σpi1A+⋯+pikiA+piki+1A+⋯+pini−1A+piniA.For the linear case,(11)pirA=pirM+1−Mrair−biruir,ifr≤ki,pirA=λirpirM+1−Mr−kiair−biruir,ifr≥ki.For the convex case,(12)pirA=pirM+1−Mrairuirv,ifr≤ki,pirA=λirpirM+1−Mr−kiairuirv,ifr≥ki.LetPn,m,k=n1,n2,…,nm;k1,k2,…,km denote an allocation vector. We provide a lemma concerning an upper bound on the number of Pn,m,k vectors.Lemma 1.
The number ofPn,m,k vectors is bounded from above by n+12m−1/m!.Proof.
See the work of Ma et al. [31].


## 3. Cases with Linear Resource Consumption Function

### 3.1. The ProblemPmqpsd,DJLR,RMAZ1

In this section, we introduce the problem to minimize the sum of total completion times and total absolute deviation of job completion times with resource consumption on all the machines. For machineMi, from the above analysis, we calculate the total completion times and the total absolute deviation of job completion times on this machine as follows:(13)TCi=ni−ki1+γβ+∑h=1ki1+ki−h1+γ+ni−ki1+γ1+σpihA+∑h=ki+1ni1+ni−h1+γpihA,TADCi=∑h=ki+1ni2h−1−ni1+γβ+∑h=1ki2h−1−ni+∑l=h+1ki2l−1−ni1+γ+∑l=ki+1ni2l−1−ni1+γ1+σpihA+∑h=ki+1ni−12h−1−ni+∑l=h+1ni2l−1−ni1+γpihA+ni−1piniA.Hence, the sum of total completion times and total absolute deviation of job completion times with resource consumption on all the machines is(14)α1∑i=1mTCi+δ1∑i=1mTADCi+∑i=1m∑j=1niGijuij=1+γβ∑i=1mα1ni−ki+∑i=1m∑h=ki+1niδ12h−1−ni+∑i=1m∑h=1kiα11+ki−h1+γ+ni−ki1+γ1+σ+δ12h−1−ni+∑l=h+1ki2l−1−ni1+γ+∑l=ki+1ni2l−1−ni1+γ1+σpihA+∑i=1m∑h=ki+1niα11+1+γni−h+δ12h−1−ni+∑l=h+1ni2l−1−ni1+γpihA+∑i=1mα1+ni−1δ1piniA+∑i=1m∑h=1niGihuih.Let(15)A1=1+γβ∑i=1mα1ni−ki+∑i=1m∑h=ki+1niδ12h−1−ni,wih=α11+ki−h1+γ+ni−ki1+γ1+σ+δ12h−1−ni+∑l=h+1ki2l−1−ni1+γ+∑l=ki+1ni2l−1−ni1+γ1+σ,i=1,2,…,m,h=1,2,…,ki,α11+1+γni−h+δ12h−1−ni+∑l=h+1ni2l−1−ni1+γ,i=1,2,…,m,h=ki+1,ki+2,…,ni−1,α1+ni−1δ1i=1,2,…,m,h=ni.Thus,(16)α1∑i=1mTCi+δ1∑i=1mTADCi+∑i=1m∑j=1niGijuij=A1+∑i=1m∑h=1kiwihpihM+1−Mhaih+∑i=1m∑h=ki+1niwihλihpihM+1−Mh−kiaih+∑i=1m∑h=1niGih−wihbihuih.From the above equation, for any job sequence, the optimal resource allocation for a job depends on the sign ofGih−wihbih. If Gih−wihbih is negative, the maximum feasible amount of the resource should be allocated to job Jih, if Gih−wihbih is positive, no resource should be allocated to job Jih, and if Gih−wihbih is equal to zero, any of value of resource consumption will not affect the total cost. Let uih∗ denote the optimal resource allocation for job Jih, where(17)uih=u¯ih,ifGih−wihbih<0,u0∈0,u¯ih,ifGih−wihbih=0,0,ifGih−wihbih>0.From (17), we can obtain the optimal resource allocation for any given optimal sequence.SinceA1 is a constant, when ni and ki is given, we can express the problem as the following assignment problem:(18)F1=A1+min∑i=1m∑j=1n∑h=1niθijhxijh,AP1s.t.∑j=1nxijh=1,i=1,2,…,m,h=1,2,…,ni,∑i=1m∑h=1nixijh=1,j=1,2,…,n,xijh=0or1,i=1,2,…,m,h=1,2,…,ni,j=1,2,…,n,where(19)θijh=wihpijh+Gij−wihbiju¯ij,ifGij−wihbij<0,wihp¯ijh,ifGij−wihbij≥0,pijh=pijM+1−Mhaij,i=1,2,…,m,j=1,2,…,n,h=1,2,…,ki,λijpijM+1−Mh−kiaij,i=1,2,…,m,j=1,2,…,n,h=ki+1,ki+2,…,ni.Consequently, whenPn,m,k vector is given, optimal job scheduling and optimal resource allocation are given by Algorithm 1.Algorithm 1: Algorithm to solve the problem of minimizing the sum of total completion times and total absolute deviation of job completion times with linear resource consumption.
Step 1: jobs are scheduled byAP1Step 2: optimal job resource allocation is calculated by formula (17)Since thePn,m,k vector is given, we know that the problem can be solved in On3 time. Together with Lemma 1, it is easy to obtain the following theorem.Theorem 1.
The problemPmqpsd,DJLR,RMAZ1 can be solved in On2m+2 time.


### 3.2. The ProblemPmqpsd,DJLR,RMAZ2

In this section, we study the problem to minimize the sum of total waiting times and total absolute deviation of job waiting times with resource consumption on all the machines. For machineMi, we compute the total waiting times and the total absolute deviation of job waiting times on this machine as follows:(20)TWi=ni−kiβ+∑h=1kini−ki1+σ+ki−hpihA+∑h=ki+1nini−hpihA,TADWi=ki−1ni−kiβ+∑h=1kiki−hni−kiσ+h−1ki−h+ni−ki1+σpihA+∑h=ki+1nikini−hpihA.Hence, the sum of total waiting times and total absolute deviation of job waiting times with resource consumption on all the machines is(21)α2∑i=1mTWi+δ2∑i=1mTADWi+∑i=1m∑j=1niGijuij=∑i=1mα2+ki−1δ2ni−kiβ+∑i=1m∑h=1kiα2ni−ki1+σ+ki−h+δ2ki−hni−kiσ+h−1ki−h+ni−ki1+σpihA+∑i=1m∑h=ki+1niα2+kiδ2ni−hpihA+∑i=1m∑h=1niGihuih.Let(22)A2=∑i=1mα2+ki−1δ2ni−kiβ,φih=α2ni−ki1+σ+ki−h+δ2ki−hni−kiσ+h−1ki−h+ni−ki1+σ,i=1,2,…,m,h=1,2,…,ki,α2+kiδ2ni−h,i=1,2,…,m,h=ki+1,ki+2,…,ni.Thus,(23)α2∑i=1mTWi+δ2∑i=1mTADWi+∑i=1m∑j=1niGijuij=A2+∑i=1m∑h=1kiφihpihM+1−Mhaih+∑i=1m∑h=ki+1niλihφihpihM+1−Mh−kiaih+∑i=1m∑h=1niGih−φihbihuih.For any job sequence, the optimal resource allocation for a job depends on the sign ofGih−φihbih. Let uih∗ denote the optimal resource allocation for job Jih, where(24)uih=u¯ih,ifGih−φihbih<0,u0∈0,u¯ih,ifGih−φihbih=0,0,ifGih−φihbih>0.From (24), we can get the optimal resource allocation for any given optimal sequence.Accordingly, whenni and ki is given, we can indicate the problem as the following assignment problem:(25)F2=A2+min∑i=1m∑j=1n∑h=1niρijhyijh,AP2s.t.∑j=1nyijh=1,i=1,2,…,m,h=1,2,…,ni,∑i=1m∑h=1niyijh=1,j=1,2,…,n,yijh=0or1,i=1,2,…,m,h=1,2,…,ni,j=1,2,…,n,where(26)ρijh=φihpijh+Gij−φihbiju¯ij,ifGij−φihbij<0,φihpijh,ifGij−φihbij≥0,pijh=pijM+1−Mhaij,i=1,2,…,m,j=1,2,…,n,h=1,2,…,ki,λijpijM+1−Mh−kiaij,i=1,2,…,m,j=1,2,…,n,h=ki+1,ki+2,…,ni.Hence, whenPn,m,k vector is given, optimal job scheduling and optimal resource allocation are given by Algorithm 2.Algorithm 2: Algorithm to solve the problem of minimizing the sum of total waiting times and total absolute deviation of job waiting times with linear resource consumption.
Step 1: jobs are scheduled byAP2Step 2: optimal job resource allocation is calculated by formula (24)Thus, when thePn,m,k vector is given, the problem can be solved in On3 time. Together with Lemma 1, we have the following theorem.Theorem 2.
The problemPmqpsd,DJLR,RMAZ2 can be solved in On2m+2 time.


## 3.1. The ProblemPmqpsd,DJLR,RMAZ1

In this section, we introduce the problem to minimize the sum of total completion times and total absolute deviation of job completion times with resource consumption on all the machines. For machineMi, from the above analysis, we calculate the total completion times and the total absolute deviation of job completion times on this machine as follows:(13)TCi=ni−ki1+γβ+∑h=1ki1+ki−h1+γ+ni−ki1+γ1+σpihA+∑h=ki+1ni1+ni−h1+γpihA,TADCi=∑h=ki+1ni2h−1−ni1+γβ+∑h=1ki2h−1−ni+∑l=h+1ki2l−1−ni1+γ+∑l=ki+1ni2l−1−ni1+γ1+σpihA+∑h=ki+1ni−12h−1−ni+∑l=h+1ni2l−1−ni1+γpihA+ni−1piniA.Hence, the sum of total completion times and total absolute deviation of job completion times with resource consumption on all the machines is(14)α1∑i=1mTCi+δ1∑i=1mTADCi+∑i=1m∑j=1niGijuij=1+γβ∑i=1mα1ni−ki+∑i=1m∑h=ki+1niδ12h−1−ni+∑i=1m∑h=1kiα11+ki−h1+γ+ni−ki1+γ1+σ+δ12h−1−ni+∑l=h+1ki2l−1−ni1+γ+∑l=ki+1ni2l−1−ni1+γ1+σpihA+∑i=1m∑h=ki+1niα11+1+γni−h+δ12h−1−ni+∑l=h+1ni2l−1−ni1+γpihA+∑i=1mα1+ni−1δ1piniA+∑i=1m∑h=1niGihuih.Let(15)A1=1+γβ∑i=1mα1ni−ki+∑i=1m∑h=ki+1niδ12h−1−ni,wih=α11+ki−h1+γ+ni−ki1+γ1+σ+δ12h−1−ni+∑l=h+1ki2l−1−ni1+γ+∑l=ki+1ni2l−1−ni1+γ1+σ,i=1,2,…,m,h=1,2,…,ki,α11+1+γni−h+δ12h−1−ni+∑l=h+1ni2l−1−ni1+γ,i=1,2,…,m,h=ki+1,ki+2,…,ni−1,α1+ni−1δ1i=1,2,…,m,h=ni.Thus,(16)α1∑i=1mTCi+δ1∑i=1mTADCi+∑i=1m∑j=1niGijuij=A1+∑i=1m∑h=1kiwihpihM+1−Mhaih+∑i=1m∑h=ki+1niwihλihpihM+1−Mh−kiaih+∑i=1m∑h=1niGih−wihbihuih.From the above equation, for any job sequence, the optimal resource allocation for a job depends on the sign ofGih−wihbih. If Gih−wihbih is negative, the maximum feasible amount of the resource should be allocated to job Jih, if Gih−wihbih is positive, no resource should be allocated to job Jih, and if Gih−wihbih is equal to zero, any of value of resource consumption will not affect the total cost. Let uih∗ denote the optimal resource allocation for job Jih, where(17)uih=u¯ih,ifGih−wihbih<0,u0∈0,u¯ih,ifGih−wihbih=0,0,ifGih−wihbih>0.From (17), we can obtain the optimal resource allocation for any given optimal sequence.SinceA1 is a constant, when ni and ki is given, we can express the problem as the following assignment problem:(18)F1=A1+min∑i=1m∑j=1n∑h=1niθijhxijh,AP1s.t.∑j=1nxijh=1,i=1,2,…,m,h=1,2,…,ni,∑i=1m∑h=1nixijh=1,j=1,2,…,n,xijh=0or1,i=1,2,…,m,h=1,2,…,ni,j=1,2,…,n,where(19)θijh=wihpijh+Gij−wihbiju¯ij,ifGij−wihbij<0,wihp¯ijh,ifGij−wihbij≥0,pijh=pijM+1−Mhaij,i=1,2,…,m,j=1,2,…,n,h=1,2,…,ki,λijpijM+1−Mh−kiaij,i=1,2,…,m,j=1,2,…,n,h=ki+1,ki+2,…,ni.Consequently, whenPn,m,k vector is given, optimal job scheduling and optimal resource allocation are given by Algorithm 1.Algorithm 1: Algorithm to solve the problem of minimizing the sum of total completion times and total absolute deviation of job completion times with linear resource consumption.
Step 1: jobs are scheduled byAP1Step 2: optimal job resource allocation is calculated by formula (17)Since thePn,m,k vector is given, we know that the problem can be solved in On3 time. Together with Lemma 1, it is easy to obtain the following theorem.Theorem 1.
The problemPmqpsd,DJLR,RMAZ1 can be solved in On2m+2 time.


## 3.2. The ProblemPmqpsd,DJLR,RMAZ2

In this section, we study the problem to minimize the sum of total waiting times and total absolute deviation of job waiting times with resource consumption on all the machines. For machineMi, we compute the total waiting times and the total absolute deviation of job waiting times on this machine as follows:(20)TWi=ni−kiβ+∑h=1kini−ki1+σ+ki−hpihA+∑h=ki+1nini−hpihA,TADWi=ki−1ni−kiβ+∑h=1kiki−hni−kiσ+h−1ki−h+ni−ki1+σpihA+∑h=ki+1nikini−hpihA.Hence, the sum of total waiting times and total absolute deviation of job waiting times with resource consumption on all the machines is(21)α2∑i=1mTWi+δ2∑i=1mTADWi+∑i=1m∑j=1niGijuij=∑i=1mα2+ki−1δ2ni−kiβ+∑i=1m∑h=1kiα2ni−ki1+σ+ki−h+δ2ki−hni−kiσ+h−1ki−h+ni−ki1+σpihA+∑i=1m∑h=ki+1niα2+kiδ2ni−hpihA+∑i=1m∑h=1niGihuih.Let(22)A2=∑i=1mα2+ki−1δ2ni−kiβ,φih=α2ni−ki1+σ+ki−h+δ2ki−hni−kiσ+h−1ki−h+ni−ki1+σ,i=1,2,…,m,h=1,2,…,ki,α2+kiδ2ni−h,i=1,2,…,m,h=ki+1,ki+2,…,ni.Thus,(23)α2∑i=1mTWi+δ2∑i=1mTADWi+∑i=1m∑j=1niGijuij=A2+∑i=1m∑h=1kiφihpihM+1−Mhaih+∑i=1m∑h=ki+1niλihφihpihM+1−Mh−kiaih+∑i=1m∑h=1niGih−φihbihuih.For any job sequence, the optimal resource allocation for a job depends on the sign ofGih−φihbih. Let uih∗ denote the optimal resource allocation for job Jih, where(24)uih=u¯ih,ifGih−φihbih<0,u0∈0,u¯ih,ifGih−φihbih=0,0,ifGih−φihbih>0.From (24), we can get the optimal resource allocation for any given optimal sequence.Accordingly, whenni and ki is given, we can indicate the problem as the following assignment problem:(25)F2=A2+min∑i=1m∑j=1n∑h=1niρijhyijh,AP2s.t.∑j=1nyijh=1,i=1,2,…,m,h=1,2,…,ni,∑i=1m∑h=1niyijh=1,j=1,2,…,n,yijh=0or1,i=1,2,…,m,h=1,2,…,ni,j=1,2,…,n,where(26)ρijh=φihpijh+Gij−φihbiju¯ij,ifGij−φihbij<0,φihpijh,ifGij−φihbij≥0,pijh=pijM+1−Mhaij,i=1,2,…,m,j=1,2,…,n,h=1,2,…,ki,λijpijM+1−Mh−kiaij,i=1,2,…,m,j=1,2,…,n,h=ki+1,ki+2,…,ni.Hence, whenPn,m,k vector is given, optimal job scheduling and optimal resource allocation are given by Algorithm 2.Algorithm 2: Algorithm to solve the problem of minimizing the sum of total waiting times and total absolute deviation of job waiting times with linear resource consumption.
Step 1: jobs are scheduled byAP2Step 2: optimal job resource allocation is calculated by formula (24)Thus, when thePn,m,k vector is given, the problem can be solved in On3 time. Together with Lemma 1, we have the following theorem.Theorem 2.
The problemPmqpsd,DJLR,RMAZ2 can be solved in On2m+2 time.


## 4. Cases with Convex Resource Consumption Function

In this section, we will consider the problems under convex resource consumption function, i.e.,(27)Pmqpsd,DJCR,RMAZ,Z∈Z1,Z2.Let(28)p¯ih=pihM+1−Mhaih,i=1,2,…,m,h=1,2,…,ki,λihpihM+1−Mh−kiaih,i=1,2,…,m,h=ki+1,ki+2,…,ni.Similar to the analysis of problemPmqpsd,DJLR,RMAZ1, if ni and ki is given, we calculate the problem to minimize the sum of total completion times and total absolute deviation of job completion times with convex resource consumption as follows:(29)H1=α1∑i=1mTCi+δ1∑i=1mTADCi+∑i=1m∑j=1niGijuij=A1+∑i=1m∑h=1niwihp¯ihuihv+∑i=1m∑h=1niGihuih,where(30)A1=1+γβ∑i=1mα1ni−ki+∑i=1m∑h=ki+1niδ12h−1−ni,wih=α11+ki−h1+γ+ni−ki1+γ1+σ+δ12h−1−ni+∑l=h+1ki2l−1−ni1+γ+∑l=ki+1ni2l−1−ni1+γ1+σ,i=1,2,…,m,h=1,2,…,ki,α11+1+γni−h+δ12h−1−ni+∑l=h+1ni2l−1−ni1+γ,i=1,2,…,m,h=ki+1,ki+2,…,ni−1,α1+ni−1δ1,i=1,2,…,m,h=ni.By taking the first derivative ofH1 with respect to uih, i=1,2,…,m and h=1,2,…,ni, equating the result to zero, and solving it for uih, we can obtain the optimal resource allocation (denoted by uih∗):(31)∂H1∂uih=−vwihp¯ihvuih−v−1+Gih=0,uih∗=vwihGih1/v+1p¯ihv/v+1.By substitutinguih∗ into the objective function H1, we obtain a new unified expression as follows:(32)H1=A1+∑i=1m∑h=1niv−v/v+1+v1/v+1wih1/v+1Gihp¯ihv/v+1.Therefore, we can formulate the minimum problem as the following assignment problem:(33)H1=A1+min∑i=1m∑j=1n∑h=1niξijhx¯ijh,AP3s.t.∑j=1nx¯ijh=1,i=1,2,…,m,h=1,2,…,ni,∑i=1m∑h=1nix¯ijh=1,j=1,2,…,n,x¯ijh=0or1,i=1,2,…,m,h=1,2,…,ni,j=1,2,…,n,where(34)ξijh=v−v/v+1+v1/v+1wih1/v+1GijpijM+1−Mhaijv/v+1,i=1,2,…,m,j=1,2,…,n,h=1,2,…,ki,v−v/v+1+v1/v+1wih1/v+1GijλijpijM+1−Mh−kiaijv/v+1,i=1,2,…,m,j=1,2,…,n,h=ki+1,ki+2,…,ni.Consequently, whenPn,m,k vector is given, optimal job scheduling and optimal resource allocation are given by Algorithm 3.Algorithm 3: Algorithm to solve the problem of minimizing the sum of total completion times and total absolute deviation of job completion times with convex resource consumption.
Step 1: jobs are scheduled byAP3Step 2: optimal job resource allocation is calculated by formula (31)Together with Lemma1, we have the following theorem.Theorem 3.
The problemPmqpsd,DJCR,RMAZ1 can be solved in On2m+2 time.Similar to the analysis of problemPmqpsd,DJLR,RMAα2∑i=1mTWi+δ2∑i=1mTADWi+∑i=1m∑j=1niGijuij, if ni and ki is given, we calculate the problem to minimize the sum of total waiting times and total absolute deviation of job waiting times with convex resource consumption as follows:(35)H2=α2∑i=1mTWi+δ2∑i=1mTADWi+∑i=1m∑j=1niGijuij=A2+∑i=1m∑h=1niφihp¯ihuihv+∑i=1m∑h=1niGihuih,where(36)A2=∑i=1mα2+ki−1δ2ni−kiβ,φih=α2ni−ki1+σ+ki−h+δ2ki−hni−kiσ+h−1ki−h+ni−ki1+σ,i=1,2,…,m,h=1,2,…,ki,α2+kiδ2ni−h,i=1,2,…,m,h=ki+1,ki+2,…,ni,p¯ih=pihM+1−Mhaih,i=1,2,…,m,h=1,2,…,ki,λihpihM+1−Mh−kiaih,i=1,2,…,m,h=ki+1,ki+2,…,ni.Hence, taking the first derivative ofH2 with respect to uih, i=1,2,…,m and h=1,2,…,ni, equating the result to zero, and solving it for uih, we can obtain the optimal resource allocation (denoted by uih∗):(37)∂H2∂uih=−vφihp¯ihvuih−v−1+Gih=0,uih∗=vφihGih1/v+1p¯ihv/v+1.By substitutinguih∗ into the objective function H2, we obtain a new unified expression as follows:(38)H2=A2+∑i=1m∑h=1niv−v/v+1+v1/v+1φih1/v+1Gihp¯ihv/v+1.Therefore, we can formulate the minimum problem as the following assignment problem:(39)H2=A2+min∑i=1m∑j=1n∑h=1niηijhy¯ijh,AP4s.t.∑j=1ny¯ijh=1,i=1,2,…,m,h=1,2,…,ni,∑i=1m∑h=1niy¯ijh=1,j=1,2,…,n,y¯ijh=0or1,i=1,2,…,m,h=1,2,…,ni,j=1,2,…,n,where(40)ηijh=v−v/v+1+v1/v+1φih1/v+1GijpijM+1−Mhaijv/v+1,i=1,2,…,m,j=1,2,…,n,h=1,2,…,ki,v−v/v+1+v1/v+1φih1/v+1GijλijpijM+1−Mh−kiaijv/v+1,i=1,2,…,m,j=1,2,…,n,h=ki+1,ki+2,…,ni.Therefore, whenPn,m,k vector is given, optimal job scheduling and optimal resource allocation are given by Algorithm 4.From the above analysis and Lemma1, we have the following theorem.Algorithm 4: Algorithm to solve the problem of minimizing the sum of total waiting times and total absolute deviation of job waiting times with convex resource consumption.
Step 1: jobs are scheduled byAP4Step 2: optimal job resource allocation is calculated by formula (37)Theorem 4.
The problemPmqpsd,DJCR,RMAZ2 can be solved in On2m+2 time.


## 5. Conclusions

In this paper, two versions of parallel-machine scheduling problems to minimize the sum of the total completion times, the total absolute deviation of job completion times, and the total resource allocation and the sum of the total waiting times, the total absolute deviation of job waiting times, and the total resource allocation are considered, respectively. We present the problems in this research can be solved polynomially. Future research will be worth extending to multiple rate-modifying activity or other objective scheduling problems.



---

*Source: 6687525-2021-01-18.xml*