Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems

D Niraj Ramesh, M Krishnamoorthy, Andreas T Ernst

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationData and Decision Sciences in Action
Subtitle of host publicationProceedings of the Australian Society for Operations Research Conference 2016
EditorsRuhul Sarker, Hussein A Abbass, Simon Dunstall, Philip Kilby, Richard Davis, Leon Young
Place of PublicationCham Switzerland
PublisherSpringer
Pages43-69
Number of pages27
ISBN (Electronic)9783319559148
ISBN (Print)9783319559131
DOIs
Publication statusPublished - 2018

Publication series

NameLecture Notes in Management and Industrial Engineering
PublisherSpringer
ISSN (Print)2198-0772
ISSN (Electronic)2198-0780

Cite this

Ramesh, D. N., Krishnamoorthy, M., & Ernst, A. T. (2018). Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems. In R. Sarker, H. A. Abbass, S. Dunstall, P. Kilby, R. Davis, & L. Young (Eds.), 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
Ramesh, D Niraj ; Krishnamoorthy, M ; Ernst, Andreas T. / Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems. Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016. editor / Ruhul Sarker ; Hussein A Abbass ; Simon Dunstall ; Philip Kilby ; Richard Davis ; Leon Young. Cham Switzerland : Springer, 2018. pp. 43-69 (Lecture Notes in Management and Industrial Engineering).
@inproceedings{ebd4c800b88c4005acf26c1d4acd9104,
title = "Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems",
abstract = "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.",
author = "Ramesh, {D Niraj} and M Krishnamoorthy and Ernst, {Andreas T}",
year = "2018",
doi = "10.1007/978-3-319-55914-8_4",
language = "English",
isbn = "9783319559131",
series = "Lecture Notes in Management and Industrial Engineering",
publisher = "Springer",
pages = "43--69",
editor = "Ruhul Sarker and Abbass, {Hussein A} and Simon Dunstall and Philip Kilby and Richard Davis and Leon Young",
booktitle = "Data and Decision Sciences in Action",

}

Ramesh, DN, Krishnamoorthy, M & Ernst, AT 2018, Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems. in R Sarker, HA Abbass, S Dunstall, P Kilby, R Davis & L Young (eds), 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.

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 proceedingConference PaperOtherpeer-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 -

Ramesh DN, Krishnamoorthy M, Ernst AT. Efficient Models, Formulations and Algorithms for Some Variants of Fixed Interval Scheduling Problems. In Sarker R, Abbass HA, Dunstall S, Kilby P, Davis R, Young L, editors, Data and Decision Sciences in Action: Proceedings of the Australian Society for Operations Research Conference 2016. Cham Switzerland: Springer. 2018. p. 43-69. (Lecture Notes in Management and Industrial Engineering). https://doi.org/10.1007/978-3-319-55914-8_4