Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/61341
Title: Multitasking via alternate and shared processing : algorithms and complexity
Authors: Hall, NG
Leung, JYT
Li, CL 
Keywords: Efficient algorithm
Intractability
Motivations for multitasking
Scheduling
Issue Date: 2016
Publisher: North-Holland
Source: Discrete applied mathematics, 2016, v. 208, p. 41-58 How to cite?
Journal: Discrete applied mathematics 
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.
URI: http://hdl.handle.net/10397/61341
ISSN: 0166-218X
DOI: 10.1016/j.dam.2016.03.018
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

4
Last Week
1
Last month
Citations as of Oct 20, 2018

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
Citations as of Oct 19, 2018

Page view(s)

53
Last Week
0
Last month
Citations as of Oct 22, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.