Scheduling fixed tasks while maximizing the minimum idle interval via Precoloring Extension on unit interval graphs

MAPSP'15 p. 128-130

International conference - Proceedings of MAPSP 2015 (2015)

Authors: Marin Bougeret and Guillerme Duvillié and Rodolphe Giroudeau

In this paper, we consider an hotel booking management problem motivated by the following situation. Consider an hotel with m rooms. Suppose that the booking management system already accepted $n_r$ future reservations (where each reservation $r_l$ requires one room between a starting time $s(r_l)$ and an end date $d(r_l)$, i.e. the system attributed a room for each reservation, without overlap. Now, suppose that $n_t$ new reservations are submitted. Our objective in this paper is to accept these $n_t$ reservations while maximizing the size of the minimum idle period (where an idle period is an unoccupied room).

We show that problem is $\textbf{NP}$-hard from a reduction from Precoloring Extension on unit interval graphs ($\textbf{PreExt}$). We also highlight a reduction from $\textbf{PreExt}$ to our problem proving that the letter is FPT when parameterized by the number of machines.

We provide an ad hoc dynamic programming algorithm which also runs in time FPT when parameterized by $m$ and a $2$-dual approximation algorithm.