Assigning consecutive classes for a teacher

[sarthakgaur]

Problem:

There are two teachers in a school. Ben (0) and Sam (1).
1. Ben teaches Math, and Sam teaches Science.
2. Assume Ben's index is 0 and Sam's is 1.
3. Both teachers must give 4 classes in a week.
4. In a week, there are only 5 working days i.e Monday - Friday.
5. In a day at most 3 classes can be scheduled.
6. Sam always teaches 2 periods in a day consecutively.

Code:

from ortools.sat.python import cp_model


class TeacherPeriodsSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, periods, num_teachers, num_days, num_periods, sols):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self._periods = periods
        self._num_teachers = num_teachers
        self._num_days = num_days
        self._num_periods = num_periods
        self._solutions = set(sols)
        self._solution_count = 0

    def on_solution_callback(self):
        if self._solution_count in self._solutions:
            print('Solution %i' % self._solution_count)
            for t in range(self._num_teachers):
                for d in range(self._num_days):
                    for p in range(self._num_periods):
                        if self.Value(self._periods[(t, d, p)]):
                            print("Teacher %i teaches on day %i and period %i." % (t, d, p))
                print()
        self._solution_count += 1
    
    def solution_count(self):
        return self._solution_count


def main():
    # Data.
    num_teachers = 2
    num_days = 5
    num_periods = 3 # Maximum number of periods in a day.

    all_teachers = range(num_teachers)
    all_days = range(num_days)
    all_periods = range(num_periods)

    # Creates the model.
    model = cp_model.CpModel()

    # Create variables.
    periods = {}
    for d in all_days:
        for p in all_periods:
            for t in all_teachers:
                periods[(t, d, p)] = model.NewBoolVar('t%i_d%i_p%i' % (t, d, p))

    # Constraints.
    # Each Teacher should teach 4 classes in a week.
    for t in all_teachers:
        model.Add(sum(periods[(t, d, p)] for d in all_days for p in all_periods) == 4)

    # Only one teacher can teach in a period.
    for d in all_days:
        for p in all_periods:
            model.Add(sum(periods[(t, d, p)] for t in all_teachers) < 2)

    # Contraint for Sam?

    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    solver.parameters.linearization_level = 0
    a_few_solutions = range(2)
    solution_printer = TeacherPeriodsSolutionPrinter(periods, num_teachers, num_days,
        num_periods, a_few_solutions)
    solver.Solve(model)

    for t in range(num_teachers):
        for d in range(num_days):
            for p in range(num_periods):
                if solver.Value(periods[(t, d, p)]):
                    print("Teacher %i teaches on day %i and period %i." % (t, d, p))
        print()


    # Statistics.
    print()
    print('Statistics')
    print('  - wall time       : %f s' % solver.WallTime())
    print('  - Number of period requests met : %i' % solver.ObjectiveValue()),

if __name__ == '__main__':
    main()

How do I solve the consecutive class constraint? The solution should be generic enough to work for n number of periods in a day consecutively.

[jmarca]

What do you mean by consecutive? You do not have a notion of time in your solver. Does consecutive `===` ``` if (from_period + 1 == to_period) then consecutive[from_period,to_period]=True else consecutive[from_period,to_period]=False ``` James

[sarthakgaur]

num_periods = 3
# ...
all_periods = range(num_periods) # -> [0, 1, 2]

Assume period at index 0 is the first period, 1 is the second period, and 2 is the last period.

[Mizux]

I guess you have

sam = 1
for d in range(num_days):
   model.Add(periods[(sam, d, 0)] + periods[(sam, d, 2)] == 1).OnlyEnforceIf(periods[(sam, d, 1)])
   model.Add(periods[(sam, d, 0)] + periods[(sam, d, 2)] == 0).OnlyEnforceIf(periods[(sam, d, 1)].Not())

i.e. if Sam works first or last period it must also work the period P1 in order to be consecutive i.e. [P0,P1] or [P1,P2] ?

In the same mood we can say Sam choice is to work P0 or P2 the day he work since it will be force to work P1 as well aka P1 is not really a "variable" for Sam -> we could try to reduce the search space by "hacking" the model for Sam..

[sarthakgaur]

Yes. Here's what a simple solution should look like. B is Ben and S is Sam. This is 5 x 3 grid representing 5 days containing 3 periods each.

S S X
B X X
B S S
B X X
B X X

[Mizux]

    for d in range(num_days):
      out = ''
      for p in range(num_periods):
        if solver.Value(periods[(0, d, p)]):
            out += 'B'
        elif solver.Value(periods[(1, d, p)]):
            out += 'S'
        else:
            out += 'X'
        out += ' '
      print(out)

[sarthakgaur]

Awesome.

[Mizux]

off topic you also miss

In a day at most 3 classes can be scheduled.

aka

# at most three classes in a day
for d in all_days:
    model.Add(sum(periods[(t, d, p)] for t in all_teachers for p in all_periods) <= 3)

[sarthakgaur]

Not really required because there are only 3 periods in a day. It would be required if the number of periods is more than 3.

[Mizux]

do you mean you only have one class room ? I mean Sam and Ben could teach at the same time for different classes (in two distinct class rooms) ?
note: thinking about having also a class [0-3] array and concurrent classe e.g. while class 0 learn math, class 2 can learn science... ;)

[sarthakgaur]

Yes, there is only one class. I tried to make this problem as simple as possible.

Also, thanks for the suggestion. This is not a real problem. The actual problem is a lot more complex and we do have a lot of classes, but this is the core constraint I am struggling with, so I made this question as easy to understand as possible.

[jmarca]

Okay, so what I said. So use that rule to define booleans, for consecutive classes, then set your constraint using that. Check out the help docs for Boolean logic, esp the part about how to multiply two Booleans ConsecutiveboolAB * teacherAclassA * teacherAclassB = BoolTeacherDoesConsecutiveClass Etc. James

…

On Sep 26, 2022, at 11:00, sarthakgaur ***@***.***> wrote:  Yes. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you commented.

[sarthakgaur]

Should I make boolean variables for all the combinations possible and then set constraints on those? Are there any examples that solve problems similar to this? I have checked Shift Scheduling example. That seems more complicated than my problem.

[sarthakgaur]

Here is the solution to the problem:

def negated_bounded_span(works, start, length):
    sequence = []

    # Left border (start of works, or works[start - 1])
    if start > 0:
        sequence.append(works[start - 1])
    for i in range(length):
        sequence.append(works[start + i].Not())
    # Right border (end of works or works[start + length])
    if start + length < len(works):
        sequence.append(works[start + length])

    return sequence

def add_hard_sequence_constraint(model, works, hard_min, hard_max):
    # Forbid sequences that are too short.
    for length in range(1, hard_min):
        for start in range(len(works) - length + 1):
            model.AddBoolOr(negated_bounded_span(works, start, length))

    # Just forbid any sequence of true variables with length hard_max + 1
    for start in range(len(works) - hard_max):
        model.AddBoolOr([works[i].Not() for i in range(start, start + hard_max + 1)])

# Contraint for Sam
sam = 1
for d in all_days:
    works = [periods[(sam, d, p)] for p in all_periods]
    add_hard_sequence_constraint(model, works, 2, 2)

References:

1. https://github.com/google/or-tools/blob/stable/examples/python/shift_scheduling_sat.py
2. https://stackoverflow.com/questions/56872713/setting-binary-constraints-with-google-or-tools
3. https://activimetrics.com/blog/ortools/cp_sat/addboolor/