# Results of Parallel-Machine Scheduling Model with Maintenance Activity considering Time-Dependent Deterioration, Delivery Times, and Resource Allocation

Authors: Li Sun; Xiao-hong Zhang; Lei Ning
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This paper investigates parallel-machine scheduling models with maintenance activity, delivery times, time-dependent deterioration, and resource allocation. We consider two forms of the problem: the first is to minimize the sum of total completion times, total machine loads, the total absolute deviation of job completion times, and the total resource allocation; the second is to minimize the sum of total waiting times, total machine loads, the total absolute deviation of job waiting times, and the total resource allocation. The problems are proved to be solvable in polynomial time.


---

## Body

## 1. Introduction

Initiated by Vickson [1], scheduling problems with controllable processing times through resource allocation have been studied extensively by researchers since 1980. Wang et al. [2] introduce resource allocation scheduling with learning effect. They analyse the problem with two different processing time functions pj=p¯jra−ajuj and pj=p¯jra/ujk,uj>0. They provide a polynomial time algorithm to the problem. Zhu et al. [3] investigate scheduling problems and show that all the presented problems are polynomially solvable. Liu and Feng [4] show two-machine no-wait flow shop scheduling problems. Liu et al. [5] consider a parallel-machine scheduling problem to minimize the sum of resource consumption and outsourcing cost given. Liu et al. [6] study scheduling problems on single machine to determine the optimal job schedule, the optimal due window location, and the optimal resource allocation.On the other hand, deteriorating scheduling problems have attracting widespread attention since Gupta and Gupta [7] and Browne and Yechiali [8]. More recent papers considering deterioration scheduling problem include Huang and Wang [9], Wang et al. [10], Cheng et al. [11], Cheng et al. [12], Lee et al. [13], Wang and Wang [14], Cheng [15], Wu et al. [16], Yin et al. [17], Zhao and Tang [18], Lai and Lee [19], Miao et al. [20], Yin et al. [21], and Yin et al. [22].In scheduling, Lee and Leon [23] introduce a new class of scheduling situations with rate-modifying activity in which the machines need to be maintained and become unavailable. Recently, scheduling problem with a rate-modifying activity becomes a research hotspot. Yin et al. [24] consider a single-machine batch delivery scheduling and common due date assignment problem. They provide some properties of the optimal schedule for the problem. Wang and Wei [25] introduce identical parallel-machine scheduling problems and show that the problems remain polynomially solvable under the proposed model. Wang and Wang [26] address SLK due date assignment scheduling problem with a rate-modifying activity. They present a polynomial time solution for this problem. Zhu et al. [27] address a single machine scheduling problem and show that the problems are solvable in on4 time for a linear resource allocation function and are solvable in on2logn time for a convex resource allocation function. Ji et al. [28] consider single-machine common due-window and deteriorating rate-modifying activity scheduling problem. They provide polynomial solution algorithms for the corresponding problems. Yang and Yang [29] introduce unrelated parallel-machine scheduling problems with multiple rate-modifying activities. Hsu et al. [30] extend an unrelated parallel-machine scheduling environment and present a more efficient algorithm to solve the extended problem.Jobs’ processing time is impacted greatly by the environment in modern manufacture. There is some extra time to be needed to deal with this thing. This treatment can be performed after the component has been processed by the machine but before it is delivered to the customer so it can be delivered with a guarantee of safety. The extra time to eliminate the adverse effects between the main processing and the delivery of a job is called as a past-sequence-dependent delivery time. Delivery time is firstly introduced into scheduling problem by Koulamas and Kyparisis. Liu et al. [31] consider the single-machine delivery time scheduling problem, which was introduced in Koulamas and Kyparisis [32]. Liu [33] introduce parallel-machine learning effect scheduling with p-s-d delivery time. Shen and Wu [34] study single-machine scheduling with delivery time and general learning effects. Sun et al. [35] consider scheduling models with DeJong’s learning effect, delivery times, rate-modifying activity, and resource allocation, respectively. The problems are proved to be solvable in polynomial time.In this paper, we investigate parallel-machine scheduling problem with time-dependent deterioration delivery time maintenance activity and resource allocation, and some new results are given. The remaining part of this paper is formed as follows: we take shape the problem and present some notations and one lemma in Section2. In Section 3, we introduce the version of the problem with linear resource consumption function. We analyse the problem with convex resource allocation and present an example to illustrate the application in Section 4. In the last section, we conclude the paper.


## 2. Problem Formulation

There aren independent and nonpreemptive jobs, which are simultaneously available for processing on m identical parallel machines. We suppose that m<n throughout the paper. Let aij be the normal processing time of job Jij and pij be the actual processing time of job Jij. Let aik and pik be the normal processing time and the actual processing time of the kth job Jik on machine Mi. Cij and Wij are the completion time and the waiting time of the jth job on machine Mi in a sequence.One deteriorating maintenance activity (denoted by DMA) is allowed on each machine throughout the scheduling to improve machine production efficiency. The deteriorating maintenance duration is represented byft=β+σt, which is longer if it is started later, where β>0 is the basic maintenance activity time, σ>0 is the deterioration rate of maintenance activity, and t is the starting time of the deteriorating maintenance activity. The deteriorating maintenance activity can be scheduled immediately after any job’s processing completion and its starting time is not known in advance. The position of deteriorating maintenance activity on machine Mi is denoted by ki, if the deteriorating maintenance activity is scheduled immediately after completing the processing of the kith job Jki. The machine will revert to its initial condition, and the aging effect will start anew after the maintenance activity.Letni denote the number of jobs located on machine Mi and ki denote the position of deteriorating maintenance activity on machine Mi. Hence, the deteriorating maintenance activity duration is ft=β+σ∑l=1kipil. If a job is scheduled on the jth position of machine Mi in a sequence, its actual processing time with resource consumption is as follows.A linear resource consumption function is given by(1)pij=aij+bt−λijuij=aij+b∑l=1j−1pil−λijuij,if,j≤ki,pij=aij+bt−λijuij=aij+b∑l=kij−1pil−λijuijif,j>ki,where λij is the weight of the resource which is allocated to job Jij. uij is the amount of the resource allocated to job Jij with 0≤uij≤u¯ij<aij+bj−1a¯i/λij, if j≤ki; 0≤uij≤u¯ij<aij+bj−ki−1a¯i/λij, and a¯i=minaij,j=1,2,…,ni if j≥ki. Jobs’ deterioration rate is b.A convex resource consumption function is given by(2)pij=aijuijv+bt=aijuijv+b∑l=1j−1pilifj≤ki,pij=aijuijv+bt=aijuijv+b∑l=ki+1j−1pilifj>ki,where v is a positive constant, uij is the amount of the resource allocated to job Jij with 0≤uij≤u¯ij, and u¯ij is the maximum resource allocation of job Jij.As in the study of Koulamas and Kyparisis [32], the processing of job Jir must be followed by the p-s-d delivery time qir, which can be calculated as qi1=0 and qir=γWir=γ∑l=1r−1pil, before maintenance activity, and qir=γWir=γ∑l=1r−1pil+ft, after maintenance activity, where γ≥0 is a normalizing constant.As usual, we assume that the postprocessing operation of any jobJil modelled by its delivery time qil is performed off-line. Therefore, it is not affected by the availability of the machine and it can be implemented immediately upon completion of the main operation resulting in(3)Ci1=pi1andCij=Wij+pij+qij=1+γWij+pij,j=2,3,…ni.Let denote the p-s-d delivery time byqpsd. In addition, we denote TADC the total absolute deviation of job completion times and TADW the total absolute deviation of job waiting times, i.e., TADC=∑i=1m∑l=1ni∑k=lniCil−Cik and TADW=∑i=1m∑l=1ni∑k=lniWil−Wik. Let TC indicate the job’s total processing times and TW indicate the job’s total waiting times, i.e., TC=∑i=1m∑r=lniCir and TW=∑i=1m∑r=lniWir. We denote the load of machine Mi by Li, and the total machine load (TML) is ∑i=lmLi, i.e., TML=∑i=1mLi. As in the study of Liu and Feng [4], we will try to find the optimal job sequence, the optimal DMA, and the optimal resource consumption on parallel-machine schedule such that the following cost functions are minimized:(4)δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij,δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij,where δ1,δ2,δ3,δ4 represent the per unit time contribution for the total machine load, the total processing (waiting) time, and the total absolute deviation of job completion (waiting) times with δ1>0, δ2>0, δ3>0, and δ4>0. Gij is the per unit time cost associated with resource allocation. Let LRA denote linear resource allocation and CRA denote convex resource allocation. Using the three-field notation introduced by Graham et al., for scheduling problems, we denote the two versions of the problems as(5)Pm|qpsd,LRA,DMA|z,Pm|qpsd,CRA,DMA|z,z∈δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij,δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij.We first present some notations and one lemma before the main results. If the number of jobs on machineMi is ni and the position of the job preceding the deterioration maintenance activity is ki, the jobs’ completion times and waiting times on machine Mi are as follows.For the linear case,(6)Cih=aih−λihuih+∑l=1h−11+γ+b1+bh−l−1ail−λiluil,i=1,2,…,m,h=1,2,…,ki,1+γβ+1+γ1+σ∑l=1ki1+bki−lail−λiluil+∑l=ki+1ni−11+γ+b1+bni−l−1ail−λiluil+aini−λiniuinii=1,2,…,m,h=ki+1,ki+2,…,ni,Wih=aih−1−λih−1uih−1+∑l=1h−21+bh−l−1ail−λiluil,i=1,2,…,m,h=1,2,…,ki,β+1+σ∑l=1ki1+bki−lail−λiluil+∑l=ki+1h−21+bh−l−1ail−λiluil+aih−1−λih−1uih−1,i=1,2,…,m,h=ki+1,ki+2,…,ni.For the convex case,(7)Cih=aihuihv+∑l=1h−11+γ+b1+bh−l−1ailuilv,i=1,2,…,m,h=1,2,…,ki,1+γβ+1+γ1+σ∑l=1ki1+bki−lailuilv+∑l=ki+1ni−11+γ+b1+bni−l−1ailuilv+ainiuiniv,i=1,2,…,m,h=ki+1,ki+2,…,ni,Wih=aih−1uih−1v+∑l=1h−21+bh−l−1ailuilv,i=1,2,…,m,h=1,2,…,ki,β+1+σ∑l=1ki1+bki−lailuilv+∑l=ki+1h−21+bh−l−1ailuilv+aih−1uih−1v,i=1,2,…,m,h=ki+1,ki+2,…,ni.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 Ma et al. [36].


## 3. Cases with Linear Resource Consumption Function

### 3.1. The ProblemPm|qpsd,LRA,DMA|δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij

In this section, we introduce the problem to minimize the sum of total machine load, total completion times, and total absolute deviation of job completion times with resource consumption on all the machines. From the above analysis, for machineMi, we calculate the machine load, the total completion times, and the total absolute deviation of job completion times as follows:(8)Li=1+γβ+1+γ1+σ∑l=1ki1+bki−lail−λiluil+∑l=ki+1ni−11+γ+b1+bni−l−1ail−λiluil+aini−λiniuini,TCi=∑l=1niCil=ni−ki1+γβ+∑l=1ki1+1+γ+b1+bki−l−1b+ni−ki1+γ1+σ1+bki−lail−λiluil+∑l=ki+1ni1+1+γ+b1+bni−l−1bail−λiluil,TADCi=∑l=1ni2l−1−niCil=∑l=ki+1ni2l−1−ni1+γβ+∑l=1ki2l−1−ni+∑h=l+1ki2h−1−ni1+γ+b1+bh−l−1+∑h=ki+1ni2h−1−ni1+γ1+σ1+bki−lail−λiluil+∑l=ki+1ni−12l−1−ni+∑h=l+1ni2h−1−ni1+γ+b1+bh−l−1ail−λiluil+ni−1aini−λiniuini.Hence, the sum of total machine load, total completion times, and total absolute deviation of job completion times with resource consumption on all the machines is(9)δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij=1+γβ∑i=1mδ1+δ2ni−ki+δ3∑l=ki+1ni2l−1−ni+∑i=1m∑l=1kiδ11+γ1+σ1+bki−l+δ21+1+γ+b1+bki−l−1b+ni−ki1+γ1+σ1+bki−l+δ32l−1−ni+∑h=l+1ki2h−1−ni1+γ+b1+bh−l−l+∑h=ki+1ni2h−1−ni1+γ1+σ1+bki−lail−λiluil+∑i=1m∑h=ki+1ni−1δ11+γ+b1+bni−l−1+δ21+1+γ+b1+bni−l−1b+δ32l−1−ni+∑h=l+1ni2h−1−ni1+γ+b1+bh−l−1ail−λiluil+∑i=1mδ1+δ2+ni−1δ3aini−λiniuini+∑i=1m∑l=1niGiluil.Let(10)A1=1+γβ∑i=1mδ1+δ2ni−ki+δ3∑l=ki+1ni2l−1−ni,wil=δ11+γ1+σ1+bki−l+δ21+1+γ+b1+bki−l−1b+ni−ki1+γ1+σ1+bki−l+δ32l−1−ni+∑h=l+1ki2h−1−ni1+γ+b1+bh−l−l+∑h=ki+1ni2h−1−ni1+γ1+σ1+bki−l,i=1,2,…,m,l=1,2,…,ki,δ11+γ+b1+bni−l−1+δ21+1+γ+b1+bni−l−1b+δ32l−1−ni+∑h=l+1ni2h−1−ni1+γ+b1+bh−l−1,i=1,2,…,m,l=ki+1,ki+2,…,ni−1,δ1+δ2+ni−1δ3,i=1,2,…,m,l=ni.Thus,(11)δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij=A1+∑i=1m∑l=1niwilail+∑i=1m∑l=1niGil−λilwiluil.From the above equation, for any job sequence, the optimal resource allocation for a job depends on the sign ofGil−λilwil. If Gil−λilwil is negative, the maximum feasible amount of the resource should be allocated to job Jil, if Gil−λilwil is positive, no resource should be allocated to job Jil, and if Gil−λilwil is equal to zero, any of value of resource consumption will not affect the total cost. Let uil∗ denote the optimal resource allocation for job Jil, where(12)uil=u¯il,ifGil−λilwil<0,u0∈0,u¯il,ifGil−λilwil=0,0,ifGil−λilwil>0.From equation (12), we can obtain the optimal resource allocation for any given optimal sequence.SinceA1 is a constant, when ni and ki are given, we can express the problem as the following assignment problem:(13)F1=A1+min∑i=1m∑j=1n∑l=1niθijlxijl,AP1s.t.∑j=1nxijl=1i=1,2,…,m,l=1,2,…,ni∑i=1m∑l=1nixijl=1j=1,2,…,nxijl=0or1i=1,2,…,m,l=1,2,…,ni,j=1,2,…,n,where(14)θijl=wilaij+Gij−λijwilu¯ij,ifGij−λijwil<0,wilaij,ifGij−λijwil≥0.Consequently, when thePn,m,k vector is given, optimal job scheduling and optimal resource allocation are given in Algorithm 1.Algorithm 1: Algorithm for the problem to minimize the sum of total completion times, total machine loads, the total absolute deviation of job completion times, and the total resource allocation under linear resource consumption.
Step 1: jobs are scheduled byAP1.Step 2: optimal job resource allocation is calculated by formula (12).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 problemPm|qpsd,LRA,DMA|δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij can be solved in On2m+2 time.


### 3.2. The ProblemPm|qpsd,LRA,DMA|δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij

In this section, we study the problem to minimize the sum of the total machine load, the total waiting times, and the total absolute deviation of job waiting times with resource consumption. For machineMi, we compute the machine load, the total waiting times, and the total absolute deviation of job waiting times as follows:(15)Li=1+γβ+1+γ1+σ∑l=1ki1+bki−lail−λiluil+∑l=ki+1ni−11+γ+b1+bni−l−1ail−λiluil+aini−λiniuini,TWi=∑l=1niWil=ni−ki−1β+∑l=1kini−ki−11+σ1+bki−l+1+bki−l−1bail−λiluil+∑l=ki+1ni1+bni−l−1bail−λiluil,TADWi=∑l=1ni2l−1−niWil=kini−kiβ+∑h=1ki∑l=hki−12l+1−ni1+bl−h+ni−kini+ki+1−1+nini−ki−11+σ1+bki−laih−λihuih+∑h=ki+1ni−1∑l=hni−12l+1−ni1+bl−haih−λihuih.Hence, the sum of total machine load, total waiting times, and total absolute deviation of job waiting times with resource consumption on all the machines is(16)δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij,=∑i=1mβδ11+σ+δ2ni−ki−1+δ3kini−ki+∑i=1m∑l=1kiδ11+γ1+σ1+bki−l+δ2ni−ki−11+σ1+bki−l+1+bki−l−1b+δ3∑h=lki−12h+1−ni1+bh−l+ni−kini+ki+1−1+nini−ki−11+σ1+bki−hail−λiluil+∑i=1m∑l=ki+1ni−1δ11+γ+b1+bni−l−1+δ21+bni−l−1b+δ3∑h=lni−12h+1−ni1+bh−lail−λiluil+∑i=1mδ1aini−λiniuini+∑i=1m∑l=1niGiluil.Let(17)A2=∑i=1mβδ11+σ+δ2ni−ki−1+δ3kini−ki,φil=δ11+γ1+σ1+bki−l+δ2ni−ki−11+σ1+bki−l+1+bki−l−1b+δ3∑h=lki−12h+1−ni1+bh−l+ni−kini+ki+1−1+nini−ki−11+σ1+bki−h,i=1,2,…,m,l=1,2,…,ki,δ11+γ+b1+bni−l−1+δ21+bni−l−1b+δ3∑h=lni−12h+1−ni1+bh−l,i=1,2,…,m,l=ki+1,ki+2,…,ni−1,δ1,i=1,2,…,m,l=ni.Thus,(18)δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij=A2+∑i=1m∑l=1niφilail+∑i=1m∑l=1niGil−λilφiluil.For any job sequence, the optimal resource allocation for a job depends on the sign ofGil−λilφil. Let uil∗ denote the optimal resource allocation for job Jil, where(19)uil=u¯il,ifGil−λilφil<0,u0∈0,u¯il,ifGil−λilφil=0,0,ifGil−λilφil>0.From equation (19), we can get the optimal resource allocation for any given optimal sequence.Accordingly, whenni and ki are given, we can indicate the problem as the following assignment problem:(20)F2=A2+min∑i=1m∑j=1n∑l=1niρijlyijl,AP2s.t.∑j=1nyijl=1i=1,2,…,m,l=1,2,…,ni∑i=1m∑l=1niyijl=1j=1,2,…,nyijl=0or1i=1,2,…,m,l=1,2,…,ni,j=1,2,…,n,where(21)ρijl=φilaij+Gij−φilλiju¯ij,ifGij−φilλij<0,φilaij,ifGij−φilλij≥0.Hence, when thePn,m,k vector is given, optimal job scheduling and optimal resource allocation are given in Algorithm 2.Algorithm 2: Algorithm for the problem to minimize the sum of total waiting times, total machine loads, the total absolute deviation of job waiting times, and the total resource allocation under linear resource consumption.
Step 1: jobs are scheduled byAP2.Step 2: optimal job resource allocation is calculated by formula (19).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 problemPm|qpsd,LRA,DMA|δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij can be solved in On2m+2 time.


## 3.1. The ProblemPm|qpsd,LRA,DMA|δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij

In this section, we introduce the problem to minimize the sum of total machine load, total completion times, and total absolute deviation of job completion times with resource consumption on all the machines. From the above analysis, for machineMi, we calculate the machine load, the total completion times, and the total absolute deviation of job completion times as follows:(8)Li=1+γβ+1+γ1+σ∑l=1ki1+bki−lail−λiluil+∑l=ki+1ni−11+γ+b1+bni−l−1ail−λiluil+aini−λiniuini,TCi=∑l=1niCil=ni−ki1+γβ+∑l=1ki1+1+γ+b1+bki−l−1b+ni−ki1+γ1+σ1+bki−lail−λiluil+∑l=ki+1ni1+1+γ+b1+bni−l−1bail−λiluil,TADCi=∑l=1ni2l−1−niCil=∑l=ki+1ni2l−1−ni1+γβ+∑l=1ki2l−1−ni+∑h=l+1ki2h−1−ni1+γ+b1+bh−l−1+∑h=ki+1ni2h−1−ni1+γ1+σ1+bki−lail−λiluil+∑l=ki+1ni−12l−1−ni+∑h=l+1ni2h−1−ni1+γ+b1+bh−l−1ail−λiluil+ni−1aini−λiniuini.Hence, the sum of total machine load, total completion times, and total absolute deviation of job completion times with resource consumption on all the machines is(9)δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij=1+γβ∑i=1mδ1+δ2ni−ki+δ3∑l=ki+1ni2l−1−ni+∑i=1m∑l=1kiδ11+γ1+σ1+bki−l+δ21+1+γ+b1+bki−l−1b+ni−ki1+γ1+σ1+bki−l+δ32l−1−ni+∑h=l+1ki2h−1−ni1+γ+b1+bh−l−l+∑h=ki+1ni2h−1−ni1+γ1+σ1+bki−lail−λiluil+∑i=1m∑h=ki+1ni−1δ11+γ+b1+bni−l−1+δ21+1+γ+b1+bni−l−1b+δ32l−1−ni+∑h=l+1ni2h−1−ni1+γ+b1+bh−l−1ail−λiluil+∑i=1mδ1+δ2+ni−1δ3aini−λiniuini+∑i=1m∑l=1niGiluil.Let(10)A1=1+γβ∑i=1mδ1+δ2ni−ki+δ3∑l=ki+1ni2l−1−ni,wil=δ11+γ1+σ1+bki−l+δ21+1+γ+b1+bki−l−1b+ni−ki1+γ1+σ1+bki−l+δ32l−1−ni+∑h=l+1ki2h−1−ni1+γ+b1+bh−l−l+∑h=ki+1ni2h−1−ni1+γ1+σ1+bki−l,i=1,2,…,m,l=1,2,…,ki,δ11+γ+b1+bni−l−1+δ21+1+γ+b1+bni−l−1b+δ32l−1−ni+∑h=l+1ni2h−1−ni1+γ+b1+bh−l−1,i=1,2,…,m,l=ki+1,ki+2,…,ni−1,δ1+δ2+ni−1δ3,i=1,2,…,m,l=ni.Thus,(11)δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij=A1+∑i=1m∑l=1niwilail+∑i=1m∑l=1niGil−λilwiluil.From the above equation, for any job sequence, the optimal resource allocation for a job depends on the sign ofGil−λilwil. If Gil−λilwil is negative, the maximum feasible amount of the resource should be allocated to job Jil, if Gil−λilwil is positive, no resource should be allocated to job Jil, and if Gil−λilwil is equal to zero, any of value of resource consumption will not affect the total cost. Let uil∗ denote the optimal resource allocation for job Jil, where(12)uil=u¯il,ifGil−λilwil<0,u0∈0,u¯il,ifGil−λilwil=0,0,ifGil−λilwil>0.From equation (12), we can obtain the optimal resource allocation for any given optimal sequence.SinceA1 is a constant, when ni and ki are given, we can express the problem as the following assignment problem:(13)F1=A1+min∑i=1m∑j=1n∑l=1niθijlxijl,AP1s.t.∑j=1nxijl=1i=1,2,…,m,l=1,2,…,ni∑i=1m∑l=1nixijl=1j=1,2,…,nxijl=0or1i=1,2,…,m,l=1,2,…,ni,j=1,2,…,n,where(14)θijl=wilaij+Gij−λijwilu¯ij,ifGij−λijwil<0,wilaij,ifGij−λijwil≥0.Consequently, when thePn,m,k vector is given, optimal job scheduling and optimal resource allocation are given in Algorithm 1.Algorithm 1: Algorithm for the problem to minimize the sum of total completion times, total machine loads, the total absolute deviation of job completion times, and the total resource allocation under linear resource consumption.
Step 1: jobs are scheduled byAP1.Step 2: optimal job resource allocation is calculated by formula (12).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 problemPm|qpsd,LRA,DMA|δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij can be solved in On2m+2 time.


## 3.2. The ProblemPm|qpsd,LRA,DMA|δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij

In this section, we study the problem to minimize the sum of the total machine load, the total waiting times, and the total absolute deviation of job waiting times with resource consumption. For machineMi, we compute the machine load, the total waiting times, and the total absolute deviation of job waiting times as follows:(15)Li=1+γβ+1+γ1+σ∑l=1ki1+bki−lail−λiluil+∑l=ki+1ni−11+γ+b1+bni−l−1ail−λiluil+aini−λiniuini,TWi=∑l=1niWil=ni−ki−1β+∑l=1kini−ki−11+σ1+bki−l+1+bki−l−1bail−λiluil+∑l=ki+1ni1+bni−l−1bail−λiluil,TADWi=∑l=1ni2l−1−niWil=kini−kiβ+∑h=1ki∑l=hki−12l+1−ni1+bl−h+ni−kini+ki+1−1+nini−ki−11+σ1+bki−laih−λihuih+∑h=ki+1ni−1∑l=hni−12l+1−ni1+bl−haih−λihuih.Hence, the sum of total machine load, total waiting times, and total absolute deviation of job waiting times with resource consumption on all the machines is(16)δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij,=∑i=1mβδ11+σ+δ2ni−ki−1+δ3kini−ki+∑i=1m∑l=1kiδ11+γ1+σ1+bki−l+δ2ni−ki−11+σ1+bki−l+1+bki−l−1b+δ3∑h=lki−12h+1−ni1+bh−l+ni−kini+ki+1−1+nini−ki−11+σ1+bki−hail−λiluil+∑i=1m∑l=ki+1ni−1δ11+γ+b1+bni−l−1+δ21+bni−l−1b+δ3∑h=lni−12h+1−ni1+bh−lail−λiluil+∑i=1mδ1aini−λiniuini+∑i=1m∑l=1niGiluil.Let(17)A2=∑i=1mβδ11+σ+δ2ni−ki−1+δ3kini−ki,φil=δ11+γ1+σ1+bki−l+δ2ni−ki−11+σ1+bki−l+1+bki−l−1b+δ3∑h=lki−12h+1−ni1+bh−l+ni−kini+ki+1−1+nini−ki−11+σ1+bki−h,i=1,2,…,m,l=1,2,…,ki,δ11+γ+b1+bni−l−1+δ21+bni−l−1b+δ3∑h=lni−12h+1−ni1+bh−l,i=1,2,…,m,l=ki+1,ki+2,…,ni−1,δ1,i=1,2,…,m,l=ni.Thus,(18)δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij=A2+∑i=1m∑l=1niφilail+∑i=1m∑l=1niGil−λilφiluil.For any job sequence, the optimal resource allocation for a job depends on the sign ofGil−λilφil. Let uil∗ denote the optimal resource allocation for job Jil, where(19)uil=u¯il,ifGil−λilφil<0,u0∈0,u¯il,ifGil−λilφil=0,0,ifGil−λilφil>0.From equation (19), we can get the optimal resource allocation for any given optimal sequence.Accordingly, whenni and ki are given, we can indicate the problem as the following assignment problem:(20)F2=A2+min∑i=1m∑j=1n∑l=1niρijlyijl,AP2s.t.∑j=1nyijl=1i=1,2,…,m,l=1,2,…,ni∑i=1m∑l=1niyijl=1j=1,2,…,nyijl=0or1i=1,2,…,m,l=1,2,…,ni,j=1,2,…,n,where(21)ρijl=φilaij+Gij−φilλiju¯ij,ifGij−φilλij<0,φilaij,ifGij−φilλij≥0.Hence, when thePn,m,k vector is given, optimal job scheduling and optimal resource allocation are given in Algorithm 2.Algorithm 2: Algorithm for the problem to minimize the sum of total waiting times, total machine loads, the total absolute deviation of job waiting times, and the total resource allocation under linear resource consumption.
Step 1: jobs are scheduled byAP2.Step 2: optimal job resource allocation is calculated by formula (19).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 problemPm|qpsd,LRA,DMA|δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij 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.Pm|qpsd,CRA,DMA|z,(22)z∈δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij,δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij.Similar to the analysis of problemPm|qpsd,LRA,DMA|δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij, if ni and ki are given, we calculate the problem to minimize the sum of the total machine load, the total completion times and the total absolute deviation of job completion times with convex resource consumption as follows:(23)H1=δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij=A1+∑i=1m∑l=1niwilailuilv+∑i=1m∑l=1niGiluil,where(24)A1=1+γβ∑i=1mδ1+δ2ni−ki+δ3∑l=ki+1ni2l−1−ni,wil=δ11+γ1+σ1+bki−l+δ21+1+γ+b1+bki−l−1b+ni−ki1+γ1+σ1+bki−l+δ32l−1−ni+∑h=l+1ki2h−1−ni1+γ+b1+bh−l−l+∑h=ki+1ni2h−1−ni1+γ1+σ1+bki−l,i=1,2,…,m,l=1,2,…,ki,δ11+γ+b1+bni−l−1+δ21+1+γ+b1+bni−l−1b+δ32l−1−ni+∑h=l+1ni2h−1−ni1+γ+b1+bh−l−1,i=1,2,…,m,l=ki+1,ki+2,…,ni−1,δ1+δ2+ni−1δ3,i=1,2,…,m,l=ni.By taking the first derivative ofH1 with respect to uil, i=1,2,…,m, l=1,2,…,ni, equating the result to zero, and solving it for uil, we can obtain the optimal resource allocation (denoted by uil∗).(25)∂H1∂uil=−vwilailvuil−v−1+Gil=0uil∗=vwilGil1/v+1ailv/v+1.By substitutinguil∗ into the objective function H1, we obtain a new unified expression as follows:(26)H1=A1+∑i=1m∑l=1niv−v/v+1+v1/v+1wil1/v+1Gilailv/v+1.Therefore, we can formulate the minimum problem as the following assignment problem:(27)H1=A1+min∑i=1m∑j=1n∑l=1niξijlx¯ijl,s.t.∑j=1nx¯ijl=1i=1,2,…,m,l=1,2,…,niAP3∑i=1m∑l=1nix¯ijl=1j=1,2,…,nx¯ijl=0or1i=1,2,…,m,l=1,2,…,ni,j=1,2,…,n,where(28)ξijl=v−v/v+1+v1/v+1wil1/v+1Gijaijv/v+1,i=1,2,…,m,j=1,2,…,n,l=1,2,…,ni.Consequently, when thePn,m,k vector is given, optimal job scheduling and optimal resource allocation are given Algorithm 3.Algorithm 3: Algorithm for the problem to minimize the sum of total completion times, total machine loads, the total absolute deviation of job completion times, and the total resource allocation under the convex resource consumption.
Step 1: jobs are scheduled byAP3.Step 2: optimal job resource allocation is calculated by formula (25).Together with Lemma1, we have the following theorem.Theorem 3.
The problemPm|qpsd,CRA,DMA|δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij can be solved in On2m+2 time.Similar to the analysis of problemPm|qpsd,LRA,DMA|δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij, if ni and ki are 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:(29)H2=α2∑i=1mTWi+δ2∑i=1mTADWi+∑i=1m∑j=1niGijuij=A2+∑i=1m∑l=1niφilailuilv+∑i=1m∑l=1niGiluil,where(30)A2=∑i=1mβδ11+σ+δ2ni−ki−1+δ3kini−ki,φil=δ11+γ1+σ1+bki−l+δ2ni−ki−11+σ1+bki−l+1+bki−l−1b+δ3∑h=lki−12h+1−ni1+bh−l+ni−kini+ki+1−1+nini−ki−11+σ1+bki−h,i=1,2,…,m,l=1,2,…,ki,δ11+γ+b1+bni−l−1+δ21+bni−l−1b+δ3∑h=lni−12h+1−ni1+bh−l,i=1,2,…,m,l=ki+1,ki+2,…,ni−1,δ1,i=1,2,…,m,l=ni.Hence, taking the first derivative ofH2 with respect to uil, i=1,2,…,m, l=1,2,…,ni, equating the result to zero, and solving it for uil, we can obtain the optimal resource allocation (denoted by uil∗).(31)∂H2∂uil=−vφilailvuil−v−1+Gil=0uil∗=vφilGil1/v+1ailv/v+1.By substitutinguil∗ into the objective function H2, we obtain a new unified expression as follows:(32)H2=A2+∑i=1m∑l=1niv−v/v+1+v1/v+1φil1/v+1Gilailv/v+1.Therefore, we can formulate the minimum problem as the following assignment problem:(33)H2=A2+min∑i=1m∑j=1n∑l=1niηijly¯ijl,AP4s.t.∑j=1ny¯ijl=1i=1,2,…,m,l=1,2,…,ni∑i=1m∑l=1niy¯ijl=1j=1,2,…,ny¯ijl=0or1i=1,2,…,m,l=1,2,…,ni,j=1,2,…,n,where ηijl=v−v/v+1+v1/v+1φil1/v+1Gijaijv/v+1.Therefore, when thePn,m,k vector is given, optimal job scheduling and optimal resource allocation are given Algorithm 4.Algorithm 4: Algorithm for the problem to minimize the sum of total waiting times, total machine loads, the total absolute deviation of job waiting times, and the total resource allocation under convex resource consumption.
Step 1: jobs are scheduled byAP4.Step 2: optimal job resource allocation is calculated by formula (31).From the above analysis and Lemma1, we have the following theorem.Theorem 4.
The problemPm|qpsd,CRA,DMA|δ1TML+δ2TW+δ3TADW+δ4∑i=1m∑j=1niGijuij can be solved in On2m+2 time.Example. We consider three jobs assigned to two parallel machines to minimize the sum of the total machine loads, the total completion times, the total absolute deviation of job completion times, and the total resource allocation under linear resource allocation. Using the three-field notation, we denote the problem as Pm|qpsd,LRA,DMA|δ1TML+δ2TC+δ3TADC+δ4∑i=1m∑j=1niGijuij. Thus, n1,n2∈0,3,1,2 and ki=0,1,2.i=1,2. Here, we only consider the situation: n1,n2=1,2 and ki=1.i=1,2. Three jobs are J1,J2,J3 and two machines are M1,M2. Let Jijr denote job Ji be assigned the rth position on machine Mj. When n1,n2=1,2 and ki=1, there are six schedules:(34)π1=J111,J221,J322,π2=J111,J321,J222,π3=J211,J121,J322,π4=J211,J321,J122,π5=J311,J121,J222,π6=J311,J221,J122,a1=8,a2=15,a3=20,λ1=2,λ2=1,λ3=5;G1=2,G2=1,G3=3,β=5,σ=2;γ=0.3,δ1=0.3,δ2=0.5,δ3=0.8,δ4=0.1;b=2,u¯ij=4.By calculation, in schedulingπ1,(35)w111=0.3∗1+0.31+21+2−1+0.51+1+0.3+2∗1+20−1−12+1−01+0.31+21+20−1+0.82∗1−1−1+2∗1−1−11+0.31+21+20−1=0.6873,w221=0.3∗1+0.31+21+21−1+0.51+1+0.3+2∗1+21−1−12+2−11+0.31+21+21−1+0.82∗1−1−2+2∗2−1−21+0.31+21+21−1=5.94,w322=0.3+0.5+2−1∗0.8=1.6,A1=1+0.3∗5∗0.3+0.51−1+0.82∗1−1−1+0.3+0.52−1+0.82∗2−1−2=12.35,G1−λ1w111=2−2∗0.6873=0.6254>0,G2−λ2w221=1−1∗5.94=−4.94<0,G3−λ3w321=3−5∗1.6=−5<0.Therefore, the optimal resource allocation isu1=0, u2=4, and u3=4, and the objective function value is(36)δ1TMLπ1+δ2TCπ1+δ3TADCπ1+δ4∑i=1m∑j=1niGijuij=12.35+8∗0.6873+15∗5.94+20∗1.6+4.94∗4−5∗4=99.1884.By the same method, we have the minimization objective function value and the optimal resource allocation of other schedule as Table1.From Table1, it is easy to obtain that the optimal schedule is J211,J121,J322 or J211,J321,J122. The optimal resource allocation is u1=4, u2=0, and u3=4.Table 1
Other schedule results.
The minimization value of the objective functionThe optimal resource allocationu1,u2,u3π251.4484(0, 4, 4)π342.6595(4, 0, 4)π442.6595(4, 0, 4)π553.95(4, 4, 4)π6101.6904(4, 4, 4)


## 5. Conclusions

In this paper, parallel-machine scheduling problems with past-sequence-dependent delivery times, time-dependent deterioration, maintenance activity, and resource consumption are considered. We present two versions of the scheduling problems can be solved polynomially. Future research will be worth extending to multiple maintenance activities or other objective scheduling problems.



---

*Source: 8826345-2021-10-25.xml*