•
確率スケジューリング問題について
木瀬洋，塩山忠義
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 1.緒言 スケジューリングは本特集でも見られるように 種々の分野においてシステムの運用効率を高める ための重要な手段である.本稿は，たとえば金重 少量生産システムのモデルとしてしばしば研究対 象となっている機械スケジューリング問題(以下 では単にスケジューリング問題と言う)を取り上 げる. すなわち，多種の要素の一連の処理(これをジ ョブという)を数台の機械で行なうとき，与えら れた評価関数(たとえばジョブの最大完了時間)の 値を最適(最小)にするよう，各機械におけるジ ョブの処理順序を決定する問題である.スケジュ ーリング問題は代表的な組合せ最適化であり，解 (スケジュール)の数は有限であるが膨大であり， その中から最適解を見い出すことは原理的には可 能であっても実際上きわめてむずかしいという特 徴を有する. スケジューリングに必要な全データがあらかじ め確定している場合を確定スケジューリング問 題，データの一部が不確定(すなわち，確率変数) である場合を確率スケジューリング問題と言う. ただし，ここでは確率変数の分布は既知とする. 本稿の主目的は確率スケジューリングに関する詳 きせひろし，しおやま ただよし京都工芸繊維大学 工芸学部機械工学科 干 606 京都市左京区松ヶ崎 750 (46) 細な文献調査ではなく，確率スケジューリングの むずかしさを確定スケジューリングと比較して論 ずることである. (最近の研究状況を解説したもの として文献 [1 りがある) 確定スケジューリングの研究の歴史は他の OR と同じくらい古く，かつ現在も活発である.特に 1970年代初期に Cook [8J および Karp [26J によ って提唱された組合せ最適化に対する NP 完全理 論により飛躍的に発展した(たとえば文献 [20， 27J 参照) .しかしこれらの結果の大部分はすべてのデ ータが既知で時間とともに増加も，変化もしない， いわゆる萱盟な場合である.他方，確率スケジュ ーリングは(結果として静的な場合もあるが)本 質的には塾盟である. (少なくとも時間とともに処 理状態が徐々に確定していく. )このため確率スケ ジューリングは単に組合せ最適化だけではなく， 重宝過主における最適制御問題でもある. l つの確定スケジューリング問題に対応する確 率スケジューリング問題としてここでは 2 種の定 式化を取り上げる. 1 つは，たとえば(確率変数で ある)ジョブ最大完了時間の期待値を最小にする 問題である.この種の問題を期待値最小化スケジ ムニム乙とと言うことにする.他は，たとえばジ ョブ終了時聞が納期を越える確率があらかじめ決 められた値以下ならば納期退れでないとした上で 納期遅れジョブ数を最小にする問題である.この 種の問題を確率制約スケジューリングと言うこと にする.いずれの場合も確率変数の分散を 0 とすれば， 確定型になる.したがって確率スケジューリング は確定スケジューリングの一般化と見なされる. しかしながら，確定型が解けなくても対応する期 待値最小化スケジュ}リング問題が解ける場合が しばしば存在する.この原因は仮定された確率分 布の特異性にある.すなわち，解ける問題のほと んどは指数分布またはそれに類する分布を仮定し ている.このことによって最も簡単な確率過程(い わゆるマルコブ過程)が保証されることになる. この状況は信頼性や待ち行列の理論と軌をーにす るところである.したがって，指数分布の場合は 確定型の一般化ではなく，別のクラスであると言 える.他方，確率制約スケジューリングの研究は 現在まで多くを見ない.にもかかわらず，次のよ うな理由でこの問題は重要である.この問題では データの分布として正規分布がむしろ扱いやす い.正規分布は，たとえばジョブ処理時間につい ては少なくとも指数分布より実際に即応している 場合が多い.かつ，正規分布は任意の確定値(一 定分布)の完全な一般化である. このような背景のもとで，以下では問題の分類 と計算複雑性に関する予備知識を述べた上で期待 値最小化スケジューリングおよび確率制約スケジ ューリングの各々について論じることにする.
2
.
スケジューリング問題と計算複雑性 の分類 ここでは以下の論議の便宜のため，問題の分類 と問題のむずかしさ(計算複雑性)の表現につい て簡単に述べる.2
.
1
問題の分類 従来の確定スケジューリング理論では問題を 3 つの特徴 α ，ß
, r で分類し， αIßlr と記すこと が多い(たとえば [1 1， 20J 参照).ここでもこの 分類に準拠する. α は機械数に関するもので，主な例を以下に示 す. α=土:システムは l 機械からなり，各ジョブ は一度だけ処理される.よ盤盟国璽と言う. α =Pm : システムは m 台の同一機械からなり， 各ジョブはいずれか 1 台の機械で一度だけ処理さ れる.同一並列機械問題と言う. α =Qm: システムは m 台の処理速度の異なる機 械からなること以外はPm と同じである.二壁韮型 盤盤盟墨と言う. α=長:システムは m 機械からなり，各ジョブ は順次，各機械で一度ずつ処理される.どのジョ ブも機械を通過する順序は同一である.三工二三ニ :1'y三国璽と言う. α=主:各ジョブが機械を通過する順序が異な る以外はFm と同じである.ジョブショップ問題と 言う. F はジョブの処理に関する付加条件である.主 な例を以下に示す. 戸 =pmtn: 処理中のジョブの一時中断 (pre E旦些些旦)が許されることを示す. ß= 主主主:ジョブ聞に処理上の先行制約 (prece dence constraints) がある. ß=rJ: 各ジョブの準備時間 (!eady time) あ るいは最早開始時刻が異なる. T は最適化(ここでは最小化)されるべき目的 関数を表わす.主な例を以下に示す. r=Cmax : ジョブ j の終了時聞を Cj とすると， Cmax=maxCj である.最大完了時間と言う.r=~Cj: C
jの総和を表わす，主工堕盟主E
と言 う. r=~Tj :各ジョブ j に納期 djが与えられたと き ，T
j=max{O
, cj-dj} で与えられる.すなわち， 担盟遅主主Eを表わす. r=~Uj:Tj
>
0 のとき ，Uj=l
. それ以外はUj=
0 とする.遅れジョブ数と言う. この他， 各ジョブに重み Wjj/. 与えられている とき， 重み和 ~WjC"
~WjT
j, ~WjUj
が考 えられる.期待値最小化の場合，たとえば Cmaxの7
5
1
代りに E(Cmax) を用い，確率制約の場合，戸に確 率制約を導入することにする.
2
.
2
計算複雑性の表現 問題を解くのに必要な計算量，すなわち計算複 雑性に関して NP 完全理論は問題を(効率よく)盤丘三問題と主主主主と(いわゆる旦E室全)問
題に分類する. たとえばジョブ数 n を問題の規模としたとき， この問題がo (j(n)) の計算量で解けるとする.ここ で f(n)はn の関数で， O (j(n)) はこの問題のどんな 例に対しても c点n) ( C は n に無関係な定数)以下 の計算量ですむことを表わす.このとき ，J(n)が n の多項式で表わされる問題は解けると言い，がな ど指数関数以上の問題はむずかしいと言う n の 増加に対する両者の増加速度の違いを考えれば， この区別は妥当である.問題が解けることの証明 は n の多項式程度の計算でその問題を解くアルゴ リズム(多項式時間アルゴリズムと言う)を見い 出せばよい.問題がむずかしいことの証明は多項 式時間アルゴリズムが存在しないことを証明すれ ぽよいが，これは文字どおりむずかしい.実際， このことが証明された例はまだ存在しない.しか しながら，これまでむずかしいとされてきた問題 のすべてが今考えている問題に帰着することが示 せるとする.このとき，もしこの問題が解けるな らばすべてのむずかしい問題も解けることにな る.実際，これまで歴史的にもきわめてむずかし いとされている組合せ最適化問題が非常に多数存 在する(文献 [15J 参照) .現時点ではこれらが一 挙に解決するとは考えがたい.そこでこのように 最もむずかしい組合せ最適化問題は NP 完全であ ると言う. NP 完全なスケジューリング問題では 最悪の場合 n の指数関数以上の計算量を覚悟し なければならない.3
.
期待値最小化スケジューリング ここでは 2. の分類にしたがって対応する確定お よび確率スケジューリング問題の計算複雑性を比7
5
2
(48) 較することにする.なお，この章では特に断らな いかぎり，各ジョブ j の処理時聞は平均 1/μj の独 立した車整盆亙と仮定する. 3.1 機械問題 ① lldj=dlL
:
Wj Uj は NP 完全である [26J. (dJ=d は納期一定を表わす. )他方 lldj=dl E(wJ Uj) は解ける [10]. すなわち ， Wj 仰の大 きい順が最適となる. ② llpmtn,dL:
wj Cj は NP 完全である[30J. 他方，llpmtn
, dE(L
:
wj Cj) は準備時間 rJ が任 意の結合確率分布の場合でも解ける[ 40]. すなわ ち，最適スケジュールではどの時点 t でも手元に ある(円近 t を満たす)ジョブのうち最大の WJ 仰 をもっジョブが処理されていなければならない. ③ llprec， ρj=II L: Wj Cj は NP 完全である[
3
1
J
.
(PJ= 1 は処理時聞がすべて i であること を示す. )また ， llprecIE(L
:
wj Cj) はすべての処理 時間が平均 1 の指数分布の場合でも NP 完全であ る[39J. 両者は同ーの最適スケジュールを有する. この他の l 機械期待値最小化スケジューリング については文献 [4， 18， 19J を参照されたい.3
.
2
並列機械問題 結果を示す前に並列機械問題に対する代表的な スケジューリングを示しておく.L
EPT スケジューリング:ジョブを平均処理 時間の大きい順 (LongestE
x
p
e
c
t
e
d
Proce問 ng Iime) に並べたリストを作成する.時間 t=O か ら開始し，いずれかの機械が空(処理をしていない 状態)になるごとにリストの順番にしたがって未 処理のジョブをその機械に割り当てる.なお， リ ストの順番でジョブを機械に割り当てるスケジュ ールをリストスケジュールという. 動的 LEPT スケジューリング:一様並列機械 問題で処理の一時中断 (pmtn) が許される場合， どの時点でも常に処理速度の速い機械にはより平 均処理時間の大きいジョブを割り当てる.S
EPT スケジューリング:ジョブを平均処理時間の小さい I1頂(笹ortest ~xpected ~oce叩ng
主ime) に並べたリストスケジュールである. 動的 SEPT スケジューリング:平均処理時間 の小さいジョブを優先する以外動的 LEPT と同 じである. ④ PllCmax は2機械でも NP 完全である [26J. 他方 ， PIIE(Cmxx) は解ける. LEPT スケジュー リングが最適である[3， 44J. ⑤ PII L; Cj およびPIIE( L; Cj ) はともに解ける. (前者に対しては[7]，後者に対しては [3，
4
4
J
.
)
ともに SEPT (確定型に対しては特に SPT と言 う)が最適である.⑥ Qmlpm tnlCmax および QmlpmtnlE (Cmax) はともに解ける. (前者に対しては [22J ，後者に対 しては動的 LEPT が最適である [45J.
)
⑦ Qmlpmtnl L; Cjおよび QmlpmtnlE(
L
;
C j) は ともに解ける. (前者に対しては[32J ，後者の場 合，動的 SEPT が最適である [45J.)
他の並列機械期待値最小化に対しては文献 [16 ， 17 ， 21 ， 35 ， 36 ， 41 ， 42 ， 43J を参照されたい.3
.
3
LEPT スケジューリングの最適性 並列機械問題に対する LEPT スケジューリン グの最適性の“カラクリ"を理解するため， P211E (Cmax)，すなわち同一 2 並列機械問題を考えよ う.各ジョブ i の処理時間 Xiは平均 1/よれの指数 分布 (μie-pil) にしたがい， μ1::三 μ2< …三三 μn とする. また説明の都合上，時間 t=
0 で一方の機械M1 はすでに仮空のジョブ O を処理しており，その処 理時間Xo の分布は任意とする . (Xo=O でもよい.) もう一方の機械 M2は t=O で空である.LEPT
スケジュールにおいて 2 機械の終了時間の差を D (Xo; Xh X2， …， Xπ) と記す. これは，最後に 終了した 2 ジョブの終了時間差でもある. (ガント チャートを描くとわかりやすい. )このとき， D(XO;XhX2…
， Xω)=2C
max-L
;
ni=oXi (1) となる . L; Xjはスケジュールに関係ないから ， E (Cmax ) の代りに E(D(Xo;X1， …， Xπ )Jが最小と なることを示せばよい. 非 LEPT スケジュール としてジョブ l と 2 を交換したスケジュールを考 え，その終了時間差を D(XO;X2， Xh … ， Xn) と記 す.いずれのスケジュールにおいてもどのジョブ も最後に終了する可能性があることに注意する.LEPT
(非 LEPT) スケジュールにおいてジョブ i が最後となる確率をあ (qi) とする.ジョブ O が 最後の場合 PO=qO=P(X1+X2+…
+Xn::;;Xo),
(2) である.各ジョブ i ( i 孟 1 )が最後の場合，他のジ ョブがすべて終了したという条件のもとでの Xi の残存時聞は(豊翠金主の墾韮量生により)再び 同ーの指数分布にしたがう.また各ジョブ iが最 後とし、う事象は互いに排反であるから (2) より E(D(Xo;X
l, X2,
…)J-E(D(Xo; X2,
X 1…]=~~tL; ni=l Pi μ灼z 円 dt一~~小=仰
=L; n
巴れ
nηni=l (pか什れ
i-司巾一
1
叩qψω
叫
fρ)江~~t削
μ抑z刊 dのt= L; n
ひれ
"ηnl=l(ρ
t一q豹ωdο)ν/μ仰
t =L; η i=l(Pi 一 q小;) (1/(μtμη/(μ飽一 μ仰i) )日]， (3) ここで、最後の関係は ρη (qπ)= 1-L; ~;;lpi(qj) を 考慮した.最初に n=2 の場合を考えよう .μ1 三三 μz であるから，も L P1 ::;;q1 ならば， (3) は非正と なり，非 LEPT に対する LEPT の有利性が示せ る . 71=
2 のとき ， Pi(q;), i=O， I ， 2 は簡単に求 められ ， Pl::;;ql なることが示せる [35]. この場合， ジョプ 1 を早く開始する (t = 0 で Mzに割当て る )LEPT が有利で、あることは直観的にも理解で きる.一般にジョブ‘数が n-l の場合に LEPT の有 利性が成り立っとすると，ジョブ数が n の場合で も成り立つのである.なぜ、なら， (3) の最後の関係 は平均が 1/(μz向 /(μn 一 μi)] (i= 1， 2 ， … n ー 1 )の (n- 1) ジョブに関する式と見なせるからである. つまり，帰納法により D(Xo; X1， X2…)がD(Xo; Xz, X l，…)より常に有利であることが示せた.次 に任意の k ( 1ζh 三三 n ー 1 )に対して Xk と Xk+l を交換した非 LEPT スケジュールと比較してみ る.このとき， D(Xo; X l，・・・ ， Xk-1 ， Xk ， Xk+h...， X偽) =D(Xo,X!, …,Xk-!;Xk, Xk+!, …,X n), (4) とすれば，再び上述の論議が成り立ち，非LEPT に対する LEPT の有利性が示せる.(
4
9
)
7
5
3
以上，やや乱雑な論議であったが， LEPT スケ ジュールの最適性が指数分布の特殊な性質にもと づいていることが理解できょう.もう l つ見逃が ぜない点は，期待値最小化では問題のすべての実 現例に対して LEPTが常に最適であることを意味 しないことである.この意味では確定型はより厳 しい条件を要求していることになる.当然だが， p隅IICmaxに対して LEPT (すなわち， LPT) スケ
ジューリングは最適ではない.しかしながら，こ の問題に対する重宝盟盤垣 [5， 6J によれば，
LPT
はPmllCmax に対してきわめて優秀な近似解法のよ うである.3
.
4
フローショ‘y プ問題 ⑧ 解ける場合は 2 機械フローショップ問題に おける F211Cmax と F211E (Cmax) の場合しか知られ ていない.前者の纏定的な場合に対しては有名な Johnson ルールがある [24J :最適スケジュールで ジョブ t が j に先行する必要十分条件は min(A ， Bj) S:min
(Aj, Bi) である.ただし ， Ai'Bi はそ れぞれ第 1 および第 2 機械におけるジョブ i の処 理時聞を表わす.確率的な場合 ， Ai ， Bi がそれぞ れ平均 1/f-lli, 1/μ2iの指数分布にしたがうとする と， μli 一 μ2i の大きい JI慣が最適で、ある [1 ， 9J. 両ス ケジューリングが一致していない点が興味深い. なお，両問題とも最適スケジュールで、は第 1 およ び第 2 機械でのスケジュールが同一で、なければな らないことを指摘しておく. この他の確率フローショップ問題については文 献 [12 ， 13 ， 14， 33 ， 38J を参照されたい.3
.
5
ジョブショ'"プ問題 確率ジョブショップ問題は現在未開拓の分野で あり，次の結果が知られるのみである.⑨ J211Cmaxおよび J21IE(Cmax) はともに解け る.前者に対しては Jackson ルールがある [23J. 後者の確率型に対しては次の方法が最適解を与え る[37]:第 l 機械の次に第 2 機械で処理されるジ ョブ集合を A ， 逆の順序で処理されるジョブ集合 を B とする.また 機械しか要求しないジョブ
7
5
4
(50) を単処理ジョブということにする.このとき，第1 (2) 機械が空になるごとに μ1i一 μ2i (μ2i 一 μli) の 大きい A(B) のジョブを割り当てる.そのような ジョブがないときは任意の単処理ジョブを割り当 てる.
4
.
確率制約スケジューリング 現在公表されている確率制約スケジューリング 問題は次の場合だけのようである. 各ジョブ j (j = 1, 2,…, n) の処理時間釦は独 立した正規分布 N(mj， 町2) にしたがう.ただし， mj およびviは平均と分散である.また，各ジョブ j には既知の納期 dj が与えられている.ここでは ジョブ jの終了時間 Cjがんを越える確率があら かじめ与えられた値 α (1 /2ζα< 1) 以下(すなわ ち ， pk>dj) S:a) ならば納期遅れと見なさない とする.このとき納期遅れジョブゃ数 L:. Ujを最小に するスケジュールを決定したい.明らかに，全分 散をo ~こするとこの問題は lll L:. Uj になる.そこで 以下ではこの問題を l ゆ (Cj 注 dJ
) 三三 α I L:. Uj と記す. IIp(
c
j ~とめ)三 α I L:. Uj は lll L:. Ujの完全な一般化で ある. IIp (cj ミ dj ) 三三 α I L:. Uj の特徴は終了時間 Cj もま た正規分布にしたがうことである.すなわち，ス ケジュール (i t，i
2, …, in ) において j 番目のジョブの終了時間Cij=Pi1 +Pi2+ … +pij は(主墨金主 の豆生生より )N( L:. h~lmil" L:. h=lV2仇)となる.よ ってジョブんが(確率的)納期を満たす (p (Cij 注 d川三三 α) 必要十分条件は (dij-L:. h=lm山 )/C L:. h=l V2ihJ1/2;::>: φ-1(α) ， (5) である.ただし， φ 一 1(α) は標準正規分布N(O ， 1) の 分布関数 φ (u) の逆関数で、ある. (5) よりスケジュ ール(九九…，ら)が最適である必要条件はらが 納期を満たすならば，九 (h=I ， 2 ， …j- l) も満た し，かっ ， dij 二三 d仇とならねばならないことであ る.そこで納期を満たすジョブ集合を1={ih ... id と記すと，問題は
max.
ks
u
b
j
e
c
t
t
o
(
5
)
f
o
r
ijεL (6)と定式化できる [2J. この意味では 1Ip(Cj>dj) ζ α I2: Ujは確定的問題と言えよう.以下ではこの問 題が NP 完全であること，および特殊な場合には 解けることを示そう.
4
.
1
NP 完全性 ⑮ 111 2: Ujは解ける[34J. 他方 ， 1Ip(cj>dj ) 孟 α I 2: Uj は NP 完全である [29J. すなわち， NP 完 全であることが知られている次のナップザッグ問 題 [26J はこの問題に帰着する. KNAPSACK: 与えられた N+2 個の正整数 {at.…
,aN, b， k} に対して 2: :"=1 xi=k， かつ，2: f=1 aiXi=b を満たす O 一 l 変数 xi(i=l ， … ， N) が存 在するかどうかを決定せよ. この KNAPSACK に対して次の 1Ip (cj>dj ) 三 α I 2: Uj を考える: n=N+ 1 ， α=φ (4kA(kA -b )1/2),
mi=A+ai, Vi2=A-ai' i= 1 ， ・ "， N，di= (kA+b) + φ1(α)(kA-b)1/2 ， i=l ， … ， N，
mN+l 任意の正整数 ， V2N+l=4kA(kA-b) (kA+
l),
dN+1=kA+b+mN+l+ φ → (α) (kA -b+V2N+l)1/2,
A> 2: ι1 ai を満たす任意の整数， という設定のもとで納期を満たすジョブが (k+1) 以上あるかどうかを決定せよ. 結論だけを述べるとこの問題で納期を満たすジ ョブ数が(k+
1 )以上である必要十分条件は KNAPSACK が解をもつことである.言し、かえ ると ， 1Ip (cj>dj) 三三 α I 2: Ujが解ければ ， NP完全 な KNAPSACK も解けることになる.4
.
2
解ける場合 ⑪ すべての納期が等しい場合 11ρ (cj 三とん) I 2: Uj は解ける [25]. ⑩の結果と比較すると，わ ずか 1 ジョブの納期が異なるだけで問題のむずか しさが急変することがわかる. ⑫処理時間の平均mi と分散 V2i が“ agreeable" な条件 (mi<mj訪問Z 豆町2) を満たす場合は解け る [28J. 1987 年 11 月号 5. 結言 確率スケジューリング問題はここ数年盛んに論 じられるようになってきた.本文はその主な 12 (①~⑫)の結果を確定的問題と対比させながら論 じた.これらの結果から確率スケジューリング問 題はよりむずかしいとは一概に言えないようであ る.今後さらに発展すると確信する. この拙文が その一助になれば幸いである.なお，筆者の不勉 強のため誤った点があるもか知れない.読者諸氏 の率直な御批判を仰ぎたい. 参芳文献<1] P.C. Bagga( 1970) N.Job, 2-Machine Sequenｭ cing Problem with Stochastic Service Times. Opsearch 7,18
•
199.[2] S. J. Balut(1973) Scheduling to Minimize the Number of Late Jobs When Set-up and Processing Times Are Uncertain. 19,1283-1288.
[3] J. Bruno, et al.(1981) Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan. JACM
28
,
100-113.[4] S. Chakravarthy( 1986) A Single-Machine Scheduling Problem with Random Processing Times. Naval Res. Logist. Quart. 33 ， 39 ト397.
[5] E. G. Coffman, et al.(1984) A Note on Expected Makespans for Largest-First Sequenｭ cings of lndependent Tasks on Two Processors. Math. Operations Res. 9,260-266.
[6] E.G. Coffman, et al.(1985)On the Expected Relative Performance of List Scheduling. ORSA 33,548-561.
[7] R.W. Conway, et al.(1967)Theory of Scheduling. Addison-Wesley, Reading Mass. [8] S. A. Cook (1971) The Complexity of
Theorem-Proving Procedures. Proc. 3rd Ann. ACM Symp. Theory of Computing, 151-158. [6] A.A. Cunningham, et al.(1973) Scheduling
Jobs, with Exponentially Distributed Processing
Times, on Two Machines of a Flow Shop. Naval Res. Logist.Quart. 20,69-81.
[IOJ C. Derman, et al. (1978) A Renewal Decision Problem. Management Sci.24,554-561.
[IIJ M. A. H. Dempster, et al.(Eds.) (1982) Deterministic and Stochastic Scheduling. D.
Reidel, Dordrecht, Boston,London. (Proceedings of the N A TO Advanced Study and Research Institute on Theoretical Approaches to Scheｭ duling Problems Held in Durham, England, July 6-17, 1981)
[12J R. D. Folly & S. Suresh( 1984) Minimizing the Expected Flowtime in Stochastic Flow Shops. IEEE Trans. 16
,
391-395.[13J R. D. FolIy & S. Suresh(1986) Scheduling n Nonoverlapping Jobs and Two Stochastic Jobs in a Flow Shop.Naval Res.Logist. Quart.
33,123-128.
[14J F .G. Forst (1983) Minimizing Total Expecｭ ted Costs in the Two-Machine, Stochastic Flow Shop. Operations Res. Letters 2
,
58-61.[15J M.R.Garey & D.S. Johnson( 1979)Computer and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Franciscoo. [16J J. C. G tt ns (198 1)島fultiserver Scheduling
of Jobs with Increasing Completion Ratios. J. Appl.Probab. 18,321-324.
[17] K. D. Glazebrook (1979) Scheduling Tasks with Exponential Service Times on Parallel Processors. J. Appl.Probab. 16,685-689.
[18J K. D. Glazebrook( 1980) On Single-Machine Sequencing with Oder Constraints. N aval Res. Logist. Quart. 27,123-130.
[19JK.D. Glazebrook (1980) On Stochastic Scheduling with Precedence Relations and Switching Costs. J.Appl.Probab. 17,1016-1024.
[20J R.L. Graham, et al.(1979)Optimization and Approximation in Deterministic Sequencing and Scheduling : a Survey. Ann. Discrete Math. 5
,
287-326.
7
5
6
(52)[21J L.V. D. Heyden (1981) Scheduling Jobs with Exponential Processing and Arrival Times on Identical Processors so as to Miniｭ mize the Expected Makespan. Math. Operations Res. 8,305-312.
[22J E. C. Horvath, et al.(1977) A Level Algoｭ rithm for Preemptive Scheduling. JACM 24,32
-43.
[23J J. R. Jackson (1956) An Extension of Johnson's Resu!ts on Job Lot Scheduling. Naval Res. Logist. Quart. 3
,
201-203.[24J S. M. Johnson (1954) Optimal Two- and Three-Stage Production Schedules with Setup Times Included. Naval Res. Logist. Quart. 1, 61-68.
[25J N. Katoh & T.lbaraki( 1983) A Polynomial Time AIgorithm for a Chance-Constrained Single Machine Scheduling Problem.Operations Res. Letters 2
,
62-65.[26JR.M. Karp (1972) Reducibility among Combinatorial Problem. In: R.E. Miller & J. W. Thatcher(Eds.) Complexity of Computer
Computations, Plenum Press, New Y ork, 85 -103.
[27J 木瀬洋 (1980) 機械スケジューリング問題の近似解 法，本誌 25 ， 765-771.
[28J H.Kise, et a.l(1982)An Efficient Algorithm for a Chance-Constrained Scheduling Problem. JORSJ 25,193-203.
[29J H. Kise & T. Ibaraki (1983) On Balut's Algorithm and NP-Completeness for a Chanceｭ Constrained Scheduling Problem. Management Sci.29
,
384-388.[30J T. Labetoulle, et al.(1979) Preemptive Scheduling of Uniform Machines Subject to Release Dates. Technical Rep. Mathematisch
Centrum, Amsterdam.
[31J E. L. Lawler (1978) Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints. Ann. Discrete Math. 2,75-90.
Stochastic Scheduling Complexity of Stochastic Scheduling Problems: in [IIJ, 355-365.
[40J M. Pinedo (1983)
with Release Dates and Due Dates. ORSA 31
,
[32J E. L. Lawler & J. Labetoulle (1978) On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming. JACM 25
,
612-619.
559-572. On Johnson's
P. S. Ku & S.C. Niu (1986) [33J
Scheduling Jobs with Exponentially Distributed Processing Times on Two Machines with Resource Constraints.
M. Pinedo (1984) [41J
Two.Machine Flow Shop with Random Pro
-Management Sci. 30,883-889.
[42J M.H. Rothkopf (1966) Scheduling Indepen・
dent Tasks on Parallel Processors. Management cessing Times. ORSA 34,130-136.
[34J J. M. Moore(1968) An n Job, One Machine Sequencing Algorithm for Minimizing the Numｭ ber of Late Jobs. Management Sci. 13
,
102-109.M. Pinedo (1979) Scheduling of Stochastic
Sci. 12
,
437-447.[43J M. H. Rothkopf (1966) Scheduling with Random Service Times. Management Sci. 12
,
707-713.
[44JR. R. Weber (1982) Scheduling Jobs with Stochastic Processing Requirements on Parallel Machines to Minimize Makespan or Flow Time. J. Appl.Probab.
,
19,
167-182.[45J G. Weiss (1980) Scheduling Tasks with Exponential Service Times on Non.ldentical Processors to Minimize Various Cost Functions. [35J
Tasks on Two Parallel Processors. Naval Res. Logist. Ouart. 26
,
527-535.[36J M. Pinedo (1980) Scheduling Spares with Exponential Lifetimes in a Two-Component Parallel System. J.Appl.Probab. 17, 1025-1032. [37J M. Pinedo (1981) A Note on the Two
Machine Job Shop with Exponential Processing Times. Naval Res. Logist. Quart. 28
,
693-696.[38J M. Pinedo (1982) Minimizing the Expected Makespan in Stochatic Flow Shops. ORSA 30
,
148-162.
J. Appl.Probab. 17, 187-202.
B6
通産資料調査会
THE JOHNS Traffic Processes in Queueing Ralph L. Disney HOPKINS
$54.45 '87.9.29 A6 Networks
Pe士er C. Kiessler UNIVERITY A Markov Renewal Approach PRESS
オベレーションズ・リサーチ入門 6H.M. ワグナ著森村英典，伊理正夫監 培風館 225P ￥ 3， 000 61.10.30 B6 訳平本巌，反町泊子， 待ち行列 前島信共訳 新 SL動A向~のシミュレーション言語
