Online Timely Bin Packing

Abstract

Within 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.