Employee Scheduling 문제는 회사나 조직에서 근무 시간의 로테이션을 효율적으로 관리하기 위해 사용하는 최적화 문제입니다.
이 문제는 각 직원(Employee)에게 제약 조건을 고려하면서도 최적의 업무가 할당되도록 하며,
직원 간의 근무 균형을 맞추는 것을 목적으로 합니다.
예를 들어, 병원에서 근무하는 간호사들의 경우, 매일 8시간씩 3교대로 업무가 배정됩니다.
이때, 매일 각 교대 근무조에 한 명의 간호사가 배정되며, 각 간호사는 2일 동안 최소 두 번 교대 근무를 해야 하는 제약이 있습니다.
이러한 제약 조건을 고려하여 모든 간호사에게 공정한 스케줄을 작성할 때 Employee Scheduling 문제를 적용할 수 있습니다.
Decision Variable
shifts = {}
for n in all_nurses:
for d in all_days:
for s in all_shifts:
shifts[(n, d, s)] = model.NewBoolVar('s_n%id%is%i' % (n, d, s))
Python
복사
의사 결정 변수를 정의하기 위해 간호사(nurse), 근무일(day), 근무조(shift)로 구성된 튜플(순서가 있는 집합)을 생성하여 리스트에 저장합니다.
True or False 형의 의사 결정 변수를 정의할 때는 model.NewBoolVar() 함수를 사용합니다.
(참고, MIP에서 정수형 의사 결정 변수를 정의할 때는 solver.IntVar() 함수 사용)
각 Shift에 반드시 1명의 nurse를 assign 하는 제약 생성하기
for d in all_days:
for s in all_shifts:
model.AddExactlyOne(shifts[(n, d, s)] for n in all_nurses)
Python
복사
모든 nurse는 하루에 1개 이하의 shift에만 assign 하는 제약 생성하기
for n in all_nurses:
for d in all_days:
model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts)
Python
복사
근무 가능한 nurse의 균등 배분을 위한 제약 생성하기
min_shifts_per_nurse = (num_shifts * num_days) // num_nurses
if num_shifts * num_days % num_nurses == 0:
max_shifts_per_nurse = min_shifts_per_nurse
else:
max_shifts_per_nurse = min_shifts_per_nurse + 1
for n in all_nurses:
shifts_worked = []
for d in all_days:
for s in all_shifts:
shifts_worked.append(shifts[(n, d, s)])
model.Add(min_shifts_per_nurse <= sum(shifts_worked))
model.Add(sum(shifts_worked) <= max_shifts_per_nurse)
Python
복사
모든 간호사(nurse)가 공평하게 근무를 할 수 있도록, 각 간호사가 근무할 수 있는 근무조(shift)의 최대 상한값을 설정할 필요가 있습니다.
이 최대 상한값을 max_shifts_per_nurse로 정의하고, 각 간호사에게 할당된 근무조의 수를 합산하면서,
이 합산값이 max_shifts_per_nurse를 넘지 않도록 제약을 추가합니다.
이를 통해 간호사별로 근무조가 균등하게 배분되도록 유도할 수 있습니다.
Solver 수행하기
solver = cp_model.CpSolver()
status = solver.Solve(model)
Python
복사
Constraint solver인 cp_model을 실행한 후, 결과 상태값을 status 변수에 저장할 수 있습니다.
status 변수가 True이면 해를 찾았다는 의미이고, True가 아니라면 주어진 제약 조건을 만족하는 해를 찾을 수 없음을 의미합니다.
전체 소스
from ortools.sat.python import cp_model
def main():
# Data.
num_nurses = 4
num_shifts = 3
num_days = 3
all_nurses = range(num_nurses)
all_shifts = range(num_shifts)
all_days = range(num_days)
# Creates the model.
model = cp_model.CpModel()
shifts = {}
for n in all_nurses:
for d in all_days:
for s in all_shifts:
shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))
# Each shift is assigned to exactly one nurse in the schedule period.
for d in all_days:
for s in all_shifts:
model.AddExactlyOne(shifts[(n, d, s)] for n in all_nurses)
# Each nurse works at most one shift per day.
for n in all_nurses:
for d in all_days:
model.AddAtMostOne(shifts[(n, d, s)] for s in all_shifts)
min_shifts_per_nurse = (num_shifts * num_days) // num_nurses
if num_shifts * num_days % num_nurses == 0:
max_shifts_per_nurse = min_shifts_per_nurse
else:
max_shifts_per_nurse = min_shifts_per_nurse + 1
for n in all_nurses:
shifts_worked = []
for d in all_days:
for s in all_shifts:
shifts_worked.append(shifts[(n, d, s)])
model.Add(min_shifts_per_nurse <= sum(shifts_worked))
model.Add(sum(shifts_worked) <= max_shifts_per_nurse)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
for d in all_days:
print('Day', d)
for n in all_nurses:
for s in all_shifts:
if solver.Value(shifts[(n, d, s)]) == 1:
print('Nurse', n, 'works shift', s)
print()
if __name__ == '__main__':
main()
Python
복사
결과는 아래와 같습니다.
Day 0
Nurse 1 works shift 2
Nurse 2 works shift 1
Nurse 3 works shift 0
Day 1
Nurse 0 works shift 0
Nurse 1 works shift 1
Nurse 3 works shift 2
Day 2
Nurse 0 works shift 0
Nurse 2 works shift 1
Nurse 3 works shift 2
Python
복사
Keyword: Logistics Optimization, 물류 최적화, Linear Programming, Mixed Integer Programming, Google OR Tools
Reference:
[1] Employee Scheduling by Google, https://developers.google.com/optimization/scheduling/employee_scheduling, Creative Commons Attribution 4.0 License
