Multitasking via alternate and shared processing: Algorithms and complexity

Nicholas G. Hall; Joseph Y.-T. Leung; Chung-Lun Li

doi:10.1016/j.dam.2016.03.018

Multitasking via alternate and shared processing: Algorithms and complexity

Nicholas G. Hall, Joseph Y.-T. Leung, Chung-Lun Li^*

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

31 Citations (Scopus)

Abstract

This work is motivated by disruptions that occur when jobs are processed by humans, rather than by machines. For example, humans may become tired, bored, or distracted. This paper presents two scheduling models with multitasking features. These models aim to mitigate the loss of productivity in such situations. The first model applies "alternate period processing" and aims either to allow workers to take breaks or to increase workers' job variety. The second model applies "shared processing" and aims to allow workers to share a fixed portion of their processing capacities between their primary tasks and routine activities. For each model, we consider four of the most widely studied and practical classical scheduling objectives. Our purpose is to study the complexity of the resulting scheduling problems. For some problems, we describe a fast optimal algorithm, whereas for other problems an intractability result suggests the probable nonexistence of such an algorithm. © 2016 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	41-58
Journal	Discrete Applied Mathematics
Volume	208
DOIs	https://doi.org/10.1016/j.dam.2016.03.018
Publication status	Published - 31 Jul 2016
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

The authors thank the three anonymous referees for their helpful comments and suggestions. This work is supported in part by the Summer Fellowship Program, Fisher College of Business, The Ohio State University, to the first author; in part by the National Science Foundation under grant CMMI-0969830, to the second author; and in part by Research Grants Council of Hong Kong under grant PolyU5195/13E, to the third author.

Research Keywords

Efficient algorithm
Intractability
Motivations for multitasking
Scheduling

RGC Funding Information

RGC-funded

Access Output

10.1016/j.dam.2016.03.018Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{41fbf2e97d124592bd4968c6bd9cf76c,

title = "Multitasking via alternate and shared processing: Algorithms and complexity",

abstract = "This work is motivated by disruptions that occur when jobs are processed by humans, rather than by machines. For example, humans may become tired, bored, or distracted. This paper presents two scheduling models with multitasking features. These models aim to mitigate the loss of productivity in such situations. The first model applies {"}alternate period processing{"} and aims either to allow workers to take breaks or to increase workers' job variety. The second model applies {"}shared processing{"} and aims to allow workers to share a fixed portion of their processing capacities between their primary tasks and routine activities. For each model, we consider four of the most widely studied and practical classical scheduling objectives. Our purpose is to study the complexity of the resulting scheduling problems. For some problems, we describe a fast optimal algorithm, whereas for other problems an intractability result suggests the probable nonexistence of such an algorithm. {\textcopyright} 2016 Elsevier B.V. All rights reserved.",

keywords = "Efficient algorithm, Intractability, Motivations for multitasking, Scheduling",

author = "Hall, {Nicholas G.} and Leung, {Joseph Y.-T.} and Chung-Lun Li",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2016",

month = jul,

day = "31",

doi = "10.1016/j.dam.2016.03.018",

language = "English",

volume = "208",

pages = "41--58",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Multitasking via alternate and shared processing

T2 - Algorithms and complexity

AU - Hall, Nicholas G.

AU - Leung, Joseph Y.-T.

AU - Li, Chung-Lun

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2016/7/31

Y1 - 2016/7/31

N2 - This work is motivated by disruptions that occur when jobs are processed by humans, rather than by machines. For example, humans may become tired, bored, or distracted. This paper presents two scheduling models with multitasking features. These models aim to mitigate the loss of productivity in such situations. The first model applies "alternate period processing" and aims either to allow workers to take breaks or to increase workers' job variety. The second model applies "shared processing" and aims to allow workers to share a fixed portion of their processing capacities between their primary tasks and routine activities. For each model, we consider four of the most widely studied and practical classical scheduling objectives. Our purpose is to study the complexity of the resulting scheduling problems. For some problems, we describe a fast optimal algorithm, whereas for other problems an intractability result suggests the probable nonexistence of such an algorithm. © 2016 Elsevier B.V. All rights reserved.

AB - This work is motivated by disruptions that occur when jobs are processed by humans, rather than by machines. For example, humans may become tired, bored, or distracted. This paper presents two scheduling models with multitasking features. These models aim to mitigate the loss of productivity in such situations. The first model applies "alternate period processing" and aims either to allow workers to take breaks or to increase workers' job variety. The second model applies "shared processing" and aims to allow workers to share a fixed portion of their processing capacities between their primary tasks and routine activities. For each model, we consider four of the most widely studied and practical classical scheduling objectives. Our purpose is to study the complexity of the resulting scheduling problems. For some problems, we describe a fast optimal algorithm, whereas for other problems an intractability result suggests the probable nonexistence of such an algorithm. © 2016 Elsevier B.V. All rights reserved.

KW - Efficient algorithm

KW - Intractability

KW - Motivations for multitasking

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=84992297280&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84992297280&origin=recordpage

U2 - 10.1016/j.dam.2016.03.018

DO - 10.1016/j.dam.2016.03.018

M3 - RGC 21 - Publication in refereed journal

SN - 0166-218X

VL - 208

SP - 41

EP - 58

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Multitasking via alternate and shared processing: Algorithms and complexity

Abstract

Bibliographical note

Funding

Research Keywords

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this