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

Catusse, Nicolas; Cambazard, Hadrien; Brauner, Nadia; Lemaire, Pierre; Penz, Bernard; Lagrange, Anne-Marie; Rubini, Pascal

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

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3060-3065.

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.

Nicolas Catusse, Hadrien Cambazard, Nadia Brauner, Pierre Lemaire, Bernard Penz, Anne-Marie Lagrange, and Pascal Rubini. 2016. A Branch-and-Price Algorithm for Scheduling Observations on a Telescope. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 3060–3065. https://ijcai.org/proceedings/2016/434

@inproceedings{ijcai2016p434,
  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 = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {3060--3065},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/434},
}

TY  - CPAPER
TI  - A Branch-and-Price Algorithm for Scheduling Observations on a Telescope
AU  - Catusse, Nicolas
AU  - Cambazard, Hadrien
AU  - Brauner, Nadia
AU  - Lemaire, Pierre
AU  - Penz, Bernard
AU  - Lagrange, Anne-Marie
AU  - Rubini, Pascal
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 3060
EP  - 3065
UR  - https://ijcai.org/proceedings/2016/434
ER  -