Title: A novel greedy quantum inspired cuckoo search algorithm for variable sized bin packing problem

Authors: Abdesslem Layeb; Seriel Rayene Boussalia

Addresses: Computer Science Department, MISC Lab, University of Constantine 2, Constantine, Algeria ' Computer Science Department, MISC Lab, University of Constantine 2, Constantine, Algeria

Abstract: Bin packing is a well-known NP-hard optimisation problem which has several real applications. Classical bin packing (BPP) is a simple model where all bins are identical. However, the variable sized bin packing problem (VSBPP) is a generalisation of the bin packing problem where bins of different capacities are available for packing a set of items having different weights. The objective is to pack all the items in the bins minimising the sum of the remaining spaces of the used bins. In this paper, we present a new approach based on the quantum inspired cuckoo search algorithm to deal with the variable sized bin packing problem (VSBPP) problem. The contribution consists in defining an appropriate quantum representation based on qubit representation to represent bin packing solutions. The second contribution is a proposition of a new hybrid quantum measure operation which uses first fit heuristic to pack no filled objects by the standard measure operation. The third contribution is the use of a new hybrid randomised heuristic based on both first fit and best heuristics. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.

Keywords: variable sized bin packing problem; VSBPP; heuristics; cuckoo search algorithm; quantum computing; hybrid algorithms; optimisation; qubit representation.

DOI: 10.1504/IJMOR.2014.065420

International Journal of Mathematics in Operational Research, 2014 Vol.6 No.6, pp.732 - 751

Received: 11 Mar 2013
Accepted: 10 Jul 2013
Published online: 31 Oct 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article