Topological sort into a limited number of bins, each with limited capacity

Question

I'm working on a scheduling/design tool for educational courses. I have lists of courses, some which require others to be taken first (dependencies), others that require courses to be taken together with it (co-requisites). Some courses cannot be taken before a particular semester, and most courses are only offered during certain semesters.

I have a limited number of semesters, which I can model as bins, where each course takes up a certain amount of space (units) and each bin has a limited capacity.

What I want to do is, given a partially-ordered list of courses, to present a schedule (or schedules) that meets all the constraints (i.e. allows the student to take all the requirements in 4 years without overloading them in any of the semesters).

I can definitely solve this with a brute force algorithm (i.e. try each combination and check if it works), but I was wondering if I can do something a bit more refined.

It would be great if I could use a better data structure that automatically maintains the constraints, like a heap but customized to this application.

Any ideas?

My suspicion is that it can't really be done in less time and that it is actually NP-complete. I certainly can't be the first person to want to do this.

Answer 1

You don't quite pin down the problem here — if not all courses can be fitted into the semesters, what counts as the best schedule? The natural thing to do would be to give each course a score and aim to maximize the score of the courses scheduled.

The decision version of this problem ("is there a schedule with score $≥ K$?") is in NP, since it's easy to check in polynomial time that a proposed schedule satisfies the constraints.

The problem is NP-hard even for a single semester, by a reduction from PARTIALLY ORDERED KNAPSACK. This problem is [MP12] in Garey & Johnson, Computers and Intractability:

INSTANCE: Finite set $U$, partial order $⋖$ on $U$, for each $u ∈ U$ a size $s(u) ∈ Z^{+}$ and a value $v(u) ∈ Z^{+}$, positive integers $B$ and $K$.

QUESTION: Is there a subset $U′ ⊆ U$ such that if $u ∈ U′$ and $u′ ⋖ u$, then $u′ ∈ U′$, and such that $\sum_{u ∈ U′} s(u) ≤ B$ and $\sum_{u ∈ U′} v(u) ≥ K$?

In the reduction we translate each $u$ into a course with length $s(u)$ and score $v(u)$, if $u′ ⋖ u$ then $u′$ is a prerequisite course for $u$, and there is a single semester of length $B$.

Garey and Johnson note that PARTIALLY ORDERED KNAPSACK is "solvable in pseudo-polynomial time if $⋖$ is a 'tree' partial order". But I doubt that extends to multiple semesters.