---
title: "A Branch-and-Price Algorithm for Scheduling Observations on a Telescope"
authors:
  - "Nicolas Catusse"
  - "Hadrien Cambazard"
  - "Nadia Brauner"
  - "Pierre Lemaire"
  - "Bernard Penz"
  - "Anne-Marie Lagrange"
  - "Pascal Rubini"
doi: ""
url: "https://ijcai.org/proceedings/2016/434"
pdf: "https://ijcai.org/proceedings/2016/0434.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "3060-3065"
track: ""
keywords:
---

# 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

*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.