Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Multi-objective optimisation of the generalized bin packing problem
This project aimed to investigate multi-objective optimisation of the generalized bin packing problem, which involves the allocation of compulsory and non-compulsory items into a set of bins. The items have characteristics such as weight, width, height, and due date, while the bins have characterist...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English English |
| Published: |
Department of Statistical Sciences
2026
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613183992135680 |
|---|---|
| access_status_str | Open Access |
| author | Plumbley, Andrea |
| author2 | Rakotonirainy, Rosephine Georgina |
| author_browse | Plumbley, Andrea Rakotonirainy, Rosephine Georgina |
| author_facet | Rakotonirainy, Rosephine Georgina Plumbley, Andrea |
| author_sort | Plumbley, Andrea |
| collection | Thesis |
| description | This project aimed to investigate multi-objective optimisation of the generalized bin packing problem, which involves the allocation of compulsory and non-compulsory items into a set of bins. The items have characteristics such as weight, width, height, and due date, while the bins have characteristics such as capacity and cost. The main objective of this problem is to minimize cost which usually corresponds to minimizing the number of bins used. However, in many real-world applications there may be multiple objectives that are trying to be met, and these may be competing such as item due dates and load balancing objectives. Classical methods for solving such problems involve combining the objectives into a single objective or converting some of the objectives into constraints with associated goals. Both approaches require one to have prior knowledge of the decision-makers' preferences in terms of a trade-off between the different objectives which are often difficult to obtain. In this work, a multi-objective evolutionary model is proposed to tackle the generalized bin packing problem. The proposed approach optimises the problem across multiple objectives, allowing decision-makers to make a trade-off between solutions presented as a Pareto front. Two objective combinations were considered: cost and item lateness, and cost and load imbalance. The developed model was tested on one- and two-dimensional problem instances, demonstrating its ability to minimize objectives and provide a set of conflicting solutions in certain cases. The results also highlighted potential limitations of the algorithm, such as premature convergence and a lack of solution diversity. Potential reasons for these limitations and recommendations for future research to improve the current algorithm are discussed. This work contributes to the limited literature on multi-objective optimisation of the generalized bin packing problem, providing a multi-objective evolutionary algorithm for the problem, while also highlighting some of the problems encountered when performing multi-objective optimisation. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/42619 |
| institution | University of Cape Town (South Africa) |
| language | English eng |
| last_indexed | 2026-06-10T12:32:06.010Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2026 |
| publishDateRange | 2026 |
| publishDateSort | 2026 |
| publisher | Department of Statistical Sciences |
| publisherStr | Department of Statistical Sciences |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/42619 Multi-objective optimisation of the generalized bin packing problem Plumbley, Andrea Rakotonirainy, Rosephine Georgina Bin Packing This project aimed to investigate multi-objective optimisation of the generalized bin packing problem, which involves the allocation of compulsory and non-compulsory items into a set of bins. The items have characteristics such as weight, width, height, and due date, while the bins have characteristics such as capacity and cost. The main objective of this problem is to minimize cost which usually corresponds to minimizing the number of bins used. However, in many real-world applications there may be multiple objectives that are trying to be met, and these may be competing such as item due dates and load balancing objectives. Classical methods for solving such problems involve combining the objectives into a single objective or converting some of the objectives into constraints with associated goals. Both approaches require one to have prior knowledge of the decision-makers' preferences in terms of a trade-off between the different objectives which are often difficult to obtain. In this work, a multi-objective evolutionary model is proposed to tackle the generalized bin packing problem. The proposed approach optimises the problem across multiple objectives, allowing decision-makers to make a trade-off between solutions presented as a Pareto front. Two objective combinations were considered: cost and item lateness, and cost and load imbalance. The developed model was tested on one- and two-dimensional problem instances, demonstrating its ability to minimize objectives and provide a set of conflicting solutions in certain cases. The results also highlighted potential limitations of the algorithm, such as premature convergence and a lack of solution diversity. Potential reasons for these limitations and recommendations for future research to improve the current algorithm are discussed. This work contributes to the limited literature on multi-objective optimisation of the generalized bin packing problem, providing a multi-objective evolutionary algorithm for the problem, while also highlighting some of the problems encountered when performing multi-objective optimisation. 2026-01-20T08:40:03Z 2026-01-20T08:40:03Z 2025 2026-01-20T08:36:03Z Thesis / Dissertation Masters MSc http://hdl.handle.net/11427/42619 en eng application/pdf Department of Statistical Sciences Faculty of Science University of Cape Town |
| spellingShingle | Bin Packing Plumbley, Andrea Multi-objective optimisation of the generalized bin packing problem |
| thesis_degree_str | Master's |
| title | Multi-objective optimisation of the generalized bin packing problem |
| title_full | Multi-objective optimisation of the generalized bin packing problem |
| title_fullStr | Multi-objective optimisation of the generalized bin packing problem |
| title_full_unstemmed | Multi-objective optimisation of the generalized bin packing problem |
| title_short | Multi-objective optimisation of the generalized bin packing problem |
| title_sort | multi objective optimisation of the generalized bin packing problem |
| topic | Bin Packing |
| url | http://hdl.handle.net/11427/42619 |
| work_keys_str_mv | AT plumbleyandrea multiobjectiveoptimisationofthegeneralizedbinpackingproblem |