An Efficient Assignment Algorithm, Given Preferences and Capacity Constraints

Overview

Objectives/Goals The goal of my project is to design an efficient algorithm that creates assignments that maximize overall satisfaction, and to then make software specifically applying the algorithm to scheduling in schools. Methods/Materials I used a laptop computer with a django setup and a sqlite3 database. I tested the algorithm against already existing methods and created a web app to make interaction easier. Results The algorithm I created works in less than a minute when making seven assignments per person for 500 people. It does not guarantee optimality, as the problem it solves is known to be np hard, but it is efficient, running in time that is, in the worst case, a quadratic in the number of people. Conclusions/Discussion I built a heuristic that takes the preferences of many people and then tries to output assignments that will create the highest overall satisfaction level. This is done efficiently using a combination of limited back tracking, random sampling, and pairwise switchings, as opposed to the known optimal but inefficient methods of simply trying all permutations or full back tracking. The algorithm I created can also be used to make better and more efficient decisions in many other aspects of public life.

Competition history

• CSEF 2016 Mathematics & Computer Science · Entry J1409

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2016 project