Employee scheduling problem - CP SAT
246 views
Skip to first unread message
Rodrick HOU
May 29, 2023, 3:04:33 AM5/29/23
to or-tools-discuss
I face some questions when I use OR-TOOLS CP-SAT. I guaranteed there have solutions, but or-tools didn't give me infeasible solution. My conditons are as follows:
1. There have only one kind of shift, each employee can only work or rest every day.
2. I have 17 employees, 8 of them should work 22 days in June, 9 of them should work 21 days in June.
3. Two days off every week except holidays, example: in 22 June is dragon boat festival in China, so except for overtime staff, other employees should rest 3 days in that week contains 22 June.
4. [13, 15] of employees work in weekdays, [8, 10] employees work in weekends.
5. The first four days and 22, 23, 24 days are preset.
6. Maximum of 7 days of work followed by rest.
My codes are:
# 17 employees
num_of_staff = 17
# contains off-shift
num_shifts = 2
# o-off, w-work
shifts = ['O', 'W']
# June has 30 days
june_days = 30
# except first four days, June has four weeks
num_of_weeks = 4
# Because the last five days of June and the first two days of July form a week
# so the total days is 32
days = 32
# weekend in these days, days begin with 0 index
weekends = [
2, 3, 9, 10, 16, 17, 22, 23, 30, 31
]
# Fixed assignment: (employee, shift, day), preset value
fixed_assignments = [
(0, 1, 0),
(0, 1, 1),
(0, 0, 2),
(0, 1, 3),
(1, 1, 0),
(1, 1, 1),
(1, 0, 2),
(1, 1, 3),
(2, 1, 0),
(2, 1, 1),
(2, 1, 2),
(2, 0, 3),
(3, 1, 0),
(3, 1, 1),
(3, 1, 2),
(3, 0, 3),
(4, 1, 0),
(4, 1, 1),
(4, 1, 2),
(4, 0, 3),
(5, 1, 0),
(5, 1, 1),
(5, 0, 2),
(5, 1, 3),
(6, 1, 0),
(6, 0, 1),
(6, 1, 2),
(6, 1, 3),
(7, 1, 0),
(7, 1, 1),
(7, 1, 2),
(7, 0, 3),
(8, 0, 0),
(8, 0, 1),
(8, 1, 2),
(8, 1, 3),
(9, 1, 0),
(9, 0, 1),
(9, 0, 2),
(9, 1, 3),
(10, 1, 0),
(10, 1, 1),
(10, 0, 2),
(10, 1, 3),
(11, 1, 0),
(11, 1, 1),
(11, 1, 2),
(11, 0, 3),
(12, 0, 0),
(12, 1, 1),
(12, 1, 2),
(12, 1, 3),
(13, 1, 0),
(13, 1, 1),
(13, 0, 2),
(13, 1, 3),
(14, 1, 0),
(14, 1, 1),
(14, 0, 2),
(14, 0, 3),
(15, 1, 0),
(15, 1, 1),
(15, 1, 2),
(15, 0, 3),
(16, 0, 0),
(16, 0, 1),
(16, 1, 2),
(16, 1, 3),
(0, 0, 21),
(1, 0, 21),
(2, 0, 21),
(3, 0, 21),
(4, 1, 21),
(5, 1, 21),
(6, 0, 21),
(7, 1, 21),
(8, 0, 21),
(9, 1, 21),
(10, 1, 21),
(11, 0, 21),
(12, 0, 21),
(13, 1, 21),
(14, 1, 21),
(15, 1, 21),
(16, 0, 21),
(0, 0, 22),
(1, 0, 22),
(2, 0, 22),
(3, 0, 22),
(4, 1, 22),
(5, 1, 22),
(6, 0, 22),
(7, 1, 22),
(8, 0, 22),
(9, 1, 22),
(10, 1, 22),
(11, 0, 22),
(12, 0, 22),
(13, 1, 22),
(14, 1, 22),
(15, 1, 22),
(16, 0, 22),
(0, 0, 23),
(1, 0, 23),
(2, 0, 23),
(3, 0, 23),
(4, 1, 23),
(5, 1, 23),
(6, 0, 23),
(7, 1, 23),
(8, 0, 23),
(9, 1, 23),
(10, 1, 23),
(11, 0, 23),
(12, 0, 23),
(13, 1, 23),
(14, 1, 23),
(15, 1, 23),
(16, 0, 23),
]
shift_constrains = [
# rest continuous two days is preferred
(0, 1, 2, 5, 2, 3, 10),
]
model = cp_model.CpModel()
work = {}
# init work
for e in range(num_of_staff):
for s in range(num_shifts):
for d in range(days):
work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d))
# each staff has one shift each day
for e in range(num_of_staff):
for d in range(days):
model.Add(sum(work[e, s, d] for s in range(num_shifts)) == 1)
# init preset
for e, s, d in fixed_assignments:
model.Add(work[e, s, d] == 1)
# each employee works maximum of 7 days followed by rest
max_seq_length = 7
for e in range(num_of_staff):
works = [work[e, 0, d] for d in range(days)]
for start in range(len(works) - max_seq_length):
model.AddBoolOr([works[i] for i in range(start, start + max_seq_length + 1)])
# except 22 June, each employee work 21 days in June
for e in range(num_of_staff):
sum_of_shifts_worked = [work[(e, 0, d)] for d in range(june_days) if d != 21]
model.Add(sum(sum_of_shifts_worked) == 8)
# Linear terms of the objective in a minimization context.
obj_int_vars = []
obj_int_coeffs = []
obj_bool_vars = []
obj_bool_coeffs = []
for e in range(num_of_staff):
for w in range(num_of_weeks):
# Special handling due to holidays during the week, except w = 2, d = 3, each employee rest two days
if w == 2:
# plus 4 is because of first four days didn't consider into this condition
works = [work[e, 0, d + w * 7 + 4] for d in range(7) if d != 3]
model.Add(sum(works) == 2)
else:
# plus 4 is because of first four days didn't consider into this condition
works = [work[e, 0, d + w * 7 + 4] for d in range(7)]
model.Add(sum(works) == 2)
# shift constrains
for ct in shift_constrains:
shift, hard_min, soft_min, min_cost, soft_max, hard_max, max_cost = ct
for e in range(num_of_staff):
works = [work[e, shift, d] for d in range(days)]
variables, coeffs = add_soft_sequence_constraint(
model, works, hard_min, soft_min, min_cost, soft_max, hard_max,
max_cost,
'shift_constraint(employee %i, shift %i)' % (e, shift))
obj_bool_vars.extend(variables)
obj_bool_coeffs.extend(coeffs)
# number of employees worked
for d in range(days):
# work[e, 1, d] represent employee worked in day d
works = [work[e, 1, d] for e in range(num_of_staff)]
# 周末特殊限制
if d in weekends:
model.Add(sum(works) == model.NewIntVar(8, 10, ''))
# 正常工作日限制, 冗余人力全都分配到正常班
else:
model.Add(sum(works) == model.NewIntVar(13, 15, ''))
# find best solution
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))))
solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 16
solution_printer = cp_model.ObjectiveSolutionPrinter()
status = solver.Solve(model, solution_printer)
num_of_staff = 17
# contains off-shift
num_shifts = 2
# o-off, w-work
shifts = ['O', 'W']
# June has 30 days
june_days = 30
# except first four days, June has four weeks
num_of_weeks = 4
# Because the last five days of June and the first two days of July form a week
# so the total days is 32
days = 32
# weekend in these days, days begin with 0 index
weekends = [
2, 3, 9, 10, 16, 17, 22, 23, 30, 31
]
# Fixed assignment: (employee, shift, day), preset value
fixed_assignments = [
(0, 1, 0),
(0, 1, 1),
(0, 0, 2),
(0, 1, 3),
(1, 1, 0),
(1, 1, 1),
(1, 0, 2),
(1, 1, 3),
(2, 1, 0),
(2, 1, 1),
(2, 1, 2),
(2, 0, 3),
(3, 1, 0),
(3, 1, 1),
(3, 1, 2),
(3, 0, 3),
(4, 1, 0),
(4, 1, 1),
(4, 1, 2),
(4, 0, 3),
(5, 1, 0),
(5, 1, 1),
(5, 0, 2),
(5, 1, 3),
(6, 1, 0),
(6, 0, 1),
(6, 1, 2),
(6, 1, 3),
(7, 1, 0),
(7, 1, 1),
(7, 1, 2),
(7, 0, 3),
(8, 0, 0),
(8, 0, 1),
(8, 1, 2),
(8, 1, 3),
(9, 1, 0),
(9, 0, 1),
(9, 0, 2),
(9, 1, 3),
(10, 1, 0),
(10, 1, 1),
(10, 0, 2),
(10, 1, 3),
(11, 1, 0),
(11, 1, 1),
(11, 1, 2),
(11, 0, 3),
(12, 0, 0),
(12, 1, 1),
(12, 1, 2),
(12, 1, 3),
(13, 1, 0),
(13, 1, 1),
(13, 0, 2),
(13, 1, 3),
(14, 1, 0),
(14, 1, 1),
(14, 0, 2),
(14, 0, 3),
(15, 1, 0),
(15, 1, 1),
(15, 1, 2),
(15, 0, 3),
(16, 0, 0),
(16, 0, 1),
(16, 1, 2),
(16, 1, 3),
(0, 0, 21),
(1, 0, 21),
(2, 0, 21),
(3, 0, 21),
(4, 1, 21),
(5, 1, 21),
(6, 0, 21),
(7, 1, 21),
(8, 0, 21),
(9, 1, 21),
(10, 1, 21),
(11, 0, 21),
(12, 0, 21),
(13, 1, 21),
(14, 1, 21),
(15, 1, 21),
(16, 0, 21),
(0, 0, 22),
(1, 0, 22),
(2, 0, 22),
(3, 0, 22),
(4, 1, 22),
(5, 1, 22),
(6, 0, 22),
(7, 1, 22),
(8, 0, 22),
(9, 1, 22),
(10, 1, 22),
(11, 0, 22),
(12, 0, 22),
(13, 1, 22),
(14, 1, 22),
(15, 1, 22),
(16, 0, 22),
(0, 0, 23),
(1, 0, 23),
(2, 0, 23),
(3, 0, 23),
(4, 1, 23),
(5, 1, 23),
(6, 0, 23),
(7, 1, 23),
(8, 0, 23),
(9, 1, 23),
(10, 1, 23),
(11, 0, 23),
(12, 0, 23),
(13, 1, 23),
(14, 1, 23),
(15, 1, 23),
(16, 0, 23),
]
shift_constrains = [
# rest continuous two days is preferred
(0, 1, 2, 5, 2, 3, 10),
]
model = cp_model.CpModel()
work = {}
# init work
for e in range(num_of_staff):
for s in range(num_shifts):
for d in range(days):
work[e, s, d] = model.NewBoolVar('work%i_%i_%i' % (e, s, d))
# each staff has one shift each day
for e in range(num_of_staff):
for d in range(days):
model.Add(sum(work[e, s, d] for s in range(num_shifts)) == 1)
# init preset
for e, s, d in fixed_assignments:
model.Add(work[e, s, d] == 1)
# each employee works maximum of 7 days followed by rest
max_seq_length = 7
for e in range(num_of_staff):
works = [work[e, 0, d] for d in range(days)]
for start in range(len(works) - max_seq_length):
model.AddBoolOr([works[i] for i in range(start, start + max_seq_length + 1)])
# except 22 June, each employee work 21 days in June
for e in range(num_of_staff):
sum_of_shifts_worked = [work[(e, 0, d)] for d in range(june_days) if d != 21]
model.Add(sum(sum_of_shifts_worked) == 8)
# Linear terms of the objective in a minimization context.
obj_int_vars = []
obj_int_coeffs = []
obj_bool_vars = []
obj_bool_coeffs = []
for e in range(num_of_staff):
for w in range(num_of_weeks):
# Special handling due to holidays during the week, except w = 2, d = 3, each employee rest two days
if w == 2:
# plus 4 is because of first four days didn't consider into this condition
works = [work[e, 0, d + w * 7 + 4] for d in range(7) if d != 3]
model.Add(sum(works) == 2)
else:
# plus 4 is because of first four days didn't consider into this condition
works = [work[e, 0, d + w * 7 + 4] for d in range(7)]
model.Add(sum(works) == 2)
# shift constrains
for ct in shift_constrains:
shift, hard_min, soft_min, min_cost, soft_max, hard_max, max_cost = ct
for e in range(num_of_staff):
works = [work[e, shift, d] for d in range(days)]
variables, coeffs = add_soft_sequence_constraint(
model, works, hard_min, soft_min, min_cost, soft_max, hard_max,
max_cost,
'shift_constraint(employee %i, shift %i)' % (e, shift))
obj_bool_vars.extend(variables)
obj_bool_coeffs.extend(coeffs)
# number of employees worked
for d in range(days):
# work[e, 1, d] represent employee worked in day d
works = [work[e, 1, d] for e in range(num_of_staff)]
# 周末特殊限制
if d in weekends:
model.Add(sum(works) == model.NewIntVar(8, 10, ''))
# 正常工作日限制, 冗余人力全都分配到正常班
else:
model.Add(sum(works) == model.NewIntVar(13, 15, ''))
# find best solution
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))))
solver = cp_model.CpSolver()
solver.parameters.num_search_workers = 16
solution_printer = cp_model.ObjectiveSolutionPrinter()
status = solver.Solve(model, solution_printer)
Thanks
Laurent Perron
May 29, 2023, 6:06:12 AM5/29/23
to or-tools...@googlegroups.com
you should set up the log
solver.parameters.log_search_progress = True
--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/cfff6f6d-45f4-44bc-b243-2903bfa69891n%40googlegroups.com.
Rodrick HOU
May 29, 2023, 7:32:55 AM5/29/23
to or-tools-discuss
The log info are as follows, I do not understand it, Thank you so much if you can do me a favor:
Starting CP-SAT solver v9.6.2534
Parameters: log_search_progress: true num_search_workers: 16
Initial optimization model '': (model_fingerprint: 0xd434adfefcdb89b6)
#Variables: 2174 (#bools:1054 in objective)
- 2142 Booleans in [0,1]
- 10 in [8,14]
- 22 in [10,17]
#kBoolOr: 1972 (#literals: 10540)
#kLinear1: 119
#kLinear2: 544
#kLinearN: 117 (#terms: 1528)
Starting presolve at 0.00s
INFEASIBLE: ''
Unsat after presolving constraint #2741 (warning, dump might be inconsistent): linear { vars: 2163 coeffs: 1 domain: 8 domain: 8 }
Presolve summary:
- 425 affine relations were detected.
- rule 'affine: new relation' was applied 425 times.
- rule 'bool_or: always true' was applied 589 times.
- rule 'bool_or: fixed literals' was applied 224 times.
- rule 'bool_or: implications' was applied 16 times.
- rule 'bool_or: only one literal' was applied 34 times.
- rule 'linear: empty' was applied 251 times.
- rule 'linear: fixed or dup variables' was applied 395 times.
- rule 'linear: infeasible' was applied 1 time.
- rule 'linear: negative clause' was applied 3 times.
- rule 'linear: reduced variable domains' was applied 251 times.
- rule 'linear: remapped using affine relations' was applied 17 times.
- rule 'linear: singleton column' was applied 17 times.
- rule 'presolve: iteration' was applied 1 time.
Problem closed by presolve.
CpSolverResponse summary:
status: INFEASIBLE
objective: NA
best_bound: NA
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 0.006645
usertime: 0.006645
deterministic_time: 0
gap_integral: 0
Statistics
- status : INFEASIBLE
- conflicts : 0
- branches : 0
- wall time : 0.006645 s
Starting CP-SAT solver v9.6.2534
Parameters: log_search_progress: true num_search_workers: 16
Initial optimization model '': (model_fingerprint: 0xd434adfefcdb89b6)
#Variables: 2174 (#bools:1054 in objective)
- 2142 Booleans in [0,1]
- 10 in [8,14]
- 22 in [10,17]
#kBoolOr: 1972 (#literals: 10540)
#kLinear1: 119
#kLinear2: 544
#kLinearN: 117 (#terms: 1528)
Starting presolve at 0.00s
INFEASIBLE: ''
Unsat after presolving constraint #2741 (warning, dump might be inconsistent): linear { vars: 2163 coeffs: 1 domain: 8 domain: 8 }
Presolve summary:
- 425 affine relations were detected.
- rule 'affine: new relation' was applied 425 times.
- rule 'bool_or: always true' was applied 589 times.
- rule 'bool_or: fixed literals' was applied 224 times.
- rule 'bool_or: implications' was applied 16 times.
- rule 'bool_or: only one literal' was applied 34 times.
- rule 'linear: empty' was applied 251 times.
- rule 'linear: fixed or dup variables' was applied 395 times.
- rule 'linear: infeasible' was applied 1 time.
- rule 'linear: negative clause' was applied 3 times.
- rule 'linear: reduced variable domains' was applied 251 times.
- rule 'linear: remapped using affine relations' was applied 17 times.
- rule 'linear: singleton column' was applied 17 times.
- rule 'presolve: iteration' was applied 1 time.
Problem closed by presolve.
CpSolverResponse summary:
status: INFEASIBLE
objective: NA
best_bound: NA
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 0.006645
usertime: 0.006645
deterministic_time: 0
gap_integral: 0
Statistics
- status : INFEASIBLE
- conflicts : 0
- branches : 0
- wall time : 0.006645 s
Laurent Perron
May 29, 2023, 7:34:52 AM5/29/23
to or-tools...@googlegroups.com
So your problem is infeasible. It is found by presolve.
Check your model and check your data.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e32595b4-5ee7-47ef-85bf-bad3e8796222n%40googlegroups.com.
Reply all
Reply to author
Forward
0 new messages