Я провел последний месяц, создавая эту модель на основе исследований, которые можно найти здесь . Целью модели является минимизация общей численности персонала с учетом ограничений. Я попробовал два изменения количества сотрудников (переменные nF и nP для сотрудников, работающих на полную и частичную занятость соответственно), поскольку, возможно, численность персонала слишком мала, но я все еще получаю заменимый статус модели.
Я также не совсем понимаю, как правильно создать переменную, в которой "Full [k] = 1, если рабочий k назначен любой смене в любой день". Я чувствую, что это может быть источником моей проблемы.
Я использую Google Ortools Sat cp_model Solver
Вот мой код:
from __future__ import print_function
from ortools.sat.python import cp_model
def main():
"""" Solves the shift scheduling problem"""""
# create the model
model = cp_model.CpModel()
"""Hardcode of parameters"""
nSL = 3
nDS = 9
nF = 3
nP = 5
pfrate = 0.5
FG = 40
FD = 5
PG = 20
PD = 5
costf = 560
costp = 240
dursh = {}
hreq = {}
worksh = {}
shiftint = {}
"""Indices"""
days_of_week = range(7)
shift_length = range(nSL)
detailed_shifts = range(nDS)
hours = range(7)
ft_employees = range(nF)
pt_employees = range(nP)
# Loops to initialize list type parameters
for i in days_of_week:
for h in hours:
if i == 0 and h in range(3):
hreq[(i, h)] = 2
elif i == 1 and (h == 0 or h in range(2, 5)):
hreq[(i, h)] = 2
elif i == 2 and h == 0:
hreq[(i, h)] = 2
elif i == 3 and h in range(3):
hreq[(i, h)] = 2
elif i == 4 and h in range(6):
hreq[(i, h)] = 3
elif i == 5 and (h == 0 or h == 3):
hreq[(i, h)] = 4
elif i == 5 and (h in range(1, 3) or h in range(4, 6)):
hreq[(i, h)] = 3
elif i == 6 and h in range(5):
hreq[(i, h)] = 3
elif i == 6 and h == 5:
hreq[(i, h)] = 2
else:
hreq[(i, h)] = 1
"""Pure integer decision variables"""
full = {}
part = {}
assign_full = {}
assign_part = {}
staff_assigned = {}
# ft employee k, working shift of length j, on day i
for k in ft_employees:
for j in shift_length:
for i in days_of_week:
assign_full[(i, j, k)] = model.NewBoolVar('assign_full%i_%i_%i' % (i, j, k))
for k in ft_employees:
if any(assign_full[i, j, k] for j in shift_length for i in days_of_week):
full[k] = model.NewBoolVar('Full')
# pt employee l, working shift of length j, on day i
for l in pt_employees:
for j in shift_length:
for i in days_of_week:
assign_part[(i, j, l)] = model.NewBoolVar('assign_part%i_%i_%i' % (i, j, l))
for l in pt_employees:
if any(assign_part[(i, j, l)] for j in shift_length for i in days_of_week):
part[l] = model.NewBoolVar('Part')
# the number of staff assigned to detailed shift s on day i
for s in detailed_shifts:
for i in days_of_week:
staff_assigned[(s, i)] = model.NewIntVar(0, 4, 'staff_assigned%i_%s' % (s, i))
"""Apply model constraints"""
# limit on the amount of part time staff that can be used [constraint 10]
ratio = (1 - pfrate) * 10
ratio2 = pfrate * 10
model.Add(sum(part[l] for l in pt_employees) * int(ratio) <=
sum(full[k] for k in ft_employees) * int(ratio2))
# limit on full time staff's working days [constraint 11]
for k in ft_staff:
model.Add(FD >= sum(assign_full[(i, j, k)] for i in days_of_week for j in shift_length))
# limit on part time staff working days [constraint 12]
for l in pt_employees:
model.Add(PD >= sum(assign_part[(i, j, l)] for i in days_of_week for j in shift_length))
# limit of the number of hours worked per week
for j in shift_length:
if j == 0:
dursh[j] = 4
elif j == 1:
dursh[j] = 6
elif j == 2:
dursh[j] = 8
for k in ft_employees: # Limit on number of hours worked per week for ft staff [constraint 13]
model.Add(sum(dursh[j] * assign_full[(i, j, k)] for j in shift_length for i in
days_of_week) <= FG)
for l in pt_employees: # Limit on number of hours worked per week for pt staff [constraint 14]
model.Add(sum(dursh[j] * assign_part[(i, j, l)] for j in shift_length for i in
days_of_week) <= PG)
# limits the max number of shifts per day to 1
for k in ft_employees: # [constraint 15]
for i in days_of_week:
model.Add(sum(assign_full[(i, j, k)] for j in shift_length) <= 1)
for l in pt_employees: # [constraint 16]
for i in days_of_week:
model.Add(sum(assign_part[(i, j, l)] for j in shift_length) <= 1)
# [Constraint 17]
# Guarantees that the model's requirements are met
for h in hours:
for s in detailed_shifts:
if (h == 0 and s == 0) or (h == 0 and s in range(3, 5)) or (h == 0 and s == 8):
worksh[(s, h)] = 1
elif h == 1 and (s == 0 or s in range(3, 6) or s == 8):
worksh[(s, h)] = 1
elif h == 2 and (s in range(4, 9)):
worksh[(s, h)] = 1
elif h == 3 and (s == 2 or s in range(5, 9)):
worksh[(s, h)] = 1
elif h == 4 and (s in range(1, 3) or s in range(5, 9)):
worksh[(s, h)] = 1
elif h == 5 and (s in range(1, 3) or s in range(6, 8)):
worksh[(s, h)] = 1
elif h == 6 and (s == 2 or s == 7):
worksh[(s, h)] = 1
else:
worksh[(s, h)] = 0
for i in days_of_week:
for h in hours:
model.Add(sum(staff_assigned[(s, i)] * worksh[(s, h)] for s in detailed_shifts) >= hreq[
(i, h)])
# [Constraint 18]
# converts the detailed shifts into hourly shifts per day and staff will be assigned to those shifts
for j in shift_length:
for s in detailed_shifts:
if j == 0 and (s == 0 or s == 1):
shiftint[(s, j)] = 1
elif j == 1 and (s == 2 or s == 3):
shiftint[(s, j)] = 1
elif j == 2 and s in range(4, 9):
shiftint[(s, j)] = 1
else:
shiftint[(s, j)] = 0
for i in days_of_week:
for j in shift_length:
model.Add(
sum(assign_full[(i, j, k)] for k in ft_employees) + sum(assign_part[(i, j, l)]
for l in pt_employees) >=
sum(staff_assigned[(s, i)] * shiftint[(s, j)] for s in detailed_shifts))
"""Solve the model"""
# Define objective
model.Minimize(sum(full[k] * costf for k in ft_employees) + sum(part[l] * costp for l in pt_employees))
solver = cp_model.CpSolver()
status = solver.Solve(model)
for i in days_of_week:
print('Day', i)
for k in ft_employees:
for j in shift_length:
if solver.Value(assign_full[(i, j, k)]) == 1:
print('Nurse', k, 'works shift of length', j, '(requested)')
else:
print('Nurse', k, 'works shift of length', j, '(not requested).')
print()
for i in days_of_week:
for s in detailed_shifts:
print(' ' , solver.Value(staff_assigned[(s, i)]))
print()
# output the solution
print('Solve status: %s' % solver.StatusName(status))
print('Optimal objective value: %i' % solver.ObjectiveValue())
print('Statistics')
print(' - conflicts : %i' % solver.NumConflicts())
print(' - branches : %i' % solver.NumBranches())
print(' - wall time : %f s' % solver.WallTime())
print('Number of Boolean Variables: %i' % solver.NumBooleans())
print(' Model Stats ' + model.ModelStats())
if __name__ == '__main__':
main()
Возможно, что Модель действительно неосуществима, но я хотел бы убедиться, прежде чем двигаться дальше. Я ценю любой совет:)