Complexity results for the horizontal bar packing problem

Abstract : The paper deals with the problem of packing a set of horizontal bars by taking into account some constraints on the distance between two consecutive bars on the same row. This problem is deeply connected with Discrete Tomography and it finds application in workforce scheduling. We study the complexity of the problem and show that, depending on the kind of constraints considered, the problem can be polynomial or NP-Complete. We analyze in details the case where a minimal distance between consecutive bars is required and propose a greedy algorithm which solves this problem in polynomial time.
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2008, 108 (6), pp.356-359. 〈10.1016/j.ipl.2008.07.007〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00976363
Contributeur : Aurélien Arnoux <>
Soumis le : mercredi 9 avril 2014 - 17:30:29
Dernière modification le : mercredi 6 décembre 2017 - 16:46:01

Identifiants

Collections

Citation

Marie-Christine Costa, Fethi Jarray, Christophe Picouleau. Complexity results for the horizontal bar packing problem. Information Processing Letters, Elsevier, 2008, 108 (6), pp.356-359. 〈10.1016/j.ipl.2008.07.007〉. 〈hal-00976363〉

Partager

Métriques

Consultations de la notice

78