Workforce Scheduling#
이강우 & 김정자. (2012). EXCEL 2010 경영과학. 한경사, 233.
K항공에서는 최근 여행객의 증가로 인천국제공항에 기항하거나 출항하는 비행기를 증편시키려고 하며 이에 따라서 추가로 서비스 직원을 고용하려고 한다. Table 1은 새로 증편된 운항계획에 따라서 각 교대조별 근무시간, 시간대별 필요한 직원의 소요인원 및 교대조별 1명당 1일 노무비용을 조사한 결과이다. 한편 K항공의 서비스 직원은 1일 8시간 단위로 근무하며 각 교대조의 근무시간은 다음과 같다.
Table 1 교대조별 근무시간대와 근무시간대별 소요인원
근무시간대 |
교대조1 |
교대조2 |
교대조3 |
교대조4 |
교대조5 |
소요인원(명) |
|---|---|---|---|---|---|---|
06:00 ~ 08:00 |
O |
48 |
||||
08:00 ~ 10:00 |
O |
O |
79 |
|||
10:00 ~ 12:00 |
O |
O |
65 |
|||
12:00 ~ 14:00 |
O |
O |
O |
87 |
||
14:00 ~ 16:00 |
O |
O |
64 |
|||
16:00 ~ 18:00 |
O |
O |
73 |
|||
18:00 ~ 20:00 |
O |
O |
82 |
|||
20:00 ~ 22:00 |
O |
43 |
||||
22:00 ~ 24:00 |
O |
O |
52 |
|||
24:00 ~ 06:00 |
O |
15 |
||||
1인당 임금(만원) |
7 |
6 |
7.5 |
8 |
9.5 |
import os
import sys
# Add the parent directory for importing custom library
sys.path.insert(0, os.path.abspath(os.path.join(os.getcwd(), os.pardir)))
Optimization with PuLP#
from pulp import *
from ortools.utils import output
# Define problem
prob = LpProblem(name='Workforce Scheduling', sense=LpMinimize)
# Create decision variables and non-negative constraint
x1 = LpVariable(name='X1', lowBound=0, cat='Continuous')
x2 = LpVariable(name='X2', lowBound=0, cat='Continuous')
x3 = LpVariable(name='X3', lowBound=0, cat='Continuous')
x4 = LpVariable(name='X4', lowBound=0, cat='Continuous')
x5 = LpVariable(name='X5', lowBound=0, cat='Continuous')
# Set objective function
prob += 7*x1 + 6*x2 + 7.5*x3 + 8*x4 + 9.5*x5
# Set constraints
prob += x1 >= 48
prob += x1 + x2 >= 79
prob += x1 + x2 >= 65
prob += x1 + x2 + x3 >= 87
prob += x2 + x3 >= 64
prob += x3 + x4 >= 73
prob += x3 + x4 >= 82
prob += x4 >= 43
prob += x4 + x5 >= 52
prob += x5 >= 15
# Solving problem
prob.solve()
output(prob, sensitivity=False)
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
Cell In[2], line 1
----> 1 from pulp import *
2 from ortools.utils import output
4 # Define problem
ModuleNotFoundError: No module named 'pulp'
from pulp import *
from ortools.utils import output
n_shifts = 5
costs = [7, 6, 7.5, 8, 9.5]
needs = [48, 79, 65, 87, 64, 73, 82, 43, 52, 15]
table = [
[1, 0, 0, 0, 0],
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[1, 1, 1, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 1]
]
# Define problem
prob = LpProblem(name='Workforce Scheduling', sense=LpMinimize)
# Create decision variables and non-negative constraint
x = [LpVariable('X{}'.format(i), lowBound=0) for i in range(n_shifts)]
# Set objective function
prob += lpSum([costs[i]*x[i] for i in range(n_shifts)])
for i in range(len(table)):
prob += lpSum([x[j] for j in range(n_shifts) if table[i][j] == 1]) >= needs[i]
# Solving problem
prob.solve()
output(prob, sensitivity=False)
Status: Optimal
Objective value: 1301.0
Variables Values
----------- --------
X0 48
X1 31
X2 39
X3 43
X4 15
Statistics:
- Number of variables: 5
- Number of constraints: 10
- Solve time: 0.017s
Optimization with GUROBI#
from gurobipy import *
from ortools.utils import set_gurobi, custom_callback, output
n_shifts = 5
costs = [7, 6, 7.5, 8, 9.5]
needs = [48, 79, 65, 87, 64, 73, 82, 43, 52, 15]
table = [
[1, 0, 0, 0, 0],
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[1, 1, 1, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 1]
]
m = Model('Workforce Scheduling')
x = [m.addVar(vtype=GRB.CONTINUOUS, name='X{}'.format(i)) for i in range(n_shifts)]
m.update()
m.setObjective(quicksum(costs[i]*x[i] for i in range(n_shifts)), GRB.MINIMIZE)
for i in range(len(table)):
m.addConstr(quicksum(x[j] for j in range(n_shifts) if table[i][j] == 1) >= needs[i])
set_gurobi(m, verbose=False)
# Optimize model
m.optimize(custom_callback)
output(m)
Status: Optimal
Objective value: 1301.0
Variables Values
----------- --------
X0 48
X1 31
X2 39
X3 43
X4 15
Statistics:
- Number of variables: 5
- Number of constraints: 10
- Solve time: 0.000s