ML Anthology

A Branch-and-Price Algorithm for Scheduling Observations on a Telescope

Nicolas Catusse, Hadrien Cambazard, Nadia Brauner, Pierre Lemaire, Bernard Penz, Anne-Marie Lagrange, Pascal Rubini
IJCAI 2016 pp. 3060-3066
/ijcai/2016/catusse2016ijcai-branch/

Abstract

We address a parallel machine scheduling problem for which the objective is to maximize the weighted number of scheduled tasks, and with the special constraint that each task has a mandatory processing instant. This problem arises, in our case, to schedule a set of astronomical observations on a telescope. We prove that the problem is NP-complete, and we propose a constraint- programming-based branch-and-price algorithm to solve it. Experiments on real and realistic datasets show that the method provides optimal solutions very efficiently. PDF

PDF IJCAI Semantic Scholar

Cite

Text

Catusse et al. "A Branch-and-Price Algorithm for Scheduling Observations on a Telescope." International Joint Conference on Artificial Intelligence, 2016.

Markdown

[Catusse et al. "A Branch-and-Price Algorithm for Scheduling Observations on a Telescope." International Joint Conference on Artificial Intelligence, 2016.](https://mlanthology.org/ijcai/2016/catusse2016ijcai-branch/)

BibTeX

@inproceedings{catusse2016ijcai-branch,
  title     = {{A Branch-and-Price Algorithm for Scheduling Observations on a Telescope}},
  author    = {Catusse, Nicolas and Cambazard, Hadrien and Brauner, Nadia and Lemaire, Pierre and Penz, Bernard and Lagrange, Anne-Marie and Rubini, Pascal},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {3060-3066},
  url       = {https://mlanthology.org/ijcai/2016/catusse2016ijcai-branch/}
}