Solving the Shifts and Breaks Design Problem Using Integer Linear Programming

Arjan Akkermans; Gerhard F. Post; Marc Jochen Uetz

Solving the Shifts and Breaks Design Problem Using Integer Linear Programming

Arjan Akkermans, Gerhard F. Post, Marc Jochen Uetz

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

87 Downloads (Pure)

Abstract

In this paper we propose a two-phase approach to the shifts and breaks design problem using integer linear programming. In the first phase we create the shifts, while heuristically taking the breaks into account.In the second phase we assign breaks to each occurrence of any shift, one by one, repeating this until no improvement is found. This approach outperforms the current best known method for shifts and breaks design on a set of benchmark instances, as well as on real life instances.

Original language	English
Title of host publication	PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling
Editors	E.K. Burke, L. Di Gaspero, B McCollum, N. Musliu, E. Özcan
Pages	137-152
ISBN (Electronic)	978-0-9929984-2-4
Publication status	Published - 2018
Event	PATAT 2018: 12th International Conference on the Practice and Theory of Automated Timetabling - TU Wien Faculty of Electrical Engineering, Vienna, Austria Duration: 28 Aug 2018 → 31 Aug 2018 Conference number: 12 http://patatconference.org/patat2018/

Conference

Conference	PATAT 2018
Abbreviated title	PATAT 2018
Country/Territory	Austria
City	Vienna
Period	28/08/18 → 31/08/18
Internet address	http://patatconference.org/patat2018/

Access to Document

paper 16 Solving the shiftsFinal published version, 274 KB

http://patatconference.org/patat2018/proceedings/

Cite this

Akkermans, A., Post, G. F., & Uetz, M. J. (2018). Solving the Shifts and Breaks Design Problem Using Integer Linear Programming. In E. K. Burke, L. Di Gaspero, B. McCollum, N. Musliu, & E. Özcan (Eds.), PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling (pp. 137-152). [16] http://patatconference.org/patat2018/proceedings/

@inproceedings{cb07911988a64aebab03aa181feb9dbf,

title = "Solving the Shifts and Breaks Design Problem Using Integer Linear Programming",

abstract = "In this paper we propose a two-phase approach to the shifts and breaks design problem using integer linear programming. In the first phase we create the shifts, while heuristically taking the breaks into account.In the second phase we assign breaks to each occurrence of any shift, one by one, repeating this until no improvement is found. This approach outperforms the current best known method for shifts and breaks design on a set of benchmark instances, as well as on real life instances.",

author = "Arjan Akkermans and Post, {Gerhard F.} and Uetz, {Marc Jochen}",

year = "2018",

language = "English",

pages = "137--152",

editor = "E.K. Burke and {Di Gaspero}, L. and B McCollum and N. Musliu and E. {\"O}zcan",

booktitle = "PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling",

note = "PATAT 2018 : 12th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2018 ; Conference date: 28-08-2018 Through 31-08-2018",

url = "http://patatconference.org/patat2018/",

}

Akkermans, A, Post, GF & Uetz, MJ 2018, Solving the Shifts and Breaks Design Problem Using Integer Linear Programming. in EK Burke, L Di Gaspero, B McCollum, N Musliu & E Özcan (eds), PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling., 16, pp. 137-152, PATAT 2018, Vienna, Austria, 28/08/18. <http://patatconference.org/patat2018/proceedings/>

Solving the Shifts and Breaks Design Problem Using Integer Linear Programming. / Akkermans, Arjan; Post, Gerhard F.; Uetz, Marc Jochen.

PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling. ed. / E.K. Burke; L. Di Gaspero; B McCollum; N. Musliu; E. Özcan. 2018. p. 137-152 16.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Solving the Shifts and Breaks Design Problem Using Integer Linear Programming

AU - Akkermans, Arjan

AU - Post, Gerhard F.

AU - Uetz, Marc Jochen

N1 - Conference code: 12

PY - 2018

Y1 - 2018

N2 - In this paper we propose a two-phase approach to the shifts and breaks design problem using integer linear programming. In the first phase we create the shifts, while heuristically taking the breaks into account.In the second phase we assign breaks to each occurrence of any shift, one by one, repeating this until no improvement is found. This approach outperforms the current best known method for shifts and breaks design on a set of benchmark instances, as well as on real life instances.

AB - In this paper we propose a two-phase approach to the shifts and breaks design problem using integer linear programming. In the first phase we create the shifts, while heuristically taking the breaks into account.In the second phase we assign breaks to each occurrence of any shift, one by one, repeating this until no improvement is found. This approach outperforms the current best known method for shifts and breaks design on a set of benchmark instances, as well as on real life instances.

M3 - Conference contribution

SP - 137

EP - 152

BT - PATAT 2018: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling

A2 - Burke, E.K.

A2 - Di Gaspero, L.

A2 - McCollum, B

A2 - Musliu, N.

A2 - Özcan, E.

T2 - PATAT 2018

Y2 - 28 August 2018 through 31 August 2018

ER -

Solving the Shifts and Breaks Design Problem Using Integer Linear Programming

Abstract

Conference

Access to Document

Fingerprint

Cite this