A novel greedy quantum inspired cuckoo search algorithm for variable sized bin packing problem. (27th October 2014)

• Record Type: Journal Article
• Authors: Layeb, Abdesslem; Boussalia, Seriel Rayene
• Is Part Of: International journal of mathematics in operational research. Volume 6:Number 6(2014)
• Page Start: 732
• Page End: 751
• Publication Date: 2014-10-27
• Subjects: variable sized bin packing problem -- VSBPP -- heuristics -- cuckoo search algorithm -- quantum computing -- hybrid algorithms; Operations research -- Mathematical models -- Periodicals; Operations research -- Mathematics -- Periodicals; Decision making -- Mathematical models -- Periodicals; 658.4033
• Languages: English
• ISSNs: 1757-5850

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.