An enhanced branch-and-bound algorithm for the talent scheduling problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review

3 Scopus Citations
View graph of relations

Author(s)

  • Hu Qin
  • Zizhen Zhang
  • Andrew Lim
  • Xiaocong Liang

Detail(s)

Original languageEnglish
Pages (from-to)412-426
Journal / PublicationEuropean Journal of Operational Research
Volume250
Issue number2
Publication statusPublished - 16 Apr 2016
Externally publishedYes

Abstract

The talent scheduling problem is a simplified version of the real-world film shooting problem, which aims to determine a shooting sequence so as to minimize the total cost of the actors involved. In this article, we first formulate the problem as an integer linear programming model. Next, we devise a branch-and-bound algorithm to solve the problem. The branch-and-bound algorithm is enhanced by several accelerating techniques, including preprocessing, dominance rules and caching search states. Extensive experiments over two sets of benchmark instances suggest that our algorithm is superior to the current best exact algorithm. Finally, the impacts of different parameter settings, algorithm components and instance generation distributions are disclosed by some additional experiments.

Research Area(s)

  • Branch-and-bound, Dominance rules, Dynamic programming, scheduling, Talent scheduling

Citation Format(s)

An enhanced branch-and-bound algorithm for the talent scheduling problem. / Qin, Hu; Zhang, Zizhen; Lim, Andrew; Liang, Xiaocong.

In: European Journal of Operational Research, Vol. 250, No. 2, 16.04.2016, p. 412-426.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review