LATE Algorithm Discussion

Introduction

The fundamental task of LATE is to automatically allocate portions of a students free time into blocks of time to work of specific assignments. This means that late must undergo the NP-hard task of 1D bin-packing, the placing of n differently sized elements into containers of some size k.

LATE will have additional complexities to this task, including allocation with priority as an influence as well as the containers(free time blocks) being finite in number and of varying size, but these do not fundamentally change the problem and can be performed at substantially lower time complexity.

Description of Problem

As stated earlier 1D bin-packing is an NP-hard problem, meaning that there are no known algorithms to produce the optimal solution ( the minimum number of containers used) in polynomial time, so the best way to get an optimal solution is to just just everything until the densest packing is stumbled upon. This brute force algorithm has an exponential time complexity and isn't anywhere near feasible for an app expecting anything more than a development level of requests.

Chosen Solution

Fortunately there are heuristic algorithms that get reasonably good results in far less time. Enter First Fit Decreasing(FFD), in FFD the elements to be allocated are sorted in decreasing order and then starting from the smallest, each element is placed into the first container that will fit it. FFD runs in O(nlogn) time where n is the number of elements to be allocated, the solution it produces will often by non-optimal but will never used up more that 11/9 times as many containers as the optimal solution which is a fair trade off for the dramatic increase in speed.

Additions for LATE

Regarding the specifics of LATE's application of 1D bin-packing the changes will be fairly simple. To handle the influences of an assignments priority the sorting algorithm used for blocks of time(elements) will sort based on priority then size of a particular block. The size of a block is simply the difference between the start and end times and the priority of a block is equal to the given priority of that block's assignment divided by the percentage of the time originally allocated left to the deadline. Said more succinctly: total Priority = assignment priority / percent of time left

To handles due dates there will either be: a constraint in our implementation of FFD that guarantees that assignments are not allocated past their due date or this algorithm will be run multiple times for each assignment being allotted a certain subset of the free time, higher priority assignments are given first pass in this order.

And to handle the finite nature of a students free time a set of containers based on a students free time will be calculated and used as the container in FFD, throwing some error message to the user if the given amount of free time does not allow any solutions.

Wrapping Things Up

To wrap things up and provide a nice little TL;DR LATE faces the NP-hard problem of 1D bin-packing and uses the heuristic algorithm FFD to save time at the cost of an optimal solution, modifications to the algorithm will be made to suit LATE's needs but will not be fundamentally altered.