In this study, we consider two bi-objective bin packing problems that assign a number of weighted items to bins having identical capacities.
Firstly, we aim to minimize total deviation over bin capacity and minimize number of bins. We show that these two objectives are conflicting. Secondly, we study the problem of minimizing maximum overdeviation and minimizing the number of bins. We show the similarities of these two problems to parallel machine scheduling problems and benefit from the results while developing our solution approaches. For both problems, we propose exact procedures that generate efficient solutions relative to two objectives. To increase the efficiency of the solutions, we propose some lower and upper bounding procedures. The
results of our experiments show that total overdeviation problem is easier to solve compared to maximum overdeviation problem and the bin capacity, the weight of items and the number of items are important factors that effect the solution time and quality. Our procedures can solve the problems with up to 100 items in reasonable solution times.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/2/1079987/index.pdf |
| Date | 01 December 2003 |
| Creators | Ilicak, Isil |
| Contributors | Karasakal, Esra |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.002 seconds