A coordination mechanism for a scheduling game with parallel-batching machines

Abstract

In this paper we consider the scheduling problem with parallel-batching machines from a game theoretic perspective. There are m parallel-batching machines each of which can handle up to b jobs simultaneously as a batch. The processing time of a batch is the time required for processing the longest job in the batch, and all the jobs in a batch start and complete at the same time. There are n jobs. Each job is owned by a rational and selfish agent and its individual cost is the completion time of its job. The social cost is the largest completion time over all jobs, the makespan. We design a coordination mechanism for the scheduling game problem. We discuss the existence of pure Nash Equilibria and offer upper and lower bounds on the price of anarchy of the coordination mechanism. We show that the mechanism has a price of anarchy no more than $2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}$.

1 Introduction

With the development of the Internet, large-scale autonomous systems have become more and more common. The systems consist of many independent and selfish agents that compete for the usage of shared resources and act rationally on behalf of their own interest. Each agent has an individual cost and every system has some social cost. The selfish behavior of the agents results in a situation that can be characterized by some kind of equilibrium. Since the agents try to minimize their own cost, rather than the performance of the systems as a whole, such an equilibrium may lead to high cost compared to the global social optimum. A natural approach is designing protocols a priori in such a way that the selfish agents are induced to behavior that results in equilibria that nevertheless exhibit a good overall system performance. In this paper we are interested in a scheduling game on parallel-batching machines. Every agent owns a job and its individual cost is the completion time of its job. The social cost is the largest completion time over all jobs, the makespan.

Parallel-batching scheduling There are n jobs $\mathcal{{J}}=\{1,\dots , n\}$, where each job $j\in \mathcal{{J}}$ has a processing time $p_j$, which is a rational number. The jobs are indexed in non-increasing order of their processing times, i.e., $p_1\ge p_2\ge \cdots \ge p_n$. There are m parallel-batching machines $\mathcal{{M}}=\{M_1,\dots ,M_m\}$ each of which is a system that can handle up to b $(b<n)$ jobs simultaneously as a batch. The processing time of a batch is the time required for processing the longest job in the batch, and all the jobs in a batch start and complete at the same time. A schedule $\sigma$ is m series of batches

where: (i) $B_{i1},B_{i2},\dots , B_{ib_i}$ are the batches processed on machine $M_i$; (ii) the batches form a partition of $\mathcal{{J}}$, i.e., $\bigcup \limits _{i=1}^{m}\bigcup \limits _{k=1}^{b_i}B_{ik}=\mathcal{{J}}$; (iii) the starting time of each batch is definite. The makespan $C_{\max }(\sigma )$ of a schedule $\sigma$ is the maximal completion time over all jobs, and it is the social cost of the schedule. According to the scheduling notation introduced by Graham et al. (1979), the scheduling problem is expressed as $P|b<n|C_{\max }$.

Nash Equilibria and coordination mechanism What we described so far is a traditional scheduling problem, in which a central decision maker is equipped with all data of the problem and is asked to derive a feasible solution to optimize the social cost. In this paper we consider the scheduling problem from a game theoretic perspective as follows. Each of the n jobs is owned by an independent agent whose strategy is to choose a machine on which the job is to be processed (the term job and agent will be used interchangeably henceforth). The (pure) strategy set of a job is $\mathcal{{M}}=\{M_1,\dots ,M_m\}$. Each job is self-interested and does not care about the social optimum, its goal is to minimize its own completion time $C_j$. Each machine has a scheduling policy that determines how to assign all the jobs that select it to batches and specify the starting times of the resulting batches. A machine knows the IDs of those jobs that select it and their processing times. A machine does not know the processing times and strategies of the jobs that do not use it. The set of the policies of the machines is named as a coordination mechanism. All the data, including the policies of the machines and the processing times of the jobs, are publicly known to the jobs. A job will select a machine according to the policies of the machines and the processing time information of other jobs. Let $x_j\in \mathcal{{M}}$ be the strategy of job j, and let $x=(x_1,x_2,\dots ,x_n)$ denote a (pure) strategy profile of the jobs. If the coordination mechanism of the machines is specified, there is a one-to-one correspondence between the set of strategy profiles and the set of schedules of the jobs. That is, given a coordination mechanism and a strategy profile, one can specify how is $\mathcal{{J}}$ partitioned into batches and the completion time of each job in $\mathcal{{J}}$. Henceforth, we will use the term schedule and strategy profile interchangeably if we have specified a coordination mechanism. A pure Nash Equilibrium solution is a strategy profile $x=(x_1,x_2,\dots ,x_n)$ such that for every job j we have

$$\begin{aligned} C_j(x)\le C_j(x_j^{\prime },x_{-j}), \forall x_j^{\prime }\in \mathcal{{M}}\setminus \{x_j\}, \end{aligned}$$

where $C_j(x)$ is the completion time of j under strategy profile $x=(x_1,x_2,\dots ,x_n)$. The quality of a coordination mechanism is measured by the price of anarchy (PoA) (Koutsoupias and Papadimitriou 2009). It is defined as the ratio between the social cost (makespan) of the worst Nash Equilibrium and the social cost of an optimal schedule. The price of anarchy of a coordination mechanism of a scheduling game is defined by

$$\begin{aligned} PoA=\max \limits _{I\in { {\mathcal {G}}}}\max \limits _{x\in Nash(I)}\frac{C_{\max }(x)}{C_{\max }^*(I)}, \end{aligned}$$

where ${ {\mathcal {G}}}$ is the set of all instances of the scheduling game problem, Nash(I) is the set of all Nash Equilibria for I, and $C_{\max }^*(I)$ is the social cost of the optimal schedule of I.

Table 1 The price of anarchy for five different policies and scheduling problems

Related work Coordination mechanism design is introduced by Christodoulou et al. (2009). From then on many researchers are interested in the design of coordination mechanisms for scheduling game problems. They mainly study coordination mechanisms for four machine environments. To describe the machine environments, we denote the processing time of job j on machine $M_i$ by $p_{ij}$. The four machine environments are: (i) identical machine environment in which $p_{ij}=p_{kj}$ for each job j and machines $M_i$ and $M_k$; (ii) uniform or related machine environment in which every job j has a length $l_j$ and every machine $M_i$ has a speed $s_i$ such that $p_{ij}=l_j/s_i$; (iii) unrelated machine environment in which the processing times $p_{ij}$ are arbitrary positive numbers; (iv) restricted identical machine environment in which every job j comes with a length $l_j$ and a set of machines ${{\mathcal {S}}}_j$ such that $p_{ij}=l_j$ for $M_i\in {{\mathcal {S}}}_j$ and $p_{ij}=\infty$ otherwise. They analyzed the existence of pure Nash Equilibria under SPT, LPT, MAKESPAN, RANDOM and EQUI for certain machine environment and estimated the price of anarchy of the coordination mechanisms. SPT and LPT are policies that schedule the jobs without preemption respectively in order of increasing or decreasing processing times for each machine. MAKESPAN is a policy that each machine schedules its jobs in parallel by time-multiplexing and each job shares a fraction of CPU of the machine that is proportional to its processing time. RANDOM policy schedules the jobs in a random order without preemption. EQUI is a policy that each machine schedules its jobs in parallel by time-multiplexing and each job shares the same fraction until it is completed. The results are summarized in Table 1.

A number of researchers have studied the traditional parallel-batching scheduling problems that are under centralized situation (Deng et al. 2003; Lee et al. 1992; Lee and Uzsoy 1999; Ng et al. 2003; Potts and Kovalyov 2000; Uzsoy 1994; Zhang et al. 2001). Scheduling problem $P|b<n|C_{\max }$ is $NP-$hard in the strong sense even for $b=1$ (Lageweg et al. 1981). Researchers therefore turn to studying approximation algorithms for the problem. The quality of an approximation algorithm is often measured by its worst-case ratio: the smaller the ratio is, the better the algorithm will be. We say that an algorithm has a worst-case ratio $\rho$ (or is a $\rho$-approximation algorithm) if for any input instance, it always returns in polynomial time of the input size a feasible solution with an objective value not greater than $\rho$ times of the optimal value. Lee et al. (1992) considered the problem $P|b<n|C_{\max }$ and developed a $\frac{4}{3}-\frac{1}{3m}$-approximation algorithm, where m is the number of batching machines. When $b=1$ the problem $P|b<n|C_{\max }$ is $P||C_{\max }$, which is a scheduling problem considering how to assign jobs to parallel machines and process them without preemption such that the makespan is minimized. A well known approximation algorithms for $P||C_{\max }$ is the LPT-Greedy algorithm (Graham 1969). The algorithm assigns at time 0 the m longest jobs on the m machines and after that, whenever a machine is free, put the longest job among those not yet processed on the machine. The algorithm has a worst-case ratio of $\frac{4}{3}-\frac{1}{3m}$.

Our contribution In this paper we design a coordination mechanism for the scheduling game problem $P|b<n|C_{\max }$. We discuss the existence of pure Nash Equilibria and show that the mechanism has a price of anarchy no more than $2-2/(3b)-1/(3\max \{m,b\})$.

2 The FBLPT coordination mechanism

In this section we present a coordination mechanism, named FBLPT (Full Batch Longest Processing Time), for the scheduling game problem $P|b<n|C_{\max }$. Before explaining the coordination mechanism, we first describe the FBLPT rule, which is a rule to assign jobs into batches.

Lee et al. (1992) prove that the FBLPT rule is a rule to assign jobs into batches such that the total processing time of the resulting batches is minimized. Based on this insight, we design a coordination mechanism as follows.

2.1 The existence of pure Nash Equilibrium

Consider the LPT-Greedy algorithm for the scheduling problem $P|b<n|C_{\max }$. The idea of the algorithm is sorting the jobs in non-increasing order of their processing times and then assigning the jobs one by one into some batch and processing the resulting batches greedily. Define a subschedule to be in state j if jobs $1, 2, \dots , j$ have been scheduled. Job $j+1$ will be allocated in the last batch (if the batch is not full) or in a new batch (if the last batch has been full) of a machine and the machine will be the one that completes the processing of the job as early as possible. Denote the completion time on machine $M_i$ in state j by $L_i(j)$. It is equal to the total processing time of the batches on machine $M_i$ in state j. Let $N_i(j)$ be the number of jobs scheduled on machine $M_i$ in state j. Let

$$\begin{aligned} T_i(j+1)=\left\{ \begin{array}{ll} L_i(j)+p_{j+1}, &{}\quad \text{ if } N_i(j)\ (\text{ mod })\ b=0;\\ L_i(j),&{}\quad \text{ otherwise }. \end{array}\right. \end{aligned}$$

Consider the schedule produced by the LPT-Greedy algorithm. It is not difficult to see that the subschedule of the jobs processed on machine $M_i$ $(1\le i\le m)$ is consistent with the one produced by the Scheduling Policy of $M_i$. We prove the following theorem.

Theorem 1

The schedule generated by the LPT-Greedy algorithm is a pure Nash Equilibrium of the scheduling game problem $P|b<n |C_{\max }$ under the FBLPT coordination mechanism.

Proof

Let $\sigma$ be the schedule produced by the Job-Greedy algorithm. We show that $\sigma$ is a Nash Equilibrium by induction. Job 1 starts at time 0. It has no incentive to switch to other machines. Suppose that all jobs $1, 2, \dots , k$ have no incentive to switch to other machines. We consider job $k+1$. Since a machine assigns all the jobs that have selected it into batches by FBLPT rule and processes the batches in the LPT order, job $k+1$ cannot start earlier than jobs $1, 2, \dots , k$. For the same reason, the choices of job $k+2, \dots , n$ have no influence on job j. The machine for job $k+1$ in state $k+1$ is the best selection and it has no incentive to switch to other machines. Thus $\sigma$ is a Nash Equilibrium. $\square$

2.2 An upper bound on the price of anarchy

To analyze the price of anarchy of the FBLPT coordination mechanism, we need the following lemma.

Lemma 2

[See Lee et al. (1992)] There is an optimal schedule for the problem $P|b<n|C_{\max }$ such that the jobs in ${\mathcal {J}}$ are partitioned into batches by the FBLPT rule.

Theorem 3

The price of anarchy of the FBLPT coordination mechanism is at most

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}\le 2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}. \end{aligned}$$

Proof

We prove the result by contradiction. Assume that there are counterexamples each of which has a Nash Equilibrium with a makespan strictly larger than $2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}$ times of the optimum. Consider the one with the smallest number of jobs. Denote the counterexample by $I_1$ and assume that it has $n_1$ jobs. Let $\sigma _1$ be the worst Nash Equilibrium of $I_1$, whose makespan is strictly larger than $2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}$ times of the optimum. Let us have a look at the structure of $\sigma _1$. Assume that there are $b_i$ $(1\le i\le m)$ batches processed on $M_i$. Sort them in non-increasing order of their starting times and denote them by $B_{i1}, B_{i2},\dots , B_{ib_i}$, respectively. $\square$

Claim 1

There is only one batch completing at $C_{\max }(\sigma _1)$ and it consists of only one job.

If it is not the case, consider the batches that complete at $C_{\max }(\sigma _1)$. Let $B_{lb_l}$ be the batch with the earliest starting time and suppose that it starts at $t^*$. Except the longest job in batch $B_{lb_l}$, discard all jobs that start at or after $t^*$ in $\sigma _1$. Consider the resulting schedule. We obtain a new instance $I_2$ with a smaller number of jobs. All the jobs that start before $t^*$ is larger than the job remaining in $B_{lb_l}$, and all the batches that start before $t^*$ is full ( otherwise the job in $B_{lb_l}$ can reduce its completion time by unilaterally changing its strategy in $\sigma _1$). Therefore, the resulting schedule is also a Nash Equilibrium for instance $I_2$. The makespan of it is equal to $C_{\max }(\sigma _1)$ and the optimal makespan of $I_2$ is not greater than that of $I_1$. Thus, $I_2$ is a counterexample with fewer jobs than $I_1$, a contradiction.

The claim together with the fact that all the batches that start before $t^*$ is full means that $n_1 \ (\text{ mod })\ b=1$ and thus $B_{lb_l}=\{n_1\}$.

Denote the processing time of batch $B_{ik}$ by $P_{ik}$. We construct a new instance ${\mathcal {F}}$ by adding $b-1$ jobs, each with a processing time of $p_{n_1}$, to the smallest counterexample $I_1$. Assume that the set of jobs in ${\mathcal {F}}$ is $\{1,2,\dots ,n\}$. Clearly, $n \ (\text{ mod })\ b=0$. Consider a schedule of ${\mathcal {F}}$ by adding the $b-1$ jobs to the batch $B_{lb_l}$ in $\sigma _1$. Denote it by $\sigma$. Since the processing time of the added $b-1$ jobs is $p_{n_1}$, which is the smallest processing time. No job in $\sigma$ can reduce its completion time by unilaterally changing its strategy. Therefore, $\sigma$ is a Nash Equilibrium for ${\mathcal {F}}$. It is not difficult to see that $\sigma$ is equal to $\sigma _1$ in the sense that in $\sigma$ the number of the batches processed on each $M_i$ $(1\le i\le m)$ is the same as in $\sigma _1$ and the processing times of the batches are equal correspondingly. Thus, the makespan of $\sigma$ is equal to the makespan of $\sigma _1$. Without causing confusion, denote the makespan of $\sigma$ by $C_{\max }$ and denote the batches processed on $M_i$ in $\sigma$ by $B_{i1}, B_{i2},\dots , B_{ib_i}$, respectively.

On the other hand, consider the optimal schedule of ${\mathcal {F}}$. Let $\sigma ^*$ be the optimal schedule of $I_1$ that is described in Lemma 2. Sort the batches of $\sigma ^*$ in non-increasing order of their processing times and obtain a list $L^{*}=(B_{1}^{*},B_{2}^{*},\dots ,B_{d}^{*})$, where $d=\lceil \frac{n_1}{b}\rceil$. Partition the jobs in ${\mathcal {F}}$ into batches by FBLPT rule. Sort them in non-increasing order of their processing times and obtain a list $L=(B_1,B_2,\dots ,B_e)$, where $e=\lceil \frac{n}{b}\rceil$. Noting that $n_1 \ (\text{ mod }) \ b=1$ and $n=n_1+b-1$, we have $\lceil \frac{n_{1}}{b}\rceil = \lceil \frac{n}{b}\rceil$, i.e., $d=e$. For each $1\le k\le d$ the processing time of $B_{k}^{*}$ is equal to that of $B_k$. By Lemma 2, we can deduce that the optimum value of ${\mathcal {F}}$, denoted by $C_{\max }^*$, is equal to the optimum value of $I_1$. Therefore, the following claim holds.

Claim 2

${\mathcal {F}}$ is a counterexample and $\sigma$ is a Nash Equilibrium of ${\mathcal {F}}$ with a makespan strictly larger than $2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}$ times of the optimum.

In the following we analyze $\sigma$. We first give an upper bound on $C_{\max }$. In $\sigma$ the completion time of $M_l$ is $C_{\max }$ and the completion time of each other machine $M_i$ $(i\ne l)$ is at least $C_{\max }-P_{lb_l}$. We have

$$\begin{aligned} \sum \limits _{i=1}^{m}\sum \limits _{k=1}^{b_i}P_{ik}\ge & {} (m-1)(C_{\max }-P_{lb_l})+C_{\max }\nonumber \\= & {} m C_{\max }-(m-1)P_{lb_l}. \end{aligned}$$

(1)

We then provide lower bounds on $C_{\max }^*$. Clearly,

$$\begin{aligned} C_{\max }^*\ge \frac{\sum \limits _{j=1}^{n}p_j}{mb}. \end{aligned}$$

(2)

Let us give a lower bound on $\sum \limits _{j=1}^{n}p_j$. From each batch in $\sigma$ remove the longest job. Then the total processing time of the remaining jobs is

$$\begin{aligned} \sum \limits _{j=1}^{n}p_j-\sum \limits _{i=1}^{m}\sum \limits _{k=1}^{b_i}P_{ik}. \end{aligned}$$

For each $1\le i\le m$, consider the resulting batches on machine $M_i$. Note that each batch in $\sigma$ is full. There are $b-1$ jobs remaining in $B_{ik}$ ( $1\le k\le b_i$) after removing the longest job from it. Further, since $B_{i1}, B_{i2},\dots , B_{ib_i}$ satisfy the FBLPT rule, one can see that for each $k\in \{1,2,\dots ,b_i-1\}$, the processing time of each job in batch $B_{ik}$ is at least $P_{i,k+1}$ and the processing time of each job in batch $B_{ib_i}$ is at least $P_{lb_l}$. Thus the total processing time of the remaining jobs on machine $M_i$ is at least

$$\begin{aligned} (b-1)\left( \sum \limits _{k=2}^{b_i}P_{ik}+P_{lb_l}\right) . \end{aligned}$$

Thus

$$\begin{aligned} \sum \limits _{j=1}^{n}p_j-\sum \limits _{i=1}^{m}\sum \limits _{k=1}^{b_i}P_{ik}\ge & {} (b-1)\left( \sum \limits _{i=1}^{m}\sum \limits _{k=2}^{b_i}P_{ik}+mP_{lb_l}\right) \\= & {} (b-1)\left( \sum \limits _{i=1}^{m}\sum \limits _{k=1}^{b_i}P_{ik}-\sum \limits _{i=1}^{m}P_{i1}+mP_{lb_l}\right) ,\\ \end{aligned}$$

implying that,

$$\begin{aligned} \sum \limits _{j=1}^{n}p_j \ge b\sum \limits _{i=1}^{m}\sum \limits _{k=1}^{b_i}P_{ik}-(b-1)\left( \sum \limits _{i=1}^{m}P_{i1}- mP_{lb_l}\right) . \end{aligned}$$

(3)

Since $C_{\max }^{*}\ge P_{i1}$ for $i=1,2,\dots ,m$, we have

$$\begin{aligned} mC_{\max }^*\ge \sum \limits _{i=1}^{m}P_{i1}. \end{aligned}$$

(4)

By inequalities (2), (3), (1) and (4), we have the following result:

$$\begin{aligned} mbC_{\max }^*\ge & {} \sum \limits _{j=1}^{n}p_j\\\ge & {} b\sum \limits _{i=1}^{m}\sum \limits _{k=1}^{b_i}P_{ik}-(b-1)\left( \sum \limits _{i=1}^{m}P_{i1}- mP_{lb_l}\right) \\\ge & {} b\left( mC_{\max }-(m-1)P_{lb_l}\right) -(b-1)m\left( C_{\max }^*-P_{lb_l}\right) ,\\ \end{aligned}$$

which implies that

$$\begin{aligned} mbC_{\max }\le m(2b-1)C_{\max }^*+(m-b)P_{lb_l}, \end{aligned}$$

and thus

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}\le 2-\frac{1}{b}+(\frac{1}{b}-\frac{1}{m})\frac{P_{lb_l}}{C_{\max }^*}. \end{aligned}$$

(5)

In the sequel we show that the ratio $\frac{C_{\max }}{C_{\max }^*}$ is not greater than $2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}$. We distinguish three cases to discuss.

Case 1 $C_{\max }^*\ge 3P_{lb_l}$ and $b\le m$.

From inequality (5), we have

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}\le & {} 2-\frac{1}{b}+\frac{1}{3}(\frac{1}{b}-\frac{1}{m})\\= & {} 2-\frac{2}{3b}-\frac{1}{3m}\\= & {} 2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}. \end{aligned}$$

Case 2 $C_{\max }^*\ge 3P_{lb_l}$ and $b>m$.

Then $\frac{1}{b}-\frac{1}{m}<0$ and we have

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}\le & {} 2-\frac{1}{b}+(\frac{1}{b}-\frac{1}{m})\frac{P_{lb_l}}{C_{\max }^*}\\< & {} 2-\frac{1}{b}\\= & {} 2-\frac{2}{3b}-\frac{1}{3b}\\= & {} 2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}. \end{aligned}$$

Case 3 $C_{\max }^*<3P_{lb_l}.$

Note that $P_{lb_l}$ is the processing time of the shortest job in ${\mathcal {J}}$. The inequality $C_{\max }^{*}<3P_{lb_l}$ implies that in the optimal schedule of ${\mathcal {F}}$ there are at most two batches on each machine and thus $n\le 2mb$.

If $n\le mb$, recalling that each batch is full in $\sigma$, we can deduce that there is at most one batch on each machine. Hence

$$\begin{aligned} C_{\max }\le \max \limits _{1\le i\le m}\{P_{i1}\} \le C_{\max }^*, \end{aligned}$$

which means that $\frac{C_{\max }}{C_{\max }^*} \le 1$.

If $n>mb$, there is at least one machine which processes two batches in the optimal schedule. Thus $C_{\max }^*\ge 2P_{lb_l}.$ We claim that

$$\begin{aligned} C_{\max }^*\ge C_{\max }-P_{lb_l}. \end{aligned}$$

Since $n\le 2mb$ and each batch in $\sigma$ is full, there are at most 2m batches in $\sigma$. If $b_l=2$ then $C_{\max }=P_{l1}+P_{lb_l}$ and thus

$$\begin{aligned} C_{\max }^*\ge P_{l1}\ge C_{\max }-P_{lb_l}. \end{aligned}$$

If $b_l\ge 3$, there exists one machine $M_a$ which processes only one batch and the batch is completed at $P_{a1}$. Recalling that in $\sigma$ the completion time of a machine is at least $C_{\max }-P_{lb_l}$, we have

$$\begin{aligned} P_{a1}\ge C_{\max }-P_{lb_l}. \end{aligned}$$

Together with the fact that $C_{\max }^*\ge P_{a1}$, we have

$$\begin{aligned} C_{\max }^*\ge P_{a1}\ge C_{\max }-P_{lb_l}. \end{aligned}$$

In both cases the claim follows. Therefore,

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}\le 1+\frac{P_{lb_l}}{C_{\max }^*}\le \frac{3}{2}. \end{aligned}$$

The above discussion implies that

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}\le 2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}. \end{aligned}$$

Thus $\sigma$ is not a Nash Equilibrium of ${\mathcal {F}}$ with a makespan strictly larger than $2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}$ times of the optimum, leading to a contradiction. This completes the proof of the theorem. $\square$

Interestingly, if $b=1$ we have

$$\begin{aligned} 2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}=\frac{4}{3}-\frac{1}{3m}, \end{aligned}$$

which is exactly the worst-case ratio of the LPT-Greedy algorithm.

2.3 Lower bounds on the price of anarchy

To give a lower bound on the price of anarchy of the mechanism, we only need to offer an instance and estimate the ratio between the makespan of a Nash Equilibrium and the optimum. We distinguish two cases to discuss.

Case 1 $m\le b$.

Consider the following instance. There are $b(m-1)X+b$ jobs, where $X=mk+1$ for some positive integer k. b jobs are long and each of them has a processing time of X. $b(m-1)X$ jobs are short and each of them has a processing time of 1.

We can see that the optimal schedule of the instance is as follows: a machine processes a batch consisting of all the long jobs, and each of the other machines processes X batches each consisting of b short jobs. Thus the optimal makespan is $C_{\max }^*=X=mk+1$. Consider a schedule $\pi$ as follows. For each $1\le i\le m-1$, the first batch processed on $M_i$ is a batch that contains one long job and $b-1$ short jobs. The first batch on $M_m$ consists of $b-m+1$ long jobs and $m-1$ short jobs. On each machine, following the long batch there are $(m-1)k$ batches each of which consists of b short jobs. It is easy to see that $\pi$ is a Nash Equilibrium and its makespan is

$$\begin{aligned} C_{\max }= X+(m-1)k=(2m-1)k+1. \end{aligned}$$

Thus

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}= \frac{(2m-1)k+1}{mk+1}\rightarrow 2-\frac{1}{m},\ \hbox {as} \ k\rightarrow \infty . \end{aligned}$$

Specially, if $m=b$ we have

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}=\frac{(2b-1)k+1}{bk+1}\rightarrow 2-\frac{1}{b},\ \hbox {as} \ k\rightarrow \infty . \end{aligned}$$

Case 2 $m> b$.

Define r to be a positive integer such that

$$\begin{aligned} r=\left\{ \begin{array}{ll} b, &{}\quad \text{ if } \ m\ \text{(mod) }\ b=0; \\ m\ \text{(mod) }\ b,&{}\quad \text{ otherwise }. \end{array}\right. \end{aligned}$$

Set $z=\lceil m/b\rceil$, and we have $z=\frac{m+b-r}{b}$. Consider the following instance. There are m long jobs each with a processing time of X, as before, $X=mk+1$ for some positive integer k. Besides the long jobs, there are

$$\begin{aligned} (m-z)bX+b-r \end{aligned}$$

short jobs and each of them has a processing time of 1.

We can see that the optimal schedule of the instance is as follows: for each $1\le i\le z-1$, machine $M_i$ processes a batch consisting of b long jobs; $M_z$ processes a batch containing r long jobs and $b-r$ short jobs; for each $z+1\le i\le m$, machine $M_i$ processes X batches each consisting of b short jobs. Thus the optimal makespan is $C_{\max }^*=X=mk+1$. Consider a schedule $\pi ^\prime$ as follows. For each $1\le i\le m$, machine $M_i$ processes a batch containing one long job and then $b-1$ shorts jobs and $(m-z)k$ batches each with b short jobs. Clearly, $\pi ^\prime$ is a Nash Equilibrium and its makespan is

$$\begin{aligned} C_{\max }=X+(m-z)k=(2m-z)k+1. \end{aligned}$$

Thus

$$\begin{aligned} \frac{C_{\max }}{C_{\max }^*}=\frac{(2m-z)k+1}{mk+1} \rightarrow 2-\frac{z}{m}=2-\frac{\frac{m+b-r}{b}}{m}=2-\frac{1}{b}-\frac{1}{m}+\frac{r}{mb}, \hbox {as} \ k \rightarrow \infty . \end{aligned}$$

In summary, we have proved the following theorem.

Theorem 4

If $m\le b$ there is an instance with a Nash Equilibrium such that $\frac{C_{\max }}{C_{\max }^*} \ge 2-\frac{1}{m}$; If $m>b$ there is an instance with a Nash Equilibrium such that $\frac{C_{\max }}{C_{\max }^* }\ge 2-\frac{1}{b}-\frac{1}{m}+\frac{r}{mb}$. $\square$

Corollary 5

When $m=b$ the analysis of the price of anarchy of the FBLPT coordination mechanism in Theorem 3 is tight.

Proof

Note that $2-\frac{2}{3b}-\frac{1}{3\max \{m,b\}}=2-\frac{1}{b}= 2-\frac{1}{m}$ when $m= b$. The result follows. $\square$