일정 편성 문제 예시

Python으로 배우는 공급망 분석

Aaren Stubberfield

Supply Chain Analytics Mgr.

예상 수요

요일	필요 운전기사 수
0 = 월요일	11
1 = 화요일	14
2 = 수요일	23
3 = 목요일	21
4 = 금요일	20
5 = 토요일	15
6 = 일요일	8

질문:

총 몇 명의 운전기사를 채용해야 합니까?

제약:

각 기사는 연속 5일 근무 후 2일 휴무를 주 단위로 반복함

단계	정의
의사결정변수	X$_{\text{i}}$ = i일차에 근무하는 기사 수
목표	최소화 z = X$_{\text{0}}$ + X$_{\text{1}}$ + X$_{\text{2}}$ + X$_{\text{3}}$ + X$_{\text{4}}$ + X$_{\text{5}}$ + X$_{\text{6}}$
제약	X$_{\text{0}}$ ≥ 11
	X$_{\text{1}}$ ≥ 14
	X$_{\text{2}}$ ≥ 23
	X$_{\text{3}}$ ≥ 21
	X$_{\text{4}}$ ≥ 20
	X$_{\text{i}}$ ≥ 0 (i = 0, ..., 6)

단계	정의
의사결정변수	X$_{\text{i}}$ = i일차에 근무하는 기사 수
목표	최소화 z = X$_{\text{0}}$ + X$_{\text{1}}$ + X$_{\text{2}}$ + X$_{\text{3}}$ + X$_{\text{4}}$ + X$_{\text{5}}$ + X$_{\text{6}}$
제약	X$_{\text{0}}$ + X$_{\text{3}}$ + X$_{\text{4}}$ + X$_{\text{5}}$ + X$_{\text{6}}$ ≥ 11
	X$_{\text{0}}$ + X$_{\text{1}}$ + X$_{\text{4}}$ + X$_{\text{5}}$ + X$_{\text{6}}$ ≥ 14
	X$_{\text{0}}$ + X$_{\text{1}}$ + X$_{\text{2}}$ + X$_{\text{3}}$ + X$_{\text{6}}$ ≥ 23
	X$_{\text{0}}$ + X$_{\text{1}}$ + X$_{\text{2}}$ + X$_{\text{3}}$ + X$_{\text{4}}$ ≥ 21
	X$_{\text{1}}$ + X$_{\text{2}}$ + X$_{\text{3}}$ + X$_{\text{4}}$ + X$_{\text{5}}$ ≥ 15
	X$_{\text{i}}$ ≥ 0 (i = 0, ..., 6)

코딩 예제

# Initialize Class
model = LpProblem("Minimize Staffing", 
                   LpMinimize)
days = list(range(7))

# Define Decision Variables
x = LpVariable.dicts('staff_', days,
                      lowBound=0, cat='Integer')

# Define Objective
model += lpSum([x[i] for i in days])

# Define Constraints
model += x[0] + x[3] + x[4] + x[5] + x[6] >= 11
model += x[0] + x[1] + x[4] + x[5] + x[6] >= 14
model += x[0] + x[1] + x[2] + x[5] + x[6] >= 23
model += x[0] + x[1] + x[2] + x[3] + x[6] >= 21
model += x[0] + x[1] + x[2] + x[3] + x[4] >= 20
model += x[1] + x[2] + x[3] + x[4] + x[5] >= 15
model += x[2] + x[3] + x[4] + x[5] + x[6] >= 8

# Solve Model
model.solve()

요약

초기 변수는 효과가 없었음
일부 제약을 반영하는 의사결정변수

연습해 봅시다!

Python으로 배우는 공급망 분석