0. 说明
0.1 工程文件
Github 完整工程 :https://github.com/Raytto/ClassSchedule
0.2 排课说明包括实现思路
换另一篇文章：
0.3 Jupyter Notebook
In [ ]:
1. 数据设置¶
1.1 时空信息¶
In [1]:
# 班级序号
all_class_indexes = [i for i in range(1, 11)]
# all_class_indexes = [1]
# 天序号
all_days_indexes = [i for i in range(1, 8)]
# 每天天内的课程序号
all_course_indexes = [i for i in range(0, 14)]
1.2 时间化分¶
In [2]:
all_section = ["dawn", "morning", "afternoon", "evening"]
indexes_by_section = {
"dawn": [0],
"morning": [1, 2, 3, 4, 5],
"afternoon": [6, 7, 8, 9],
"evening": [10, 11, 12, 13],
}
max_section_len = max([len(x) for x in indexes_by_section.values()])
# time用(day,index)表示
time_by_section = {
"dawn": [(the_day, 0) for the_day in range(1, 7)], # 星期1到6都有早自习
"morning": [
(the_day, the_index)
for the_day in range(1, 6)
for the_index in indexes_by_section["morning"]
],
"afternoon": [
(the_day, the_index)
for the_day in range(1, 6)
for the_index in indexes_by_section["afternoon"]
],
"evening": [
(the_day, the_index)
for the_day in [1, 2, 3, 4, 5, 7]
for the_index in indexes_by_section["evening"]
], # 周天有晚自习
}
In [3]:
# time_by_section["evening"]
max_section_len
Out[3]:
5
1.3 课程信息¶
In [4]:
# 课程类型
all_subjects = [
"语文",
"美术",
"政治",
"地理",
"英语",
"心理",
"生物",
"体育",
"化学",
"音乐",
"历史",
"数学",
"物理",
"劳动",
"班会",
"", # 无课
]
In [5]:
# 一些不需要老师的课程
no_teacher_subjects = ["劳动", ""]
1.4 教师信息¶
In [6]:
# 教师信息：名字：负责的科目和科目对应的班级
teachers_duties = {
"teacher_28": {"语文": [1, 3]},
"teacher_59": {"数学": [1, 7]},
"teacher_18": {"英语": [1, 9]},
"teacher_15": {"政治": [1, 3]},
"teacher_6": {"历史": [1, 4, 6]},
"teacher_46": {"地理": [1, 2, 6], "班会": [1]},
"teacher_50": {"美术": [1, 2, 8, 9, 10]},
"teacher_51": {"化学": [1, 2]},
"teacher_13": {"物理": [1, 2, 4]},
"teacher_39": {"生物": [1, 9, 10]},
"teacher_29": {"心理": [1, 2, 8, 9, 10]},
"teacher_52": {"音乐": [1, 2, 9, 10]},
"teacher_22": {"体育": [1, 2, 8, 9, 10]},
"teacher_24": {"英语": [2, 6]},
"teacher_53": {"数学": [2]},
"teacher_2": {"语文": [2], "班会": [2]},
"teacher_35": {"生物": [2, 4, 8]},
"teacher_57": {"历史": [2, 3, 7]},
"teacher_37": {"政治": [2, 7]},
"teacher_26": {"英语": [3, 7]},
"teacher_32": {"数学": [3], "班会": [3]},
"teacher_54": {"地理": [3, 4, 5]},
"teacher_20": {"物理": [3]},
"teacher_1": {"音乐": [3, 4, 5, 6, 7, 8]},
"teacher_23": {"生物": [3, 6], "班会": [6]},
"teacher_42": {"化学": [3, 9]},
"teacher_43": {"美术": [3, 4, 5, 6, 7]},
"teacher_12": {"体育": [3, 4, 5, 6, 7]},
"teacher_44": {"心理": [3, 4, 5, 6, 7]},
"teacher_7": {"语文": [4, 8]},
"teacher_8": {"数学": [4, 10]},
"teacher_16": {"英语": [4, 10]},
"teacher_55": {"化学": [4, 7], "班会": [4]},
"teacher_33": {"政治": [4, 5, 10]},
"teacher_34": {"语文": [5, 9]},
"teacher_19": {"数学": [5, 6]},
"teacher_40": {"物理": [5, 7], "班会": [7]},
"teacher_41": {"英语": [5, 8]},
"teacher_45": {"生物": [5, 7]},
"teacher_25": {"化学": [5, 6], "班会": [5]},
"teacher_30": {"历史": [5, 8, 9, 10]},
"teacher_9": {"语文": [6]},
"teacher_27": {"物理": [6, 9]},
"teacher_17": {"政治": [6]},
"teacher_21": {"语文": [7, 10]},
"teacher_10": {"地理": [7, 8, 9, 10]},
"teacher_47": {"数学": [8], "班会": [8]},
"teacher_14": {"政治": [8, 9]},
"teacher_36": {"物理": [8, 10], "班会": [10]},
"teacher_31": {"化学": [8, 10]},
"teacher_38": {"数学": [9], "班会": [9]},
}
1.5 班级信息¶
In [7]:
# 班级分了物理和历史两个方向
all_foucs = ["physics", "history"]
# 方向和班级序号的关系
class_foucs_info = {"physics": [3, 4, 5, 6, 7, 8, 9, 10], "history": [1, 2]}
1.6 各班的科目数量要求¶
针对 “对某种方向的班级，某时间集合内，要求某科目数量刚好为n” 这种需求
In [8]:
# 用一个数据结构描述,每一个要求为(foucs,[(day1,index1),(day2,index2)], aim_subject, aim_num)
subject_num_requirements = []
1.6.1 早自习要求¶
每班 周一到周六 ，早自习课程要求 语文英语各3节
In [9]:
morning_time_set = [(the_day, 0) for the_day in range(1, 7)]
for the_foucs in all_foucs:
for the_subject in ["语文", "英语"]:
subject_num_requirements.append((the_foucs, morning_time_set, the_subject, 3))
1.6.2 正课数量要求¶
In [10]:
# 正课程数量要求
subject_requirement_in_regular = {
"physics": {
"语文": 6,
"数学": 7,
"英语": 8,
"物理": 5,
"化学": 4,
"生物": 3,
"政治": 2,
"历史": 2,
"地理": 2,
"体育": 2,
"心理": 1,
"劳动": 1,
"美术": 1,
"音乐": 1,
},
"history": {
"语文": 6,
"数学": 7,
"英语": 8,
"物理": 2,
"化学": 2,
"生物": 2,
"政治": 4,
"历史": 4,
"地理": 4,
"体育": 2,
"心理": 1,
"劳动": 1,
"美术": 1,
"音乐": 1,
},
}
for the_foucs in subject_requirement_in_regular.keys():
for the_subject, the_num in subject_requirement_in_regular[the_foucs].items():
subject_num_requirements.append(
(
the_foucs,
(time_by_section["morning"] + time_by_section["afternoon"]),
the_subject,
the_num,
)
)
1.6.3 晚自习数量要求¶
In [11]:
### 晚自数要求
subject_num_in_evening = {
"physics": {
"语文": 3,
"数学": 4,
"英语": 3,
"物理": 4,
"化学": 3,
"生物": 3,
"政治": 1,
"历史": 1,
"地理": 1,
"班会": 1,
},
"history": {
"语文": 3,
"数学": 4,
"英语": 3,
"物理": 1,
"化学": 1,
"生物": 1,
"政治": 3,
"历史": 4,
"地理": 3,
"班会": 1,
},
}
for the_foucs in subject_num_in_evening.keys():
for the_subject, the_num in subject_num_in_evening[the_foucs].items():
subject_num_requirements.append(
(the_foucs, time_by_section["evening"], the_subject, the_num)
)
In [12]:
# time_by_section["evening"]
1.6.4 休息时间要求¶
In [13]:
rest_time_set = []
for the_index in (
indexes_by_section["morning"]
+ indexes_by_section["afternoon"]
+ indexes_by_section["evening"]
):
rest_time_set.append((6, the_index))
for the_index in (
indexes_by_section["dawn"]
+ indexes_by_section["morning"]
+ indexes_by_section["afternoon"]
):
rest_time_set.append((7, the_index))
for the_foucs in all_foucs:
subject_num_requirements.append((the_foucs, rest_time_set, "", len(rest_time_set)))
In [14]:
# rest_time_set
1.6.5 特殊课程要求¶
In [15]:
for the_foucs in all_foucs:
# 星期天第一节晚自习上班会
subject_num_requirements.append((the_foucs, [(7, 10)], "班会", 1))
# 星期一下午最后一节上劳动
subject_num_requirements.append((the_foucs, [(1, 9)], "劳动", 1))
In [16]:
# subject_num_requirements
In [17]:
len(rest_time_set)
Out[17]:
23
1.2 特殊信息¶
1.2.1 教研时间段¶
In [18]:
jiaoyan_day_section = {
"语文": (4, "afternoon"),
"数学": (3, "morning"),
"英语": (1, "afternoon"),
"物理": (4, "afternoon"),
"化学": (2, "morning"),
"生物": (2, "morning"),
"政治": (5, "morning"),
"历史": (5, "morning"),
"地理": (4, "afternoon"),
"体育": (1, "morning"),
"音乐": (1, "morning"),
"美术": (1, "morning"),
"心理": (1, "morning"),
}
2. 预处理¶
In [19]:
# 生成一个通过班级和课程找到老师的映射表，方便后续查询
# 需要要求一个班的同一科目只有一个老师负责
map_class_subject_to_teacher = {} # by (the_class_index,the_subject)
for the_teacher, duties in teachers_duties.items():
for the_subject, the_classes in duties.items():
for the_class_index in the_classes:
map_class_subject_to_teacher[(the_class_index, the_subject)] = the_teacher
# 一些课程不需要老师
for the_class_index in all_class_indexes:
for the_subject in no_teacher_subjects:
map_class_subject_to_teacher[(the_class_index, the_subject)] = ""
In [20]:
# str(map_class_subject_to_teacher)
In [21]:
# 生成一些方便后续使用的变量
all_teachers = teachers_duties.keys()
classes_of_teacher = {}
subjects_of_teacher = {}
for the_teacher, duties in teachers_duties.items():
classes_of_teacher[the_teacher] = []
subjects_of_teacher[the_teacher] = []
for the_subject, the_classes in duties.items():
classes_of_teacher[the_teacher] = list(
set(classes_of_teacher[the_teacher]) | set(the_classes)
)
if the_subject not in subjects_of_teacher[the_teacher]:
subjects_of_teacher[the_teacher].append(the_subject)
In [22]:
# classes_of_teacher
3. 设置模型¶
口语课是单周口语，双周英语，单独用一个变量来记
3.1 求解目标变量¶
In [23]:
from ortools.sat.python import cp_model
# 创建模型
model = cp_model.CpModel()
# 创建目标变量：每班每节课的科目
# model.course_vars = Var(
# all_class_indexes,
# all_days_indexes,
# all_course_indexes,
# all_subjects,
# domain=Binary,
# )
course_vars = {}
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_index in all_course_indexes:
for the_subject in all_subjects:
course_vars[the_class,the_day,the_index,the_subject] = model.NewBoolVar(f'course_vars{the_class}_{the_day}_{the_index}_{the_subject}')
# 创建目标变量：每班每节课是否是外教课
# model.is_spoken_course = Var(
# model.all_class_indexes,
# model.all_days_indexes,
# model.all_course_indexes,
# domain=Binary,
# )
is_spoken_course = {}
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_index in all_course_indexes:
is_spoken_course[the_class,the_day,the_index] = model.NewBoolVar(f'is_spoken_course{the_class}_{the_day}_{the_index}')
3.1 预设一些通用约束函数¶
3.1.1 逻辑与约束¶
In [24]:
def logic_cons_and(model,a,xs):
model.AddBoolAnd(xs).OnlyEnforceIf(a)
model.AddBoolOr([x.Not() for x in xs]).OnlyEnforceIf(a.Not())
3.2 设置辅助变量¶
In [25]:
## 老师是否在上课或者教研的变量
teacher_time_vars = {}
for the_teacher in all_teachers:
for the_day in all_days_indexes:
for the_index in all_course_indexes:
teacher_time_vars[the_teacher,the_day,the_index] = model.NewBoolVar(f'teacher_time_vars{the_teacher}_{the_day}_{the_index}')
## bigM，用于一些约束中使非线性约束转化为线性约束
bigM = 10000
# 可以有连续课程的section
indexes_could_consecutive = (
indexes_by_section["morning"][:-1]
+ indexes_by_section["afternoon"][:-1]
+ indexes_by_section["evening"][:-1]
)
In [26]:
# 创建变量指针哪些课程将连续上(对班级而言)
will_consecutive_by_class_time_subject = {}
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_index in indexes_could_consecutive:
for the_subject in all_subjects:
will_consecutive_by_class_time_subject[the_class,the_day,the_index,the_subject] = model.NewBoolVar(f'will_consecutive_by_class_time_subject_{the_class}_{the_day}_{the_index}_{the_subject}')
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_index in indexes_could_consecutive:
for the_subject in all_subjects:
logic_cons_and(
model,
will_consecutive_by_class_time_subject[
the_class, the_day, the_index, the_subject
],
[
course_vars[the_class, the_day, the_index, the_subject],
course_vars[
the_class, the_day, the_index + 1, the_subject
],
],
)
# 创建变量计算每班每个day_section内每科有多少连续次数(对班级而言)
sections_could_consecutive = [x for x in all_section if x != "dawn"]
consecutive_num_by_class_day_section_subject = {}
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_section in sections_could_consecutive:
for the_subject in all_subjects:
consecutive_num_by_class_day_section_subject[the_class,the_day,the_section,the_subject] = model.NewIntVar(0, max_section_len, f'consecutive_num_by_class_day_section_subject_{the_class}_{the_day}_{the_section}_{the_subject}')
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_section in sections_could_consecutive:
for the_subject in all_subjects:
model.Add(
consecutive_num_by_class_day_section_subject[
the_class, the_day, the_section, the_subject
]
== sum(
will_consecutive_by_class_time_subject[
the_class, the_day, the_index, the_subject
]
for the_index in indexes_by_section[the_section][:-1]
)
)
# 创建变量计算每班每个day_section内每科有多少节课(对班级而言)
num_by_class_day_section_subject = {}
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_section in all_section:
for the_subject in all_subjects:
num_by_class_day_section_subject[the_class,the_day,the_section,the_subject] = model.NewIntVar(0, max_section_len, f'num_by_class_day_section_subject_{the_class}_{the_day}_{the_section}_{the_subject}')
# 创建变量对应每班每个day_section内每科是否有课(对班级而言)
any_by_class_day_section_subject = {}
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_section in all_section:
for the_subject in all_subjects:
any_by_class_day_section_subject[the_class,the_day,the_section,the_subject] = model.NewBoolVar(f'any_by_class_day_section_subject_{the_class}_{the_day}_{the_section}_{the_subject}')
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_section in all_section:
for the_subject in all_subjects:
model.Add(
num_by_class_day_section_subject[
the_class, the_day, the_section, the_subject
]
== sum(
course_vars[the_class, the_day, the_index, the_subject]
for the_index in indexes_by_section[the_section]
)
)
# 用 b<=M*a
# b>=0.5-M(1-a)
# 约束a=1 if b >0 else a=0
a = any_by_class_day_section_subject[
the_class, the_day, the_section, the_subject
]
b = num_by_class_day_section_subject[
the_class, the_day, the_section, the_subject
]
model.Add(b>0).OnlyEnforceIf(a)
model.Add(b==0).OnlyEnforceIf(a.Not())
# model.Add(b <= a * bigM)
# model.Add(b >= 1 - bigM * (1 - a))
In [27]:
# 创建变量计算每老师每个day_section内每科有多少节课(对老师而言)
num_by_teacher_day_section = {}
for the_teacher in all_teachers:
for the_day in all_days_indexes:
for the_section in all_section:
num_by_teacher_day_section[the_teacher,the_day,the_section] = model.NewIntVar(0, max_section_len, f'num_by_teacher_day_section_{the_teacher}_{the_day}_{the_section}')
# 创建变量对应每老师每个day_section内每科是否有课(对老师而言)
any_by_teacher_day_section = {}
for the_teacher in all_teachers:
for the_day in all_days_indexes:
for the_section in all_section:
any_by_teacher_day_section[the_teacher,the_day,the_section] = model.NewBoolVar( f'any_by_teacher_day_section{the_teacher}_{the_day}_{the_section}')
for the_teacher in all_teachers:
for the_day in all_days_indexes:
for the_section in all_section:
# for the_subject in all_subjects:
has_jiaoyan = 0
for the_subject in set(teachers_duties[the_teacher].keys()) & set(
jiaoyan_day_section.keys()
):
if (
the_section == jiaoyan_day_section[the_subject][1]
and the_day == jiaoyan_day_section[the_subject][0]
):
has_jiaoyan = 1
model.Add(
num_by_teacher_day_section[the_teacher, the_day, the_section]
== sum(
course_vars[the_class, the_day, the_index, the_subject]
for the_index in indexes_by_section[the_section]
for the_subject, the_class_list in teachers_duties[
the_teacher
].items()
for the_class in the_class_list
)
+ has_jiaoyan
)
# 用 b<=M*a
# b>=0.5-M(1-a)
# 约束a=1 if b >0 else a=0
a = any_by_teacher_day_section[the_teacher, the_day, the_section]
b = num_by_teacher_day_section[the_teacher, the_day, the_section]
model.Add(b>0).OnlyEnforceIf(a)
model.Add(b==0).OnlyEnforceIf(a.Not())
# model.add(b <= a * bigM)
# model.add(b >= 1 - bigM * (1 - a))
4. 加约束¶
4.1 最基本约束¶
4.1.1 每教师同时至多上一节课¶
In [ ]:
In [28]:
# 定义约束
for the_teacher in all_teachers:
for the_day in all_days_indexes:
for the_index in all_course_indexes:
has_jiaoyan = 0
for the_subject in set(teachers_duties[the_teacher].keys()) & set(
jiaoyan_day_section.keys()
):
if (
the_index in indexes_by_section[jiaoyan_day_section[the_subject][1]]
and the_day == jiaoyan_day_section[the_subject][0]
):
has_jiaoyan = 1
break
model.Add(
teacher_time_vars[the_teacher, the_day, the_index]
== (
sum(
course_vars[(the_class, the_day, the_index, the_subject)]
for the_subject, the_class_list in teachers_duties[the_teacher].items()
for the_class in set(the_class_list)&set(all_class_indexes)
if the_class in all_class_indexes
)
+ has_jiaoyan
)
)
# if the_teacher == "teacher_24" and the_day ==1 and the_index == 7:
# print(has_jiaoyan)
In [29]:
# model.teacher_time_constraint.pprint()
In [30]:
# # teachers_duties
# model.addCons(course_vars[(2, 1, 6, "英语")] == 1)
# model.addCons(course_vars[(2, 1, 7, "英语")] == 1)
# model.addCons(course_vars[(2, 1, 8, "英语")] == 1)
# model.addCons(
# teacher_time_vars[(the_teacher, the_day, the_index)]
# == quicksum([course_vars[(2, 1, 6, "英语")] , course_vars[(6, 1, 6, "英语")]])
# + (1 == jiaoyan_day_section["英语"][0]) * (1 in [1, 2, 3])
# )
In [31]:
# (1 == jiaoyan_day_section["英语"][0]) * (1 in [1, 2, 3])
4.1.2 每班同时仅上一节课¶
包含空课
In [32]:
# 定义约束
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_index in all_course_indexes:
model.Add(
sum(
course_vars[the_class, the_day, the_index, the_subject]
for the_subject in all_subjects
)
== 1
)
4.2 各时段课程数量约束¶
In [33]:
for the_class in all_class_indexes:
the_class_foucs = "history"
if the_class_index in class_foucs_info["physics"]:
the_class_foucs = "physics"
for the_foucs, time_set, aim_subject, aim_num in subject_num_requirements:
if the_foucs == the_class_foucs:
# print(the_foucs," ",time_set," ",aim_subject," ",aim_num)
model.add(
sum(
course_vars[
(
the_class,
aim_day,
aim_index,
aim_subject,
)
]
for aim_day, aim_index in time_set
)
== aim_num
)
In [ ]:
4.3 特殊约束¶
4.3.1 口语课要求¶
In [34]:
# 约束 : 对每个班的任意时间而言，单周的口语在双周对应英语
for a_class in all_class_indexes:
for a_day in all_days_indexes:
for a_course_Indices in all_course_indexes:
model.Add(
course_vars[(a_class, a_day, a_course_Indices, "英语")]
>= is_spoken_course[(a_class, a_day, a_course_Indices)]
)
# 约束 : 每个班每周需要一节口语课
for the_class in all_class_indexes:
model.Add(
sum(
is_spoken_course[(the_class, the_day, the_index)]
for the_day in all_days_indexes
for the_index in all_course_indexes
)
== 1
)
# 约束 : 同一时间只能有一节口语课
for the_day in all_days_indexes:
for the_index in all_course_indexes:
model.Add(
sum(
is_spoken_course[(the_class, the_day, the_index)]
for the_class in all_class_indexes
)
<= 1
)
# 约束 : 口语仅在周一周五正课阶段上
for the_class in all_class_indexes:
for the_day in [2, 3, 4, 6, 7]:
for the_index in all_course_indexes:
model.Add(
is_spoken_course[(the_class, the_day, the_index)] == 0
)
for the_day in [1, 5]:
for the_index in indexes_by_section["dawn"] + indexes_by_section["evening"]:
model.Add(
is_spoken_course[(the_class, the_day, the_index)] == 0
)
4.3.2 每班每科正课每天数量限制¶
语数外 至少1节，至多2节 其他科目至多1节
In [35]:
main_subjects = ["语文","数学","英语"]
for the_class in all_class_indexes:
for the_day in [1,2,3,4,5]:
for the_subject in filter(lambda x: x != "", all_subjects):
if the_subject in main_subjects:
model.Add(
sum(
course_vars[
(
the_class,
the_day,
the_index,
the_subject,
)
]
for the_index in (
indexes_by_section["morning"] + indexes_by_section["afternoon"]
)
)
<= 2
)
model.Add(
sum(
course_vars[
(
the_class,
the_day,
the_index,
the_subject,
)
]
for the_index in (
indexes_by_section["morning"] + indexes_by_section["afternoon"]
)
)
>= 1
)
else:
model.Add(
sum(
course_vars[
(
the_class,
the_day,
the_index,
the_subject,
)
]
for the_index in (
indexes_by_section["morning"] + indexes_by_section["afternoon"]
)
)
<= 1
)
4.3.3 每班每科晚自习每天至多两节¶
In [36]:
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_subject in filter(lambda x: x != "", all_subjects):
model.Add(
sum(
course_vars[
(
the_class,
the_day,
the_index,
the_subject,
)
]
for the_index in indexes_by_section["evening"]
)
<= 2
)
4.3.4 每个班而言每个时间段内的相同两节课需要连续¶
In [37]:
# 创建连续约束，每班每个day_section内，同课程要么没有，要么数量是连续次数+1
# if k then a=b-1 转线性约束
# a>=b-1-M*(1-k)
# a<=b-1+M*(1-k)
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_section in sections_could_consecutive:
for the_subject in all_subjects:
a = consecutive_num_by_class_day_section_subject[
the_class, the_day, the_section, the_subject
]
b = num_by_class_day_section_subject[
the_class, the_day, the_section, the_subject
]
k = any_by_class_day_section_subject[
the_class, the_day, the_section, the_subject
]
model.Add(a==b-1).OnlyEnforceIf(k)
# model.Add(a >= b - 1 - bigM * (1 - k))
# model.Add(a <= b - 1 + bigM * (1 - k))
4.3.5 每个班每天每科不会上下午都上¶
In [38]:
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_subject in filter(lambda x: x != "", all_subjects):
model.Add(
any_by_class_day_section_subject[
the_class, the_day, "morning", the_subject
]
+ any_by_class_day_section_subject[
the_class, the_day, "afternoon", the_subject
]
<= 1
)
4.3.6 周五下午行政不排课¶
In [39]:
### 周五下午行政不排课
xingzheng_teachers = [
"teacher_56",
"teacher_3",
"teacher_48",
"teacher_53",
"teacher_49",
"teacher_4",
"teacher_29",
"teacher_20",
"teacher_11",
"teacher_58",
"teacher_5",
]
for the_teacher in xingzheng_teachers:
if the_teacher not in teachers_duties.keys():
# print(f" teacher {the_teacher} has no class")
continue
for the_subject, the_classes in teachers_duties[the_teacher].items():
for the_class in the_classes:
for the_index in indexes_by_section["afternoon"]:
model.Add(
course_vars[(the_class, 5, the_index, the_subject)] == 0
)
4.3.7 教研时间不上课¶
In [40]:
# for the_subject, all_the_times in jaoyan_requirement.items():
# for the_day, the_section in all_the_times:
# for the_index in index_section[the_section]:
# for the_teacher in all_teachers:
# if teachers_and_subjects_map[the_teacher] == the_subject:
# for the_class in teachers_and_class_map[the_teacher]:
# model.Add(
# course_vars[(the_class, the_day, the_index, the_subject)]
# == 0
# )
4.3.8 如果下午是教研会晚上一般不安排晚自习¶
In [41]:
for the_subject, day_section in jiaoyan_day_section.items():
the_day, the_section = day_section
if the_section == "afternoon":
for the_index in indexes_by_section["evening"]:
for the_class in all_class_indexes:
model.Add(
course_vars[(the_class, the_day, the_index, the_subject)] == 0
)
4.3.9 各班各科每周的晚自习前后均匀¶
前两节晚自习数量 与 后两节晚自习数量的差值低于1
In [42]:
half_evening = {"early": [10, 11], "late": [12, 13]}
half_evening_num_by_class_half_subject = {}
for half_name in half_evening.keys():
for the_class in all_class_indexes:
for the_subject in all_subjects:
half_evening_num_by_class_half_subject[half_name,the_class,the_subject] = model.NewIntVar(0, max_section_len* len(all_days_indexes), f'half_evening_num_by_class_half_subject{half_name}_{the_class}_{the_subject}')
for the_class in all_class_indexes:
for the_subject in filter(lambda x: x != "", all_subjects):
for the_half_name, the_half_indexes in half_evening.items():
model.Add(
half_evening_num_by_class_half_subject[
the_half_name, the_class, the_subject
]
== sum(
course_vars[the_class, the_day, the_index, the_subject]
for the_day in all_days_indexes
for the_index in the_half_indexes
)
)
model.Add(
half_evening_num_by_class_half_subject[
"early", the_class, the_subject
]
- half_evening_num_by_class_half_subject[
"late", the_class, the_subject
]
<= 1
)
model.Add(
half_evening_num_by_class_half_subject["late", the_class, the_subject]
- half_evening_num_by_class_half_subject[
"early", the_class, the_subject
]
<= 1
)
In [ ]:
5. 加目标¶
5.1 子目标¶
5.1.1 教师需要出现的section总数尽量少¶
In [43]:
teacher_num_by_day_section = {}
for the_day in all_days_indexes:
for the_section in all_section:
teacher_num_by_day_section[the_day, the_section] = model.NewIntVar(0, len(all_teachers), f'teacher_num_by_day_section_{the_day}_{the_section}')
for the_day in all_days_indexes:
for the_section in all_section:
model.Add(
teacher_num_by_day_section[the_day, the_section]
== sum(
any_by_teacher_day_section[the_teacher, the_day, the_section]
for the_teacher in all_teachers
)
)
total_teacher_shows_day_section = model.NewIntVar(
0, len(all_teachers) * len(all_days_indexes) * len(all_section),f"total_teacher_shows_day_section"
)
model.Add(
total_teacher_shows_day_section
== sum(
teacher_num_by_day_section[the_day, the_section]
for the_day in all_days_indexes
for the_section in all_section
)
)
Out[43]:
<ortools.sat.python.cp_model.Constraint at 0x18991b60150>
5.1.2 老师每天课程集中得尽量多¶
靠目标函数中的系数体现我们希望各个出现的倾向性
In [44]:
care_section_from_to = [
("dawn","morning"),
("dawn","afternoon"),
("dawn","evening"),
("morning","afternoon"),
("afternoon","evening"),
("morning","evening"),
]
teacher_times_by_section_from_to = {}
teacher_day_section_from_to = {}
for section_from,section_to in care_section_from_to:
teacher_times_by_section_from_to[section_from,section_to] = model.NewIntVar(
0, len(all_teachers)*len(all_days_indexes),
f'teacher_times_by_section_from_to_{section_from}_{section_to}'
)
for section_from,section_to in care_section_from_to:
for the_teacher in all_teachers:
for the_day in [1,2,3,4,5]:
teacher_day_section_from_to[the_teacher,the_day,section_from,section_to] = model.NewBoolVar(
f'teacher_day_section_from_to_{the_teacher}_{the_day}_{section_from}_{section_to}'
)
for the_teacher in all_teachers:
for the_day in [1,2,3,4,5]:
a = teacher_day_section_from_to[the_teacher, the_day, "dawn","morning"]
b = any_by_teacher_day_section[the_teacher, the_day, "dawn"]
c = any_by_teacher_day_section[the_teacher, the_day, "morning"]
d = any_by_teacher_day_section[the_teacher, the_day, "afternoon"].Not()
e = any_by_teacher_day_section[the_teacher, the_day, "evening"].Not()
model.AddBoolAnd([b, c,d,e]).OnlyEnforceIf(a) # b and c 必须为 True 时，a 为 True
model.AddBoolOr([b.Not(),c.Not(),d.Not(),e.Not()]).OnlyEnforceIf(a.Not())
model.Add(
teacher_times_by_section_from_to["dawn","morning"]
== sum (
teacher_day_section_from_to[the_teacher, the_day, "dawn","morning"]
for the_teacher in all_teachers
for the_day in [1,2,3,4,5]
)
)
for the_teacher in all_teachers:
for the_day in [1,2,3,4,5]:
a = teacher_day_section_from_to[the_teacher, the_day, "dawn","afternoon"]
b = any_by_teacher_day_section[the_teacher, the_day, "dawn"]
d = any_by_teacher_day_section[the_teacher, the_day, "afternoon"]
e = any_by_teacher_day_section[the_teacher, the_day, "evening"].Not()
model.AddBoolAnd([b,d,e]).OnlyEnforceIf(a) # b and c 必须为 True 时，a 为 True
model.AddBoolOr([b.Not(),d.Not(),e.Not()]).OnlyEnforceIf(a.Not())
model.Add(
teacher_times_by_section_from_to["dawn","afternoon"]
== sum (
teacher_day_section_from_to[the_teacher, the_day, "dawn","afternoon"]
for the_teacher in all_teachers
for the_day in [1,2,3,4,5]
)
)
for the_teacher in all_teachers:
for the_day in [1,2,3,4,5]:
a = teacher_day_section_from_to[the_teacher, the_day, "dawn","evening"]
e = any_by_teacher_day_section[the_teacher, the_day, "evening"]
model.AddBoolAnd([b,e]).OnlyEnforceIf(a) # b and c 必须为 True 时，a 为 True
model.AddBoolOr([b.Not(),e.Not()]).OnlyEnforceIf(a.Not())
model.Add(
teacher_times_by_section_from_to["dawn","evening"]
== sum (
teacher_day_section_from_to[the_teacher, the_day, "dawn","evening"]
for the_teacher in all_teachers
for the_day in [1,2,3,4,5]
)
)
for the_teacher in all_teachers:
for the_day in [1,2,3,4,5]:
a = teacher_day_section_from_to[the_teacher, the_day, "morning","afternoon"]
b = any_by_teacher_day_section[the_teacher, the_day, "dawn"].Not()
f = any_by_teacher_day_section[the_teacher, the_day, "morning"]
d = any_by_teacher_day_section[the_teacher, the_day, "afternoon"]
e = any_by_teacher_day_section[the_teacher, the_day, "evening"].Not()
model.AddBoolAnd([b,d,e,f]).OnlyEnforceIf(a) # b and c 必须为 True 时，a 为 True
model.AddBoolOr([b.Not(),d.Not(),e.Not(),f.Not()]).OnlyEnforceIf(a.Not())
model.Add(
teacher_times_by_section_from_to["morning","afternoon"]
== sum (
teacher_day_section_from_to[the_teacher, the_day, "morning","afternoon"]
for the_teacher in all_teachers
for the_day in [1,2,3,4,5]
)
)
for the_teacher in all_teachers:
for the_day in [1,2,3,4,5]:
a = teacher_day_section_from_to[the_teacher, the_day, "morning","evening"]
b = any_by_teacher_day_section[the_teacher, the_day, "dawn"].Not()
f = any_by_teacher_day_section[the_teacher, the_day, "morning"]
e = any_by_teacher_day_section[the_teacher, the_day, "evening"]
model.AddBoolAnd([b,e,f]).OnlyEnforceIf(a) # b and c 必须为 True 时，a 为 True
model.AddBoolOr([b.Not(),e.Not(),f.Not()]).OnlyEnforceIf(a.Not())
model.Add(
teacher_times_by_section_from_to["morning","evening"]
== sum (
teacher_day_section_from_to[the_teacher, the_day, "morning","evening"]
for the_teacher in all_teachers
for the_day in [1,2,3,4,5]
)
)
for the_teacher in all_teachers:
for the_day in [1,2,3,4,5]:
a = teacher_day_section_from_to[the_teacher, the_day, "afternoon","evening"]
b = any_by_teacher_day_section[the_teacher, the_day, "dawn"].Not()
f = any_by_teacher_day_section[the_teacher, the_day, "morning"].Not()
c = any_by_teacher_day_section[the_teacher, the_day, "afternoon"]
e = any_by_teacher_day_section[the_teacher, the_day, "evening"]
model.AddBoolAnd([b,e,c,f]).OnlyEnforceIf(a) # b and c 必须为 True 时，a 为 True
model.AddBoolOr([b.Not(),e.Not(),c.Not(),f.Not()]).OnlyEnforceIf(a.Not())
model.Add(
teacher_times_by_section_from_to["afternoon","evening"]
== sum (
teacher_day_section_from_to[the_teacher, the_day, "afternoon","evening"]
for the_teacher in all_teachers
for the_day in [1,2,3,4,5]
)
)
Out[44]:
<ortools.sat.python.cp_model.Constraint at 0x18992d35610>
5.2 综合目标函数¶
In [45]:
model.Minimize(
teacher_num_by_day_section[1, "evening"] * 100
+ teacher_num_by_day_section[2, "evening"] * 100
+ teacher_num_by_day_section[3, "evening"] * 100
+ teacher_num_by_day_section[4, "evening"] * 100
+ teacher_num_by_day_section[5, "evening"] * 100
+ teacher_num_by_day_section[7, "evening"] * 1000
+ total_teacher_shows_day_section * 10
- teacher_times_by_section_from_to["dawn","morning"] * 5
- teacher_times_by_section_from_to["afternoon","evening"] *5
+ teacher_times_by_section_from_to["dawn","afternoon"] * 5
+ teacher_times_by_section_from_to["morning","afternoon"] * 5
+ teacher_times_by_section_from_to["morning","evening"] * 20
+ teacher_times_by_section_from_to["dawn","evening"] * 200
)
6. 求解¶
In [46]:
import json
load_course_var = {}
with open('course_save_var_22500.json', 'r') as f:
load_course_var = json.load(f)
for the_class in all_class_indexes:
for the_day in all_days_indexes:
for the_index in all_course_indexes:
for the_subject in all_subjects:
str_key = str((the_class,the_day,the_index,the_subject))
model.AddHint(course_vars[the_class,the_day,the_index,the_subject],load_course_var[str_key])
6.1 使用OR-TOOLS求解¶
In [47]:
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
def __init__(self):
cp_model.CpSolverSolutionCallback.__init__(self)
print(f"Start to find Solution")
self.__solution_count = 0
def OnSolutionCallback(self):
# This method is called each time the solver finds a solution.
print(f"Solution {self.__solution_count} : Objective Value = {self.ObjectiveValue()} Time = {self.WallTime()} s")
# Access variables using the Value method, e.g., `self.Value(var_name)`
self.__solution_count += 1
In [48]:
solution_printer = SolutionPrinter()
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 600
status = solver.Solve(model,solution_printer)
Start to find Solution Solution 0 : Objective Value = 43355.0 Time = 12.4189241 s Solution 1 : Objective Value = 43230.0 Time = 12.5088962 s Solution 2 : Objective Value = 43215.0 Time = 12.8341145 s Solution 3 : Objective Value = 43205.0 Time = 13.5884324 s Solution 4 : Objective Value = 43090.0 Time = 13.644678500000001 s Solution 5 : Objective Value = 43080.0 Time = 14.400471600000001 s Solution 6 : Objective Value = 42035.0 Time = 14.4432746 s Solution 7 : Objective Value = 41905.0 Time = 15.2392365 s Solution 8 : Objective Value = 41725.0 Time = 15.876437800000001 s Solution 9 : Objective Value = 41715.0 Time = 15.930290800000002 s Solution 10 : Objective Value = 40845.0 Time = 16.4014445 s Solution 11 : Objective Value = 40720.0 Time = 16.8116881 s Solution 12 : Objective Value = 40710.0 Time = 17.272804 s Solution 13 : Objective Value = 40605.0 Time = 17.5621018 s Solution 14 : Objective Value = 40235.0 Time = 17.6107754 s Solution 15 : Objective Value = 40225.0 Time = 17.9155029 s Solution 16 : Objective Value = 40120.0 Time = 18.4559667 s Solution 17 : Objective Value = 39985.0 Time = 18.5305047 s Solution 18 : Objective Value = 39975.0 Time = 18.741297 s Solution 19 : Objective Value = 39835.0 Time = 19.0611232 s Solution 20 : Objective Value = 39825.0 Time = 19.456051300000002 s Solution 21 : Objective Value = 39810.0 Time = 19.7567169 s Solution 22 : Objective Value = 39795.0 Time = 19.9060329 s Solution 23 : Objective Value = 39775.0 Time = 20.1844861 s Solution 24 : Objective Value = 39770.0 Time = 20.5866741 s Solution 25 : Objective Value = 39750.0 Time = 20.83156 s Solution 26 : Objective Value = 39690.0 Time = 21.088503900000003 s Solution 27 : Objective Value = 39645.0 Time = 21.5616215 s Solution 28 : Objective Value = 38550.0 Time = 21.8284179 s Solution 29 : Objective Value = 38265.0 Time = 23.0057404 s Solution 30 : Objective Value = 38130.0 Time = 23.170430900000003 s Solution 31 : Objective Value = 36890.0 Time = 23.7701314 s Solution 32 : Objective Value = 36820.0 Time = 24.6299686 s Solution 33 : Objective Value = 36805.0 Time = 25.9303971 s Solution 34 : Objective Value = 36745.0 Time = 25.973803800000002 s Solution 35 : Objective Value = 36730.0 Time = 26.1270634 s Solution 36 : Objective Value = 36715.0 Time = 26.1842645 s Solution 37 : Objective Value = 36705.0 Time = 26.796547500000003 s Solution 38 : Objective Value = 36690.0 Time = 26.9445301 s Solution 39 : Objective Value = 36650.0 Time = 27.511156500000002 s Solution 40 : Objective Value = 36640.0 Time = 27.8817683 s Solution 41 : Objective Value = 36605.0 Time = 28.0686314 s Solution 42 : Objective Value = 34815.0 Time = 28.436296400000003 s Solution 43 : Objective Value = 34785.0 Time = 29.559608500000003 s Solution 44 : Objective Value = 33905.0 Time = 29.625215100000002 s Solution 45 : Objective Value = 33850.0 Time = 30.393147300000003 s Solution 46 : Objective Value = 33795.0 Time = 30.4985739 s Solution 47 : Objective Value = 33760.0 Time = 31.1791328 s Solution 48 : Objective Value = 33690.0 Time = 31.7087073 s Solution 49 : Objective Value = 33570.0 Time = 32.408804 s Solution 50 : Objective Value = 33340.0 Time = 33.160873200000005 s Solution 51 : Objective Value = 33250.0 Time = 34.362544400000004 s Solution 52 : Objective Value = 33120.0 Time = 35.3299857 s Solution 53 : Objective Value = 33100.0 Time = 36.1085514 s Solution 54 : Objective Value = 33085.0 Time = 36.8508301 s Solution 55 : Objective Value = 32745.0 Time = 37.3974312 s Solution 56 : Objective Value = 32725.0 Time = 37.819274300000004 s Solution 57 : Objective Value = 32680.0 Time = 38.7144806 s Solution 58 : Objective Value = 32450.0 Time = 38.7613198 s Solution 59 : Objective Value = 32345.0 Time = 39.556668200000004 s Solution 60 : Objective Value = 31430.0 Time = 40.522091 s Solution 61 : Objective Value = 31405.0 Time = 41.293227300000005 s Solution 62 : Objective Value = 31350.0 Time = 42.0510479 s Solution 63 : Objective Value = 31075.0 Time = 42.4240173 s Solution 64 : Objective Value = 31060.0 Time = 43.2031311 s Solution 65 : Objective Value = 31045.0 Time = 43.4931111 s Solution 66 : Objective Value = 30715.0 Time = 44.3648437 s Solution 67 : Objective Value = 30700.0 Time = 45.7018817 s Solution 68 : Objective Value = 30595.0 Time = 47.293911300000005 s Solution 69 : Objective Value = 30590.0 Time = 47.8724684 s Solution 70 : Objective Value = 30565.0 Time = 48.4729791 s Solution 71 : Objective Value = 30380.0 Time = 48.685947600000006 s Solution 72 : Objective Value = 30330.0 Time = 49.5712831 s Solution 73 : Objective Value = 30320.0 Time = 50.474759500000005 s Solution 74 : Objective Value = 30305.0 Time = 50.712679800000004 s Solution 75 : Objective Value = 30280.0 Time = 51.5694619 s Solution 76 : Objective Value = 30245.0 Time = 51.8197393 s Solution 77 : Objective Value = 30235.0 Time = 51.85376290000001 s Solution 78 : Objective Value = 30200.0 Time = 52.6684308 s Solution 79 : Objective Value = 29870.0 Time = 53.478479500000006 s Solution 80 : Objective Value = 29845.0 Time = 54.458032200000005 s Solution 81 : Objective Value = 29830.0 Time = 54.599983900000005 s Solution 82 : Objective Value = 29805.0 Time = 55.5559449 s Solution 83 : Objective Value = 29700.0 Time = 55.841832000000004 s Solution 84 : Objective Value = 29695.0 Time = 56.660539400000005 s Solution 85 : Objective Value = 28595.0 Time = 57.2847268 s Solution 86 : Objective Value = 28455.0 Time = 58.66789180000001 s Solution 87 : Objective Value = 28435.0 Time = 59.4957088 s Solution 88 : Objective Value = 28430.0 Time = 60.0715043 s Solution 89 : Objective Value = 27365.0 Time = 60.8221817 s Solution 90 : Objective Value = 27355.0 Time = 61.468439000000004 s Solution 91 : Objective Value = 27290.0 Time = 62.0337906 s Solution 92 : Objective Value = 27270.0 Time = 62.788823 s Solution 93 : Objective Value = 27260.0 Time = 63.657580200000005 s Solution 94 : Objective Value = 27245.0 Time = 64.2416518 s Solution 95 : Objective Value = 27240.0 Time = 64.33816850000001 s Solution 96 : Objective Value = 27220.0 Time = 64.9124118 s Solution 97 : Objective Value = 27210.0 Time = 65.73147110000001 s Solution 98 : Objective Value = 27185.0 Time = 66.8888893 s Solution 99 : Objective Value = 27170.0 Time = 67.0634881 s Solution 100 : Objective Value = 27155.0 Time = 67.6958062 s Solution 101 : Objective Value = 27135.0 Time = 68.5466967 s Solution 102 : Objective Value = 27085.0 Time = 69.95090470000001 s Solution 103 : Objective Value = 27070.0 Time = 70.3711129 s Solution 104 : Objective Value = 27025.0 Time = 71.2447416 s Solution 105 : Objective Value = 27010.0 Time = 71.998571 s Solution 106 : Objective Value = 26995.0 Time = 72.9960918 s Solution 107 : Objective Value = 26990.0 Time = 74.2706524 s Solution 108 : Objective Value = 26980.0 Time = 74.4881927 s Solution 109 : Objective Value = 26855.0 Time = 75.82119 s Solution 110 : Objective Value = 26845.0 Time = 76.0170038 s Solution 111 : Objective Value = 26820.0 Time = 76.57962690000001 s Solution 112 : Objective Value = 26800.0 Time = 77.3523821 s Solution 113 : Objective Value = 26695.0 Time = 78.55117460000001 s Solution 114 : Objective Value = 26685.0 Time = 80.33650390000001 s Solution 115 : Objective Value = 26675.0 Time = 81.47919040000001 s Solution 116 : Objective Value = 26560.0 Time = 82.43304040000001 s Solution 117 : Objective Value = 26450.0 Time = 83.5241962 s Solution 118 : Objective Value = 26415.0 Time = 86.80081050000001 s Solution 119 : Objective Value = 26390.0 Time = 88.10185560000001 s Solution 120 : Objective Value = 26280.0 Time = 88.7571613 s Solution 121 : Objective Value = 26245.0 Time = 89.9340578 s Solution 122 : Objective Value = 26235.0 Time = 92.4972635 s Solution 123 : Objective Value = 26205.0 Time = 96.2000378 s Solution 124 : Objective Value = 26140.0 Time = 96.3235851 s Solution 125 : Objective Value = 26130.0 Time = 100.19327820000001 s Solution 126 : Objective Value = 26120.0 Time = 101.6609124 s Solution 127 : Objective Value = 26105.0 Time = 104.19408030000001 s Solution 128 : Objective Value = 26085.0 Time = 105.18848600000001 s Solution 129 : Objective Value = 26075.0 Time = 107.92553430000001 s Solution 130 : Objective Value = 26070.0 Time = 109.13310270000001 s Solution 131 : Objective Value = 26010.0 Time = 110.32515360000001 s Solution 132 : Objective Value = 26005.0 Time = 113.25241650000001 s Solution 133 : Objective Value = 25995.0 Time = 116.71639370000001 s Solution 134 : Objective Value = 25890.0 Time = 117.44775030000001 s Solution 135 : Objective Value = 25875.0 Time = 121.14740490000001 s Solution 136 : Objective Value = 25785.0 Time = 121.62004030000001 s Solution 137 : Objective Value = 25765.0 Time = 125.7971665 s Solution 138 : Objective Value = 25755.0 Time = 131.4600349 s Solution 139 : Objective Value = 25740.0 Time = 132.7700782 s Solution 140 : Objective Value = 25730.0 Time = 134.34565750000002 s Solution 141 : Objective Value = 25720.0 Time = 135.6275291 s Solution 142 : Objective Value = 25710.0 Time = 137.0183522 s Solution 143 : Objective Value = 25700.0 Time = 141.3760226 s Solution 144 : Objective Value = 25695.0 Time = 143.00884720000002 s Solution 145 : Objective Value = 25685.0 Time = 147.1757365 s Solution 146 : Objective Value = 25675.0 Time = 148.69833780000002 s Solution 147 : Objective Value = 25655.0 Time = 150.1113429 s Solution 148 : Objective Value = 25560.0 Time = 151.5189762 s Solution 149 : Objective Value = 25550.0 Time = 152.3568971 s Solution 150 : Objective Value = 25545.0 Time = 153.996483 s Solution 151 : Objective Value = 25535.0 Time = 157.0594096 s Solution 152 : Objective Value = 25510.0 Time = 165.4955971 s Solution 153 : Objective Value = 25490.0 Time = 167.4100893 s Solution 154 : Objective Value = 25480.0 Time = 168.7994796 s Solution 155 : Objective Value = 25475.0 Time = 173.0331228 s Solution 156 : Objective Value = 25470.0 Time = 174.3354184 s Solution 157 : Objective Value = 25465.0 Time = 175.295464 s Solution 158 : Objective Value = 25455.0 Time = 179.7208947 s Solution 159 : Objective Value = 25350.0 Time = 181.9291411 s Solution 160 : Objective Value = 25345.0 Time = 183.45486640000001 s Solution 161 : Objective Value = 25335.0 Time = 186.0674691 s Solution 162 : Objective Value = 25330.0 Time = 187.13813370000003 s Solution 163 : Objective Value = 24650.0 Time = 192.64123130000002 s Solution 164 : Objective Value = 24645.0 Time = 196.44730080000002 s Solution 165 : Objective Value = 24635.0 Time = 197.6413277 s Solution 166 : Objective Value = 24630.0 Time = 206.1572831 s Solution 167 : Objective Value = 24625.0 Time = 210.8393528 s Solution 168 : Objective Value = 24615.0 Time = 215.0766805 s Solution 169 : Objective Value = 24610.0 Time = 216.9417693 s Solution 170 : Objective Value = 24600.0 Time = 218.07130450000002 s Solution 171 : Objective Value = 24595.0 Time = 221.2565409 s Solution 172 : Objective Value = 24515.0 Time = 232.4581373 s Solution 173 : Objective Value = 24510.0 Time = 248.037283 s Solution 174 : Objective Value = 24505.0 Time = 271.50884390000004 s Solution 175 : Objective Value = 24495.0 Time = 310.30175710000003 s Solution 176 : Objective Value = 24490.0 Time = 311.9746045 s Solution 177 : Objective Value = 24480.0 Time = 341.1917821 s Solution 178 : Objective Value = 24475.0 Time = 343.5733343 s Solution 179 : Objective Value = 24370.0 Time = 356.3554465 s Solution 180 : Objective Value = 24360.0 Time = 363.22030290000004 s Solution 181 : Objective Value = 24355.0 Time = 391.8866509 s Solution 182 : Objective Value = 24350.0 Time = 395.75241270000004 s Solution 183 : Objective Value = 24345.0 Time = 412.25727880000005 s Solution 184 : Objective Value = 24335.0 Time = 475.95491430000004 s Solution 185 : Objective Value = 24315.0 Time = 495.8155269 s Solution 186 : Objective Value = 24250.0 Time = 500.4818136 s Solution 187 : Objective Value = 24240.0 Time = 501.51144860000005 s Solution 188 : Objective Value = 24230.0 Time = 505.2651784 s Solution 189 : Objective Value = 24215.0 Time = 509.87142050000006 s Solution 190 : Objective Value = 24130.0 Time = 511.0115541 s Solution 191 : Objective Value = 24105.0 Time = 511.9637288 s Solution 192 : Objective Value = 24100.0 Time = 516.8905831000001 s Solution 193 : Objective Value = 24095.0 Time = 596.0800211000001 s
In [49]:
if status == cp_model.OPTIMAL:
print("方案 OPTIMAL")
elif status == cp_model.FEASIBLE:
print("方案 FEASIBLE")
elif status == cp_model.INFEASIBLE:
print("INFASIBLE")
elif status == cp_model.MODEL_INVALID:
print("MODEL_INVALID")
elif status == cp_model.UNKNOWN:
print("UNKNOWN")
方案 FEASIBLE
In [50]:
# 保存结果
save_course_var = {}
if status in [cp_model.OPTIMAL,cp_model.FEASIBLE]:
for the_key in course_vars.keys():
str_key = str(the_key)
save_course_var[str_key] = solver.Value(course_vars[the_key])
# 将临时解写入文件
with open(f'course_save_var_{int(solver.ObjectiveValue())}.json', 'w') as f:
json.dump(save_course_var, f)
In [51]:
# teacher_time_vars[the_teacher, the_day, the_index]
6.2 抽查解信息¶
In [52]:
print(solver.Value(teacher_time_vars[("teacher_24", 1, 6)]))
print(solver.Value(course_vars[(2, 1, 7, "英语")]))
print(map_class_subject_to_teacher[2, "英语"])
# print(model.any_by_class_day_section_subject[1, 2, "morning", "数学"].value)
1 0 teacher_24
In [55]:
# 班级信息x
the_class = 2
for the_day in all_days_indexes:
for the_index in all_course_indexes:
for the_subject in all_subjects:
if solver.Value(course_vars[(the_class, the_day, the_index, the_subject)]) == 1:
print(
f"the_class {the_class} the_day {the_day} the_index {the_index} the_subject {the_subject}"
)
the_class 2 the_day 1 the_index 0 the_subject 语文 the_class 2 the_day 1 the_index 1 the_subject 语文 the_class 2 the_day 1 the_index 2 the_subject 英语 the_class 2 the_day 1 the_index 3 the_subject 英语 the_class 2 the_day 1 the_index 4 the_subject 化学 the_class 2 the_day 1 the_index 5 the_subject 物理 the_class 2 the_day 1 the_index 6 the_subject 数学 the_class 2 the_day 1 the_index 7 the_subject 数学 the_class 2 the_day 1 the_index 8 the_subject 生物 the_class 2 the_day 1 the_index 9 the_subject 劳动 the_class 2 the_day 1 the_index 10 the_subject 生物 the_class 2 the_day 1 the_index 11 the_subject 生物 the_class 2 the_day 1 the_index 12 the_subject 数学 the_class 2 the_day 1 the_index 13 the_subject 数学 the_class 2 the_day 2 the_index 0 the_subject 语文 the_class 2 the_day 2 the_index 1 the_subject 体育 the_class 2 the_day 2 the_index 2 the_subject 数学 the_class 2 the_day 2 the_index 3 the_subject 物理 the_class 2 the_day 2 the_index 4 the_subject 政治 the_class 2 the_day 2 the_index 5 the_subject 语文 the_class 2 the_day 2 the_index 6 the_subject 音乐 the_class 2 the_day 2 the_index 7 the_subject 化学 the_class 2 the_day 2 the_index 8 the_subject 历史 the_class 2 the_day 2 the_index 9 the_subject 英语 the_class 2 the_day 2 the_index 10 the_subject 英语 the_class 2 the_day 2 the_index 11 the_subject 英语 the_class 2 the_day 2 the_index 12 the_subject 物理 the_class 2 the_day 2 the_index 13 the_subject 历史 the_class 2 the_day 3 the_index 0 the_subject 英语 the_class 2 the_day 3 the_index 1 the_subject 地理 the_class 2 the_day 3 the_index 2 the_subject 英语 the_class 2 the_day 3 the_index 3 the_subject 英语 the_class 2 the_day 3 the_index 4 the_subject 体育 the_class 2 the_day 3 the_index 5 the_subject 化学 the_class 2 the_day 3 the_index 6 the_subject 语文 the_class 2 the_day 3 the_index 7 the_subject 数学 the_class 2 the_day 3 the_index 8 the_subject 物理 the_class 2 the_day 3 the_index 9 the_subject 政治 the_class 2 the_day 3 the_index 10 the_subject 政治 the_class 2 the_day 3 the_index 11 the_subject 物理 the_class 2 the_day 3 the_index 12 the_subject 语文 the_class 2 the_day 3 the_index 13 the_subject 语文 the_class 2 the_day 4 the_index 0 the_subject 英语 the_class 2 the_day 4 the_index 1 the_subject 语文 the_class 2 the_day 4 the_index 2 the_subject 英语 the_class 2 the_day 4 the_index 3 the_subject 地理 the_class 2 the_day 4 the_index 4 the_subject 美术 the_class 2 the_day 4 the_index 5 the_subject 物理 the_class 2 the_day 4 the_index 6 the_subject 生物 the_class 2 the_day 4 the_index 7 the_subject 数学 the_class 2 the_day 4 the_index 8 the_subject 数学 the_class 2 the_day 4 the_index 9 the_subject 历史 the_class 2 the_day 4 the_index 10 the_subject 数学 the_class 2 the_day 4 the_index 11 the_subject 数学 the_class 2 the_day 4 the_index 12 the_subject 生物 the_class 2 the_day 4 the_index 13 the_subject 化学 the_class 2 the_day 5 the_index 0 the_subject 英语 the_class 2 the_day 5 the_index 1 the_subject 数学 the_class 2 the_day 5 the_index 2 the_subject 生物 the_class 2 the_day 5 the_index 3 the_subject 英语 the_class 2 the_day 5 the_index 4 the_subject 英语 the_class 2 the_day 5 the_index 5 the_subject 心理 the_class 2 the_day 5 the_index 6 the_subject 化学 the_class 2 the_day 5 the_index 7 the_subject 语文 the_class 2 the_day 5 the_index 8 the_subject 语文 the_class 2 the_day 5 the_index 9 the_subject 物理 the_class 2 the_day 5 the_index 10 the_subject 物理 the_class 2 the_day 5 the_index 11 the_subject 化学 the_class 2 the_day 5 the_index 12 the_subject 化学 the_class 2 the_day 5 the_index 13 the_subject 英语 the_class 2 the_day 6 the_index 0 the_subject 语文 the_class 2 the_day 6 the_index 1 the_subject the_class 2 the_day 6 the_index 2 the_subject the_class 2 the_day 6 the_index 3 the_subject the_class 2 the_day 6 the_index 4 the_subject the_class 2 the_day 6 the_index 5 the_subject the_class 2 the_day 6 the_index 6 the_subject the_class 2 the_day 6 the_index 7 the_subject the_class 2 the_day 6 the_index 8 the_subject the_class 2 the_day 6 the_index 9 the_subject the_class 2 the_day 6 the_index 10 the_subject the_class 2 the_day 6 the_index 11 the_subject the_class 2 the_day 6 the_index 12 the_subject the_class 2 the_day 6 the_index 13 the_subject the_class 2 the_day 7 the_index 0 the_subject the_class 2 the_day 7 the_index 1 the_subject the_class 2 the_day 7 the_index 2 the_subject the_class 2 the_day 7 the_index 3 the_subject the_class 2 the_day 7 the_index 4 the_subject the_class 2 the_day 7 the_index 5 the_subject the_class 2 the_day 7 the_index 6 the_subject the_class 2 the_day 7 the_index 7 the_subject the_class 2 the_day 7 the_index 8 the_subject the_class 2 the_day 7 the_index 9 the_subject the_class 2 the_day 7 the_index 10 the_subject 班会 the_class 2 the_day 7 the_index 11 the_subject 语文 the_class 2 the_day 7 the_index 12 the_subject 物理 the_class 2 the_day 7 the_index 13 the_subject 地理
7. 输出到 xlsx¶
7.1 基本设置¶
In [56]:
# 输出到 xlsx
from copy import copy
import numpy as np
import pandas as pd
from openpyxl import load_workbook
In [57]:
def copy_sheet(source_sheet, target_sheet):
# 复制单元格内容和格式
for row in source_sheet.iter_rows():
for cell in row:
target_cell = target_sheet[cell.coordinate]
target_cell.value = cell.value
if cell.has_style:
target_cell._style = copy(cell._style)
if cell.hyperlink:
target_cell.hyperlink = copy(cell.hyperlink)
if cell.comment:
target_cell.comment = copy(cell.comment)
# 复制行高
for row, dimension in source_sheet.row_dimensions.items():
target_sheet.row_dimensions[row].height = dimension.height
# 复制列宽
for col, dimension in source_sheet.column_dimensions.items():
target_sheet.column_dimensions[col].width = dimension.width
# 指定所有列的宽度
fixed_width = 20 # 设置的宽度值
# 获取工作表的最大列数
max_column = target_sheet.max_column
# 遍历所有列并设置宽度
for col in range(1, max_column + 1):
col_letter = target_sheet.cell(row=1, column=col).column_letter # 获取列字母
target_sheet.column_dimensions[col_letter].width = fixed_width
# 复制合并单元格
if source_sheet.merged_cells:
target_sheet.merged_cells = source_sheet.merged_cells
7.2 输出班级课表¶
In [58]:
# 输出班级表
workbook_class = load_workbook("sample_class.xlsx")
map_from_index_to_row = [3, 5, 7, 8, 10, 11, 15, 16, 17, 18, 21, 22, 23, 24]
map_from_day_to_col = [1, 2, 3, 4, 5, 6, 7, 8]
working_teachers = []
sample_sheet = workbook_class["排版"]
for the_class in all_class_indexes:
the_sheet = workbook_class.create_sheet(title=f"高2024级{the_class}班")
copy_sheet(sample_sheet, the_sheet)
the_sheet.cell(row=1, column=1).value = f"高2024级{the_class}班 课表"
for the_day in all_days_indexes:
for the_index in all_course_indexes:
for the_subject in all_subjects:
has_course = solver.Value(course_vars[
(the_class, the_day, the_index, the_subject)
])
if has_course:
is_spoken = solver.Value(is_spoken_course[
(the_class, the_day, the_index)
])
if is_spoken == 1:
content = "口语(单周)\n英语(双周)"
else:
content = the_subject
teacher = map_class_subject_to_teacher[(the_class, the_subject)]
# print(f'row {row_index} col {col_index} content {content}')
# print(f'row {the_index}')
the_sheet.cell(
row=map_from_index_to_row[the_index],
column=map_from_day_to_col[the_day],
).value = f"{content}\n{teacher}"
if teacher not in working_teachers:
working_teachers.append(teacher)
workbook_class.remove(sample_sheet)
workbook_class.save(f"result_class_{int(solver.ObjectiveValue())}.xlsx")
7.3 输出老师课表¶
In [59]:
# 输出老师表
workbook_teacher = load_workbook("sample_class.xlsx")
map_from_index_to_row = [3, 5, 7, 8, 10, 11, 15, 16, 17, 18, 21, 22, 23, 24]
map_from_day_to_col = [1, 2, 3, 4, 5, 6, 7, 8]
sample_sheet = workbook_teacher["排版"]
for the_teacher in working_teachers:
if the_teacher != "":
# print(the_teacher)
the_sheet = workbook_teacher.create_sheet(title=f"{the_teacher}")
copy_sheet(sample_sheet, the_sheet)
the_sheet.cell(row=1, column=1).value = f"{the_teacher} 课表"
for the_day in all_days_indexes:
for the_index in all_course_indexes:
# 教研
for the_subject, the_times in teachers_duties[the_teacher].items():
the_jiaoyan_day_section = jiaoyan_day_section.get(the_subject, None)
if (
the_jiaoyan_day_section != None
and the_day == the_jiaoyan_day_section[0]
and the_index in indexes_by_section[the_jiaoyan_day_section[1]]
):
the_sheet.cell(
row=map_from_index_to_row[the_index],
column=map_from_day_to_col[the_day],
).value = f"{the_subject}教研\n{the_teacher}"
# 其他课
for the_class in all_class_indexes:
for the_subject in all_subjects:
has_course = solver.Value(course_vars[
(the_class, the_day, the_index, the_subject)
])
if (
has_course == 1
and map_class_subject_to_teacher[(the_class, the_subject)]
== the_teacher
):
is_spoken = solver.Value(is_spoken_course[
(the_class, the_day, the_index)
])
if is_spoken == 1:
content = "口语(单周)\n英语(双周)"
else:
content = the_subject
the_sheet.cell(
row=map_from_index_to_row[the_index],
column=map_from_day_to_col[the_day],
).value = f"{content}\n{the_class}班\n{the_teacher}"
# 单独输出口语sheet
the_sheet = workbook_teacher.create_sheet(title="口语")
copy_sheet(sample_sheet, the_sheet)
for the_day in all_days_indexes:
for the_index in all_course_indexes:
for the_class in all_class_indexes:
is_spoken = solver.Value(is_spoken_course[(the_class, the_day, the_index)])
if is_spoken == 1:
content = "口语(单周)"
the_sheet.cell(
row=map_from_index_to_row[the_index],
column=map_from_day_to_col[the_day],
).value = f"{content}\n{the_class}班"
workbook_teacher.remove(sample_sheet)
workbook_teacher.save(f"result_teacher_{int(solver.ObjectiveValue())}.xlsx")
In [ ]:
# jiaoyan_day_section = {
# "语文": (4, "afternoon"),
# "数学": (3, "morning"),
# "英语": (1, "afternoon"),
# "物理": (4, "afternoon"),
# "化学": (2, "morning"),
# "生物": (2, "morning"),
# "政治": (5, "morning"),
# "历史": (5, "morning"),
# "地理": (4, "afternoon"),
# "体育": (1, "morning"),
# "音乐": (1, "morning"),
# "美术": (1, "morning"),
# "心理": (1, "morning"),
# }