An Analogy between Bin Packing Problem and Permutation Problem: A New Encoding Scheme

Abstract : The bin packing problem aims to pack a set of items in a minimum number of bins, with respect to the size of the items and capacity of the bins. This is an NP-hard problem. Several approach methods have been developed to solve this problem. In this paper, we propose a new encoding scheme which is used in a hybrid resolution: a metaheuristic is matched with a list algorithm (Next Fit, First Fit, Best Fit) to solve the bin packing problem. Any metaheuristic can be used but in this paper, our proposition is implemented on a single solution based metaheuristic (stochastic descent, simulated annealing, kangaroo algorithm). This hybrid method is tested on literature instances to ensure its good results.
Type de document :
Communication dans un congrès
Bernard Grabot; Bruno Vallespir; Samuel Gomes; Abdelaziz Bouras; Dimitris Kiritsis. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2014, Ajaccio, France. Springer, IFIP Advances in Information and Communication Technology, AICT-438 (Part I), pp.572-579, 2014, Advances in Production Management Systems. Innovative and Knowledge-Based Production Management in a Global-Local World. 〈10.1007/978-3-662-44739-0_70〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01388599
Contributeur : Hal Ifip <>
Soumis le : jeudi 27 octobre 2016 - 11:47:01
Dernière modification le : vendredi 1 décembre 2017 - 01:15:39

Fichier

978-3-662-44739-0_70_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Michel Gourgand, Nathalie Grangeon, Nathalie Klement. An Analogy between Bin Packing Problem and Permutation Problem: A New Encoding Scheme. Bernard Grabot; Bruno Vallespir; Samuel Gomes; Abdelaziz Bouras; Dimitris Kiritsis. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2014, Ajaccio, France. Springer, IFIP Advances in Information and Communication Technology, AICT-438 (Part I), pp.572-579, 2014, Advances in Production Management Systems. Innovative and Knowledge-Based Production Management in a Global-Local World. 〈10.1007/978-3-662-44739-0_70〉. 〈hal-01388599〉

Partager

Métriques

Consultations de la notice

71

Téléchargements de fichiers

88