监考安排 https://www.v2ex.com/t/1092902

README.md

逻辑

假设监考员设置中的，监考科目和监考教室支持设置多个，以/作为分隔。

问题

缺少一些前置逻辑校验，若数据本身逻辑有问题，则可能会导致无解。

监考教室设置

• 必监考教室: 当前有两个逻辑: 只能在当前教室 / 至少在这个教室一次。但这个逻辑在一定条件下，会和不监考教室有冲突。
• 不监考教室: 当前老师，一定不会出现在该教室。

invigilation_schedule.py

"""
Filename: invigilation_schedule.py
Author: lpe234
Date: 2024-11-27
Version: 1.0
Description: 监考安排 https://www.v2ex.com/t/1092902
"""

from datetime import datetime

import pandas as pd
from numpy import ndarray
from ortools.sat.python import cp_model


class Teacher(object):

    def __init__(self, arr: ndarray[7]):
        self.no = arr[0]
        self.name = arr[1]
        self.s_y = arr[2]
        self.s_n = arr[3]
        self.r_y = arr[4]
        self.r_n = arr[5]
        self.times_limit = int(arr[6])

    def __str__(self):
        return f'T({self.no} {self.name} {self.times_limit})'

    def __repr__(self):
        return self.__str__()


class Subject(object):

    def __init__(self, arr: ndarray[4]):
        self.code = arr[0]
        self.name = arr[1]
        self.date = arr[2]
        self.time = arr[3]

    def __str__(self):
        return f'S({self.code} {self.name} {self.date} {self.time})'

    def __repr__(self):
        return self.__str__()


class Room(object):
    serials = []

    def __init__(self, arr: ndarray[10]):
        self.name = arr[0]
        self.nums = arr[1:]

    def __str__(self):
        return f'R({self.name} {self.nums})'

    def __repr__(self):
        return self.__str__()


def read_data() -> (list[Teacher], list[Subject], list[Room]):
    xlsx_file = '监考安排.xlsx'
    sheets = pd.read_excel(xlsx_file, sheet_name=None)
    pd_teachers = sheets['监考员设置']
    pd_subjects = sheets['考试科目设置']
    pd_rooms = sheets['考场设置']
    # 构建模型数据
    teachers = [Teacher(d) for d in pd_teachers.values if isinstance(d[1], str)]
    subjects = [Subject(d) for d in pd_subjects.values]
    Room.serials = pd_rooms.columns[1:].tolist()
    rooms = [Room(d) for d in pd_rooms.values]
    #
    return teachers, subjects, rooms


def write_data(res: list[(str, str, str)], teachers: list[Teacher], subjects: list[Subject], rooms: list[Room]):
    # 1 考场
    room_names = [r.name for r in rooms]
    room_data = {
        '考场': room_names
    }
    for s in subjects:
        room_data[s.name] = [[] for _ in rooms]
    for ss in subjects:
        for rs in rooms:
            for s, r, t in res:
                if ss.name == s and rs.name == r:
                    idx = room_names.index(r)
                    room_data[s][idx].append(t)
    # 整理下数据
    for ss in subjects:
        ds = room_data[ss.name]
        for idx in range(len(ds)):
            ds[idx] = ', '.join(ds[idx])
    # 2 老师
    teacher_names = [t.name for t in teachers]
    teacher_data = {
        '老师': teacher_names
    }
    for s in subjects:
        teacher_data[s.name] = [None for _ in teachers]
    for ss in subjects:
        for ts in teachers:
            for s, r, t in res:
                if ss.name == s and ts.name == t:
                    idx = teacher_names.index(t)
                    teacher_data[s][idx] = r
    # 写数据
    date_str = datetime.now().strftime('%Y%m%d_%H%M%S')
    with pd.ExcelWriter(f'监考安排_{date_str}.xlsx') as writer:
        pd.DataFrame(room_data).to_excel(excel_writer=writer, sheet_name='考场安排')
        pd.DataFrame(teacher_data).to_excel(excel_writer=writer, sheet_name='监考员安排')


def solve(teachers: list[Teacher], subjects: list[Subject], rooms: list[Room]):
    # 1. 初始化模型
    model = cp_model.CpModel()

    # 2. 创建变量
    inv_schedule = {}
    teacher_date = {}
    for s in subjects:
        for r in rooms:
            for t in teachers:
                var_name = f'subject_{s.name}_room_{r.name}_teacher_{t.name}'
                inv_schedule[(s.name, r.name, t.name)] = model.NewBoolVar(var_name)
        for t in teachers:
            var_name = f'teacher_{t.name}_date_{s.date}'
            teacher_date[(t.name, s.date)] = model.NewBoolVar(var_name)

    # 2. 添加约束
    # 同一科目，同一个老师，最多只能出现一次
    for s in subjects:
        for t in teachers:
            model.AddAtMostOne(inv_schedule[(s.name, r.name, t.name)] for r in rooms)
    # 同一科目 某教室，只能出现指定数量老师
    for s in subjects:
        for r in rooms:
            idx = r.serials.index(s.name)
            nums = r.nums[idx]
            model.Add(sum(inv_schedule[(s.name, r.name, t.name)] for t in teachers) == nums)
    # 同一老师限制最长场次
    for t in teachers:
        model.Add(sum(inv_schedule[(s.name, r.name, t.name)] for s in subjects for r in rooms) <= t.times_limit)
    # 限制 必监考科目/不监考科目
    for t in teachers:
        # 必监考科目
        if isinstance(t.s_y, str):
            sys = t.s_y.split('/')
            for sy in sys:
                model.AddExactlyOne(inv_schedule[(sy, r.name, t.name)] for r in rooms)
        # 不监考科目
        if isinstance(t.s_n, str):
            sns = t.s_n.split('/')
            for sn in sns:
                model.Add(sum(inv_schedule[(sn, r.name, t.name)] for r in rooms) == 0)
    # 限制 必监考教室/不监考教室
    for t in teachers:
        # 必监考教室
        if isinstance(t.r_y, str):
            rys = t.r_y.split('/')
            for ry in rys:
                # 逻辑1: 这个老师至少在这个教室一次
                # model.AddAtLeastOne(inv_schedule[(s.name, ry, t.name)] for s in subjects)
                # 逻辑2: 这个老师只能在这个教室
                model.Add(sum(inv_schedule[(s.name, r.name, t.name)] for s in subjects for r in rooms if r.name != ry) == 0)
        # 不监考教室
        if isinstance(t.r_n, str):
            rns = t.r_n.split('/')
            for rn in rns:
                model.Add(sum(inv_schedule[(s.name, rn, t.name)] for s in subjects) == 0)
    # 工作时间
    for t in teachers:
        for s in subjects:
            model.AddBoolOr([inv_schedule[(s.name, r.name, t.name)].Not() for r in rooms]).OnlyEnforceIf(
                teacher_date[(t.name, s.date)].Not())
            model.AddBoolOr([inv_schedule[(s.name, r.name, t.name)] for r in rooms]).OnlyEnforceIf(
                teacher_date[(t.name, s.date)])

    # 4. 定义目标函数
    # 尽量不要分散排 -> 每个老师工作的日期date数量最少 -> 全部老师工作日期最少
    model.Minimize(sum(teacher_date[(t.name, s.date)] for s in subjects for t in teachers))

    # 5. 添加求解器
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    # 6. 处理结果
    result = []
    if status == cp_model.OPTIMAL:
        for s in subjects:
            for r in rooms:
                for t in teachers:
                    if solver.boolean_value(inv_schedule[(s.name, r.name, t.name)]):
                        print(f'科目: {s.name}, 教室: {r.name}, 老师: {t.name}')
                        result.append((s.name, r.name, t.name))

    else:
        print('no solution')

    # 7. 返回结果
    return result


def main():
    teachers, subjects, rooms = read_data()
    result = solve(teachers, subjects, rooms)
    write_data(result, teachers, subjects, rooms)


if __name__ == '__main__':
    main()

感谢大佬提供的帮助，我试图理解和利用AI来补充（# 限制 必监考科目/不监考科目）、（限制 必监考教室/不监考教室），目前一直没成功。目前程序跑起来正常，盼望您帮我补充一下这两个约束条件，万谢。

感谢大佬提供的帮助，我试图理解和利用AI来补充（# 限制 必监考科目/不监考科目）、（限制 必监考教室/不监考教室），目前一直没成功。目前程序跑起来正常，盼望您帮我补充一下这两个约束条件，万谢。

更新了一下

真是很感谢帮忙更新了这两个功能，目前确实遇到no solution。我用手工排的数据模拟了一下，提示不监考场次（单人设置两次）超过40人就无解。将比监考全部切换到到不监考，同样也会提示无解。

手工解决这个问题的思路是先处理这些特殊设置的监考员，然后再用其他正常的监考员进行补充。

真是很感谢帮忙更新了这两个功能，目前确实遇到no solution。我用手工排的数据模拟了一下，提示不监考场次（单人设置两次）超过40人就无解。将比监考全部切换到到不监考，同样也会提示无解。

手工解决这个问题的思路是先处理这些特殊设置的监考员，然后再用其他正常的监考员进行补充。

https://github.com/lpe234/invigilation_schedule 新建了个仓库，来点测试数据吧