Absolute bounds of list algorithms for parallel machines scheduling with unavailability periods

• DOI: http://doi.org/10.1111/itor.12589
• Author: Jihene Kaabi,Amine Mahjoub,Youssef Harrath
• Published date: 01 May 2021
• Date: 01 May 2021

Intl. Trans. in Op. Res. 28 (2021) 1594–1610

DOI: 10.1111/itor.12589

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Absolute bounds of list algorithms for parallel machines

scheduling with unavailability periods

Amine Mahjouba,b, Jihene Kaabicand Youssef Harratha,∗

aDepartment of Computer Science, College of Information Technology, University of Bahrain,Kingdom of Bahrain

bUniversity of Sousse, ISSAT Sousse, Tunisia

cDepartment of Information Systems, College of Information Technology, Universityof Bahrain, Kingdom of Bahrain

E-mail: amahjoub@uob.edu.bh [Mahjoub]; jkaapi@uob.edu.bh [Kaabi]; yharrath@uob.edu.bh [Harrath]

Received 26 February2018; received in revised form 3 June 2018; accepted 7 August 2018

Abstract

Weaddress the problem of scheduling a set of independent tasks on mparallel and identical machines subject

to an arbitrary number of unavailability periods.The objective is to minimize the makespan. The problem was

already investigated and was proved to be strongly NP-hard. Moreover, when the number of unavailability

periods per machine exceeds 1, there is no bound for the problem. We proved the existence of tight absolute

bounds when there is only one unavailability period per machine.In the general case, we proposed an efficient

binary linear program and proved that the list algorithm based on the largest processing time (LPT rule) has

a high performance. This study wasmotivated by grid scheduling, where a large number of independent jobs

is sent to computing resources whose availability cannot be guaranteed.

Keywords:identical parallel machines; resource unavailability; list scheduling; absolute performance bound

1. Introduction and motivation

Under economical and technological factors, parallel and distributed systems have evolved dramat-

ically. A distributed system is often defined with a set of machines (PCs, supercomputers, etc.) that

communicate through a high-speed network infrastructure. Morerecent technologies of distributed

systems include grid platforms in which machines are geographically distributed. Machines of recent

platforms are communicating through the Internet instead of local or metropolitan area networks.

Existing algorithms on grid systems aim to solve very large problems that could not be solved on

old and classical platforms. Users working on these types of systems do not know where their pro-

grams are running. The challenging problem is howto manage availableresources of such systems in

a transparent way so thatthe user abstraction level is kept. Tasksscheduling problem in parallel and

distributed systems consist of determining the processors on which available tasks will be executed

∗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.

A. Mahjoub et al. / Intl. Trans. in Op. Res. 28 (2021) 1594–1610 1595

and at what start times. The efficient use of grid desktop requires good managementand scheduling

of its resources. This means finding suitable schedules of available tasks on these resources. How-

ever, these resources are subject to perturbations and are not available at all times. Additionally, the

Internet, which is the communication network, is known to be unpredictable. Such perturbations

and unpredictability make it more complex to manage efficiently the global set of resources.

In this study, we consider a simple model of a desktop grid system. Wesuppose that the machines

are identical and are subject to an arbitrary number of unavailability periods that are known in

advance.We consider thatthe applications to be executed are composed of a set of independent tasks.

The goal is to execute efficiently the applications on such systems, which is equivalentto scheduling

a set of independent tasks on identical parallel machines subject to unavailability constraints. The

objective is to minimize the completion time of the last task or makespan.

In this paper, we developed tight absolute performance bounds for list schedules when there is

only one unavailability period in each machine. Furthermore, an efficient binary linear program

(BLP) was developed for the general case when there is more than one unavailability period in each

machine. Additionally, we proved that the list algorithm based on the LPT rulehasaveryhigh

performance for the problem.

The rest of the paper is organized as follows. Section 2 is dedicated to an overview of the literature.

In Section 3, the results for one unavailability period per machine will be presented. Section 4 will

be dedicated to the general case with any number of unavailabilities and an efficient BLP will be

proposed. An experimental study is detailed in Section 5. Section 6 concludes the studyand suggests

some perspectives for future works.

2. Lite rature revi ew

In traditional scheduling research, whether in parallel computing or in industrial engineering, it is

usually assumed that the machines are always available.This assumption can be reasonable for some

short-term situations. Nevertheless, for long-term situations, for various reasons such as refueling,

tool changing, and routine inspections, machines may be unavailable in some time periods. Thus,

this situation leads to coordination problems between job processing and machine availability. The

time interval where the machine under consideration is not available to process any job is called

unavailable interval of the machine. Although these unavailable intervals can be viewed as machine

maintenance periods, these machine unavailabilities are usually called tool changes and periodic

maintenance in the industrial engineering field (Akturk et al., 2003, 2004, 2007) and sometimes

called reservation or unavailabilities periods in the parallel computing area (Lee, 1991; Diedrich

et al., 2010; Xu et al., 2013).

For the remaining part of this section, let us denote by m,n,andC∗the number of machines, the

number of tasks, and the optimal value of the makespan, respectively.

The parallel machine scheduling problem without precedence constraints was proved to be NP-

complete (Garey and Johnson, 1979). However,several heuristics based on different techniques have

been proposed in the literature. Among these, list schedules are paramount (Graham, 1969), as they

are simple to design and fast to implement, and haverather good performances. A list algorithm con-

sists in first preparing a list with all the jobs. Then the uppermost job is assigned to the first available

machine, and the processcontinues until all the jobs in the list have been assigned. List schedules can

be adapted to noncontinuously available machines (due to unavailability periods or breakdowns).

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies