1
$\begingroup$

Problem statement

In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students.

$i$-th section has:

  1. A student capacity: $cap_i$.
  2. Two lecture timings. (Formally, each section has two elements from $S$ associated with itself, where $S$ contains all lecture timings.)
  3. A parent course $course_i$. ($m \leq n$)

$i$-th course has:

  1. Some lecture section(s) under it. (As mentioned above.)
  2. A parent course category $category_i$. ($t \leq m$)

Each student has ordered all $n$ sections from $1$ to $n$ on the basis of his/her preference.

Now, each student $i$ has to be allocated $q_i$ ($2 \geq q_i \geq 1$) sections such that:

  1. No student has been allocated more than two or more section that have the same element(s) from $S$ associated with themselves. Formally, if the sets of lecture timings of allocated sections for a student $i$ are $T_1$, $T_2$, $\cdots$, $T_{q_i}$, then allocation should ensure that $|T_1 \cup T_2 \cup \cdots \cup T_{q_i}| = 2{q_i}$.
  2. No student has been allocated two or more sections which have the same parent course.
  3. No student has been allocated more than $u$ sections which have a parent course which have the same course category. ($u \geq 1$) Formally, let $X$ be a list of $category_{course_{j}}$ where $j$ is any section allocated to a student. The frequency of any element in $X$ should not exceed $u$.
  4. No section $j$ is allocated to more than $cap_j$ students.
  5. $\sum_{j=1}^p cost(j)$ is minimized. $cost(x)$ is defined as the sum of positions of the $x$th student's allocated sections in his/her preference list. For example, a student had ordered the courses P, Q, R, S in the order: R, Q, S, P. If he/she was allocated Q and S, cost() function will return 5. (2+3)

Constraints:

  • $1 \leq t \leq 7$
  • $3 \leq m \leq 9$
  • $5 \leq n \leq 30$
  • $250 \leq p \leq 700$
  • $\sum_{i=1}^p q_i \leq \sum_{i=1}^n cap_i$

My take

I tried to represent the problem in the form of a k-partite graph. Doing so would have helped implement network flow algorithms like minimum-cost, maximum-flow. However, I have not been able to come up with any representation that satisfies all of the given constraints.

$\endgroup$

closed as unclear what you're asking by dkaeae, Evil, Discrete lizard Aug 17 at 13:48

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

Timetabling is known to be NP-complete. Your more complex variant is too. Don't expect "nice" or "efficient" solutions. Either settle for an approximate solution (good luck in deriving one) or some sort of randomized heuristic.

I'd try some variant of genetic algorithms (look around for it's application to time tabling, they use special mutation and crossover operations that at least try to respect restrictions).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.