人（設備）を増やすと全体のパフォーマンスが低下!? スケジューリングの重要性

人（設備）を増やすと全体のパフォーマンスが低下!?　スケジューリングの重要性

　生産計画や作業計画において、スケジューリングは非常に重要となります。なぜならばタスクの割り当ての仕方によって工場やシステム全体のスループット（出来高）が変わってくるからです。中止していないと個々の設備の能力を増やしたり、また設備や人を増やすとかえって全体のパフォーマンスが下がることがあります。

以下の論文にはそういった例がいくつか紹介されています。「Bounds for Certain Multiprocessing Anomalies」 R.L. GRAHAM

さて今回は上記論文を参考に、人（設備）を増やすと全体のパフォーマンスが低下することを確認してみます。

まず、スケジューリングについてリスト法と呼ばれる方法をとります。これは作業（Task)を優先順位順に並べて、空いている設備に割り当てていくという方法です。

例えば、2台の設備(P₁,P₂)に対し、タスクを3つ(T₁,T₂,T₃)割り当てることを考えます。

また各処理時間とタスクの半順序（タスク間の依存関係）は以下のようになっているとします。

ここでタスクの優先順位はT₁,T₂,T₃である。また各タスクにかかる時間は「/」の後ろに記載しています。また半順序があるので、T₃はT₁が完了後にのみ開始することができます。優先順位リストに従い、かつ半順序に従ってタスクを割り当てていくと

になり、総処理時間ω = 3となります。

さて、次に同じようにして以下の問題を考え、これに対して設備を追加することで全体のスループットを向上させることを考えます。

まず設備が2台の場合のガントチャートは以下のようになり、

総処理時間ω = 1 + 3 + 2 + 2 + 2 = 10となります。ここで設備を1台増やすと

となり、総処理時間ω' = 1 + 2 + 9 = 12となります。

つまり、設備を追加したことで全待ち時間が増えてしまい、総処理時間が増えてしまいました。したがって、単純な割り付けロジックでは待ち時間が増えてしまうことがあるため、スケジューリングを行う際には注意が必要である、ということです。

なお上にあげた論文では、上記のように設備（Processor unit)を増やした場合だけでなく、個々の能力を上げた場合や優先順位リストを変更した場合も載っています。