A hybrid improvement heuristic for the bin-packing problem and its application to the multiprocessor scheduling problem

• Adriana C. F. Alvim PUC-Rio
• Celso C. Ribeiro PUC-Rio

Resumo

This work presents a hybrid improvement procedure for the bin packing problem and its application to the multiprocessor scheduling problem. This heuristic has several features: a new lower bound; reductions; initial solutions by reference to the dual problem; heuristics for load redistribution, and an improvement process utilizing tabu search. It improved the best known solutions for many of the benchmark instances and found the largest number of optimal solutions with respect to the other available approximate algorithms.

Referências

Alvim, A. C. F. (2003). Uma Heurística Híbrida de Melhoria para o Problema de Bin Packing e sua Aplicação ao Problema de Escalonamento de Tarefas. PhD thesis, Pontifícia Universidade Católica do Rio de Janeiro.

Alvim, A. C. F. and Ribeiro, C. C. (2004). A hybrid bin-packing heuristic to multiprocessor scheduling. In Ribeiro, C. and Martins, S., editors, Lecture Notes in Computer Science, volume 3059, pages 1–13. Springer-Verlag.

Alvim, A. C. F., Ribeiro, C. C., Glover, F., and Aloise, D. J. (2004). A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 10:205–229.

Dell’Amico, M. and Martello, S. (1995). Optimal scheduling of tasks on identical parallel processors. ORSA Journal on Computing, 7:191–200.

Fekete, S. P. and Schepers, J. (2001). New classes of fast lower bounds for bin packing problems. Mathematical Programming, 91:11–31.

Fleszar, K. and Hindi, K. S. (2002). New heuristics for one-dimensional bin packing. Computers and Operations Research, 29:821–839.

França, P. M., Gendreau, M., Laporte, G., and Müller, F. M. (1994). A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective. Computers and Operations Research, 21:205–210.

Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York.

Glover, F. and Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers, Boston.

Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal of Applied Mathematics, 17:416–429.

Hochbaum, D. S. and Shmoys, D. B. (1987). Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of ACM, 34:144–162.

Karmarkar, N. and Karp, R. M. (1982). The differencing method of set partitioning. Relatório Técnico UCB/CSD 82/113, Computer Science Division, University of California, Berkeley.

Martello, S. and Toth, P. (1990). Knapsack problems: algorithms and computer implementations. Wiley, London.

Necciari, E. (2001). [link].

Scholl, A. and Klein, R. (2003). [link].

Scholl, A., Klein, R., and Jürgens, C. (1997). BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers and Operations Research, 24:627–645.

Schwerin, P. and Wäscher, G. (1997). The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP. International Transactions in Operational Research, 4:337–389.

Schwerin, P. and Wäscher, G. (1999). A new lower bound for the bin-packing problem and its integration to MTP. Pesquisa Operacional, 19:111–129.

SICUP (2003). [link].

Valério de Carvalho, J. M. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86:629–659.