Skip to content

Instantly share code, notes, and snippets.

@htlin222

htlin222/排班小精靈.py

Created March 9, 2025 11:03
Show Gist options
  • Save htlin222/1752307939a71c88d55dfe64668b3449 to your computer and use it in GitHub Desktop.
Save htlin222/1752307939a71c88d55dfe64668b3449 to your computer and use it in GitHub Desktop.
Download ZIP
排班小精靈 (Scheduling Wizard) - Python Version
Raw
排班小精靈.py
import sys
"""
排班小精靈 (Scheduling Wizard) - Python Version
输入格式 (Input Format):
---------------------
1. 第一行: 日数,起始星期,参与排班人数
First line: number_of_days,starting_weekday,number_of_staff
2. 第二行: 国定假日1,国定假日2,...
Second line: national_holiday1,national_holiday2,...
3. 后续每行: 员工工作日排班数,员工假日排班数,员工固定不排班日期1,员工固定不排班日期2,...
Following lines: workday_shifts,holiday_shifts,fixed_day_off1,fixed_day_off2,...
示例 (Example):
--------------
31,1,3
14,21
20,4,5,12,19,26
20,4,6,13,20,27
20,4,7,14,21,28
这表示这个月有31天，从星期一(1)开始，有3个人参与排班。
14号和21号是国定假日。
第一个员工排20个工作日，4个假日，固定不排班日期是5,12,19,26。
以此类推。
"""
# 初始化全局变量
i, k, t, day, start, mem, max_score, score, today, check = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
balance = [0] * 10
w = [0] * 10
h = [0] * 10
b = [0] * 10
lim = [0] * 10
shift = [0] * 32
holi = [0] * 36
best = [0] * 32
order = [0] * 32
no = [[0 for _ in range(36)] for _ in range(10)]
want = [[0 for _ in range(32)] for _ in range(10)]
sum_val = [[0 for _ in range(32)] for _ in range(10)] # 计算从1开始
count = [[0 for _ in range(10)] for _ in range(10)] # 1-7为星期，8为工作日，9为假日
penalty = [0, 2, 2, 2, 32, 64, 128, 128] # 惩罚值按照工作天
def maxof(x, y):
return x if x > y else y
def print_result(r): # 打印排班
print("")
for k in range(1, start):
print(" ", end="")
for k in range(1, day + 1):
print(f"{r[k]:2d} ", end="")
if (k + start - 1) % 7 == 0 and k < day:
print("")
print(f" \nScore={max_score}")
def main():
global i, k, t, day, start, mem, max_score, score, today, check
global balance, w, h, b, lim, shift, holi, best, order, no, want, sum_val, count
try:
with open("input.txt", "r") as file:
# 输入：月份天数、起始星期、参与排班人数
line = file.readline().strip().split(',')
day, start, mem = int(line[0]), int(line[1]), int(line[2])
# 输入：国定假日
line = file.readline().strip().split(',')
for item in line:
if item:
holi[int(item)] = 1
# 输入：工作日排班天数、假日排班天数、固定不排班日期
for i in range(1, mem + 1):
line = file.readline().strip().split(',')
w[i], h[i] = int(line[0]), int(line[1])
for j in range(2, len(line)):
if line[j]:
no[i][int(line[j])] = 1
except FileNotFoundError:
print("\n请有 input.txt，请见 README.txt")
input("输入任意字结束：")
return 0
# 定义前置排班
for i in range(1, mem + 1):
for k in range(3, day + 1):
if no[i][k] == 1 and (start + k - 2) % 7 > 4:
want[i][k - (start + k - 2) % 7 + 3] = 1 # 假日固定不排班
if no[i][k] == 1 and holi[k] == 1:
want[i][k - 2] = 1 # 国定假日固定不排班
if no[i][k] == 1 and no[i][k + 1] == 1:
want[i][k - 2] = 1 # 连续固定不排班
for k in range(2, day + 1):
if (start + k - 2) % 7 > 4 or holi[i] == 1 or no[i][k] == 1:
want[i][k - 1] = 0 # 没有人会想在假前一天排班
for k in range(1, day + 1):
if no[i][k] == 1:
want[i][k] = 0 # 没办法排班就不会想排班
# 计算各日期好坏
value = [[0 for _ in range(32)] for _ in range(10)]
for i in range(1, day + 1):
if holi[34] > 0 and holi[i] > 0:
value[0][i] += holi[34] # 有连假才好
elif holi[i + 1] > 0:
value[0][i] -= 1 # 前一天排班差
elif (start + i - 1) % 7 == 0:
value[0][i] += 1 # 排星期日有 day off
elif (start + i - 1) % 7 == 4:
value[0][i] += 1 # 排星期四有 day off
elif (start + i - 1) % 7 > 4:
value[0][i] -= 1 # 排五六没有 day off
value[0][0] += value[0][i] # 好坏总和
for i in range(1, mem + 1):
value[0][0] -= no[i][33] + no[i][34] + no[i][35] - 1 # 确认好坏平衡
for i in range(1, mem + 1):
if no[i][33] == 0 and holi[33] == 0:
value[0][0] += 16384
if value[0][0] < 0:
print("好坏平衡绝对无法完成！")
input("输入任意字结束：")
return 0
# 计算工作日排班数量
t = 0
for i in range(1, day + 1):
if (start + i - 2) % 7 < 5 and holi[i] == 0:
t += 1
for i in range(1, mem + 1):
t -= w[i]
# 计算假日排班数量
k = 0
for i in range(1, day + 1):
if (start + i - 2) % 7 > 4 or holi[i] == 1:
k += 1
for i in range(1, mem + 1):
k -= h[i]
# 检查排班数量是否合理
if t + k == 0 and t > 0:
print(f"假日排班数{t}天应改为工作日")
input("输入任意字结束：")
return 0
if t + k == 0 and t < 0:
print(f"工作日排班数{k}天应改为假日")
input("输入任意字结束：")
return 0
if t > 0:
print(f"\n工作日排班数少{t}天")
elif t < 0:
print(f"\n工作日排班数多{-t}天")
if k > 0:
print(f"\n假日排班数少{k}天")
elif k < 0:
print(f"\n假日排班数多{-k}天")
if t != 0 or k != 0:
input("输入任意字结束：")
return 0
# 优先排假日
t = 1
for i in range(1, day + 1):
if (start + i - 2) % 7 > 4 or holi[i] == 1:
order[t] = i
t += 1
check += 1
# 记录相关好坏的工作日
for i in range(1, day + 1):
if value[0][i] != 0 and (start + i - 2) % 7 < 5 and holi[i] == 0:
order[t] = i
t += 1
check += 1
# 不记录相关好坏的日期
for i in range(1, day + 1):
if value[0][i] == 0 and (start + i - 2) % 7 < 5 and holi[i] == 0:
order[t] = i
t += 1
# 重置计数
for i in range(mem + 1):
for k in range(10):
count[i][k] = 0
# 计算各人满分数理想下限，搜索法相同，递归法本身
for t in range(1, mem + 1):
for k in range(day + 1):
shift[k] = 42
sum_val[0][k] = 0
max_score = 16384
today = 1
while today > 0:
while today <= day and today > 0:
if shift[today] == 42:
shift[today] = 0
count[0][t] += 1
elif shift[today] == t:
if holi[today] == 1 and (start + today - 2) % 7 < 5:
count[t][9] -= 1
else:
count[t][((start + today - 2) % 7) // 5 + 8] -= 1
count[t][(start + today - 2) % 7 + 1] -= 1
balance[t] -= value[0][today]
shift[today] = 42
today -= 1
continue
else:
if holi[today] == 1 and (start + today - 2) % 7 < 5:
count[t][9] += 1
else:
count[t][((start + today - 2) % 7) // 5 + 8] += 1
count[0][t] -= 1
count[t][(start + today - 2) % 7 + 1] += 1
balance[t] += value[0][today]
shift[today] = t
if count[t][8] > w[t]:
continue
if count[t][9] > h[t]:
continue
if count[0][t] > day - w[t] - h[t]:
continue
if today == day:
if no[t][33] > 0 and balance[t] < no[t][33] + no[t][34] + no[t][35] - 1:
continue
elif holi[33] > 0 and balance[t] < -1:
continue
score = 0
if shift[today] == t:
if shift[today] == shift[today - 1] and today > 1:
continue
if no[t][today] == 1:
continue
if t == shift[today - 2] and today > 2:
score += 256
if t == shift[today - 3] and today > 3:
score += 1
if count[t][(start + today - 2) % 7 + 1] > 1:
score += penalty[(start + today - 2) % 7 + 1]
if no[t][today + 1] == 1:
score += 16
if max_score <= sum_val[0][today - 1] + score:
continue
sum_val[0][today] = sum_val[0][today - 1] + score
today += 1
if today > day:
max_score = sum_val[0][day]
today = day
lim[t] = max_score # 各人满分数理想下限
if lim[t] > 16383:
print(f"人员{t}排班绝对无法完成！")
input("输入任意字结束：")
return 0
# 初始化排班搜索
max_score = 16384
today = 1
# 排班预设
for k in range(day + 1):
shift[k] = 42
sum_val[0][k] = 0
# 星期别排班数预设
for i in range(mem + 1):
balance[i] = 0
for k in range(10):
count[i][k] = 0
# 搜索法本身
while today > 0:
# 选择：进位还是退回开头
while today <= day and today > 0:
if shift[order[today]] > 10:
# 选项一：前进位才排班的日期
shift[order[today]] = 1 # 分配从人员编号开始排这一天
# 计算国定假日
if holi[order[today]] == 1 and (start + order[today] - 2) % 7 < 5:
count[shift[order[today]]][9] += 1
else:
count[shift[order[today]]][((start + order[today] - 2) % 7) // 5 + 8] += 1
# 计算星期
count[shift[order[today]]][(start + order[today] - 2) % 7 + 1] += 1
# 计算好坏变动
balance[shift[order[today]]] += value[0][order[today]]
elif shift[order[today]] == mem:
# 选项二：所有人都已经排过
if holi[order[today]] == 1 and (start + order[today] - 2) % 7 < 5:
count[shift[order[today]]][9] -= 1
else:
count[shift[order[today]]][((start + order[today] - 2) % 7) // 5 + 8] -= 1
count[shift[order[today]]][(start + order[today] - 2) % 7 + 1] -= 1
balance[shift[order[today]]] -= value[0][order[today]]
shift[order[today]] = 42 # 当天排班预设
today -= 1 # 退一步改排班
continue
else:
# 选项三：还有人排班过
if holi[order[today]] == 1 and (start + order[today] - 2) % 7 < 5:
# 计算国定假日，一加一减
count[shift[order[today]]][9] -= 1
count[shift[order[today]] + 1][9] += 1
else:
# 计算非国定假日
count[shift[order[today]]][((start + order[today] - 2) % 7) // 5 + 8] -= 1
count[shift[order[today]] + 1][((start + order[today] - 2) % 7) // 5 + 8] += 1
# 计算星期
count[shift[order[today]]][(start + order[today] - 2) % 7 + 1] -= 1
count[shift[order[today]] + 1][(start + order[today] - 2) % 7 + 1] += 1
# 计算好坏变动
balance[shift[order[today]]] -= value[0][order[today]]
balance[shift[order[today]] + 1] += value[0][order[today]]
shift[order[today]] += 1 # 换下一人员排这一天
if today == 4:
print(f" {shift[order[1]]} {shift[order[2]]} {shift[order[3]]} {shift[order[4]]} ...")
# 排班检查
if shift[order[today]] == shift[order[today - 1]] and order[today] > 1:
continue # QD
if shift[order[today]] == shift[order[today] + 1] and order[today] <= day - 1:
continue # QD
if count[shift[order[today]]][8] > w[shift[order[today]]]:
continue # 工作日排班数
if count[shift[order[today]]][9] > h[shift[order[today]]]:
continue # 假日排班数
if no[shift[order[today]]][order[today]] == 1:
continue # 固定不排班
# 计分
score = 0
if shift[order[today]] == shift[order[today] - 2] and order[today] > 2:
score += 256 # QOD
if shift[order[today]] == shift[order[today] + 2] and order[today] <= day - 2:
score += 256 # QOD
if shift[order[today]] == shift[order[today] - 3] and order[today] > 3:
score += 1 # Q3D
if shift[order[today]] == shift[order[today] + 3] and order[today] <= day - 3:
score += 1 # Q3D
if count[shift[order[today]]][(start + order[today] - 2) % 7 + 1] > 1:
score += penalty[(start + order[today] - 2) % 7 + 1]
# 前置排班
for i in range(1, mem + 1):
if want[i][order[today]] > 0 and shift[order[today]] != i:
score += 8
# 固定不排班前一日
if no[shift[order[today]]][order[today] + 1] == 1:
score += 16
# 若惩罚已超上限，则不继续排
if max_score <= sum_val[0][today - 1] + score:
continue
# 计算今日排班人员导致之惩罚
t = sum_val[shift[order[today]]][today - 1] + score
# 加上非今日排班人员理想值
for i in range(1, mem + 1):
if i != shift[order[today]]:
t += maxof(sum_val[i][today - 1], lim[i])
# 检查好坏平衡
if today == check:
for i in range(1, mem + 1):
if no[i][33] > 0 and balance[i] < no[i][33] + no[i][34] + no[i][35] - 1:
t += 16384
elif holi[33] > 0 and balance[i] < -1:
t += 16384
# 将以上列入准量，若预期惩罚超出上限，则不继续排
if t >= max_score:
continue
# 复制各人员累积的惩罚
for k in range(mem + 1):
sum_val[k][today] = sum_val[k][today - 1]
# 更新今日的惩罚
sum_val[shift[order[today]]][today] += score
# 更新今日的惩罚总和
sum_val[0][today] += score
# 经过上述严选后，才继续排下一天
today += 1
if today > day:
for k in range(1, day + 1):
best[k] = shift[k] # 复制最佳排班
for k in range(1, 10):
b[k] = balance[k] # 复制最佳排班好坏
max_score = t # 复制最佳惩罚
print_result(shift)
today = day # 不惩罚已探索过的区域
# 输出最佳排班
print("\n-----------------------\n 一 二 三 四 五 六 日")
print_result(best)
# 计算星期别排班数
for i in range(1, day + 1):
count[best[i]][(start + i - 2) % 7 + 1] += 1
# 计算各种惩罚
for i in range(1, mem + 1):
print(f"\n人员{i} {w[i]}工{h[i]}假({b[i]:+d})：", end="")
# QOD 排班
t = 0
for k in range(1, day):
if best[k] == i and best[k + 2] == i and k + 2 <= day:
t += 1
if t > 0:
print(f"有{t}次QOD排班, ", end="")
t = 0
# Q3D 排班
for k in range(1, day):
if best[k] == i and best[k + 3] == i and k + 3 <= day:
t += 1
if t > 0:
print(f"有{t}次Q3D排班, ", end="")
# 前置排班
for k in range(1, day):
if best[k] == i and want[i][k] > 0:
print(f"前置排班({k}号), ", end="")
# 固定不排班前一天
for k in range(1, day):
if best[k] == i and no[i][k + 1] == 1:
print(f"固定不排班前一天({k}号)排班, ", end="")
# 惩罚排班
for k in range(1, 8):
if count[i][k] > 1:
print(f"W{k}惩罚排班, ", end="")
# 好坏作业(总结)
print("\n好坏讨论(总结)：", end="")
if holi[33] > 0:
print("改善(-1) ", end="")
for i in range(1, mem + 1):
if no[i][33] > 0:
print(f"人员{i}(+{no[i][33] + no[i][34] + no[i][35] - 1}) ", end="")
print("\n\n输入任意字结束：", end="")
input()
return 0
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment