Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10523913 | Operations Research Letters | 2014 | 6 Pages |
Abstract
This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial-time algorithm. We also provide direct optimal solutions for special trees like stars and paths.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Giovanni Andreatta, Luigi De Giovanni, Paolo Serafini,