UPM Institutional Repository

Improved Multicrossover Genetic Algorithm For Twodimensional Rectangular Bin Packing Problem


Citation

Sarabian, Maryam (2010) Improved Multicrossover Genetic Algorithm For Twodimensional Rectangular Bin Packing Problem. Masters thesis, Universiti Putra Malaysia.

Abstract

Bin Packing Problem is a branch of Cutting and Packing problems which has many applications in wood and metal industries. In this research we focus on non-oriented case of Two–Dimensional Rectangular Bin Packing Problem (2DRBPP). The objective of this problem is to pack a given set of small rectangles, which may be rotated by 90˚, without overlaps into a minimum numbers of identical large rectangles. Our aim is to improve the performance of the MultiCrossover Genetic Algorithm (MXGA) proposed from the literature for solving the problem. We focus on four major components of the MXGA which consist of selection, crossover, mutation and replacement. Initial computational experiments are conducted independently on the named components using some benchmark problem instances. The most competitive techniques from each component are combined to form a new algorithm called Improved MXGA (MXGAi). Extensive computational experiments are performed using benchmark data sets to assess the effectiveness of the proposed algorithm. The MXGAi is shown to be competitive when compared with MXGA, Standard GA, Unified Tabu Search (UTS) and Randomised Descent Method (RDM).


Download File

[img]
Preview
PDF
FS_2010_5_A.pdf

Download (523kB)

Additional Metadata

Item Type: Thesis (Masters)
Subject: Algorithms
Subject: Genetic algorithms - Mathematical models
Subject: Packaging
Call Number: FS 2010 5
Chairman Supervisor: Lee Lai Soon, PhD
Divisions: Faculty of Science
Depositing User: Mohd Nezeri Mohamad
Date Deposited: 19 Jul 2011 01:25
Last Modified: 27 May 2013 07:50
URI: http://psasir.upm.edu.my/id/eprint/11988
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item