コラム・特集

2.3 順序付けと日程計画

IEハンドブック

第11部 計画と管理

第2章 製造システムとプロジェクトのための計画と管理

2.3 順序付けと日程計画

優先‖順序計画,職場統制と日程計画の要素は,最終的に生産システムのパフォーマンスを決定する。もし,利用可能な能力があり,適当な時期に生産指示があり, しかも材料も使用可能であるなら,日程計画は単純な業務に思われるかもしれない。しかしながら,このような場合はない。日程計画問題の複雑さは,簡単な単一機械の場合を考えることによって説明できる。もし,いま1台の機械でN種のジョブが加工されるとき,N種のジョブにはN!通りの順序がある。5種のジョブの場合には120通りの順序になり,10種のジョブに対しては3,628,800順序がある。ジョプの種類および機械の台数が増加したとき,組み合わせの数は極端に大きくなり,現在のコンピュータを用いても,これらの一部分だけの発生または評価しかできない。もし現存のシステムの時間変動や優先順位の変更を考慮するとすれば,最善の日程計画の決定は, しばしば不可能な業務となる。

単一機械問題
単一機械の決定論的問題は,発展的で分析的な論法を含んでいる。この研究は多くの順序付けの規則を規定しており,それはさらに複雑な状態に対して試験され,多くの現存の日程計画システムの基本となっている。単一機械問題は,よく引用される次の3つの規則に帰着する。

最小加工時間規則
最小時間のジョブが第1位になるように最小加工時間(SPT)によって,ジョプを順序付けよ。

この順序は,
1.平均滞留時間を最小にする(ここで,滞留時間はジョプの完了時間と到着時間の差である)。
2.ジョプの平均待ち時間を最小にする。
3.ジョブの平均納期ずれを最小にする(ここで,納期ずれは完了時間と納期との差である)。

SPTはこれらの性質があるので,非常によく用いられる順序付けの1つである。もしそれぞれのジョブに,そのジョブの重要さの程度を示す重みや優先順序が与えられるなら,SPTを一般化し,重み付きSPT(WSPT)と呼ぶ。これは重み付き平均滞留時間を最小にするために用いる。ジョブは加工時間と重み,あるいは優先順序の割合をとって,その小さい順に順序付けられるSPTの順序付けは,職場の作業負荷を過度にする欠点がある。もし,新しいジョブがたびたび到着するなら,それらの中の長い加工時間のジョブを列の終わりに押しやるので,長い期間受け入れられず, システムに残るかもしれない。この性質がジョブの納期を考える規則を導いた。そのような2つの規則を次に示す。

納期規則
最早納期によってジョブを順序付けよ。この順序はジョブの最大納期ずれを最小にする。おもしろいことに,納期ずれの情報を使用しないSPTが, この性質をもっている。さらによい結果は,納期と加工時間を1つの規則の中に組み合わせることによって,達成されることが想像される。推論によるこの方針が,余裕時間(スラック)規則を開発した。

余裕時間規則
最小余裕時間に従ってジョプを順序付けよ。ここで,余裕時間はジョブが納期までに完了するものとして,そのジョプを開始しなければならない以前に,残っている時間の合計である。この川順序はジョプの最小納期ずれを最大にする。

直観的な訴えではあるが,この規則は単一機械問題では有益な性質を示さない。しかしながら,納期が基本的評価基準となる複数の機械を含む問題においては有効となる。

これらの規則の1つの応用例を図表11.2.2に示す。これらの規則は他に有益な性質をもつかもしれないが,この図表は数学的に証明できることのみを含んでいる。

単一機械問題の変形
単一機械のケースにおいては, しばしば興味ある他の目標がある。これらの1つは納期遅れジョブの数を最小化することである。納期遅れジョブとは,完了時間がそれらの納期を過ぎたジョブをさす。この問題の簡単な順序付け規則はない。しかしながらHodgsonのアルゴリズムとして知られる手続きが,最小納期遅れジョブ数を与える。
この手続きのステップは次のようになる.

1.納期規則を用いてジョブを順序付けよ。
2.もし,順序付けられたジョプの中に,納期遅れがなければ,最適解は見つけられたことになる――テップ4にすすめ。さもなければ,順序列の中で最初に納期遅れとなるジョプを見出せ。これを第1番目のジョブと仮定せよ。
3.最初の1個のジョプの中で最長のジョブを選び,それを順序列から除きなさい。ジョブの完了時間を更新して,ステップ2へ進め。
4.もし,順序列から除いたジョブがあるなら,現在の順序列の最後に,順序に関係なく加えなさい。

この手続きの例を次に示す。

 

並列機械問題
さらに複雑な日程計画の問題は,個々のジョブは1つの工程をもっているが,そのジョプを加工するために,いくつかの機械が利用可能な場合である。この問題は,それぞれのジョブの配分をどの機械にするか,個々の機械でのジョブの順序付けをどうするかという2つのことを含んでいる。複数の機械があるので, メイクスパン(makespan:ジョブの加工順序列全体を考えて,その完了時間と開始時間の差で定義される)の問題となるもし,すべてのジョブが1台の機械で加工されるとすると,最大可能メイクスパンが得られる,しかし実際には,ジョブはそれぞれの機械に分配されるのでメイクスパンは減少する。このような問題に対して,整数計画法がある。

いま
Xij=1, もしジョブiが機械jで加工される
とき;0,そうでないとき
ti=ジョブiの加工時間
n=ジョブの数
m=機械の数

のとき, yを次の制約のもとで最小にする。
m∑j=1 X ij=1  i=1,……,n
y-n∑i=1 tiXij ≧ 0     j=1,……,m
X ij ≧ 0かつ整数

第1の制約は,それぞれのジョブがただ1回だけ加工されることを要求している。変数yはメイクスパンを表わす。第2の制約は,yは,少なくとも稼働率のもっとも高い機械の加工時間の合計に等しいことを要求している これが最小化される理由は,yがこの機械の加工時間の和に等しく,それがメイクスパンになるからである。

小規模の問題に対しては,整数計画法を用いることによって解を得ることは可能である。しかし,問題の大きさとともに計算時間が指数的に増加するので,これは現実問題に対して有効な手段ではない。それに替わり,最適解は保証されない力ヽよい結果が得られると思われる,いくつかの手続きが開発されている.最小メイクスパンを発見するために考えられた1つの手続きは,最大加工時間(LPT)規則を用いる。この規則はSPTと反対である,すなわち, ジョプは最大加工時間によって順序付けられる。この手続きは次のようになる。

1.LPT規則を用いてジョプを順序付けよ。
2.割り当てられた加工時間の合計が最小である機械に,順番に,ジョブを与えなさい。

例題が図表11.2.3で解かれている。


LPT規則はSPT規則の反対なので,この問題の場

合,平均滞留時間を最大にする傾向がある逆LPT(RLPT)と呼ばれるLPTの変形を第3の不テップとして,このLPTの手続きに加える。

3.それぞれの機械に与えられたジョプの順序を逆にせよ.

これはメイクスパンは変更しないが,図表11.2.3に示されるように,平均滞留時間を改善する。もし,メイクスパンより平均滞留時間を最小にすることが目的なら,非常に簡単な最適手続き,それはSPT規則に基づく,が用いられる.

1. SPT規則を用いてジョブを1臓序付けなさい。
2.割り当てられた加工時間の合計が最小の機械に、順番にジョブを与えない。

この手続きによって作られた順序は図表11.2.3に含まれている。
さらに複雑な並列機械問題の目的として,たとえば,納期遅れの最小化,重み付き平均滞留時間,または段取時間などがあるが,その最適化は簡単でない手続きとして知られている。動的整数計画法は,納期遅れと重み付き平均滞留時間の問題に用いられてきた。段取問題は複数セールスマンの「巡回セールスマン」の問題として公式化される。もし最大負荷の制約が計算手順の中で加えられるなら,機械が車に,最大負荷が容量に,そして段取時間が距離に対応する配車問題となる。これらのアプローチは,すべて現実の問題に対しては多くの計算時間が必要である。機械にジョプを割り付けるための負荷や納期の調整,それから機械ごとの順序付けには,準最適アプローチが手短で,簡単な計算の解を与える。

フロー・ショップとジョブ・ショップの問題
フロー・ショップとジョブ・ショップは,両方とも複数の機械を含んでおり,注文仕様に従って,一連の作業からなるジョプを加工する.フロー・ショップは一方向の流れであるが,それぞれのジョブはすべての機械で加工する必要はない。

2機械フロー・ショップのメイクスパンを最小化する最適化手続きは, S.M.Johnsonによって開発された。この手続きは次のように要約される。

行うべき作業の中から最小可能加工時間を選びなさいもし,その加工時間が第1の機械のものであるなら,可能な位置の最初にそのジョブを配置しなさい。もしそうでなければ,つまり第2の機械なら,加工可能な位置の最後にそのジョプを配置しなさい。そして,すべてのジョブが配置されるまで繰り返しなさい。

この手続きの例を図表11.2.4に示す。


Johnsonの手続きはJacksonによって, 2機械ジョブ・ショップに応用された。ジョブは次の4つの集合に分割される。

{A}機械1だけを必要とするジョプの集合
{B}機械2だけを必要とするジョブの集合
{AB}はじめに機械1で加工され,次に機械2で加工されるジョプの集合
{BA}機械2で加工され,次に機械1で加工されるジョプの集合

この手続きの順序は,
1.Johnson規則を用いて{AB}のジョブを順序付ける。
2.Johnson規則を用いて{BA}のジョブを川順序付ける
3.{A}と{B}のジョブを順序に関係なく並べる.
4.順序を次のように構成する。

機械1 {AB}  {A}   {BA}
機械2{BA}  {B}  {AB}

この手続きは,それぞれの機械が,順序の制約でジョブを待っている,アイドル時間の合計を最小にすることによって,メイクスパンを最小にしている。

Johnson規則は,また, 3台以上の機械のフロー・ショップにも用いることができる 3機械フロー・ショップの場合, 2台の仮想機械を想定する 仮想機械の加工時間(ij)は次のように計算する。

t i1=ti1+ti2 i=1,…,n
t i2=t i2+ti3 i =1,…,n

ここで,
t ij=機械jのジョブ i の加工時間
n =ジョブの数
t ij=仮想機械jのジョブ i の加工時間
ジョブの順序を決めるために,2台の仮想機械にjohnson規則を適用する。この手続きは,次の条件のいずれかを満足すれば最適メイクスパンを作る。

1. min{ t i1} ≫  max{ ti2 }
2. min{t i3 } ≫  max{ ti2 }

これは機械2が,機械1と機械3のいずれか,または両方に支配され,随路ないことを意味する また最適順序なら,機械1と2の場合のみの順序が,械2と3の場合のみの順序と同一であることがJohnson規則によってる。その時,この順序はまた3機械問題の場合にも最適である。

機械が3台より多いフロー・ショップについて,Ompbell,Dudek,そしてSmithによって提案された手続きは,メイクスパン問題に対して, 1つのよい解(必ずしも最適ではない)を探すのに用いられる。それは複数ステージエ程といわれ,それぞれのステージに2台の仮想機械を想定し,順序を決めるためにjonson規則を用いる。この手続きは機械をmとしたときm-1の可能な,異なった順序結果を得る。これらの順序はそれから評価され,最小のメイクスパンの順序が使用される。m-1ステージのそれぞれに対して,仮想機械の時間は次のように計算される。

ステージ1.

t i1=ti1
t i2=t im

ステージ2.

t i1=ti1+ti2
t i1=ti,m-1+ti,m2

ステージK、3 <K<m-1

t i1=k∑j=1・t ij
t i2=m∑j=m-k+1・t ij

この手続きは機械台数mのフロー・ショップを,一連の2機械フロー・ショップに縮小し,全機械の最もよい順序付けに利用している。2または3機械フロー・ショップの場合,最小メイクスパンを生じる順序は,すべての機械(工程)でジョプの加工順序は同じになる。しかしながら, 4台以上の機械の最適スケジュールでは, ジョプの順序は,機械が異なると異なってくる必要があるかもしれない。

Ompbell,Dudek,そしてSmithの手続きでは, この種のスケジュールを捜すことはできない。したがって,たとえば整数計画のような方法論が,そのような最適スケジュールを捜すために用いられるにちがいない。整数計画法は, ジョブ・ショップやフロー・ショップの問題のため開発され,また, これらの多くは出版されている。分岐限界法は,また, ジョブ・ショップの問題に応用されている しかし, これらのアプローチは, どちらも現実の問題に有効でない。なぜなら,それらは法外の計算時間と記憶容量,またはそのいずれかを必要とする。

大きな工場を管理する1つの方法は,ディスパッチング(差立)の手続きを用いることである。機械の負荷がなくなったときはいつでも, その機械を待っているジョブの列が調べられ,優先規則が適用され,加工すべき次のジョブが選ばれる.ジョブを選ぶためによく用いられる優先規則として,次のようなものがある。

・最小作業時間
・その列の最大待ち時間
・最大後続作業数
・最小残り仕事時間
・最大残り仕事時間
・最小余裕時間
・最小納期
・余裕時間を残り作業数で割った値の最小値

SPT規則は,優先規則の中で最もよいものであると思われる。しかしながら, これは,用いられる能力評価基準と工場の種類の両方に依存する_工場における異なった優先規則のパフォーマンスは, コンピュータ・シミュレーションによって評価することができる。それぞれの規則でシミュレーションを多数回実行し,それから能力評価基準の,平均と分散の最もよい規則を実施のために選ぶことができる。

順序付けに加えて,この種の問題に対して,いくつかの代替アプローチが追求されている。フロー・ショップの機械間の最適バッファの決定は,多くの注目を集めている。しかしながら, これらの手法は,たとえばコンベァ・システムのような,中間在庫が制限されて設計される状況に対して,基本的に応用可能である これらの状況に関しては,いくつかのめざましい効果が得られているが,それらの手法は一般に応用が大へん困難である。そして,よい結果にかぎって,プロダクト・ミックスはできない 1つの代替の手法は人の能力を選択し,割り当てることによって流れを管理することである この種の手続きはよい結果を得ることはできるが,容易に用いることができる一般的手法はまだない。多くの手続きは限られた状況において,良いまたは最適解を与える。段取問題,工程制御の問題,輸送問題,そして組立ライン・バランシング問題はその例である。

能力評価基準(Performance Measures)
生産システムの品質を測るパフォーマンス管理要素は,また管理機能に十分な効果をもたらすことができる.基本的能力評価基準は3つの一般的目標に分けられる。

1.顧客の満足度を最大にする これはすべての注文が納期までに完成されることを意味する。一般に達成すべき割合の多くの下限は90から95%である。
2.加工中の仕事を最小にする これは加工中の在庫の合計が最月ヽになるようにシステムを管理し,それによって在庫投資費用を最小にすることを意味する。
3.資源の利用を最大にする これは資源(人力,機械,その他)を可能な限り,最大限に利用することを意味する。

理想的なシステムは,これらのすべての目標を達成することである。にもかかわらず現実には,どれか1つの目標を達成すると,他の2つの目標は逆の効果を示す傾向がある。したがって,システムの使用者は,これらの目標に順位をつけ,受け入れられる重み付き目標機能を,探すことを企てなければならない。

能力評価基準を応用する場合, システムの目標を,作業現場の目標に一致させることを守るべきである。たとえば,現場の職長のパフォーマンスは, しばしば1カ月間の金額換算の産出によって測られる。これは月の初めの2, 3週は無理な増産体制をとり,高金額の製品を生産し,残りの1, 2週は職長に与えられた分担のために費やすという,ムダな職長の行為を招く結果となる。その結果, システム・パフォーマンスは,客の満足度の不足,機械の有効利用不足を招くことになる。

それは工程における部分的仕事を短縮するかもしれないが,高額の部品は発送日まで待たねばならないし,他部門からの低額部品は,組立てを待たねばならないかもしれない.システム全体を考えると,このような環境のもとでは,工程中の真の仕事は増加している。

 本コラムは絶版となっている「IEハンドブック(サルベンティ編・日本能率協会訳・1986)」をアーカイブとして掲載するものです。このハンドブックの各章は多くの事例と理論を通して生産性向上に対するアイデアを提供するべく専門家によって執筆されています。基盤をなしているIEの考え方・原則はインダストリアル・エンジニアリングにかかわるすべてのひとに有用でしょう。

関連記事一覧

2019ものづくり公開セミナーガイド

B2Bデジタルマーケティングセミナー

ものづくり人材育成ソリューション

マーケティング分野オンラインセミナー