这是我的问题表述的简化版本：
from ortools.sat.python import cp_model
def solve_shift_scheduling():
num_employees = 6
num_weeks = 4
shifts = ['.', 'M']
fixed_assignments = [
(0, 1, 0),
(0, 1, 2),
(0, 1, 5),
(1, 0, 0),
(1, 1, 1),
(1, 1, 6),
(2, 1, 0),
(2, 1, 2),
(2, 1, 5),
(2, 1, 6),
(5, 1, 1),
(5, 1, 5)]
requests = [
(3, 1, 3, -2),
(3, 1, 4, -2),
(4, 1, 2, -2),
(4, 1, 3, -2),
(4, 1, 4, -2)]
weekly_cover_demands = [
(4,), # Monday
(4,), # Tuesday
(4,), # Wednesday
(4,), # Thursday
(4,), # Friday
(4,), # Saturday
(4,), # Sunday
]
employee_max_shifts = [
(1,3), # employee 0
(1,3), # employee 1
(1,4), # employee 2
(1,2), # employee 3
(1,3), # employee 4
(1,2), # employee 5
]
num_days = num_weeks * 7
num_shifts = len(shifts)
model = cp_model.CpModel()
work = {}
for e in range(num_employees):
for s in range(num_shifts):
for d in range(num_days):
work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d))
# Linear terms of the objective in a minimization context.
obj_int_vars = []
obj_int_coeffs = []
obj_bool_vars = []
obj_bool_coeffs = []
# Exactly one shift per day.
for e in range(num_employees):
for d in range(num_days):
model.Add(sum(work[e, s, d] for s in range(num_shifts)) == 1)
# Fixed assignments.
for e, s, d in fixed_assignments:
model.Add(work[e, s, d] == 1)
# Employee requests
for e, s, d, w in requests:
obj_bool_vars.append(work[e, s, d])
obj_bool_coeffs.append(w)
# Employee shifts constraint
for e in range(num_employees):
for w in range(num_weeks):
s, max_shifts = employee_max_shifts[e]
works = [work[e, s, d + w * 7] for d in range(7)]
total_shifts = model.NewIntVar(0, max_shifts, '')
model.Add(total_shifts==sum(works))
# Cover constraints
for s in range(1, num_shifts):
for w in range(num_weeks):
for d in range(7):
works = [work[e, s, w * 7 + d] for e in range(num_employees)]
demand = weekly_cover_demands[d][s - 1]
worked = model.NewIntVar(0, demand, '')
model.Add(worked == sum(works))
name = 'under_demand: (shift={}, week={}, day={})'.format(s, w, d)
under = model.NewIntVar(0, demand, name)
model.Add(under == demand - worked)
obj_int_vars.append(under)
obj_int_coeffs.append(20)
# Objective
model.Minimize(
sum(obj_bool_vars[i] * obj_bool_coeffs[i]
for i in range(len(obj_bool_vars))) +
sum(obj_int_vars[i] * obj_int_coeffs[i]
for i in range(len(obj_int_vars))))
# Solve the model.
solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 8
solver.parameters.max_time_in_seconds = 600
solution_printer = cp_model.ObjectiveSolutionPrinter()
status = solver.SolveWithSolutionCallback(model, solution_printer)
# Print solution.
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print()
header = ' '
for w in range(num_weeks):
header += 'M T W T F S S '
print(header)
for e in range(num_employees):
schedule = ''
for d in range(num_days):
for s in range(num_shifts):
if solver.BooleanValue(work[e, s, d]):
schedule += shifts[s] + ' '
print('worker %i: %s' % (e, schedule))
此外，我还想添加一个尝试平衡每日覆盖范围的条件：
# Balance Coverage
for s in range(1, num_shifts):
for w in range(num_weeks):
each_days_gap = []
daily_demands = []
for d in range(7):
demand = weekly_cover_demands[d][s - 1]
daily_demands.append(demand)
works = [work[e, s, w*7+d] for e in range(num_employees)]
demand_gap = model.NewIntVar(0, demand, '')
model.Add((demand - sum(works)) == demand_gap)
each_days_gap.append(demand_gap)
min_demand_gap = model.NewIntVar(0, max(daily_demands), '')
max_demand_gap = model.NewIntVar(0, max(daily_demands), '')
model.AddMinEquality(min_demand_gap, each_days_gap)
model.AddMaxEquality(max_demand_gap, each_days_gap)
name = 'target_gap: (shift={}, week={})'.format(s,w)
delta = model.NewIntVar(0, max(daily_demands), name)
model.Add(delta == max_demand_gap-min_demand_gap)
obj_int_vars.append(delta)
obj_int_coeffs.append(10)
通过添加此规则，它会导致运行时间增加 +20 倍，这意味着随着添加额外的约束，问题开始需要 10 多分钟才能解决。有没有更有效的方法来实施上述规则？