# A Coordination Mechanism for Scheduling Game on Parallel-Batch Machines with Deterioration Jobs

Authors: Ganhua Yu
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In this study, we consider a parallel-batch machines scheduling game problem with deterioration jobs. The processing time of a job is a simple linear function of its starting time. Each of the parallel-batch machines can process up toB jobs simultaneously as a batch. The processing time of a batch is the processing time of the job with the longest deteriorating rate in the batch. All jobs in the same batch start and complete at the same time. Each job as an agent and its individual cost is the completion time of the job. We present a coordination mechanism for the scheduling game problem with social cost of minimizing the makespan in this paper, namely fully batch longest deteriorating rate. For this problem, we precisely quantify the inefficiency of Nash equilibrium by the logarithm price of anarchy. It is defined to be the ratio between the logarithm of social cost of the worst Nash equilibrium and the logarithm of social cost of an optimum schedule. In addition, we discuss the existence of Nash equilibrium and present an upper bound and lower bounds on the logarithm price of anarchy of the coordination mechanism. We show that the mechanism has a logarithm price of anarchy at most 2−1/3maxm,B−2/3B.


---

## Body

## 1. Introduction

For tradition scheduling problems, it is assumed that the processing times of jobs are fixed. However, the processing times may deteriorate due to wear and tear of the machines in the real world. Examples can be found in steel production, fire fighting, and resource allocation, where any delay in processing a job may increase its cost. In this paper, we consider the proportional deterioration model. In this model, the processing time of a job is a simple linear function of its starting time. Consider there aren jobs J=J1,J2,…,Jn, where each job j∈J has a deteriorating rate aj>0. The jobs are indexed in nonincreasing order of their deteriorating rates, i.e., a1≥a2≥⋯≥an. There are m machines M=M1,M2,…,Mm, and machines are available at time t0. If Jj starts to be processed on machine Mi at time t≥t0, its actual processing time is pj=ajt, where i=1,2,…,m. Without loss of generality, we assume t0=1 throughout this paper. Further studies on deterioration model can be found in other papers, e.g., Gawiejnowicz and Kurc [1], Miao [2], Qian and Han [3], Chai et al. [4].Research on parallel-batch machine scheduling may date back to Brucker et al. [5]. Each of the parallel-batch machine can process up to B jobs simultaneously as a batch. The processing time of a batch is equal to the time of processing the job with the longest deteriorating rate in the batch. All jobs in the same batch start and complete at the same time. For each i=1,2,…,m, each machine Mi can process bi1≤bi≤n batches, i.e., Bi1,Bi2,…,Bibil, where Bik1≤k≤bi is the k-th batch processed on machine Mi. Obviously, we have J=∪i=1m∪k=1biBik. More results on parallel-batch machine scheduling can be found in Li and Li [6], Muter [7], Xu et al. [8], and Fowler and Monch [9]. According to the three-field notation αβγ of Graham et al. [10], we denoted our problem as PmB<n,pj=ajtCmax, where pj, aj, and Cmax denote the processing time, the deteriorating rate, and the maximum completion time over all jobs, respectively.In contrast to traditional scheduling problem in which controlled by a central decision maker, each job now can individually decide which machine to be processed in scheduling game. Each job only is interested in minimizing its own completion time and does not care about the social optimum. We call a schedule Nash equilibrium (NE) if no job can reduce its cost by moving to a different machine [11]. The inefficient of a NE is measured by the price of anarchy (POA) [11], and it is defined as the ratio between the social cost of the worst Nash equilibrium and the social cost of an optimum schedule. Each machine has a scheduling policy to order their jobs in sequence. All the policies of the machines are named as a coordination mechanism [12, 13]. More studies on coordination mechanism for scheduling game problem can be found in Chen and Tan [14], Ye et al. [15], Chen and Xu [16], and He and Tan [17].For the scheduling game problem with deterioration jobs, POA may not be an appropriate measure, since the exponents of the social cost of the worst Nash equilibrium and the social cost of an optimum schedule are not the same. In order to measure the worst case of the Nash equilibrium schedule, we define another logarithm price of anarchy (LPOA). It is defined as the ratio between the logarithm of social cost of the worst Nash equilibrium and the logarithm of social cost of an optimum schedule, i.e.,(1)LPOA=maxα∈NIlnCmaxαlnCmax∗I,where α is a NE assignment, I is the set of all instance of the scheduling game, and NI is the set of NE for I.


### 1.1. Related Work

There are many researchers who have concentrated on parallel-batch and deterioration load scheduling problems without considering the game environment. Liu et al. [18] considered the scheduling problem Pmpj=ajtCmax and proved that the worst-case ratio is 1+amax1−1/m, where amax=maxj=1,...,naj. Lageweg et al. [19] showed that the scheduling problem PmCmax is NP-hard. Lee et al. [20] considered the scheduling problem PmB<nCmax and designed a 4/3−1/3m-approximation algorithm. Miao et al. [21] showed that the scheduling problem PmB<n,pj=ajtCmax is NP hard and presented an FPTAS algorithm.In recent years, Chen et al. [22] considered the scheduling game problem Pmpj=ajtCmax and proved that the POA has a tight bound of 1+amax1−1/m under SDR police. Under LDR policy, POA is at most maxi=1,2,…m1+am+i+11−1/i and at least 1+am+i+11−1/ii=1,2,…,m. Under MS policy, they proved that the POS = 1. Fan et al. [23] proved that the POA of FBLPT coordination mechanism for the scheduling game problem QmB<nCmax is at most 1+smax/s¯1−1/maxm,B+δ, where δ=1/ms¯Cmax∗∑i=1mi−1siε. In classical scheduling theory, it is assumed that the processing times of jobs are fixed. But the processing times may deteriorate due to wear and tear of the machines in the real world. Parallel-batch processing and job deterioration coexist in many realistic scheduling game situations. Examples can be found in network economic and resource allocation. In this paper, we consider the proportional deterioration scheduling game model PmB<n,pj=ajtCmax.


### 1.2. Our Contribution

To the best of our knowledge, the scheduling game problemPmB<n,pj=ajtCmax has never been discussed. For the scheduling game problem PmB<n,pj=ajtCmax, (i) we design a coordination mechanism with social cost of minimizing the makespan in this paper, namely fully batch longest deteriorating rate; (ii) we present a logarithm price of anarchy to measure the inefficient of a Nash equilibrium and discuss the existence of Nash equilibrium; (iii) we show that the coordination mechanism has a logarithm price of anarchy at most 2−1/3maxm,B−2/3B; (iv) if m≤B, the coordination mechanism has a logarithm price of anarchy at least 2−1/m; if m>B, the coordination mechanism has a logarithm price of anarchy at least 2−m+B−R/mB.


## 1.1. Related Work

There are many researchers who have concentrated on parallel-batch and deterioration load scheduling problems without considering the game environment. Liu et al. [18] considered the scheduling problem Pmpj=ajtCmax and proved that the worst-case ratio is 1+amax1−1/m, where amax=maxj=1,...,naj. Lageweg et al. [19] showed that the scheduling problem PmCmax is NP-hard. Lee et al. [20] considered the scheduling problem PmB<nCmax and designed a 4/3−1/3m-approximation algorithm. Miao et al. [21] showed that the scheduling problem PmB<n,pj=ajtCmax is NP hard and presented an FPTAS algorithm.In recent years, Chen et al. [22] considered the scheduling game problem Pmpj=ajtCmax and proved that the POA has a tight bound of 1+amax1−1/m under SDR police. Under LDR policy, POA is at most maxi=1,2,…m1+am+i+11−1/i and at least 1+am+i+11−1/ii=1,2,…,m. Under MS policy, they proved that the POS = 1. Fan et al. [23] proved that the POA of FBLPT coordination mechanism for the scheduling game problem QmB<nCmax is at most 1+smax/s¯1−1/maxm,B+δ, where δ=1/ms¯Cmax∗∑i=1mi−1siε. In classical scheduling theory, it is assumed that the processing times of jobs are fixed. But the processing times may deteriorate due to wear and tear of the machines in the real world. Parallel-batch processing and job deterioration coexist in many realistic scheduling game situations. Examples can be found in network economic and resource allocation. In this paper, we consider the proportional deterioration scheduling game model PmB<n,pj=ajtCmax.


## 1.2. Our Contribution

To the best of our knowledge, the scheduling game problemPmB<n,pj=ajtCmax has never been discussed. For the scheduling game problem PmB<n,pj=ajtCmax, (i) we design a coordination mechanism with social cost of minimizing the makespan in this paper, namely fully batch longest deteriorating rate; (ii) we present a logarithm price of anarchy to measure the inefficient of a Nash equilibrium and discuss the existence of Nash equilibrium; (iii) we show that the coordination mechanism has a logarithm price of anarchy at most 2−1/3maxm,B−2/3B; (iv) if m≤B, the coordination mechanism has a logarithm price of anarchy at least 2−1/m; if m>B, the coordination mechanism has a logarithm price of anarchy at least 2−m+B−R/mB.


## 2. The FBLDR Coordination Mechanism

We first describe the longest deteriorating rate (LDR) rule and fully batch longest deteriorating rate (FBLDR) rule for the scheduling game problemPmB<n, pj=ajtCmax.


### 2.1. LDR Rule

Step 1: Sort all jobs inJ in nonincreasing order of their deteriorating rates and obtain a list of all jobsStep 2: Assign each job in the list to the machine that completes the job earliest


### 2.2. FBLDR Rule

Step 1: Sort all jobs inJ in nonincreasing order of their deteriorating rates and obtain a list of all jobsStep 2: If there are more thanB jobs in the list, place the first B jobs in a batch and iterate. Otherwise, place the remaining jobs in a batch, called an unfilled batch.In the following, we describe the FBLDR coordination mechanism for the scheduling game problemPmB<n,pj=ajtCmax.


### 2.3. FBLDR Coordination Mechanism

Scheduling policy ofMi:Group all the jobs that have selectedMi into batches by FBLDR rule. At time t0=1, start processing the resulting batches greedily in nonincreasing order of their deteriorating rates.


## 2.1. LDR Rule

Step 1: Sort all jobs inJ in nonincreasing order of their deteriorating rates and obtain a list of all jobsStep 2: Assign each job in the list to the machine that completes the job earliest


## 2.2. FBLDR Rule

Step 1: Sort all jobs inJ in nonincreasing order of their deteriorating rates and obtain a list of all jobsStep 2: If there are more thanB jobs in the list, place the first B jobs in a batch and iterate. Otherwise, place the remaining jobs in a batch, called an unfilled batch.In the following, we describe the FBLDR coordination mechanism for the scheduling game problemPmB<n,pj=ajtCmax.


## 2.3. FBLDR Coordination Mechanism

Scheduling policy ofMi:Group all the jobs that have selectedMi into batches by FBLDR rule. At time t0=1, start processing the resulting batches greedily in nonincreasing order of their deteriorating rates.


## 3. Existence of NE for the Scheduling Game ProblemPmB<n,pj=ajtCmax

In the section, we prove the existence of NE of the scheduling game problemPmB<n,pj=ajtCmax. We first consider the LDR-Greedy algorithm for the scheduling problem PmB<n,pj=ajtCmax and then show that the NE is the schedule generated by the LDR-Greedy algorithm.For the scheduling game problemPmB<n,pj=ajtCmax, we obtain a LDR-Greedy algorithm. The idea of the LDR-Greedy algorithm is similar to LPT-Greedy algorithm [24]. The following description provides the details of LDR-Greedy algorithm.Sorting the jobs in nonincreasing order of their deteriorating rates, then assigning the jobs one by one into some batch, and processing the resulting batches greedily. If the jobj has been scheduled and the job j+1 has not been processed, it is called state j. If the batch has not been full, then the job j+1 will be allocated in the last batch of a machine which completes job j+1 earliest; otherwise, the job j+1 will be allocated in a new batch of a machine which completes job j+1 earliest. Let set Cij and nij be the completion time on machine Mi in state j and the number of jobs scheduled on machine Mi in state j, respectively. Set(2)Gij+1=Cij1+aj+1,ifnijmodB=0,Cij,otherwise.


### 3.1. Algorithm LDR-Greedy

Step 1. Fori=1,2,…,m, set Ci0=1, ni0=0,j=1Step 2. ComputeGij and i∗j=argmin1≤i≤mGij. Then, assign job j to the ⌈ni∗jj−1+1/B⌉-th batch of Mi∗jStep 3. Ifi=i∗j, set Ci∗jj=Gi∗jj, ni∗jj=ni∗jj−1+1; otherwise, set(3)Cij=Gij−1,nij=nij−1.Step 4. Ifj<n, then j=j+1. Repeat Step 2.Example 1.
To illustrate Algorithm LDR-Greedy, consider the following instance:n=5, a1=5, a2=4,a3=3,a4=2,a5=1,B=2,m=2 Due to FBLDR rule, job 1 and job 2 are placed in a batch, job 3 and job 4 are placed in a batch, and job 5 is placed in a batch. According to Algorithm LDR-Greedy, then we get that job 1 and job 2 are processed on machine 1, and job 3, job 4, and job 5 are processed on machine 2.(4)C11=C12=1×1+5=6,G11=C101+a1=6,G12=C11=6,C23=C24=1×1+3=4,G23=C221+a3=4,G24=C23=4,C25=8,G25=C241+a5=8.
Consider the schedule produced by Algorithm LDR-Greedy. It is worth noticing that the subschedule of the jobs processed on machineMi1≤i≤m is consistent with the one produced by the scheduling policy Mi. Similar to Nong et al. [24], we obtain the following theorem.Theorem 1.
Under the FBLDR coordination mechanism, there is a NE for the scheduling game problemPmB<n,pj=ajtCmax, and the NE is the schedule generated by the LDR-Greedy algorithm.Proof.
We prove the theorem by contradiction. Letτ be the schedule produced by the LDR-Greedy algorithm. If τ is not a NE, then assume that k is the smallest index which can complete earlier by switching from its current machine i∗k to machine i′k. According to the FBLDR rule and the LDR rule, each job k′ that starts its processing before job k has a deteriorating rate at least ak, and it means that Gi′jk≥Gi∗jk. But the assumption means that Gi′jk<Gi∗jk, which is a contradiction to i∗j=argmin1≤i≤mGij. Thus, τ is a NE.


## 3.1. Algorithm LDR-Greedy

Step 1. Fori=1,2,…,m, set Ci0=1, ni0=0,j=1Step 2. ComputeGij and i∗j=argmin1≤i≤mGij. Then, assign job j to the ⌈ni∗jj−1+1/B⌉-th batch of Mi∗jStep 3. Ifi=i∗j, set Ci∗jj=Gi∗jj, ni∗jj=ni∗jj−1+1; otherwise, set(3)Cij=Gij−1,nij=nij−1.Step 4. Ifj<n, then j=j+1. Repeat Step 2.Example 1.
To illustrate Algorithm LDR-Greedy, consider the following instance:n=5, a1=5, a2=4,a3=3,a4=2,a5=1,B=2,m=2 Due to FBLDR rule, job 1 and job 2 are placed in a batch, job 3 and job 4 are placed in a batch, and job 5 is placed in a batch. According to Algorithm LDR-Greedy, then we get that job 1 and job 2 are processed on machine 1, and job 3, job 4, and job 5 are processed on machine 2.(4)C11=C12=1×1+5=6,G11=C101+a1=6,G12=C11=6,C23=C24=1×1+3=4,G23=C221+a3=4,G24=C23=4,C25=8,G25=C241+a5=8.
Consider the schedule produced by Algorithm LDR-Greedy. It is worth noticing that the subschedule of the jobs processed on machineMi1≤i≤m is consistent with the one produced by the scheduling policy Mi. Similar to Nong et al. [24], we obtain the following theorem.Theorem 1.
Under the FBLDR coordination mechanism, there is a NE for the scheduling game problemPmB<n,pj=ajtCmax, and the NE is the schedule generated by the LDR-Greedy algorithm.Proof.
We prove the theorem by contradiction. Letτ be the schedule produced by the LDR-Greedy algorithm. If τ is not a NE, then assume that k is the smallest index which can complete earlier by switching from its current machine i∗k to machine i′k. According to the FBLDR rule and the LDR rule, each job k′ that starts its processing before job k has a deteriorating rate at least ak, and it means that Gi′jk≥Gi∗jk. But the assumption means that Gi′jk<Gi∗jk, which is a contradiction to i∗j=argmin1≤i≤mGij. Thus, τ is a NE.


## 4. An Upper Bound on the LPOA

In the section, we present an upper bound on the LPOA of the FBLDR coordination mechanism. The following lemma plays an important role in the LPOA analysis.Lemma 1.
There is an optimal schedule for the problemPmB<n, pj=ajtCmax such that the jobs in J are partitioned into batches by the FBLDR rule [21].Theorem 2.
For the scheduling problemPmB<n,pj=ajtCmax, the LPOA of the FBLDR coordination mechanism is at most 2−1/3maxm,B−2/3B.Proof.
We prove the theorem by contradiction. Assume that there are counterexamples with the LPOA strictly larger than2−1/3maxm,B−2/3B. Denote the counterexample I′ with the smallest number of jobs, and assume I′ has n′ jobs. Input I′ into the LDR-Greedy algorithm and let τ1 be the schedule returned, whose LPOA is strictly larger than 2−1/3maxm,B−2/3B. Assume that there are bi1≤i≤m batches processed on machine Mi1≤i≤m. Sort all the bi batches in nonincreasing order of their starting time on machine Mi, and then denote them by Bi1,Bi2,…,Bibi, respectively.
According to the work of Nong et al. [24], when the FBLPT rule and LPT-Greedy algorithm replaced by the FBLDR rule and LDR-Greedy algorithm, respectively, we can obtain two similar claims with the proof omitted.Claim 1.
There is only one batch completing atCmaxτ1, and the batch contains job n′ only.
Denote the longest deteriorating rate of jobs in batchBik by aik. We construct a new instance Ψ by adding B−1 jobs, each with a deteriorating rate of an′, to the smallest counterexample I′. Assume the set of jobs in Ψ is J1,J2,…,Jn, then we havean=an′.Claim 2.
Ψ is a counterexample, and τ is a NE of Ψ with LPOA strictly larger than 2−1/3maxm,B−2/3B.
Next, we analyzeτ, denote the completion time of Mh is Cmax in τ. Therefore, Ci≥Cmax/1+ahbh, for each i≠h. Hence, we get that(5)∏i=1m∏k=1bi1+aik=∏i=1mCi=∏i≠hmCi×Ch≥∏i≠hmCmax1+ahbh×Cmax=∏i=1mCmax11+ahbhm−1=Cmaxm11+ahbhm−1.
We then provide lower bound onCmax∗, denote the completion time of machine Mi in an optimal schedule by Ci∗. Obviously,(6)∏i=1mCmax∗≥∏i=1mCi∗≥∏j=1n1+aj1/B.
Hence,(7)Cmax∗≥∏j=1n1+aj1/mB.
When removing the job with longest deteriorating rate from each batch inτ, then we obtain that the total processing time of the remaining jobs is(8)∏j=1n1+aj∏i=1m∏k=1bi1+aik,where aik is the longest deteriorating rate of jobs in Bik, for each k=1,2,…,bi.
Consider the resulting batches on machineMi (1≤i≤m). Note that there are B−1 jobs remaining in Bik1≤k≤bi after removing the job with longest deteriorating rate from each batch in τ. Since Bik1≤k≤bi satisfy the FBLDR rule, we can see that for each k∈1,2,…,bi−1, the deteriorating rate of each job in batch Blk is at least ai,k+1, and the deteriorating rate of each job in batch Bibi is at least ahbh Hence, the total processing time of the remaining jobs on machine Mi is at least(9)∏k=2bi1+aik×1+ahbhB−1.
Therefore, we deduce that(10)∏j=1n1+aj∏i=1m∏k=1m1+aik≥∏i=1m∏k=2bi1+aik×1+ahbhB−1=∏i=1m∏k=1bi1+aikB−1∏i=1m1+ahbh1+ai1B−1.
Thus, we get that(11)∏j=1n1+aj≥∏i=1m∏k=1bi1+aikB∏i=1m1+ahbh1+ai1B−1.
SinceCmax∗≥1+ai1, for i=1,2,…m, we obtain that(12)∏i=1m1Cmax∗≤∏i=1m11+ai1.
By inequalities (1)–(4), we deduce that(13)Cmax∗mB≥2∏j=1n1+aj≥3∏i=1m∏k=1bi1+aikB∏i=1m1+ahbh1+ai1B−1≥1CmaxmB11+ahbhm−1B∏i=1m1+ahbh1+ai1B−1≥4CmaxmB11+ahbhm−1B1+ahbhmB−1∏i=1m1Cmax∗B−1=CmaxmB1+ahbhB−mCmax∗m1−B,which implies that(14)Cmax∗mB≥CmaxmB1+ahbhB−mCmax∗m1−B.
Hence, we get that(15)mBlnCmax∗≥mBlnCmax+B−mln1+ahbh+m1−BlnCmax∗.
And thus,(16)lnCmaxlnCmax∗≤1+m−BmBln1+ahbhlnCmax∗+mB−1mB.
In the remainder, we show that the LPOA at most2−1/3maxm,B−2/3B. We consider three cases as follows:Case 1.B>m and 1+ahbh3≤Cmax∗.Then,3ln1+ahbh≤lnCmax∗. From inequality (5), we get that(17)lnCmaxlnCmax∗≤2−1B=2−13B−23B=2−13maxm,B−23B.Case 2.B≤m and1+ahbh3≤Cmax∗.Then,3ln1+ahbh≤lnCmax∗. From inequality (5), we obtain that(18)lnCmaxlnCmax∗≤2+m−B3mB−1B=2−13m−23B=2−13maxm,B−23B.Case 3.1+ahbh3>Cmax∗.We consider two cases as follows:Case 3.1. Ifn≤mB, since each batch is full in τ, then we obtain that there is at most one batch on each machine. Therefore, Cmax≤max1≤i≤m1+ai1≤Cmax∗ we receive that lnCmax/lnCmax∗≤1.Case 3.2. Ifn>mB, then there is at least one machine which processes two batches in the optimal schedule. Hence, 1+ahbh2≤Cmax∗. Accordingly, we get that(19)2ln1+ahbh≤lnCmax∗.Claim 3.
Cmax∗≥Cmax/1+ahbh.
According ton≤2mB and each batch is full in τ, there are at most 2m batches in τ. If bh=2, we get that Cmax=1+ah11+ahbh. Thus, we receive that(20)Cmax∗≥1+ah1=Cmax1+ahbh.
Ifbh>2, then there is one machine Mr processes only one batch, and the batch is completed at 1+ar1. Owing to the fact that the completion time of a machine is at least Cmax/1+ahbh in τ, we obtain that 1+ar1≥Cmax/1+ahbh. According to Cmax∗≥1+ar1, we get that(21)Cmax∗≥1+ar1≥Cmax1+ahbh.
The claim holds. Thus, we receive that(22)lnCmaxlnCmax∗≤ln1+ahbhCmax∗lnCmax∗=1+ln1+ahbhlnCmax∗≤1+12=32.
The above discussion implies that LPOA is no more than2−1/3maxm,B−2/3B. Hence, Ψ is not a counterexample and causes a contradiction. The proof is completed.
We note that ifB=1, then the LPOA≤4/3−1/3m, i.e., the upper bound of the LPOA is exactly the worst case ratio of the LPT-Greedy algorithm.


## 5. Lower Bounds on the LPOA

In the section, we present lower bounds on the LPOA of the FBLDR coordination mechanism for the scheduling game problemPmB<n,pj=ajtCmax.Theorem 3.
Ifm≤B, there is an instance with a NE such that LPOA≥2−1/m; if m>B, there is an instance with a NE such that LPOA≥2−m+B−R/mB.Proof.
The proof of the theorem can be divided into the two cases.Case 1.m≤B.Consider the instanceI1. There are m−1dB+B jobs, each of B jobs has a deteriorating rate of d, and each of m−1dB jobs has a deteriorating rate of x=1+d1/d−1, where d=mk+1 for some positive integer k.Letτ be an assignment of the instance I1 is as follows: for each 1≤i≤m−1, the first batch on Mi consists of a job with a deteriorating rate of d and B−1 jobs each with a deteriorating rate of x=1+d1/d−1. The first batch on Mm consists of B−m+1 jobs each with a deteriorating rate of d and m−1 jobs each with a deteriorating rate of x=1+d1/d−1. For each 1≤i≤m−1, m−1kmB jobs each with a deteriorating rate of x=1+d1/d−1 are evenly assigned to the m machines; i.e., there are m−1k batches each of which consists of B jobs. It is easily seen that τ is a NE, and then, we obtain that Cmax=1+d1+xm−1k=1+d1+m−1k/d.Now, consider an assignmentτ∗ of the instance I1 in which a machine processes a batch consisting of B jobs each with a deteriorating rate of d and m−1dB jobs and each with a deteriorating rate of x=1+d1/d−1 are evenly assigned to the remaining machines. Hence, we get that Cmax∗=1+d.Therefore, we deduce that(23)lnCmaxlnCmax∗=ln1+d1+m−1k/dln1+d=1+m−1k/dln1+dln1+d=1+m−1kd=1+m−1kmk+1⟶2−1m,k⟶∞.Case 2.m>B.Consider the instanceI2. There are m jobs each with a deteriorating rate of d and m−ydB+B−R jobs each with a deteriorating rate of x=1+d1/d−1, where d=mk+1 for some positive integer k. Set(24)R=B,ifmmodB=0,mmodB,otherwise.Moreover, sety=⌈m/B⌉, and we can see that y=m+B−R/B.
Now, consider assignmentτ′∗ of the instance I2 which is as follows: for each 1≤i≤y−1, machine Mi processes a batch consists of B jobs each with a deteriorating rate of d; machine My processes a batch consists of R jobs each with a deteriorating rate of d and B−R jobs each with a deteriorating rate of x=1+d1/d−1; for each y+1≤i≤m, machine Mi processes d batches consists of B jobs each with a deteriorating rate of x=1+d1/d−1. Thus, we receive that Cmax∗=1+d.
Consider an assignmentτ′ of the instance I2 as follows: for each 1≤i≤m, the first batch on machine Mi consists of one job each with a deteriorating rate of d and B−1 jobs each with a deteriorating rate of x=1+d1/d−1, and then, m−ykmB jobs each with a deteriorating rate of x=1+d1/d−1 are evenly assigned to the m machines; that is, there are m−yk batches each of which consists of B jobs. It is easily seen that τ′ is a NE, and then, we get that Cmax=1+d1+xm−yk=1+d1+m−yk/d.
Therefore, we deduce that(25)lnCmaxlnCmax∗=ln1+d1+m−yk/dln1+d=1+m−yk/dln1+dln1+d=1+m−ykd=1+m−ykmk+1⟶2−ym,k⟶∞=2−m+B−RmB.
According to instanceI1 and instance I2, we provide the lower bound of the LPOA of the FBLDR coordination mechanism for the scheduling game problem PmB<n, pj=ajtCmax. We note that instance I1 and instance I2 are similar to Nong et al. [24], which has been used to provide the lower bound of the POA of the FBLPT coordination mechanism for the scheduling game problem PmB<nCmax. In addition, we find that the lower bound of the LPOA of the FBLDR coordination mechanism is exactly the lower bound of the POA of the FBLPT coordination mechanism.
In combination with Theorems2 and 3, we can obtain the following conclusion.Corollary 1.
Whenm=B, the LPOA of FBLDR coordination mechanism in Theorem 2 is tight.


## 6. Conclusion

In this paper, we consider the scheduling game problemPmB<n,pj=ajtCmax. For this scheduling game problem, we design fully batch longest deteriorating rate coordination mechanism and prove the existence of Nash equilibrium. We show that the fully batch longest deteriorating rate coordination mechanism has a logarithm price of anarchy at most 2−1/3maxm,B−2/3B. It is an interesting problem to design other coordination mechanisms for the problem.



---

*Source: 3780331-2022-12-17.xml*