{"id":{"repo_id":"cape-town","oai_identifier":"oai:open.uct.ac.za:11427/42619"},"canonical_url":"https://search.dev.ndltd.org/etd/cape-town/oai:open.uct.ac.za:11427/42619","repository":{"repo_id":"cape-town","name":"University of Cape Town","base_url":"https://open.uct.ac.za/oai/request"},"display":{"title":"Multi-objective optimisation of the generalized bin packing problem","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Plumbley, Andrea"],"institution":"Department of Statistical Sciences","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Rakotonirainy, Rosephine Georgina"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025","date_published":"2025","updated_at":"2026-07-22T22:22:44Z","subjects":["Bin","Packing"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11427/42619","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Rakotonirainy, Rosephine Georgina"]},{"key":"dc:creator","label":"Author","values":["Plumbley, Andrea"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-01-20T08:40:03Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-01-20T08:40:03Z"]},{"key":"dc:date.issued","label":"Date","values":["2025"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Department of Statistical Sciences"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cape Town"]},{"key":"dc:type","label":"Dc Type","values":["Thesis / Dissertation"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Masters","MSc"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Bin","Packing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11427/42619"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Multi-objective optimisation of the generalized bin packing problem"]}]}],"canonical_facts":{"dc:contributor.advisor":["Rakotonirainy, Rosephine Georgina"],"dc:creator":["Plumbley, Andrea"],"dc:date.accessioned":["2026-01-20T08:40:03Z"],"dc:date.available":["2026-01-20T08:40:03Z"],"dc:date.issued":["2025"],"dc:description.abstract":["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."],"dc:identifier.uri":["http://hdl.handle.net/11427/42619"],"dc:language.iso":["en"],"dc:publisher.department":["Department of Statistical Sciences"],"dc:publisher.institution":["University of Cape Town"],"dc:subject":["Bin","Packing"],"dc:title":["Multi-objective optimisation of the generalized bin packing problem"],"dc:type":["Thesis / Dissertation"],"dc:type.qualificationlevel":["Masters","MSc"]},"updated_at":"2026-07-22T22:22:44Z"}