### 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

*Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016*(pp. 43-69). (Lecture Notes in Management and Industrial Engineering). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-55914-8_4

}

*Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016.*Lecture Notes in Management and Industrial Engineering, Springer, Cham Switzerland, pp. 43-69. https://doi.org/10.1007/978-3-319-55914-8_4

**Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems.** / Ramesh, D Niraj; Krishnamoorthy, M; Ernst, Andreas T.

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 -