コールセンターにおけるシフトスケジューリングアプリケーション

コールセンターは，企業と顧客の接点として近年，増々重要となってきている．電話を受け ることを主とするインバウンドの業務形態において，サービスレベルを保ちつつ各時刻に配置 するオペレータの人数を決定するシフトスケジューリング問題がKoole–Sluis [41]で扱われ，

そこではマルチモジュラ性[3, 4, 27]が重要な役割を果たしている．このマルチモジュラ性は

（変数変換を通じて）離散凸解析におけるL^♮凸性と等価な概念である．

本論文では、コールセンターにおけるシフトスケジューリングのアプリケーションを開発 して，オンラインソルバとして公開した．最適化エンジンとして、離散凸関数最小化ソルバ

ODICONを組み込んだ。アプリケーションでは，各時間区間の客の到着率λi，オペレータの

サービス率µ，客を待たせる時間の限界の基準値c などのパラメータを対話的に入力し (図 5.4)，最適化を実行すると，各シフトに配置するオペレータの最適な人数と，その際のサービ スレベルが表示される(図5.5)．

ここで用いたモデル（Koole–Sluis [41]のモデル）の概要は以下の通りである．

• コ ー ル セ ン タ ー は ，I 個 の（ 連 続 す る ）時 間 区 間 に 渡 っ て 稼 働 す る ．時 間 区 間 を i= 1,2, . . . , Iで表す．

• 各オペレータは連続したM個の時間区間に勤務する．

• 勤務シフトはK種類あり，それぞれの開始時点（と終了時点）は予め指定されている．

シフトをk = 1,2, . . . , K で表し，第kシフトの開始時間区間をIk で表す．ただし，

1 ≤I1 < I2 <· · · < IK ≤ I−M + 1とする．図5.6にシフトの例を示す（I = 13, M = 5, K= 4, I1= 1,I2= 3, I3= 6,I4= 9）．

(途中省略)

図5.3.開発したオンラインソルバ(在庫管理問題の入力と出力)

(途中省略)

図5.4.開発したオンラインソルバ(シフトスケジューリング問題の入力)

• 各時間区間 i = 1,2, . . . , I に対して，その区間におけるサービスレベルを表す関数 gi(ni)が与えられている．ここで，niは時間区間i に勤務しているオペレータの人数 である．関数giは単調増加な凹関数とする．

• 全体のサービスレベルS はS=∑

1≤i≤Igi(ni)で与えられる．

第kシフトに配置するオペレータの人数をykとすると，時間区間iのオペレータの人数ni

は

hi(y) = ∑

k:i−M <Ik≤i

yk

に等しい．したがって，サービスレベルSはy= (y1, . . . , yK) の関数として S(y) = ∑

1≤i≤I

gi(hi(y)) (y∈Z^K) (5.4)

図5.5.開発したオンラインソルバ(シフトスケジューリング問題の出力)

1 2 3 4 5 6 7 8 9 10 11 12 13

I1

I2

I3

I4

図5.6.シフトの例

となる．文献[41]に従い，サービスレベルを一定の水準sに保ってオペレータの人数を最小 化する問題

Minimize ∑

k

yk s.t. S(y)≥s, y∈Z^K (5.5) を考える．このとき，Y をパラメータとする問題

Maximize S(y) s.t. ∑

k

yk =Y, y∈Z^K (5.6)

を繰り返し解いて，最適なY を二分探索で見出すことにより，問題(5.5)の最適解を求めるこ とができる．

サービスレベルS(y)の具体形は，待ち行列モデルM/M/nに基づいて，以下のように定め る．各時間区間の客の到着率をλi (i= 1,2, . . . , I),オペレータのサービス率をµとする．客 を待たせる時間の限界の基準値c（例えばc= 11秒）を設定し，この時間内にオペレータにつ ながる客の割合をサービスレベルと定義すると，

S(y) = ∑

1≤i≤I

λi

Λ P[Wλi(ni)≤c] = ∑

1≤i≤I

λi

Λ P[Wλi(hi(y))≤c] (5.7) となる．ここで，ni=hi(y)は時間区間iのオペレータの人数を表し，Λ =∑

1≤i≤Iλiであ る．また，Wλ(n)は待ち行列モデルM/M/n(到着率λ，サービス率µ)における待ち時間(確 率変数)であり，P[· · ·]は確率を表す．待ち行列理論により，定常状態において

P[Wλ(n)≤c] = 1−Πnexp[−nµ(1−ρ/n)c] (5.8) となることが知られている．ただし，ρ=λ/µ, ρ/n <1,

Πn =

ρⁿ n!(1−ρ/n)

n∑−1 k=0

ρ^k

k! + ρⁿ n!(1−ρ/n) である．このとき，各iに対して，

gi(n) = λi

Λ P[Wλi(n)≤c]

はnに関して単調増加な凹関数^*6となり，モデルの仮定を満たす．

式(5.4)の関数S(y)は離散凹性をもつ．すなわち，gi (i= 1,2, . . . , I) が単調増加な凹関 数であるという仮定の下で，−S(y)はマルチモジュラ(multimodular)関数と呼ばれる離散凸 関数になる[41]．マルチモジュラ性はL^♮性と等価な概念であり，マルチモジュラ関数とL^♮凸 関数の間には，変数変換を通じて次のような1対1対応がある[62, 65]．

定理 5.1. 関数F :Z^K →R∪ {+∞}がマルチモジュラ関数であるための必要十分条件は，

f(x) =F(x1, x2−x1, x3−x2, . . . , xK−xK−1) (x∈Z^K) で定義される関数f :Z^K →R∪ {+∞}がL^♮凸関数であることであり，このとき

F(y) =f(y1, y1+y2, y1+y2+y3, . . . , y1+· · ·+yK) (y∈Z^K) が成り立つ．

*6関数g_iの実効定義域は{n∈Z|n > λ_i/µ}であり，n≤λ_i/µに対してはg_i(n) =−∞とする．

この事実により，問題(5.6)はK−1変数のL^♮凸関数

f˜(x) =−S(x1, x2−x1, x3−x2, . . . , xK−1−xK−2, Y −xK−1) (x∈Z^K−1) の制約なしの最小化問題と等価であることが分かる．したがって，問題(5.6)の厳密解を効率 よく求めることができる．

前節の在庫管理アプリケーションと同じく、本節で開発したシフトスケジューリングのオン ラインアプリケーションも，利用者が対話的にパラメータ入力・最適化を行って瞬時に結果を 得られる範囲の問題サイズに対して提供している。ダウンロードしたODICONソルバを利用 者のローカル環境で実行することで、独自のシフト構成やさらに大規模なスケジューリング

（n= 50程度まで）を最適化することができる。