Mixed coordination mechanisms for scheduling games on hierarchical machines

• Date: 01 January 2021
• Author: Qianqian Chen,Zhiyi Tan
• DOI: http://doi.org/10.1111/itor.12558
• Published date: 01 January 2021

Intl. Trans. in Op. Res. 28 (2021) 419–437

DOI: 10.1111/itor.12558

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Mixed coordination mechanisms for scheduling games

on hierarchical machines

Qianqian Chen and Zhiyi Tan∗

Department of Mathematics, Zhejiang University, Hangzhou 310027, P.R. China

E-mail: chenqian@zju.edu.cn [Chen]; tanzy@zju.edu.cn [Tan]

Received 19 August2017; received in revised form 7 April 2018; accepted 9 April 2018

Abstract

In this paper, we study scheduling games under mixed coordination mechanisms on hierarchical machines.

The two scheduling policies involved are LG-LPT and LG-SPT,whereLG-LPT (resp., LG-SPT) policy

sequences jobs in nondecreasing order of their hierarchies, and jobs of the same hierarchy in nonincreasing

(resp.,nondecreasing) order of their processing times. Wefirst show the existence of a Nash equilibrium. Then

we present the price of anarchy and the price of stability for the games with social costs of minimizing the

makespan and maximizing the minimum machine load. All the bounds given in this paper are tight.

Keywords:scheduling; Nash equilibrium; parallel machines; price of anarchy

1. Introduction

We consider scheduling games on hierarchical machines under mixed coordination mechanisms.

Unlike in traditional scheduling problems, where jobs are assigned by a central decision maker

(Chaudhry and Khan, 2016; Deliktas et al., 2019; Kononov et al., 2020; Santos et al., 2019), each

job can individually choose a machine to be processed in scheduling games. The choices of all jobs

constitute a schedule. Each job is an independent selfish player aiming at minimizing its individual

cost, which is its own completion time on the machine it selects in the schedule. A schedule is a

Nash equilibrium (NE) if no job can reduce its cost by moving to a different machine (Koutsoupias

and Papadimitriou, 2009).

Apart from individual cost of each job, social cost is also of interest since it measures the utility

of the overall system. In fact, it plays a similar role as an objective in traditional scheduling theory.

Two of the most common social costs are to minimize the makespan and to maximize the minimum

machine load. Here, the makespan is the maximal completion time of all the jobs, and the load of a

∗Corresponding author.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

420 Q. Chen and Z. Tan/ Intl. Trans. in Op. Res. 28 (2021) 419–437

machine is the total processing time of jobs scheduled on it. Apparently, an NE may not be optimal

in terms of social cost due to the lack of central coordination, so two measurements can be used to

quantify the inefficiency of the NE: price of anarchy (PoA), and price of stability (PoS; Anshelevich

et al., 2008; Koutsoupias and Papadimitriou, 2009). For the games with social cost of minimizing

the makespan, the PoA (resp., PoS) of an instance is defined to be the ratio of the worst (resp., best)

NE’s social cost to the optimal social cost, whereas for the games with social cost of maximizing

the minimum machine load, in reverse, the PoA (resp., PoS) of an instance is defined to be the ratio

of the optimal social cost to the worst (resp., best) one in NEs. The PoA (resp., PoS) of the game is

the supremum value of the PoA (resp., PoS) of all instances. It is clear that PoA is greater than or

equal to PoS according to their definitions.

Since every job is trying to reduce its own cost, jobs on the same machine would compete to

be processed earlier. Thus, it is necessary for machines to order their jobs in sequence according

to a specific scheduling policy to both diminish the chaos caused by unrestricted competition and

improve the performance of the NE. All the policies of machines form a coordination mechanism

(Christodoulou et al., 2009; Immorlica et al., 2009). The important problems about coordination

mechanism include analyzing some common policies and designing effective mechanisms, which

can reduce the NE’s inefficiency by guiding the jobs’ selfish behaviors.

Two of the most popular scheduling policies are the longest processing time first (LPT)andthe

shortest processing time first (SPT). The LPT (resp., SPT) policy sequences jobs that select the

same machine in nonincreasing (resp., nondecreasing) order of their processing times. These jobs

are processed on the machine one by one in the above order nonpreemptively without any idle

time. Both policies have specific advantages. First, they are widely accepted and easy to implement

in practice. Second, they are local policies in which the processing order of the jobs on the same

machine is totally determined by their processing times. Thus, the policies can be implemented in

a completely distributed fashion (Immorlica et al., 2009). Moreover, the LPT and SPT policies

have a close relationship with the famous LPT and SPT algorithms in classical scheduling theory

(Conway et al., 1967; Graham, 1969). The set of NEs for the games in which all machines adopt the

LPT (resp., SPT) policy is precisely the set of schedules that can be generated by the LPT (resp.,

SPT) algorithm (Immorlica et al., 2009). Based on the earlier works on the worst-case performance

of the LPT and SPT algorithms (Graham, 1966, 1969; Csirik et al., 1992; Woeginger, 1997), the

PoA of the scheduling game where all machines adopt the LPT or SPT policy can be obtained

directly. Some of the results are summarized in Table 1.

The majority of papers about specific scheduling policies study pure coordination mechanisms

where all machines adopt the same policy. However, pure coordination mechanisms may not be

applicable in some practical applications. In the service industry, it is probably better to provide

the customers different service options. For example, the most important customers usually need to

be served for an extremely long time. The service provider would like to give them priorities to be

served first, since their businesses are more complicated and they can bring higher profits. However,

it is unwise to make all the windows work under the LPT policy because the service provider needs

to consider not only the profits but also the total waiting time of the customers. So, it is better to

arrange some windows to work under the SPT policy to ensure the satisfying degrees for a large

number of customers with small businesses.

Therefore, mixed coordination mechanisms, where machines may adopt different scheduling

policies, are worth investigating. Christodoulou et al. (2009) proposed a coordination mechanism

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies