Student Scheduling CP-SAT Precedence

[Slyracoon23]

Hi there,

I am trying to solve a problem that is a variation of the Job Shop problem.

I have a set of classes, each of them have a number of credit hours and you try to divide them equally for each semester. (Semester is min 13 credit-hours and max 21 credit-hours)

But unlike the Job Shop problem, I also need the following:

• Some classes are prerequisites for others classes, e.g. Class A -> Class B. I can't start B unless I have already done A.

• I need to satisfy my degree requirements which may be contained by a specific class or type of class e.g.: Must take MATH 101 or must take at least 2 WRITING 3000 or above classes.

• In the end, I would like to minimize a degree to the least amount of time. That is minimize the semesters needed to complete my degree requirement.

My Code

I tried to make a simple program using the CP-SAT solver to solve for class picking while minimizing total semesters but my program does not take into account classes taken to minimize semester time.

Here is what I wrote

model = cp_model.CpModel()

class_names = ['a','b','c', 'd', 'e']

max_semester = len(class_names)

classes = {}
order = {}
for c in class_names:
    classes[c] = model.NewIntVar(0,1,'Class %s'%c)
    order[c] = model.NewIntVar(0, max_semester -1, c )
    
# Must take 3 classes to finish degree
model.Add(sum(classes.values()  ) == 3)

# define class precedence
model.Add(order['a'] < order['d'])
model.Add(order['b'] < order['d'])
model.Add(order['c'] < order['e'])

minimize order if class is taken otherwise leave it out
model.Minimize(sum(order[c] for c in class_names if classes[c] == 1))

Is their a way to solve this with using all of OR-Tools suite or just CP-SAT?

[lperron]

Please start reading

the developer guide on CP-SAT

and

the CP-SAT cookbook

And yes, this should fit perfectly with CP-SAT.

[Slyracoon23]

Thank you for the quick reply,

I have taken a look at the resources you recommended but I am still confused on how to enforce precedence.

How would you approach it?

[ghost]

In addition to the resources Laurent mentioned, I also find the official examples very good:
https://github.com/google/or-tools/tree/stable/examples/python

As for your code, maybe something like:

model.Add(order["a"] < order["d"]).OnlyEnforceIf([classes["a"], classes["d"]])

And remember that python sees if classes[c] == 1 as if BoundedLinearExpression which is always True, so maybe just:

model.Minimize(sum(order[c] for c in class_names))

[Slyracoon23]

Thank you