Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

No overlapping Scheduling using CP-SAT in OR-Tools

can anyone help me on how can I prevent overlapping in my scheduling, the scheduling must be no overlap in terms of room assignment

def schedule_variable(self):
    for program in self.programs:
        for course in self.curriculum[program]:
            # Determine the number of intervals (consecutive hours/time slots) based on course type
            if self.course_type[course].lower() == 'laboratory':
                schedule1_num_of_interval = 3
                schedule2_num_of_interval = 2
            else:
                schedule1_num_of_interval = 2
                schedule2_num_of_interval = 1
            
            # Define scheduling variables
            schedule1_room = self.model.NewIntVar(0, len(self.rooms) - 1, f'room_{program}_{course}')
            schedule2_room = self.model.NewIntVar(0, len(self.rooms) - 1, f'room_{program}_{course}')
            
            schedule1_day = self.model.NewIntVar(0, len(self.days) - 1, f'day_{program}_{course}')
            schedule_for_interval_day = self.model.NewIntVar(0, len(self.days) - 1, f'day_{program}_{course}')
            schedule2_day = self.model.NewIntervalVar(schedule1_day, 3, schedule_for_interval_day, f'schedule2_{program}_{course}')
            
            schedule_time_start = self.model.NewIntVar(0, len(self.times) - 1, f'start_{program}_{course}')
            schedule_time_end = self.model.NewIntVar(0, len(self.times) - 1, f'end_{program}_{course}')
            schedule2_time_start = self.model.NewIntVar(0, len(self.times) - 1, f'start_{program}_{course}')
            schedule2_time_end = self.model.NewIntVar(0, len(self.times) - 1, f'end_{program}_{course}')
            schedule1_time = self.model.NewIntervalVar(schedule_time_start, schedule1_num_of_interval, schedule_time_end, f'schedule1_{program}_{course}')
            schedule2_time = self.model.NewIntervalVar(schedule2_time_start, schedule2_num_of_interval, schedule2_time_end, f'schedule2_{program}_{course}')
            
            instructor = self.model.NewIntVar(0, len(self.instructor) - 1, f'end_{program}_{course}')
            
            # Update the schedules dictionary
            self.schedules[program, course] = {
                'instructor': instructor,
                'schedule1': {
                    'room': schedule1_room,
                    'day': schedule1_day,
                    'time': schedule1_time,
                },
                'schedule2': {
                    'room': schedule2_room,
                    'day': schedule2_day,
                    'time': schedule2_time,
                }
            }

I tried this but it only constraints for time

def no_overlap_constraints(self):
    for (program, course1), details1 in self.schedules.items():
        for (program, course2), details2 in self.schedules.items():
            if (program, course1) != (program, course2):
                # Constraint for Schedule 1
                self.model.AddNoOverlap([details1['schedule1']['time'], details2['schedule1']['time']])
                self.model.AddNoOverlap([details1['schedule2']['time'], details2['schedule2']['time']])

this is the output

C:\Users\Admin\project\last>python main.py (0, 0): Instructor: 0 Schedule 1 - Room: 0, Day: 0, Time: 3-6 Schedule 2 - Room: 1, Day: 3, Time: 0-2 (0, 1): Instructor: 0 Schedule 1 - Room: 1, Day: 0, Time: 6-8 Schedule 2 - Room: 1, Day: 3, Time: 5-6 (1, 2): Instructor: 1 Schedule 1 - Room: 0, Day: 0, Time: 0-3 Schedule 2 - Room: 1, Day: 3, Time: 2-4 (1, 3): Instructor: 1 Schedule 1 - Room: 1, Day: 0, Time: 8-10 Schedule 2 - Room: 1, Day: 3, Time: 4-5 (2, 0): Instructor: 0 Schedule 1 - Room: 0, Day: 0, Time: 3-6 Schedule 2 - Room: 1, Day: 3, Time: 0-2 (2, 1): Instructor: 0 Schedule 1 - Room: 1, Day: 0, Time: 6-8 Schedule 2 - Room: 1, Day: 3, Time: 5-6 (3, 2): Instructor: 1 Schedule 1 - Room: 0, Day: 0, Time: 0-3 Schedule 2 - Room: 1, Day: 3, Time: 2-4 (3, 3): Instructor: 1 Schedule 1 - Room: 1, Day: 0, Time: 8-10 Schedule 2 - Room: 1, Day: 3, Time: 4-5

like image 303
Leiner Avatar asked Dec 01 '25 16:12

Leiner


1 Answers

You need 1 overlap per resource (teacher, room, group of students).

Then you collect all intervals for each resource, and you add all intervals to the same resource/no_overlap.

See how this is done in this flexible jobshop example.

like image 54
Laurent Perron Avatar answered Dec 03 '25 06:12

Laurent Perron