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 - Funding Information:
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.
Publisher Copyright:
© 2016 Elsevier B.V. All rights reserved.
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.
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.
KW - Efficient algorithm
KW - Intractability
KW - Motivations for multitasking
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=84992297280&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84992297280&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2016.03.018
DO - 10.1016/j.dam.2016.03.018
M3 - Article
AN - SCOPUS:84992297280
SN - 0166-218X
VL - 208
SP - 41
EP - 58
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -