The multicommodity multilevel bottleneck assignment problem. (English) Zbl 1152.05354
Liberti, Leo (ed.) et al., Workshop on graphs and combinatorial optimization. Papers from the workshop, Como, Italy, May 31, 2004. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 17, 35-40 (2004).
Summary: The Multilevel Bottleneck Assignment Problem is defined on a weighted graph of \(L\) levels and consists in finding \(L-1\) complete matchings between contiguous levels, such that the heaviest path formed by the arcs in the matchings has a minimum weight. The problem, introduced by Carraresi and Gallo (1984) to model the rostering of bus drivers in order to achieve an even balance of the workload among the workers, though frequently cited, seems to have never been applied or extended to more general cases. In this paper, we discuss one possible extension, that is the introduction of multicommodity aspects to model different classes of workers.
For the entire collection see [Zbl 1109.05009].
For the entire collection see [Zbl 1109.05009].
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Beasley, J. E.; Cao, B., A Dynamic Programming based algorithm for the Crew Scheduling Problem, Computers & Operations Research, 53, 567-582 (1998) · Zbl 1040.90524 |
| [2] | P. Cappanera and G. Gallo (2003), On the Airline Crew Rostering Problem, to appear in Operations Research; P. Cappanera and G. Gallo (2003), On the Airline Crew Rostering Problem, to appear in Operations Research |
| [3] | Caprara, A.; Toth, P.; Vigo, D.; Fischetti, M., Modeling and Solving the Crew Rostering Problem, Operations Research, 46, 820-830 (1998) · Zbl 0987.90035 |
| [4] | Carraresi, P.; Gallo, G., A Multi-level Bottleneck Assignment Approach to the bus drivers’ rostering problem, European Journal of Operational Research, 16, 163-173 (1984) · Zbl 0537.90076 |
| [5] | Guignard, M.; Kim, S., Lagrangean decomposition: a model yielding stronger Lagrangean bounds, Mathematical Programming, 39, 215-228 (1987) · Zbl 0638.90074 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
