故障のある機械におけるスケジューリング問題
木島正明
1¥11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111¥111111111111111111111111111111111111111111111¥11111111111111
¥1
¥111
¥11
¥1111111111111111111111111111111111111"'111111¥11¥111¥1
11111
¥11
1
11
¥11
¥11
111

本制では台の機械により仕事を処理する場合に，どのようにして，処理すべき仕事を選ぶかと L 、う問題

(single‑machine scheduling problem) を考える.こいま，最初の時点(時点 0 とする)で K偲の仕事がありSk を仕事 h の処理要求時闘を表わす確率変数とする.要求時間の列 {Sk} は互いに独立であり ，{R(t)} との問題を扱っている多くの論文では，機械は時間に関しも独立とする.さらに，これらの確率構造は，どのようて同ーの処理能力で，連続的に稼働するものと仮定されなスケジューリングをしたかには依存しないとする.こている.しかし，この仮定は実際問題においては，非現こでは簡単のために，新しい仕事は到着しないと仮定し実的であると言わざるをえない.

よう.到着がある場合には，待ち行列の範略で議論されなぜならば機械は稼働中に故障を起こし修理または取り替えによって再る.サーパーに故障のある待ち行列を扱った文献は，たとび稼働状態に戻る J というサイクルを繰り返すからであえば [8 ， 12J などであるが，根本的なアイデアは文献[7]る.また，時間により違う処理能カを持っていると考えによる.また，割り込みを許さない政策的のみを考えるた方が，より現実的である場合が多い.たとえば，機械ことにする.

は動いては L 、るが，時間とともに，摩耗・劣化によりそ機械は同時に 1 つの仕事しか処理できないとし，処の能力が衰える場合や，修理してもその性能が完全には理しないと L 、う政策は考えないことにする".

回復しない場合などがある日.

μ k- 1 =E[Sd< ∞と仮定する.すべての仕事の処理を終

逆に，初期故障を起こす

さらに，原因が徐々に取り除かれてゆき，使用とともにより高い了する時点を表わす確率変数を T とする

性能が発俸されると L 、う場合もある.このような，より時間の総量を表わし，どういったスケジューリング政策現実に近い仮定の下でのスケジューリング問題を扱ったをとるかには依存しないで決まる確率変数である.

r は処理要求

い

論文が，最近少しずつ発表されているので，本稿では，ま，最近の結果のサーベーを行なってみたい.これまでこの採ったときの時点 t での仕事 h の数日を表わす確率変数

Ck を仕事 h の保留コストとし ， Xk(t; π) を政策 π を問題があまり扱われていなかった最大の原因は，その難とする.このとき，政策 r による総期待コストはしさであるが，(1) J( π )=Eu' r; K CkX"， (t; π )dt

なぜこの問題が難しいのかということ

J( π) を最小にするス

ケジューリング政策 π を決定することである.

1. 問題の定式化:
R(t) を時点 t における，k=1で与えられる.ここでの目的は ，も，例を通して考察してみたい.

政策 π の下で番目に処理される仕事を π (i)
この機械の処理率とする.と書く.ある仕事の処理が終わった時点で，それまでの履歴

つまり，時間区間 [a， bJ の聞には ， lR(x)dx という要の情報を使って，次にどの仕事を処理するのかを決定で求量の処理をすることができる.区間 [a ， bJ のすべてのきるので，あらかじめ:>r( i) が何であるかを知ることはで時点で R(t)=O ならば，この機械は区間 [a ， bJ で故障しきな L 川.よって， π (i)は確率変数である.いま，ていると考える.ここでは ， R(t) は時間とともに確率的(2) G(s)=inf{t:/R(x)dxミ s}αに変動しているとする幻.特に R(t) が 0 か l しかとらな

とおく •し、場合を，文献 [1 ， 2 ， 3 ， 5 ， 6 ， IIJ などでは，故障 (break­に，すべての処理を終了するために必要な時間の長さをG(s) は，処理要求時間の総和が s であるときdown) モデルと呼んで‘いる.

表わしている.よって，政策 π の下での番目の仕事

きじま(3) T i ( π)=G(Z4SRfk〉)の処理の終了時間 Ti( :>r)はまさあき筑波大学経営システム科学

干 112 文京区大塚 3-29-1

1991 年 4 月号

で与えられる.よって目的関数は© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(17)115い) J(π)=z:戸川(z;叫Sω)Jールの最適性がつねに保証されるのであろうか?

で与えられる.

ま2. 直感的背景

2 つの仕事があり，処理時間は確定的で

S2=2 とする.また，

まず ， R(t)=1 の場合を考えてみよう.これは， I この(0 ,R(t)=1 .

(5) J( π)=f E[cω 1:t=ltk冒 1{ctlltl のいちばん大きな仕事から処理する政策を ICμ ルール J と呼ぶが，定理 1:R(t)=1 のときはこのときのcμ ルールによるコストは1. 5a+5.5 であるが，逆に，最S宕d批
ω川tωkω〉となる.残っている仕事の中で，コストを c1=1 ， c2= 1. 5 とし，2.5 謡 t~玉 2.5+aC1 μ1 = 1>0.75=C2 f!2 であるから，とする(4)式は

SI=I ，\1 ，その他機械は，どの時点でも 1 単位の処理能力を持っている jことを意味している.このとき，これを見るために，次のような簡単な例を考えてみよう.いcμ ノレールが(動的最適化の意味で)最適である:
ことが知られている.実際，この事実は次の「交換の議論j と L 、う考え方にもとづいて証明できる ([7J とそこでの参考文献参照).以下では，簡単のため，初に仕事 2 を処理する場合は，コストが a+6 となり，a>1 のときは ，Cμ ルールは最適ではない .

R(t) が一定でない場合には，このような簡単なケースでも ， Cμ ルー

ノL の最適性が崩れてしまうわけである 7).
述べた理由により

しかし，上でCμ ノレールが最適である問題の範聞がわかれば，応用上も大変ありがたいので(それ以上に数学の問題としておもしろいので)，いつ C f! ルールが最適になるかと L 、う問題が深く研究されているのである.

Clμ1~C2μz ミ…注 CKμKと仮定する.

3. R(t) が任意の場合

定理 1 の寵明の概略:
政策を決定できる時点 t において ，A(t) を残っている仕事の集合とする.時点 t では，すべての履歴 F t を使って決定を下すことができる.時間軸をずらすことにより ， t=O と仮定してよい.げを cμ ルーんとし， πjを最初に J を処理し，それ以降は cμ ルールにしたがうという政策とする.

さらに，71:'を町において，最初の 2

ここでは ，{R(t)} はある種の正規化条件以外は，任意の確率過程であるとし特別の構造は仮定しないとする.たとえば新しく設置された機械では，その処理能力に関する統計的な情報は少ないので，この場合の {R(t)}は[神のみぞ知る」という状況であるから ，{R(t)} に次節で述べるような構造を仮定するには少有無理がある.

つの I1頂番を交換した政策とする.このとき ， Cμ の大きさ

よって，なるべくゆるい仮定の下で，スケジューリングの仮定より，問題を考えることも重要である .には，J( が)ー J( πj)=E[C1 S '+Cj(SI+ S j) lFo
J{R (t)} が任意、の場合[8J において次のような結果が示されているが 8\

これからの一層の研究が待たれるところである.

-E[cjSj 十 C1(S ，+ Sj) lFoJSj=E[CjS1‑C1lFoJ 豆 O定理 2

処理時間 Sk がすべて指数分布にしたがっていを得る.同様の交換の議論から ， J( 日)豆 J( 71:j) を示すこれば ，Cμ ノレールが最適である.とができるので，最適性の原理から， 71:*が最適で、ある乙定理 3:Ck=1 とする . SI~三 st ・..;;五 stSK で、あればベ処理とが示される.口時間の短い仕事から処理するノレール (ck=1 であるから，ICμ ルールの最適性 j は，最初に確定的なモデルに対して示されたもので(スミスのルーんという)，定理 iの結果は，確定的な場合に成立する簡単な最適政策が，処理時聞を確率変数とした場合にもあてはまるということを言っており，これは応用上も重要で、ある.なぜならば，仕事の処理時間が確率的に変動するものであってこれは cμ ルール)が最適である.

上の 2 つの定理の証明は，基本的には，交換の議論で行なわれる.

4. 故障宅デル
ここでは，多〈の論文で扱われている故障モテゃんにつ

も，管理者はあらかじめ全仕事を ICμ ルール」にしたがいて考える.って並べておけば，以降この処理の過程がどのような経その区間の長さはすべて独立で，状態。と l を繰り返す

緯をとったとしても気にする必要はないわけで“ imple­とする .

mentation"
で:'1 ;1:，と L 、う意味で非常に簡単だからである.

R(t) が時間とともに変化する場合でも ，176(18)Cμ ノL

つまり ， R(t) は O か l の値しかとらず，R (t )=O のときが機械の故障状態 ，ときが稼働状態を表わしていると考える .

R(t)=1 のUt を i 回目の稼働時間の長さで‘ Ut (i 孟 2) は，それぞれ，同一分布に© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

従っているとし ， Di を i 回目の故障時間の長さで Di(i最後に，静的最適化問題11) における，興味のある結果

孟 1) は，それぞれ，同ーの分布にしたがっているとする.

について触れておこう.

動的最適化.)を考えるために，時点 O で機械は稼働状態で，故障による影響は， (η式の右辺で与えられる.にあるとし，それまでにすでに z 時間稼働していたとす

定理 4る.このとき ，稼働時間 U i が DFR 18lであれば，番号の小さいものか{Ui , Dd は遅れのある交代再生過程(delayedalternatingrenewal process) となる . {Nx.
(t)} を，この場合には仰が成立するの:ck=1 とし ， SI 孟 cv... 話 evSK とする ω. もし，ら処理するのが最適である.

確率順序の関係 SI~玉 cv'" 話。vSK は，N.x(t )=max{n:U1 + ・ ..Un ;五 t}により定義される確率過程とし ，E[SIJ= …=E[SKJ

H.x (t)=E[N.x (t)J をであっても成立する.

しかし，このときの cμ 指標は，対応する再生関数とする.以下でみるように，この問題どの仕事においても同じであるからでは，再生関数の性質が重要な鍵となる .の問題は扱えない.実は，この仮定の下では，分散に関G(s) を思いだしてみると ， G(s)-s は，処理要求時間の総和 s を処して，理する聞の，機械の故障時間の総和であるから，

J(π)=z:FC4432LPω](6)

̲KK ̲̲nS山)Ddとなる.上式右辺の第 1 項は (4)式と同じであるから，上式における第 2 項目が故障による影響であるよって，第2 項が無視できるくらいに小さければ，この故障モデルにおいても cμ ルールが最適である.

ではどのような状況下で ， cμ ルールが近似的に最適となるのであろうか?
cμ ノレールと最適政策との差はどれくらいあるのであるうか?

文献 [2 ， 3 ， 6 ， 8J などでは，こういった問題も考えられている即.

う問題を考えてみよう. (6)式における π (i) は確率変数であったから，このままでは第2項の計算が進まないので，K(例7η戸=1=甲Z:FwHa(ZLPω)Jと近似する. (7)は π (k) が確率変数でない場合ω には成ーリングでは cμ 指標，すなわち処理時間の平均しか効いてこなかったが，故障モデルにおいては分散の影響が出てくるということに注意しよう.

ところで，定理 4 は ，rUi が DFR であれば，それに対応する再生関数は凹関数である J ([4 , 10J 参照)とし、う有名な結果による.では DFR と逆の性質である I
FR を仮定すれば，定理 4 と逆の「分散の小さいものかか?

残念ながら，対応する再生関数が凸関数になるとL 、う条件は，一般には知られていないので，この結果を導き出すためには，再生関数に関する研究から始めなけであるから，読者のみなさん，ぜひご一考を/注釈

甲は平均故障時簡を表わす.この近似の下では，次の経験則が成立するであろう.まず，①故障時闘が稼働時間に比べて十分小さければ ， Cμ ノレ
ーノレカ:よ L 、:

また，十分大きな t に対して，再生関数は

注1)最近，信頼性の立場から，不完全修理のモデル化がさかんに行なわれている.たとえば，

注 2)

つまり ，注 3)

いちど処理を開始したら，その処理がすべて終わ

注 4)を満たすので，②総処理要求時聞が回の稼働時間に比べて十分に③処理要求時間が指数分布に近ければ1991 年 4 月号

到着がないので，処理しないで待つとしみ政策は最適でないことがすぐにわかるが，到着がある場合にある ([7J 参照).この問題はすごく難しいようで，このさらに，定理 2 から，ということが考えられる.

{R(t)} が確率過程であるということ.

は，優先度の高い仕事がくるのを待った方がよいこともCμ ルールがよい:

よし、:[9J 参照.

るまで次の仕事を処理できないということ.

Hx(t)‑Hx(t‑h)‑h/E[U2J

大きければ ，よいことがわかる.故障のないモデルにおけるスケジュればならない.この問題は，数学的にも価値のある問題】 k=1

立する.ここで，であれば，処理時間の分散の大きな仕事から始めた方がら処理した方がよ L 、 J と L 、う結果が得られるのであろう

ここでは，経験的に，いつ cp ルールが最適になるかといL: E川

V[SIJ 孟…孟 V[SkJと L 、う/1頂序がつくので，定理 4 から，稼働時聞が DFR

N+L: E[c.<ilJ. .x(L: k =I
戸1】k=1

またはCμ ノレールではこCμ ルールが問題を扱った論文は少ないようである.

注 5)

Xk (t;n) はk が未処理ならば 1 ，終わっていれば O をとる.
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(19)177注 6)

このように，時間とともに動的に最適化を行なう

注 7)

240.
[5J Glazebrook , K.D.(1984) , “ Scheduling 5toｭ

ことを動的最適化と呼ぶ.
R(t) が確定的に変化する場合のスケジューリン

chasticJobsona Single Machine Subjecttoグ問題は，文献 [IJ で扱われている.

Breakdowns ," Naval Res. Log. Quart. , Vol.

注 8)

31 , 251‑
264.

ここでは紙面の制約のため，厳密な形では書かないが，若干の正規化条件が必要である.

注 9)

X~五 stY とは ，

[6J Glazebrook , K. D. (198 7),“ Evaluating theP(X>t) 話 P(Y>t) のことである.

順序関係話回は確率順序と呼ばれている.

このとき ， E[XJ 話 F[ Y] が成り立つ.

注 10)

Effectso
fMachineBreakdownsi
nStochastices.Log. , Vol.
SchedulingProblems ," NavalR34, 3
19‑
335.

1991 年 i 月に，カリフオルニア州モンテレーで行[7J Hirayama , T. , Kijima , M.and Nishimura ,なわれた，応用確率論に関する特別会議でも，この問題

S. (1 989) , “ Furtherに関するセッションがあった.

Schedulingo
fMulticlassGjGjl Queues ," J.

注 1 1)最初の時点でスケジューリング政策を確定してしAp〆 .

まうと L 、う最適化を，静的な最適化問題という.このとResults for DynamicProb. , Vol.26 , 595‑603.

[8J Hirayama , T.andKijima , M.(1991) ,“ Singleきは，もちろん π (k) は確定的である.

Machine Scheduling Problom when the注 12) すべての単調増加で凶な関数 f(x) に対して ， E

Machine Capacity Varies Stochastically ," to[f(x)J 孟 E [f(Y)J となるときに， X;;:;cv Y という . J順序

appear in Oper. Res.
[9J Kijima ,関係語"は確率凹順序と呼ばれている.

M. (1989) , “SomeResults for

注 13) X の分布関数を F(t) とし，密度関数を f(t) とす.
RepairableSystemswithGeneralRepair," Jる .X の故障率はAppl. Prob. , Vol.26 , 89‑102.

r(t)=f(t)j(I‑F(t))
で定義されるが ，f[IO
J Kijima , M.(1990) , “ On theUnimodalityor (t) が単調減少であるとき，

X は DFR であるという.故障率 r (t) はまで稼働してきたという条件の下で，次の瞬間に故障する率を表わしている
ので，DFR のときは，時間とともに故障しにくくなる

Transition P
robabilitiesin Markov Chains ,"Austral. J. Statist. , Vol.32 ，ト 10.
[IIJ Pinedo , M. and Rammouz , E. (1988) , “ANoteonStochastic Scheduling ona SingleMachineSubjectt
oBreakdownand Repair ,"わけである.

Prob. Engin. andInform. Sci. , Vo 1. 2, 4 ト 49.
参考文献[12J Righter , R.and Shanthikumar , J.G.(1989) ,[1J Baker , K.R.andNuttle , H.(1980) ,“ Sequen-“ Schedu 1ì ng Multiclass S ngle
ServerQueue.

cing Independent Jobs with a Single Reｭ

ing Systems toStochast
icall
y Maximizethe

source , “ Naval Res. Log. Quart. , Vo 1. 27 ,Number of Successful Departures ," Prob.

499‑
510.

.3, 323‑333.
Engin. andInform. Sci. , Vol[2J Birge , J. , Frenk , J.B.G. , Mittenthal , J.andRinnooyKan , A.H.G.(1990) ,“ Single-machine

場参平成 3 年度 OR 企業サロン

SchedulingSubjecttoStochast
icBreakdowns"

第 1 回予定.37 , 661‑677.
NavalRes. Log. Vol. and Glazebrook , K. D. (1988).
[3J Birge , J“ Assessing t
heEffectsofMachineBreakdowns

es.Letters ,inStochast
icScheduling ," Oper.RVol.7, 267‑271.

日時

5 月 7 日(火)13:30‑17:00

場所:九州電力会議室(福岡)
テーマ・ゲストスピーカー:1) r 味の素の情報化のめざすもの J
味の素紛常務取締役伊藤謙吉氏[4J Brown , M.(1980) , "Bounds , Inequalities , andMonotonicityPropertiesf
orSomeSpecialized2) r 九州地区における OR 活動 j九州産業大学工学部教授

藤野義一氏.8 , 227‑
Renewal Processes ," Ann. Prob. , Vol

178(20).

..・・・・・・四..........................・・・...........開・・・・・・・・・・・・・・・・・・・・・・・・・・© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ.