You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

基于OR-Tools CP-SAT的无重叠排课：房间分配冲突解决求助

avatar
AI 小北
2026-6-26
排课系统房间无重叠约束问题（OR-Tools CP-SAT）

问题描述

我正在使用OR-Tools的CP-SAT工具开发排课系统，核心要求是同一房间在同一天的排课时间不能重叠。目前已完成调度变量定义，但现有无重叠约束仅作用于时间维度，未关联房间和日期，导致房间分配仍存在重叠问题，需要解决这一约束缺失的问题。

调度变量定义代码 

def schedule_variable(self):
    for program in self.programs:
        for course in self.curriculum[program]:
            # 根据课程类型确定连续时间段数量
            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
            
            # 定义调度变量
            schedule1_room = self.model.NewIntVar(0, len(self.rooms) - 1, f'room_s1_{program}_{course}')
            schedule2_room = self.model.NewIntVar(0, len(self.rooms) - 1, f'room_s2_{program}_{course}')
            
            # 修正：将schedule2_day改为IntVar（原代码错误定义为IntervalVar）
            schedule1_day = self.model.NewIntVar(0, len(self.days) - 1, f'day_s1_{program}_{course}')
            schedule2_day = self.model.NewIntVar(0, len(self.days) - 1, f'day_s2_{program}_{course}')
            
            schedule_time_start = self.model.NewIntVar(0, len(self.times) - 1, f'start_s1_{program}_{course}')
            schedule_time_end = self.model.NewIntVar(0, len(self.times) - 1, f'end_s1_{program}_{course}')
            schedule2_time_start = self.model.NewIntVar(0, len(self.times) - 1, f'start_s2_{program}_{course}')
            schedule2_time_end = self.model.NewIntVar(0, len(self.times) - 1, f'end_s2_{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'instructor_{program}_{course}')
            
            # 更新调度字典
            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,
                }
            }

已实现的无重叠约束（仅时间维度）

以下代码仅全局约束时间区间不重叠，未关联房间和日期，无法满足需求：

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):
                # 仅约束时间维度，未关联房间和日期
                self.model.AddNoOverlap([details1['schedule1']['time'], details2['schedule1']['time']])
                self.model.AddNoOverlap([details1['schedule2']['time'], details2['schedule2']['time']])

运行输出 

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

解决方案

要实现房间无重叠，需约束同一房间、同一天的时间区间互不重叠。以下提供两种实现方式：

方式一：条件约束（直观易懂）

遍历所有课程对，仅当两个课程的房间和日期都相同时，约束时间区间不重叠：

def no_overlap_constraints(self):
    schedule_items = list(self.schedules.items())
    # 遍历所有不同课程对，避免重复约束
    for i in range(len(schedule_items)):
        (prog1, course1), details1 = schedule_items[i]
        for j in range(i + 1, len(schedule_items)):
            (prog2, course2), details2 = schedule_items[j]
            
            # 处理Schedule1的房间无重叠约束
            # 判断两个课程的schedule1是否同房间
            same_room_s1 = self.model.NewBoolVar(f"same_room_s1_{prog1}_{course1}_{prog2}_{course2}")
            self.model.Add(details1['schedule1']['room'] == details2['schedule1']['room']).OnlyEnforceIf(same_room_s1)
            self.model.Add(details1['schedule1']['room'] != details2['schedule1']['room']).OnlyEnforceIf(same_room_s1.Not())
            
            # 判断两个课程的schedule1是否同一天
            same_day_s1 = self.model.NewBoolVar(f"same_day_s1_{prog1}_{course1}_{prog2}_{course2}")
            self.model.Add(details1['schedule1']['day'] == details2['schedule1']['day']).OnlyEnforceIf(same_day_s1)
            self.model.Add(details1['schedule1']['day'] != details2['schedule1']['day']).OnlyEnforceIf(same_day_s1.Not())
            
            # 同房间且同一天时，时间区间必须无重叠
            self.model.AddNoOverlap([details1['schedule1']['time'], details2['schedule1']['time']]).OnlyEnforceIf(same_room_s1, same_day_s1)
            
            # 处理Schedule2的房间无重叠约束
            same_room_s2 = self.model.NewBoolVar(f"same_room_s2_{prog1}_{course1}_{prog2}_{course2}")
            self.model.Add(details1['schedule2']['room'] == details2['schedule2']['room']).OnlyEnforceIf(same_room_s2)
            self.model.Add(details1['schedule2']['room'] != details2['schedule2']['room']).OnlyEnforceIf(same_room_s2.Not())
            
            same_day_s2 = self.model.NewBoolVar(f"same_day_s2_{prog1}_{course1}_{prog2}_{course2}")
            self.model.Add(details1['schedule2']['day'] == details2['schedule2']['day']).OnlyEnforceIf(same_day_s2)
            self.model.Add(details1['schedule2']['day'] != details2['schedule2']['day']).OnlyEnforceIf(same_day_s2.Not())
            
            self.model.AddNoOverlap([details1['schedule2']['time'], details2['schedule2']['time']]).OnlyEnforceIf(same_room_s2, same_day_s2)

方式二：编码时间区间（高效优化）

将日期和时间合并为一个编码值（如day * 每日时间段数 + start_time），同一房间的所有编码后区间加无重叠约束，自动实现"同房间+同一天"的时间不重叠：

def no_overlap_constraints(self):
    max_time = len(self.times)
    total_time_slots = len(self.days) * max_time
    
    # 处理Schedule1
    room_intervals_s1 = {}
    for (prog, course), details in self.schedules.items():
        s1 = details['schedule1']
        # 编码日期+时间为一维变量
        encoded_start = self.model.NewIntVar(0, total_time_slots - 1, f"encoded_start_s1_{prog}_{course}")
        self.model.Add(encoded_start == s1['day'] * max_time + s1['time'].StartExpr())
        
        encoded_end = self.model.NewIntVar(0, total_time_slots - 1, f"encoded_end_s1_{prog}_{course}")
        self.model.Add(encoded_end == s1['day'] * max_time + s1['time'].EndExpr())
        
        encoded_interval = self.model.NewIntervalVar(encoded_start, s1['time'].SizeExpr(), encoded_end, f"encoded_interval_s1_{prog}_{course}")
        
        # 按房间分组
        room = s1['room']
        if room not in room_intervals_s1:
            room_intervals_s1[room] = []
        room_intervals_s1[room].append(encoded_interval)
    
    # 为每个房间的编码区间添加无重叠约束
    for intervals in room_intervals_s1.values():
        if len(intervals) >= 2:
            self.model.AddNoOverlap(intervals)
    
    # 处理Schedule2
    room_intervals_s2 = {}
    for (prog, course), details in self.schedules.items():
        s2 = details['schedule2']
        encoded_start = self.model.NewIntVar(0, total_time_slots - 1, f"encoded_start_s2_{prog}_{course}")
        self.model.Add(encoded_start == s2['day'] * max_time + s2['time'].StartExpr())
        
        encoded_end = self.model.NewIntVar(0, total_time_slots - 1, f"encoded_end_s2_{prog}_{course}")
        self.model.Add(encoded_end == s2['day'] * max_time + s2['time'].EndExpr())
        
        encoded_interval = self.model.NewIntervalVar(encoded_start, s2['time'].SizeExpr(), encoded_end, f"encoded_interval_s2_{prog}_{course}")
        
        room = s2['room']
        if room not in room_intervals_s2:
            room_intervals_s2[room] = []
        room_intervals_s2[room].append(encoded_interval)
    
    for intervals in room_intervals_s2.values():
        if len(intervals) >= 2:
            self.model.AddNoOverlap(intervals)

额外注意点

  1. 原代码中schedule2_day被错误定义为IntervalVar，需修正为IntVar，否则无法正确表示单个日期。
  2. 原约束仅遍历同一program的课程，需改为遍历所有课程对，确保跨program的课程也受房间约束。

内容的提问来源于stack exchange，提问作者Leiner

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
火山引擎 最新活动
全面开放
Doubao-Seedance-2.5全新模型升级

模型再升级,30秒超长叙事, 模态参考扩容

HOT
方舟Codingplan

模型自由，工具不限，最新支持 Deepseek-V4 系列、GLM-5.3 系列

HOT
方舟Agent plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列

HOT
新用户特惠专场

大模型19元起，Al应用9.9元畅享，新人首购爆款尽享优惠

最近更新时间：2026.06.26 17:44:50