Multitasking via alternate and shared processing : Algorithms and complexity
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 41-58 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 208 |
Publication status | Published - 31 Jul 2016 |
Externally published | Yes |
Link(s)
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.
Research Area(s)
- Efficient algorithm, Intractability, Motivations for multitasking, Scheduling
Bibliographic 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].
Citation Format(s)
Multitasking via alternate and shared processing: Algorithms and complexity. / Hall, Nicholas G.; Leung, Joseph Y.-T.; Li, Chung-Lun.
In: Discrete Applied Mathematics, Vol. 208, 31.07.2016, p. 41-58.
In: Discrete Applied Mathematics, Vol. 208, 31.07.2016, p. 41-58.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review