Multitasking scheduling with multiple rate‐modifying activities

• Published date: 01 September 2019
• Date: 01 September 2019
• Author: Chengbin Chu,Zhanguo Zhu,Jinlin Li,Ming Liu*
• DOI: http://doi.org/10.1111/itor.12393

Intl. Trans. in Op. Res. 26 (2019) 1956–1976

DOI: 10.1111/itor.12393

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Multitasking scheduling with multiple rate-modifying activities

Zhanguo Zhua,b, Ming Liu*c, Chengbin Chudand Jinlin Lie

aCollege of Economics and Management, Nanjing Agricultural University,Nanjing 210095, P.R. China

bLaboratoire d’Informatique,Biologie Int ´

egrative et Syst`

emes Complexes (IBISC), EA 4526, Universit´

ed’EvryVal

d’Essonne, 91020 Evry Cedex, France

cSchool of Economics & Management, TongjiUniversity, Shanghai 200092, P.R. China

dLaboratoire G´

enie Industriel, Ecole Centrale Paris, GrandeVoie des Vignes, 92295, Chˆ

atenay-Malabry Cedex, France

eBusiness School, Central South University, Changsha 410083, P.R. China

E-mail: Zhanguo.Zhu@ibisc.univ-evry.fr [Zhu]; minyivg@gmail.com [Liu*]; chengbin.chu@ecp.fr [Chu];

lijinlin@csu.edu.cn [Li]

Received 3 September 2016; receivedin revised form 3 December 2016; accepted 10 December 2016

Abstract

This paper considers scheduling problems with human operators having the option to perform multiple rate-

modifying activities (MRMAs) while they arecarrying out multitasking. Thus, the processing of a selected task

suffers jointly from interruptions byother available but unfinished tasks and MRMAs. Twotypes of objective

functions are studied: single-criterion minimizing the total completion time, and multicriteria minimizing a

weighted combination of the total completion time, the total absolute differences in completion times, and a

weighted combination of the total waiting time and the total absolutedifferences in waiting times. We propose

optimal solution algorithms for all the studied problems and also analyze some special cases of them.

Keywords:scheduling; multitasking; multiple RMAs; algorithm

1. Introduction

This paper deals with the multitasking scheduling problem that has been initiated by Hall et al.

(2015). It is a scheduling model where humans rather than machines process multiple tasks at one

time: A number of ntasks need to be processed by a work center, and the processing of the selected

task suffers from the interruption of other available but unfinished tasks. This problem originates

in a behavioral phenomenon known as multitasking that can almost be observed numerous times

each day in many fields, for example, administration, manufacturing, and project management,

and so on. In Hall et al.’s work, several principal motivations for multitasking are identified, some

new algorithms are proposed since the classical scheduling algorithms fail to solve the scheduling

problems with multitasking,and the cost increase and value gained due to multitasking are analyzed.

*Corresponding author

C

2017 The Authors.

International Transactionsin Operational Research C

2017 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.

Z. Zhu et al. / Intl. Trans. in Op. Res. 26 (2019) 1956–1976 1957

Although the introduction of the behavioral phenomenon of multitasking makes the problem more

practical, other important issues incurred by human operators at the same time are missed in their

work. Once tasks are processed byhumans rather than machines, many important behavioralissues

arise in addition to multitasking (Hall et al., 2016). One of the most important issues is that humans

usually need several breaks to recover, called multiple rate-modifying activities (MRMAs), while

they carry out multitasking (Lodree and Geiger, 2010).

As an important feature in workplaces, multitasking-related issues have attracted growing atten-

tion of different fields since the early description by Philip Stanhope to his son in a 1740’s letter.

In the field of experimental psychology, Pashler (1994) finds that experimental subjects are unable

to focus their attention when asked to multitask, which may lower their productivity. In the field

of economics, Radner and Rothschild (1975) study task prioritization by a single worker while

Coviello et al. (2014) analyze the phenonemon of task juggling (frequently called multitasking)

whereby a single worker switches from one project to another frequently. In the field of opera-

tions management, Diwas Singh (2014) investigates empirically the effect of multitasking on overall

worker performance with microlevel operational dataof the multitasking behavior in the emergency

department. In the field of scheduling, as discussed above, Hall et al. (2015) initiate the multitasking

problem, followed by Sum et al. (2015), Hall et al. (2016), and Zhu et al. (2017).

Another research direction related to our work is scheduling problem with RMA, which was first

introduced by Lee and Leon (2001), motivated by the practical phenomenon in electronic industry.

In their work, it is modeled as a special case of machine maintenance (Ma et al., 2010), which can

change the production rate of a machine, and the starting time of it is also a decision variable.

Mosheiov and Oron (2006) and Gordon and Tarasevich (2009) extend their work by considering

RMA scheduling and due-date assignment simultaneously, while Yang et al. (2010) analyze RMA

scheduling with due-window.

Zhao and Tang (2012) integratethe deterioration of jobs into RMA scheduling with due-window.

Ji et al. (2014) study scheduling problem of deteriorating jobs on a single machine with due-date

assignment, resource allocation, and an RMA, and proposed a polynomial-time algorithm to

solve it. There also exist other closely related works, such as Ozturkoglu and Bulfin (2011), and

Yin et al. (2012). Different from the above literature discussing RMA from the point of view of

machine, Lodree and Geiger (2010) and Ozturkoglu and Bulfin (2012) investigate the scheduling

problem from the point of view of RMA of human operators, analyzing the effect of RMA on

human-based scheduling system. Zhu et al. (2017) combine multitasking to the RMA of human

operators in scheduling problems, and propose the optimal solution algorithm for several classical

objectives based on Hall et al. (2015) and Lodree and Geiger (2010). Note thatall literature on RMA

discussed so far is restricted to scheduling with single RMA. In practice,the human operators usually

engage MRMAs (e.g., Ji and Cheng, 2010; Chen et al., 2014). Taking the practical administrative

planning scenario illustrating scheduling with multitasking by Hall et al. (2015) as an example, an

administrator usually engages MRMAs while she is carrying out multitasking under the support

of her team members. To our best knowledge, there is still no literature on multitasking scheduling

problems with MRMAs, although it is significant in realistic applications. In this work, we fill

this gap by addressing multitasking scheduling problems with M RMAs. Different from previous

multitasking scheduling related literature, we also investigate the multicriteria objectives consisting

of some nonregular objective functions in addition to the regular ones, which makes the problem

under study more practical.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies