Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorLiu, Alison
dc.contributor.authorKhattar, Zhadyra
dc.date.accessioned2023-09-06T10:07:23Z
dc.date.available2023-09-06T10:07:23Z
dc.date.issued2023
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/45024
dc.description.abstractWithin the traditional online bin packing problem context, items with a positive size not greater than one are sequentially introduced. These items are assigned to bins with a capacity of 1 unit each, ensuring that the cumulative size of items placed in a bin remains within its capacity limit; the goal is to use the fewest bins possible. This thesis investigates novel configurations within the domain of online timely bin packing, Online Timely Bin Packing Problem (T-BPP). We introduce a new concept of time slots, whereby each item with a positive size not larger than one is characterized by a release time and associated deadline. Item is available for packing at time slot t, if it is released before t and its deadline is after t. At time slot t, an online algorithm is free to allocate available items in a manner that aligns with its strategy ensuring that the cumulative size of items placed in each bin does not exceed one. Additionally, the utilisation of each bin is confined to a single designated time slot, after which it becomes inaccessible. The goal of T-BPP is to pack these items without missing their deadlines, with the deadline established upon the item's release, using the minimal number of unit capacity bins. It is worth noting that this particular problem formulation has not been explored previously, thus standing as a unique and uncharted research area. To address this problem, we present the Pack-at-Deadline algorithm with a competitive ratio of 2 and a lower bound of 1.67. Furthermore, our analysis demonstrates the existence of a lower bound of 1.2 for the problem.
dc.description.sponsorshipUtrecht University
dc.language.isoEN
dc.subjectThis thesis investigates novel configurations within the domain of online bin packing, Online Timely Bin Packing Problem (T-BPP). We introduce a new concept of time slots, whereby each item with a positive size not larger than one is characterised by a release time and an associated deadline. Item is available for packing at time slot t if it is released before t and its deadline is after t.
dc.titleOnline Timely Bin Packing
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsOnline Bin Packing; Online algorithms
dc.subject.courseuuComputing Science
dc.thesis.id23566


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record