×
Scholl, Armin; Klein, Robert; Jürgens, Christian

BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. (English) Zbl 0882.90113

Comput. Oper. Res. 24, No. 7, 627-645 (1997).
Summary: We consider the well-known one-dimensional bin packing problem (BPP-1), which is to pack a given set of items having different sizes into a minimum number of equal-sized bins. For solving BPP-1, an exact hybrid solution procedure, called BISON, is proposed. It favourably combines the well-known meta-strategy tabu search and a branch and bound procedure based on known and new bound arguments and a new branching scheme. Computational results indicate that BISON is very effective and outperforms existing approaches.

Cited in 51 Documents

MSC:

90C27 Combinatorial optimization

Keywords:

one-dimensional bin packing; meta-strategy tabu search; branch and bound

Software:

Bison; Tabu search
PDF BibTeX XML Cite
\textit{A. Scholl} et al., Comput. Oper. Res. 24, No. 7, 627--645 (1997; Zbl 0882.90113)
Full Text: DOI

References:

[1] Dyckhoff, H.; Finke, U., Cutting and Packing in Production and Distribution (1992), Physica: Physica Heidelberg
[2] Martello, S.; Toth, P., Knapsack Problems (1990), Wiley: Wiley Chichester · Zbl 0452.90047
[3] Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin-packing—an updated survey, (Ausiello, G.; Lucertini, M.; Serafini, P., Algorithm Design for Computer System Design (1984), Springer: Springer Berlin), 49-106 · Zbl 0558.68062
[4] Cheng, T. C.E.; Sin, C. C.S., A state-of-the-art review of parallel-machine scheduling research, European Journal of Operational Research, 47, 271-292 (1990) · Zbl 0707.90053
[5] Domschke, W.; Scholl, A.; Voβ, S., Produktionsplanung—Ablauforganisatorische Aspekte (1993), Springer: Springer Berlin
[6] Hochbaum, D. S.; Shmoys, D. B., Using dual approximation algorithms for scheduling problems: theoretical and practical results, Journal of the Association for Computing Machinery, 34, 144-162 (1987)
[7] Labbé, M.; Laporte, G.; Martello, S., An exact algorithm for the dual bin packing problem, Operations Research Letters, 17, 9-18 (1995) · Zbl 0835.90077
[8] Spieksma, F. C.R., A branch-and-bound algorithm for the two-dimensional vector packing problem, Computers and Operations Research, 21, 19-25 (1994) · Zbl 0789.90063
[9] Johnson, D. S., Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences, 9, 256-278 (1974) · Zbl 0296.65036
[10] Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM Journal on Computing, 3, 299-325 (1974) · Zbl 0297.68028
[11] Baker, B. S.; Coffman, E. G., A tight asymptotic bound for next-fit-decreasing bin-packing, SIAM Journal on Algebraic and Discrete Methods, 2, 147-152 (1981) · Zbl 0496.68049
[12] Simchi-Levi, D., New worst-case results for the bin-packing problem, Naval Research Logistics, 41, 579-585 (1994) · Zbl 0809.90111
[13] Eilon, S.; Christofides, N., The loading problem, Management Science, 17, 259-267 (1971) · Zbl 0208.45701
[14] Hung, M. S.; Brown, J. R., An algorithm for a class of loading problems, Naval Research Logistics Quarterly, 25, 289-297 (1978) · Zbl 0404.90057
[15] Scholl, A., Balancing and Sequencing of Assembly Lines (1995), Physica: Physica Heidelberg
[16] Labbé, M.; Laporte, G.; Mercure, H., Capacitated vehicle routing on trees, Operations Research, 39, 616-622 (1991) · Zbl 0736.90029
[17] Berger, I.; Bourjolly, J.-M.; Laporte, G., Branch-and-bound algorithms for the multi-product assembly line balancing problem, European Journal of Operational Research, 58, 215-222 (1992) · Zbl 0757.90029
[18] Martello, S.; Toth, P., Lower bounds and reduction procedures for the bin packing problem, Discrete Applied Mathematics, 28, 59-70 (1990) · Zbl 0704.90074
[19] Jackson, J. R., A computing procedure for a line balancing problem, Management Science, 2, 261-271 (1956)
[20] Glover, F., Tabu search: part I, ORSA Journal on Computing, 1, 190-206 (1989) · Zbl 0753.90054
[21] Glover, F., Tabu search: part II, ORSA Journal on Computing, 2, 4-32 (1990) · Zbl 0771.90084
[22] Glover, F.; Laguna, M., Tabu search, (Reeves, C. R., Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwell: Blackwell Oxford), 70-150
[23] Scholl, A.; Voβ, S., Simple assembly line balancing—heuristic approaches, Journal of Heuristics, 2, 217-244 (1996)
[24] Hübscher, R.; Glover, F., Applying tabu search with influential diversification to multiprocessor scheduling, Computers and Operations Research, 21, 877-884 (1994) · Zbl 0814.90048
[26] Klein, R.; Scholl, A., Maximizing the production rate in simple assembly line balancing—a branch and bound procedure, European Journal of Operational Research, 91, 367-385 (1996) · Zbl 0924.90094
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.