人員スケジューリング問題 PuLP

人員スケジューリング問題

人員スケジューリング最適化の例題として、従業員のシフトスケジュールを最適化する問題を考えてみましょう。

次のような条件を設定します。

🔹従業員は、1日あたり8時間を超えて働くことはできません。
🔹従業員が、1週間あたりに働くことができる最大時間数はあらかじめ決まっています。
🔹従業員は、週に1日は必ず休む必要があります。

解法・ソースコード

この問題をPuLPを使って解いていきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from pulp import *

# ①従業員のリスト
employees = ['Alice', 'Bob', 'Charlie', 'David', 'Tom', 'Nancy']

# ②日付のリスト
days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']

# ③必要な従業員数
shift_requirements = {
    'Monday': 2,
    'Tuesday': 2,
    'Wednesday': 3,
    'Thursday': 2,
    'Friday': 3,
    'Saturday': 3,
    'Sunday': 1
}

# ④各従業員が働く最大時間数
work_hours = {
    'Alice': 40,
    'Bob': 40,
    'Charlie': 40,
    'David': 40,
    'Tom': 40,
    'Nancy': 40
}

# ⑤問題を定義する
problem = LpProblem('Shift_Scheduling', LpMinimize)

# ⑥変数を定義する
shifts = LpVariable.dicts('shifts', (employees, days), 0, 1, LpInteger)

# ⑦目的関数を定義する
problem += lpSum([shifts[e][d] for e in employees for d in days])

# ⑧制約条件を追加する
# 各従業員は週に1日は必ず休む
for e in employees:
    problem += lpSum([shifts[e][d] for d in days]) >= 1

# 各日のシフトには、必要な人数が割り当てられる必要がある
for d in days:
    problem += lpSum([shifts[e][d] for e in employees]) == shift_requirements[d]

# 各従業員は1日に8時間までしか勤務できない
for e in employees:
    problem += lpSum([shifts[e][d] for d in days]) <= 8

# 各従業員が1週間に働くことができる時間数
for e in employees:
    problem += lpSum([shifts[e][d] for d in days]) * 8 <= work_hours[e]

# ⑨問題を解く
status = problem.solve()

# ⑩解を表示する
print(f'Solution status: {LpStatus[status]}')

for d in days:
    print(f'\n{d}')
    for e in employees:
        if value(shifts[e][d]) == 1:
            print(f'  {e} is working.')
        else:
            print(f'  {e} is off.')

①従業員のリストを作成しています。

②日付のリストを作成しています。

③各日に必要な従業員数を格納する辞書を作成しています。

④各従業員が働くことができる最大時間数を格納する辞書を作成しています。

⑤問題を定義するために、PuLPでLpProblemオブジェクトを作成しています。
　第一引数には問題の名前を指定し、第二引数には最小化するのか、最大化するのかを指定します。

⑥変数を定義しています。
　shiftsという名前のLpVariableオブジェクトを作成します。
　このオブジェクトはemployeesとdaysの2つのインデックスを持ちます。
　変数は、0から1の整数値を取ります。

⑦目的関数を定義しています。
　目的関数は、すべての従業員と日に対して、その従業員がその日に働く場合に1、そうでない場合に0を取るshifts変数の総和です。
　この目的関数は、スケジュールの総コストを最小限に抑えるように最適化されます。

⑧制約条件を追加しています。
　まず、各従業員が週に1日は必ず休むようにします。
　次に、各日のシフトには、必要な人数が割り当てられる必要があるようにします。
　各従業員は1日に8時間までしか勤務できないようにし、各従業員が1週間に働くことができる時間数を制限します。

⑨問題を解くために、PuLPのsolveメソッドを呼び出します。
　解決策が見つかった場合は、status変数にSolvedという文字列が格納されます。
　見つからなかった場合は、Infeasibleという文字列が格納されます。

⑩解を表示するために、各日について、各従業員が働いているかどうかを示す出力を行っています。
　これは、shifts変数の値が1の場合にその従業員が働いていることを示します。
　それ以外の場合は、その従業員が休みであることを示します。

実行結果は以下のようになります。

[実行結果]
Solution status: Optimal

Monday
  Alice is working.
  Bob is off.
  Charlie is off.
  David is off.
  Tom is working.
  Nancy is off.

Tuesday
  Alice is off.
  Bob is working.
  Charlie is off.
  David is off.
  Tom is off.
  Nancy is working.

Wednesday
  Alice is working.
  Bob is working.
  Charlie is working.
  David is off.
  Tom is off.
  Nancy is off.

Thursday
  Alice is off.
  Bob is off.
  Charlie is off.
  David is working.
  Tom is working.
  Nancy is off.

Friday
  Alice is off.
  Bob is working.
  Charlie is working.
  David is working.
  Tom is off.
  Nancy is off.

Saturday
  Alice is off.
  Bob is off.
  Charlie is working.
  David is working.
  Tom is off.
  Nancy is working.

Sunday
  Alice is off.
  Bob is off.
  Charlie is off.
  David is off.
  Tom is working.
  Nancy is off.

各曜日に誰が働けばよいのかシフトスケジュールを組むことができました。