Abstract
| Original language | English |
|---|---|
| Title of host publication | Data and Decision Sciences in Action |
| Subtitle of host publication | Proceedings of the Australian Society for Operations Research Conference 2016 |
| Editors | Ruhul Sarker, Hussein A Abbass, Simon Dunstall, Philip Kilby, Richard Davis, Leon Young |
| Place of Publication | Cham Switzerland |
| Publisher | Springer |
| Pages | 43-69 |
| Number of pages | 27 |
| ISBN (Electronic) | 9783319559148 |
| ISBN (Print) | 9783319559131 |
| DOIs | |
| Publication status | Published - 2018 |
Publication series
| Name | Lecture Notes in Management and Industrial Engineering |
|---|---|
| Publisher | Springer |
| ISSN (Print) | 2198-0772 |
| ISSN (Electronic) | 2198-0780 |
Cite this
}
Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems. / Ramesh, D Niraj; Krishnamoorthy, M; Ernst, Andreas T.
Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016. ed. / Ruhul Sarker; Hussein A Abbass; Simon Dunstall; Philip Kilby; Richard Davis; Leon Young. Cham Switzerland : Springer, 2018. p. 43-69 (Lecture Notes in Management and Industrial Engineering).Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other › peer-review
TY - GEN
T1 - Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems
AU - Ramesh, D Niraj
AU - Krishnamoorthy, M
AU - Ernst, Andreas T
PY - 2018
Y1 - 2018
N2 - The fixed interval scheduling problem—also known as the personnel task scheduling problem—optimizes the allocation of available resources (workers, machines, or shifts) to execute a given set of jobs or tasks. We introduce a new approach to solve this problem by decomposing it into separate subproblems. We establish the mathematical basis for optimality of such a decomposition and thereafter develop several new techniques (exact and heuristic) to solve the resulting subproblems. An extensive computational analysis of the new techniques proves the efficacy of these approaches when compared to other established techniques in the literature. Specifically, a hybrid integer programming formulation presented in this paper solves several larger problem instances that were not amenable to exact techniques previously. In addition, a constructive heuristic approach (based on quantification metrics for tasks and resources) gives solutions equal to the optimal. We demonstrate that our decomposition approach is applicable for several important variants within the topic of fixed interval scheduling including tactical fixed interval scheduling problem and operational fixed interval scheduling problem.
AB - The fixed interval scheduling problem—also known as the personnel task scheduling problem—optimizes the allocation of available resources (workers, machines, or shifts) to execute a given set of jobs or tasks. We introduce a new approach to solve this problem by decomposing it into separate subproblems. We establish the mathematical basis for optimality of such a decomposition and thereafter develop several new techniques (exact and heuristic) to solve the resulting subproblems. An extensive computational analysis of the new techniques proves the efficacy of these approaches when compared to other established techniques in the literature. Specifically, a hybrid integer programming formulation presented in this paper solves several larger problem instances that were not amenable to exact techniques previously. In addition, a constructive heuristic approach (based on quantification metrics for tasks and resources) gives solutions equal to the optimal. We demonstrate that our decomposition approach is applicable for several important variants within the topic of fixed interval scheduling including tactical fixed interval scheduling problem and operational fixed interval scheduling problem.
U2 - 10.1007/978-3-319-55914-8_4
DO - 10.1007/978-3-319-55914-8_4
M3 - Conference Paper
SN - 9783319559131
T3 - Lecture Notes in Management and Industrial Engineering
SP - 43
EP - 69
BT - Data and Decision Sciences in Action
A2 - Sarker, Ruhul
A2 - Abbass, Hussein A
A2 - Dunstall, Simon
A2 - Kilby, Philip
A2 - Davis, Richard
A2 - Young, Leon
PB - Springer
CY - Cham Switzerland
ER -