Modeling an assignment/scheduling problem to minimize total wait

Question

I have an assignment type problem in which there is a set of students, $S$, and a set of training classes $T$. Each training has a fixed start and end day and can accommodate at most 1 student. In addition, a training will give a student credit towards two types of requirements, and each training varies in how much credit is given for each type. A student must receive enough credit of type 1 and type 2 in order to be considered trained. For example, student ABC needs 2 credits of type 1, and 5 credits of type 2, and can be assigned to training 123, and receive 1 credit toward requirement 1, and 3 credits toward requirement 2.

Students become first available for training on different days (and have days off after too), and the model objective is to minimize the total wait time across all students, where wait time is defined as the number of days from when a student first becomes available to when they are finished with training.

In general the training dates can overlap, and a student can only take the class if they are available for the entire time of the class.

So far I have modeled the problem with arcs, where $a_{\text{st}} \in\{0,1\}$ is created if a student can possibly take the training (i.e., student is available during training). Each arc also has an attribute called wait_days which is equal to the number of days from when the student first became available to the last day of the training on that arc.

I create sets of trainings that have overlapping dates and then create a constraint in the model so that for each student at most 1 training from each of these sets is assigned in order to avoid scheduling conflicts.

conflict_sets = set()
for t1 in trainings:
   conflicts = [t1]
   for t2 in trainings:
      if t1.start <= t2.end and t1.start >= t2.start:
         conflicts.append[t2]
   conflict_sets.add(conflicts)

I have a model using the CP solver from Google OR-tools that assigns students to trainings so that the student completes both training requirements, there are no scheduling conflicts, and then it minimizes total wait time summed across all students.

from ortools.sat.python import cp_model

model = cp_model.CpModel()

arc_vars = {}
for arc in arcs:
   arc_vars[arc] = model.NewBoolVar(f'arc_{arc}')

wait_vars = {}
# total wait is at most 31 days
for s in students:
   wait_vars[s] = model.NewIntVar(0,31, f'wait_{s}')


for s in students:
   # ensure student completes both types of necessary training
   model.Add(sum(arc_vars[a] * a[1].type1 for a in arcs if a[0]==s) >= s.Type1_req)
   model.Add(sum(arc_vars[a] * a[1].type2 for a in arcs if a[0]==s) >= s.Type2_req)

   # student can't be in trainings that have overlapping times
   for c_list in conflict_sets:
      model.Add(sum(arc_vars[(s, t)] for t in c_list if (s,t) in arcs) <= 1)



# make wait variable the max waiting days 
# across all arcs a student is assigned to
for a in arcs:
   model.Add(wait_vars[a[0]] >= arc_vars[a]*arcs[a].waiting_days)

# minimize total wait time in system
model.Minimize(sum(wait_vars[s] for s in students))

Am I modeling this in an efficient way? I am new to constraint programming, and I believe this would be a good way to model it as an IP, but I'm not sure if this is true for CP. I switched to CP because it has been solving much faster than my original IP formulation. I was thinking maybe there would be a better to model the wait time or the training conflicts with a CP paradigm but I'm not sure.

Answer 1

A Boolean linear programming formulation is given for the problem.

Let suppose to have $S=[ 1,2, \cdots, n ] $ students and $T=[ 1,2, \cdots, m ]$ training classes. Let introduce $m \cdot n $ variables designated as $x_{i,j}$ where $i=1,2, \cdots, n$ and $j=1, 2, \cdots, m$. For every student is know in advance his ready time that is the day in which student is available for training

$r_1, r_2, \cdots, r_n$.

UNKNOWNS

$ x_{i,j} $ is a Boolean variable whose value is 1 if i-th student is assigned to j-th training class, 0 otherwise.

LESSONS/CLASSES CALENDAR AND DURATION

$[t_{j,s} , t_{j,e} ]$ is the Time Window of j-th class where $ t_{j,s} $ is the start day of j-th class and $ t_{j,e} $ is the end day of j-th class. It is clear that every class lasts $ d_j= t_{j,e} - t_{j,s}$ days.

We can introduce $n \cdot m$ futher variables in order to take into account the waste time spent by i-th student in waiting for j-th class starts:

$ w_{i,j} := t_{j,s} – r_i $ for all $i=1,2, \cdots, n$ and $j=1, 2, \cdots, m$.

OBJECTIVE FUNCTION

We desire to minimize the time spent by every student both in waiting for the course and in attending the course. If i-th student attends to the class l-th and p-th, we have $ x_{i,l}=1 $ and $ x_{i,p}=1 $, As a consequence, the waiting time for the two courses results as

$ w_{i,l} \cdot x_{i,l} + w_{i,p} \cdot x_{i,p} = (t_{l,s} – r_i) + (t_{p,s} – r_i) $ days.

The whole time spent in attending the two selected class is:

$ d_l \cdot x_{i,l} + d_p \cdot x_{i,p} = (t_{l,e} - t_{l,s}) + (t_{p,e} - t_{p,s}) $ days.

In general, the student $i$ will wait for

$ \sum_{j=1}^m w_{i,j} \cdot x_{i,j} $ days.

The student $i$ will spend for attending the selected classes

$ \sum_{j=1}^m d_{j} \cdot x_{i,j} $ days.

Extending the sum to all students we get the following objective function:

$ z = \sum_{i=1}^n \sum_{j=1}^m (w_{i,j} + d_j ) \cdot x_{i,j}$

We will seek $x_{i,j}^*$ such that $ z^*= \min z $

Now, it remains to write the constraints.

NO OVERLAPED CLASSES

$ \vdots $

REQUIREMENTS FOR EVERY CLASS

$ \vdots $