Purpose

•     Use evolutionary computing to solve an interesting resource allocation problem

•     Help Khoury College faculty with managing TA / lab allocation for large classes

•     Explore an important field of AI: Intelligent Decision-Support

•     Practice functional programming and test-driven development (TDD)

Overview

Northeastern University’s Khoury College offers several large classes supported by dozens of teaching

assistants (TAs).  These include Intro to Programming with Data, Discrete Structures, and Fundies. These   courses have many lab practicums that need to be supported by the course TAs. Allocating TAs to labs is a difficult but interesting resource-allocation challenge.   While a simple sign-up sheet might be a

solution, the results are often sub-optimal. In general, our goal is to assign TAs to labs that are consistent with their availability and preferences while making sure we assign enough TAs to each lab. Performing

this scheduling task by hand takes many hours of the instructor’s time and it is unlikely that they are

coming up with the best possible solution.  Solving this problem would be a great service to Khoury

college.  In this homework assignment we take on the challenge!   (Creating a web-based application to make this software more widely available would make for an excellent project, by the way.)

Two tables of data have been provided using real data from DS2000: Intro to Programming with Data.

sections.csv: A table of information about each lab/section. There are 17 sections numbered 0- 16. The

critical columns are min_ta and max_ta, the minimum and maximum number of TAs that need to be

assigned to that section.  The min/max values are determined by the number of students enrolled in that section.

tas.csv: A table of information about each TA, how many sections they are willing to support

(max_assigned) and their availability and preferences for each section (U = Unavailable, W = Willing, P = Preferred).

In this assignment,we will use evolutionary computing to assign TAs to specific recitation sections. You

should be able to use the evo.py framework developed in class as is, though you may need to modify that

code to specify a running time limit.   Your main tasks are:

a)    Define functions for each objective (described below).  Each function should be written in a functional style. Try to avoid loops and assignments.

b)   Implement at least one unit test for each objective function to verify that your objectives are

working correctly.   Three sample solutions have been provided.  Here are their evaluation scores (see below for a description of each objective):

c)    Define agents that modify existing solutions and create new solutions. These can be simple or  complex.  It is entirely up to you. I recommend having some agents that try to address specific objectives.

d)   Run your optimizer for at most 10 minutes. There is no limit on how many agent invocations you    perform or how many solutions you produce.  Your only limit is time. You will need to modify the   evo framework so that the evolve function accepts a time limit parameter. (I recommend that your time limit be specified in total seconds, e.g., time_limit=600)

e)    Report your best, non-dominated set of solutions.  You must output the solutions in table format in exactly the format specified in the deliverables section below.

Objectives

1.    Minimize overallocation of TAs (overallocation): Each TA specifies how many labs they can

support (max_assigned column in tas.csv). If a TA requests at most 2 labs and you assign to them 5 labs, that’s an overallocation penalty of 3.  Compute the objective by summing the overallocation   penalty over all TAs.  There is no minimum allocation.

2.    Minimize time conflicts (conflicts): Minimize the number of TAs with one or more time conflicts.  A time conflict occurs if you assign a TA to two labs meeting at the sametime.    If a TA has multiple

time conflicts, still count that as one overall time conflict for that TA.

3.    Minimize Under-Support (undersupport): If a section needs at least 3 TAs and you only assign 1, count that as 2 penalty points. Minimize the total penalty score across all sections.   There is no

penalty for assigning too many TAs.  You can never have enough TAs.

4.    Minimize the number of times you allocate a TA to a section they are unwilling to support

(unwilling). You could argue this is really a hard constraint, but we will treat it as an objective to be