Deakin University
Browse

File(s) under permanent embargo

An agent-based approach to the two-dimensional guillotine bin packing problem

journal contribution
posted on 2009-02-01, 00:00 authored by S Polyakovsky, R M'Hallah
The two-dimensional guillotine bin packing problem consists of packing, without overlap, small rectangular items into the smallest number of large rectangular bins where items are obtained via guillotine cuts. This problem is solved using a new guillotine bottom left (GBL) constructive heuristic and its agent-based (A-B) implementation. GBL, which is sequential, successively packs items into a bin and creates a new bin every time it can no longer fit any unpacked item into the current one. A-B, which is pseudo-parallel, uses the simplest system of artificial life. This system consists of active agents dynamically interacting in real time to jointly fill the bins while each agent is driven by its own parameters, decision process, and fitness assessment. A-B is particularly fast and yields near-optimal solutions. Its modularity makes it easily adaptable to knapsack related problems.

History

Journal

European journal of operational research

Volume

192

Pagination

767-781

Location

Amsterdam, The Netherlands

ISSN

0377-2217

Language

eng

Publication classification

C Journal article, C1.1 Refereed article in a scholarly journal

Copyright notice

2007, Elsevier B.V.

Issue

3

Publisher

Elsevier

Usage metrics

    Research Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC