<論文>装置産業のスケジューリング問題とそのモデル化 利用統計を見る

<論文>装置産業のスケジューリング問題とそのモデ

ル化

著者

今泉 淳

著者別名

Imaizumi Jun

雑誌名

経営論集

巻

49

ページ

147-168

発行年

1999-03-31

URL

http://id.nii.ac.jp/1060/00005596/

Creative Commons : 表示 - 非営利 - 改変禁止 http://creativecommons.org/licenses/by-nc-nd/3.0/deed.ja

経 営 論 集 第49 号 （1999 年3 月 ）

装置 産業 のス ケジ ューリング問題 とそ のモデル化

今 泉 淳 1 日的2 装 置産業 の 生産 システ ムの特徴 と スヶ ジ ュ ーリ ング3 本稿 が対 象と する 生産シ ステ ムの概 要3.1 シス テ ムの概 要3.2 評価尺 度3.3 本シス テ ムに対 する解 法の概 要4 抽象モデ ルの構築4.1 過去 の研究 モデル につい て4.2 本質 的に欠 かす ことの できな い要 因4.3 省略を 考慮す べ き要因4.4 日的関数 につ いて5 問題 の定義6 評価尺 度を 総所 要問題 とし た場合 の解 法の 概要6.1 分枝限定 法を 適用 す る上 で のポ イント6.2 本アプ ロ ーチ が着目す るス ケジ ュ ール の ダラ ス6.3 割り付け対 象とな る作業 と機 械の 選択6.4 下界 の計 算法6.4.1 下界l −ジa ブに基 づく下 界6.4.2 下界2 − 第2 工 程の 機械 に基づ く下 界6.5 数値実 験の結 果の概 要7 評価尺 度を総納 期遅 れとし た場 合の 解法 の概 要7.1 記号 の定 義7.2 定式化7.3 緩和の考え 方7.3.1 原問題 の特 徴7.3.2 機械 の能力を 緩和し た場 合の 子問 題と 解 の性質7.3.3 実 行可能 解 の生成方 法に 関し て考 慮す べ き点7.3.4 第1 、第2 両 工程 の緩和7.3.5 第2 工程 の みの緩和7.4 ラグ ランジ ュ緩和 問題7.5 子問題 の特徴7.6 実 行可能 ス ケジ ュールを得 るた め の手 順7.7 数 値実験 の結果 の概要8 両モデル の長所 と短所 に関す る考 察8.1 総所 要時間 最小化 モデ ル8.0 総納 期遅 れ最小化 モデ ル9 モ デルの拡 張の方 向性9.1 尺度 の複数化9.2 問題細 部の条 件を原 問題 のそ れに近 づけ る9.2.1 ジ ョブ の候 補機 械9.2.2 機 械の能力 差10 お わ りに 147

148 経 営 論 集 第49 号 （1999 年3 月 ） 1 日 的 オペ レ ーショ ソ ズ ・リ サ ーチにおけ る スケジ ュ ー リン グ研 究は 、 抽象的 な 理 論 モデル に対 する も のから 、現 実 に あ る生産 シス テ ムに対 す る もの まで 幅広 く存 在す る。多 く の研 究は、 組 合せ 問題 的 視点 か ら の モデ ル化 を 前提 にし た最 適化を 指 向し てい るが、 そ れ ら の中 の理論 的 モデ ル、 具 体的 に は フロ ーシ ョ ップ ス ケジ ュ ーリン グ問題や ジ ョブ シ ョ ップ ス ケジ ュー リン グ問 題 は、 ジ ョブ 群の 技 術的 加工 順 序や 加 工 時 間が与 えら れ たと きに 各機 械上 で の作 業 の順 序づ けを 行 う単 一 の評 価尺 度 の 問題 であ り、加 工 や 組 み立 て中心 の 機械工 業を 想定 し た モデ ル であ る。 し かし 、現 実 のシ ョ ップ が これら 理 論 モデ ル の よ うな単 純な 条件を 満 た すこ とは 稀 であ る。 一方 、 装置 産 業 の生 産 シ ステ ムの ように、 工 程 間の 重 複生産 が許 さ れた り、 ジ ョブ が 下流 工 程で 異な るジ ョブ に 分岐 す る とい う、 機械工 業に は無 い 特 徴を 持つ 生 産 シ ステ ムに対 す る理 論的 研究 は、 ほ と んどな さ れ てい ない のが現 状 である。 本 稿 では 、 装置 産業 の具 体的 事例 であ る、 ジ ョブ が 分岐し 複 数 の 尺 度 を 持つ2 工 程 並 列 機 械 フ ロ ーシ ョ ップ 生産 計 画問 題[23]を取 り上げ 、 この問 題 の抽 象 的 モデ ル化 に 関す る議 論を 行い 、 同 時 に そ れら モデ ルに 対 す る解 法 の方 向性を 提案 し、 こ れら か ら装 置 産業 を 想定 した 抽 象 モデル の研 究 の 可能 性を示 唆 する。 2 装 置 産 業 の 生 産 シ ス テ ムの 特 徴 と ス ケ ジ ュ ー リ ン グ 装置産 業 の 生産 の一 つ の特徴 とし て、 製 造プ ロ セ スが 複数 の 大規 模設 備 の集合 体 であ る点 が 挙げ ら れる。 す な わち 、 各 工程 は バ ッチ あ るい は連 続的 な 設備 の 結 合で あ り、操 業上 の条 件や 設 備 の使 用条 件、 製 品 の加 工条 件 が 生産 計画や スヶ ジ ュ ーリン グに おけ る制約 とな る。 も う一つ の特 徴 とし て、比 較 的少 ない 種類 の素 材 から 様 々 な製 品を 作 る とい う側面 が 挙げ られ る。 すな わち、 素材 や原 料 の段階 か ら、工 程を 経 るに し たが っ て様 々な中 間 品と な り、最終 的 に は多 く の種類 の完 成 品 と な る( 分 解型 生産 、あ るいは ブ レイ クダ ウン型 生産)。同 一 の中 間品 から 加工 さ れ る下流 工程 の中 間品 や 最終 製 品は 、可 能な 限 りそ の原 料 とな る上流 工 程 の中 間品を 同一 条 件で 加工 を す るこ とが 生産 上 有利 な の で、 この こ とが理 由 で加 工 がバ ッチ処 理 さ れる点 も大 き な特 徴で ある。 こ の ような 特徴 を 持つ 生産 シ ステ ムの一 例 とし て、 鉄鋼 生 産 シ ステ ム「261が挙げ ら れ る。 鉄 鋼 の 生 産 シス テ ムぱ、 この ような条 件 を備 えて い る とと もに、 物 流 の ため の設 備 も必 要と な る、 巨大 シス テ ムであ る。 鉄 鋼業 に対 す る ス ケ ジ ューリ ン グアプ ロ ーチは 、中 川eta げ≫iに も見ら れ る よ うに、評 価尺 度が 複 数で、変 数や 制 約条 件 が 膨大 な数 の数 理 計画 問題 と して 扱 わ れ、 大規 模 問題 に対 す る高速 近似 解 法 の提案 が主 とな って い る。

装 置産業 のスケジ ューリング問題とそ のモデ ル化 149 一 方 で、 機械 工業 を 前 提 にし た フ ロ ―ショ ップや ジ ョブ ショ ヅプ の よ うな 抽象 モデ ルに 対応 する、 装 置 産業 を対 象 に した 理 論 モデ ルは 存 在し ない のが現 状 であ る と考 えら れ る。 こ れは 、装 置産業 と い っ て も、製 造 す る対 象 に よって 微妙 に シ ステ ムや前 提条 件が 異 る がゆ え に、 抽 象 化を す るにし て も、そ れが どの よ うな シ ス テ ムを も 包括 する ような一般 モデル に はな りに くか っ た とい う事 情があ る も のと考 え ら れる。 犬 し か し、 装 置産 業一 般 の特徴 と して、 上 記 の ように バ ッチ 生産 、 分 解型 生産 な ど の要 素があ り、 こ の よ うな要 因を もっ た モ デルや 最 適化 問題 とし て の難し さ、 あ るい は 解 法 の開 発 は、 個 々 の具体 的 シ ステ ムの問題 解 決 に対 す る基 礎的 な 位置づ け とし て必 要 であ る と考 え る。 3 本 稿 が 対 象 と す る 生 産 シ ス テ ム の 概 要 本 節 では 、具 体的 事 例 で あ る装置 産業 の 生産 シス テ ムの生 産計 画 問題[23]と そ れに 対 す る具 体 的 ア プ ロ ーチ を 説 明す る。 3.1 シ ス テ ムの概 要2 工 程 の直 列型並 列機 械 生産 工程（ ハイブ リ ッド フ ロ ーショ ップ 勺 であ り、第1:L 程に は 能力 の 異な る機 械 が、 第2 工 程 に は能 力 の等し い 機械 が、 そ れぞ れ並列 に 存 在す る が、 そ の他に 以下 の よ うな 特徴 があ る。 _つ ス キップブ ロ ーシ ョ ップ 全 ての ジョ ブが 第1:E 程 で加 工を 受け るが 、一 部 ジョ ブ は第1:E 程の み で加 工 が終了 す る（ 図1 ）。 一部 ジa ブ が 、 特 定 の工 程 で の 加 工 を 無 し に 通 過 す る フp ― シ ョ ップを ス キ ップ フ ロ ―シ ョ ップ（skipflowshop ） と呼 ぶ吼 ジョ ブ の 分岐 第2 工 程に 進 む ジョブ は、 一 般に 複数 の ジ ョ ブ に 分 岐 し 、 分 岐 前 の 第1 二［ 程 の ジ ョブを 親ジ ョブ 、 分岐 後 の第2 工 程 のジ ョブを 子 ジョブ と呼 ぶ。 一つ の親 ジ ョブ に対 応 して

□

□

ら

□ 二

￣ ニ

□

□

し…。J:

。

…。I

図 に システ ムの概 要

150 経 営 論 集 第49 号(1999 年3 月 ） 子 ジ ョブ 群 が一 意 に定 ま り、 異 なる 親ジ3 ブを 共 有す る 子 ジa ブは 存 在 し ない。 こ れが、 分 解 型 生産 に 相 当 する 部 分 であ る。 生 産 要求 量 計 画期 間（ 通 常 レ す る ジa ブ に 対 す る要 求 量が 与え ら れる。 こ れらか ら 親 ジ ョブ の要 求 量 が定 ま る。 ジョブ の行 き 先 候補 機械 親 ジa ブ 、子 ジ ョブ とも、 加工 が可 能 な候 補 機械 が所 与 であ る。 そ の うち のど の 機械 で ど れだけ の量を 加工 す るかは 、 自由 に決 め ら れる。 加工 を 複数 台 の機械に 振 り分け た り、 あ る 機械 上 で の加工を 途中 で中 断 す るこ と も許 さ れる。 レ 中 間 在庫 第1:E 程 と第2 工 程 の 間には 親 ジョブ毎 に 専 用 の中 間 在庫 置 場が あ りご、一 定 量以 上 の 在 庫 の保 有 は望 まし くな い。 上 下工 程 の重 複生 産 第1: 工l程 の加工 と第2 工 程 の加 工 は重 複 し て よい 。 す な わち 、親 ジョブ の 加工 が完 全 に 終 わ って い な くて も、 終了 し た 「部分」 があ れ ば、 子 ジ ョブ の加工を 開始 で きる。 段 取 り 第1: エミ程 では 親 ジa ブ毎 に、 第2 工 程で は子 ジ ョ ブ 毎 に 工 具を 必 要 と し 、 相 前後 す る ジ ョブ の間 で 使用 す る 工 具が 異な る場 合に は段取 りを 必要 と す る。 3.2 評 価 尺 度 所与 の生産 要 求 に対 す る 計 画期 間 内の日単 位 の計 画 の立案 を 行い 、 以下 の点 から 評 価を する。O 需 要の 満 足 度 各 ジ ョブ （親 あ るいは 子 ジョブ ） の要 求 量 に対 す る計 画 期間 内に おけ る実 際 の生産 量 の 割 合（ ％ ） の ジョブ に関 する 平均100 ％ に近 い こ と が望 まし い 。 功 段取 り回 数 第1 、 第2 両工 程で 行っ た段 取 り回 数。 小 さい こ と が望 ま しい。iii ） 中 間在 庫 量 所 与 の上 限 （第1 工 程の 各 ジョブ の、 標 準 の能 力を 持 つ 機 械に おけ る生 産量3 口分）を 超 え た在 庫 量 （超 過在 庫量）。 各ジ ョブ毎 の毎 日 の超 過 在庫 量 が小 さ い こ と が望 ましl^ 3.3 本 シ ステ ムに対 する 解 法の 概要 本 問題 で は 、 第1 、 第2 の両工 程 が並 列な 代替 機械 から な る た めに 各機 械 で の各 ジ ョブ の加工 量 を 決定し た 上 で順 序 づけ を 行 う必 要 があ る、 複数 の評 価尺 度を 有す る 問題 で あ る。 また、 問 題の 規 模（変 数 や制 約式 の数） か ら 考え て も、直 接的 に 解く こ とは難 し く、 問題 全 体を 一つ の問題に定 式 化 し て解 くに は大 きす ぎ る。そ こ で、 な んら か の分割を 施 す。 問題 の 分割 で は、 分 割さ れた 各問題 （部 分問 題） の決定 項 目 と評 価尺 度 の組 み合 わせ方 が 大 きな ポ イ ント とな る。 本 問題 の決 定 項 目 は、 ●ど の機械 で どれだ け の量を 加 工す るか

装 置産業 のスケ ジューリン グ問題 とそのモデ ル化 151 ●どの よ うな順序 で加 工 する か ●第1 工 程 ・第2 工 程 の どちら に 関 して か に分 類 す るこ とが で きる。 第1 工 程 から 第2 工程 に も のが流 れ るため 、 決定 項 目間 に依 存関 係 があ ると見 る のが 自然 とは い え、 独立 と見 なす 考え 方 もあ り得 る。 一 方 、［解 法 の都合 ］ と「評 価尺 度 の精 度に 対す る要請 」は 必 ずし も一 致 し ない ので 、そ の バラン スを 考慮 す る こと も重 要 であ る。 以 上 の視点 を踏 まえ た上 で 、評 価尺 度 の精 度 の 劣 化 が少 ない 分割 や決 定項 目の固 定方 法 、 部 分問題 間 の情 報 の授受 を考 え たい。 そ こで 今 泉etal.'^^'では 、 ●第1 工 程 と第2 工 程 が 独立で あ る との 仮定 の下 で、 各 ジョブ の 各候 補 機械 に おけ る仮 の加 工量 を 決定 す る機械 割 り当 て ・バ ッチ サイズ 決定 問 題（数 理 計画 問題 とし て の定 式 化に 基づO ●仮 の加工 量 に基 づ き、 第1 二［ 程 に対 す る手順 と 第2 工 程 に対 す る手 順を 反復 す る順 序づ け問題 に 分 解 し階層 化 す る アプ ロ ―チを 採 用し た。 問 題 の分 割に 伴い 、 各 評 価尺度 を ど の部 分問題 で 扱 うかを 定め る 必要 が あ るが 、 基本 的に 段取 り 回数 を バ ッチ サイ ズ決 定 問題 で、 在 庫量 を順 序づけ 問題 で扱 い、 需要 の満足 度 は バ ッチ サイ ズ決定 問題 と順 序づ け 問題 の 両 方お いて 考慮 し てい る。 4 抽 象 モ デ ル の 構 築 分 割 アプp ―チに よっ て本 シ ステ ムのス ケジ ュ ールを 生成 す る方 法 を 、 今 泉etal 戸 が 議 論を し た。 こ の ような シ ステ ムに 対 する ス ケジ ュ ーリン グ問題 では 、多 く の要 因 が 複雑 に 絡 み合い 、そ の 本質 的 な難し さを 見 え に く くして い る。 そ こで 本節 で は、抽 象 モデ ル の構 築を 前 提 に、 本 シ ステ ム の要 因 の中 で、 難し さを 構成 す る要 因 とし て本質 的 でない ものや 、 解 く上 で要 因 と し て扱い に くい と考 えら れ る部 分が 何 であ るかを 議 論す る。 4 。1 過去 の研 究 モデ ル に つい て 本 シ ステ ムの特 徴 に 関し て 、既 存 の理 論 モデ ルと の関 連を 説 明す る。 並 列 機械フ ロ ーシ ョ ップ 一 般 に ハイ ブ リ ッドフ ロ ーシ ョ ップ と 呼ぼ れ、 様 々 な モデル があ る。 一 例 とし てBrahandHunsucke 岬やRajendranandChaudhur 呻 は、標 準的 フ ロ ーショ ップ 問題 の 複数機 械 の拡 張 に近 く、GuptaandTun ♂ やGuptaandTun ♂ は、特 殊形 や 変形 モデ ルと位 置付け るこ とが で き る。 段 取 り ジョブ の順 序 依存 の段 取 り時 間を 伴 う もの が典型 例 で、1 機 械 総所 要 時 間 最小化 の場合 は巡 回 セ ール スマ ン問 題 に帰 着 す るWに とな どが 良 く知 ら れ てい る。Gupta 慨ま順序 依存 の段取 り時 間を 伴 うフ ロ ーシ ョ ップ 問 題 であ り、 こ れら以 外に も段取 りコ スト な ど の最 小化を 目的に

152 経 営 論 集 第49 号 （1999 年3 月 ） し た 問題 が存 在 す る。 複数 の評 価尺 度 ほ とん ど の研 究が1 機械 問 題に 集中 し、 評 価 尺度 もジa ブ の終了 時刻 関 連尺度 が多 い。 フ ロ ーシ ョ ップを 対 象 とした よ うな研 究は さら に 少 な く、 シ ョ ップ形 態 にか か わらず 、 在 庫量 や段 取 り回数を 評価 尺度 に含 む研 究 は無い と言 って 良い 吼 重 複 生産 ロ ットを 更 に小 さ く 分割し 、工 程 間 の重 複 生産を 許 すこ とに よっ て終了 時刻 関連尺 度 の 改善を 企 図 するlotstreaming'"と 関連 する が、 本問 題に お い ては むし ろ 中 間 在庫 量 の 関 係 か ら、 積 極的 に重 複 生産 を 行 う必 要があ る部 分に違 い があ る。 ジョ ブ の 分岐 第1:E 程 のジ ョブ の完了 を 待 って 第2 工 程 が 開始 さ れる の で あ れば ジョブ が分 岐 して も問題 を 生 じ ない が 、重 複 生産 が許 さ れた ときに 第2 工 程 ジ ョブ 同士 の競 合 の問題 が生 じ る。 こ のよ うな 状況 を 扱 っ た研 究は存 在 しない 。 こ れら全 部 の要 因を 同 時 に取 り込 んだ現 実 の問題 の モデ ル は筆 者 の知 る 限 り存 在し ない が、 こ れ ら の要 因そ れぞ れは必 ず し も特 殊 な もので は なく、 い くつ かを 持 つ よ うな 現実 の問題 が少 なか らず 存 在す る と考え ら れ る。 4.2 本質的 に 欠 か すこ と の でき ない 要因 本 シ ステ ムに おい て 、 不 可欠 と考 えら れ る のは以下 の要因 で あ る と考え る。 ジ ョブ の 分岐 ジ ョブ の 分岐 は、 装 置産業 の生産 シ ステ ム の一つ の特徴 で あ りへ 従来 の モ デ ル には 考慮 さ れ てい な か った 要因 であ る。 重 複生産lotstreaming と類 似 す る面 もあ るが、 ジョブ の分 岐が 起 こる た め 中間 在 庫の 奪い合い が生 じる の で、 単純 に 同 一 視す るこ とは で きない 。 並 列機械 各段 が 単一 機 械 で 構成 さ れてい る場 合は こ の よ うな問 題 が起 こら ない の みなら ず、装 置産業 でし ば し ば見 ら れ る ショ ップ形 態 であ るこ とか ら考 え て も、 単 一 機 械で モデ ル化 する こ とは、 本質 の大 きな 部 分を 失 うことに な る。 こ れら の3 つ の要 因が 同 時に 存 在す る こと が問題 の難し くし てい る と考 えら れ、 こ れら のうち の1 つ が無 い ような 問題 は 、 組 合せ 最適 化問 題 とし て の成 立 す る とし て も、3 つ を 同時 に含 む 問題に 比 べて 格段に や さ し くな る。 4 。3 省 略 を考 慮 す べき 要 因 当 面は 省略 を考 慮 す べ き要 因 は、 以下 の よ うな もの が挙げ ら れ る。 評 価尺度 の 取 り扱 い 理 論 スケ ジ ュ ーリン グにお い ては、 多 くの評 価 尺度 が ジ ョブ の終了 時刻 関 連尺度 に 集中 し て お り、一 部 の研究 で段 取 り回 数な どが 対 象 とな っ てい る。 複数尺 度 の問題 と

装置産 業の スケジ ューリング問題とそ のモデ ル化 153 し て モデ ル化 す るか ど う かは と もか く、超 過 在庫量 の よ うな尺 度を 対 象 とす る研 究 はほ ぼ皆 無 で あ り、 解法 の構 築 す る上 でモ デ ルが好 ま しい数 学 的構 造を 有 す るか ど うか ぱ自 明 では ない。 ジ ョブ の 候 補機械 ハ イブ リッド フ ロ ―ショ ップ の研 究で は、 並列 に 並 ぶ全 機 械 で 全 ジョブ を処 理 可 能 であ る こと がほ とんど で あ る。 そ れに 対し て本 問題 で は、 段取 りや ジ ョブ の中 断 可能条 件 、 あ るい は ジa ブ を 複 数の 機械 に 跨ぐ ように割 り付け るこ と も可能 で あ り 、 加工 機械 そ のも のを 決定変 数と す るこ と は一 つ の問題 の 定義 とし て成 立す る が、多 目的 問題 と の 両立や 次項 の ジ ョブ の中 断条 件 と の 両立は 、 問題 の複雑 さ の観点 から 難 しい と考 え る。 ジ ョブ の中 断 可能 条 件 同 一機 械 上 で ジョブ 分割 （他 の ジa ブ の割 り込 み） を 許 し た り、 複数の 機械 に 跨 るこ とを許 す よ うな ハ イブ リッド フ ロ ーショ ップ の過去 の 研究 は 皆 無 で あ り、森戸etal 尹 の ような 扱い に よって定 式 化を 行 うこと も考え ら れる が、変 数 の 数な どか ら み て現 実的 で ぱ な い。 多 目的 性 多 目的 問 題 はそ れだけ で通 常 の 問題以 上 の難 しさ を有 す る と考 え て よい 。多 目的 スケ ジ ュ ーリ ン グ問題 に対 す る圧 倒 的多 数 の理 論研 究 が1 機 械 問題に 集 中 し てい る［22］こ と か ら 考え て、 本稿 が扱 う よ うな 複雑な 問題 を多 目的 問題 とし て扱 うこと は、 前述 の よ うに 問題 に 構造的 な意 味 で の利点 が 無い 限 り、 効 率的 ス ケ ジュ ールを 求め る ような アプ ロ ーチ は 容 易に は 構築で きた い と考え る。 した が って、 単 一尺 度 の問題 の特性 を 明ら かに し た後 に アプ ロ ーチす べきで あ る。 第1 工程 で終 了 する ジ ョブ 第2 工 程 の加工 時 間をO と扱え ば良 い の で、 仝 ジ ョブ が両工 程を通 過 する と仮 定し て も一 般 性 を失 わ ない。 4 ．4 日的 関数 につ い て 需要 の満 足 度 が本 シ ス テ ムにおけ る主 た る 目的 関 数で ある こ とは 言 うま で もな い が 、 目的 関数の 一般 性 とい う観点 から は 、 本 シ ステ ムに 依存 した 尺度 であ る 面 も否定 で きな い。 そ こ で、 本 アプ ロ ―チ では ス ケジ ュ ーリ ング問 題 の代表 的 な評 価尺 度 であ り、終 了 時 刻 関連 の尺 度 の一つ で ある 総所 要 時 間 で代 替を す る。 そ の理 由 として 、 ●総所 要時 間 は設 備 の稼 働率 に概 ね 相当 す ると みな すこ と がで きる ●設備 が有 効に 利 用 さ れた と きに 需要 の満足 度 が良い 値 を とる と直 観的 に推 測 さ れる な ど の点 が挙げ ら れ る。 さらに 、 従来 のフ ロ ―シ ョ ップ 問題 や ジ ョブ ショ ップ 問題 が、 総 所要 時 間最 小 化 を 中 心に 研究 が な され てい る現 状を 踏 まえ、 こ れら 問 題 に対 して 提案 さ れ てい る考 え方を 利 用 す る 可 能性 を 考慮し た り、 こ のよ うな尺 度を 目的 関 数に し た 場合 の問 題 の難 し さを 実 験的 に 分析 す る 意 図 もあ る。

154 経 営 論 集 第49 号 （1999 年3 月 ） もう一つ の考 え とし て、 個 々の ジa ブ に納 期 が与え ら れる ような 状 況で の総 納期 遅 れを尺 度 の候 補 とす るこ とを 考え る。 こ れは 、本 来 の問題 力特 ケ月 単位 で の 生産 計 画を 考 え てお り特に納 期 が与 えら れて い るわけ では な い とは いえ 、納 期 が与 えら れて い る ような 問題 で も求 解 か可 能な らば、 シ ステ ムの運用 方 法や 生 産 計 画 の方法 に一 つ の選択 肢を 与 え る可 能性 が あ る。 また、 昨 今脚 光を浴 び てい る ラグ ラン ジ ュ緩 和 を 用い た解 法[12]叫jを 適 用す る方 向性 もあ る。 そ こで 、 上 記 の議 論 を 踏 ま え た抽 象 モデ ルの 定 義、 及 び そ れに対 す る アプ ロ ーチを 以 下に 例 示す る。 5 問題の定義 上 記 の議論 か ら 構築 さ れ る 問題 （ モデル） を 説 明す る。 な お 、総 所 要時 間最 小 化問 題を6 節 で、 総納 期遅 れ最 小 化 問題 を7 節 で説 明す る が、 本 節で は、 両問 題 の 共通 部 分 の定 義 を示 す。1. 第1 、 第2 工 程 がそ れぞ れ び 台、D 台 の並 列機 械か らな る2 工程 の フ ロ ーショ ップで あ る。2. 第1 工 程 で作 業 を 終了 し た ジ ョブは 逐次 連続 的に 中 間品 と して 溜 り、 そ れを 使っ て第2 工程 の作業 を 開 始 す る こと が で きる。 すな わち 、同一 ジ ョ。ブ の第1 二［ 程 の作 業 と第2 工 程の作業 が 時 間軸上 で 重 な って 加 工 さ れる こと（ 重 複生産 、overlappingproduction) を 許 す。3. 各ジ3 ブ は 第2 工 程 で 複数 の作業 に 分岐 す る。 これ ら作 業 は同 一 種類 の中 間品 を 共有す る。 第1 工 程 の作業 を 親 作 業、 第2 工 程 の作業 を子 作業 と称 し 、 同一 の親 作業 を 共 有す る子作 業同 士を 兄弟 作 業 と 呼ぶ。4. 各作業 は、加 工 さ れ る機 械 と加工 時 間（ 日単 位）、中 間 品に 換 算 した 量 が 所与 であ る。分岐し た第2 工 程 の作 業 は 必 ず 異な る 機械上 で 加工 され る。 第1 二［ 程 であ る 日に 加工を 終 えた中 間品 （ の部 分） は 、 次 の日 以 降に 第2 工程 で利 用 可能 とな る。 あ る ジ ョブ の 第1:E 程 の1 日間に 加 工 され る量 は 、そ の ジ ョブ 全 体 の加工 時 間 と中間 品 の換 算量 か ら計 算 で き る。5. 作 業 の中 断 は許 され な い。6. 原 材 料は 常 に利 用 可 能 であ る。 この とき、 所 与 の 評価 尺 度を 最 適に す る よ うな 各作 業 の開 始時 刻 （ 開始 日） を決 定 する。 なお、 時間 軸 は第1 日か ら 開始 し 、 日単 位 で ス ケジュ ールを 考え る。 し また、 以下 の よ うな記 号 を 定義 す る。 訂“ 第1:E 程 の機 械 の 集 合 二 舒゛ 第2 工 程 の機 械 の 集合 ． 1 親 作 業f a,i ） 親作 業f の 子作 業j

装置 産業 のスケ ジュ ーリン グ問題 とその モデル化 155 6 評 価 尺 度 を 総 所 要 時 間 と し た 場 合 の 解 法 の 概 要 評価 尺度 を 総所要 時 間 とす る理 論的 ス ケジ ュ ーリン グ研究 は膨 大な 数に のぼ り、 理論 モデ ルとし て は極 めて 一般的 な 評価 尺 度で あ る。 ま た 解法構 築上 、比 較的 扱い が 容易 で 下 界 値 の計 算 も考え や すい。 こ の よ うな 観点 から 、 分枝 限定 法を 解法 の枠 組 とし て選 択す る のは一 つ の 自然 な 流 れでもあ り、 総 所要 時 間が 必ず し もシ ョ ップ一 般 の評価 尺度 では無 い とい う指摘を 考 慮 し て も、 そ の適 用 の 可能 性を 探 るこ とは 意義 が ある と考 え る。 なお 、1 日目か ら数 え て2 日間を 要 し て 全て の ジョブ の加 工 が終 わっ た場 合 、 ヱ＋1 日 の頭 （ ＝X 日の終 り） に 全て の ジ ョブ の加工 が 終 わる と定 義す る。 6.1 分枝 限定 法を 適用 する上 で のポ イ ン ト 組合 せ的 性質 を 有す る 問題 に対 し て 分枝 限定 法を 適用 す るこ とは、 自然 な流 れ の一 つ であ り、そ こで は ●ど のよ うに 分枝を 行 うか ・ 下 界値 の 計算方 法 ・ 分枝 戦略 な ど が議 論 の対 象とな る。 ま た、本 問題 固有 の特 徴 と して、「あ る子作 業 の 開始 を 最 早で 行 うこ とが、当 該 ジ ョブに とって 相 応 し いか ど うか の保 証が ない 」 とい う性 質 があ る。 すな わち 評価 尺度 が な んで あ っ て も、 従来 のフ ロ ーショ ップ や ジョブ シ ョ ップ では 、 技術 的 加工 順序 の 観点 から みれ ば同 一 ジa ブ 内 の各 作業 は早 く終了 さ せる こと が後 続す る 作業 の 開始 を 早 め、 最終的 に そ のジ ョブ の最終 作 業を 早 く終 える結果 に な る。 しか し 本問 題 では 、あ る 子作 業を 早 く終 え よ うと する と、同 一 ジ_{ョブ 内 の 別 の兄 弟 作業 の} 在 庫を 食 い潰 す結 果に な りか ねず、 別 の兄 弟作 業 の 開始 が遅 くなる 可 能性 もあ る。 こ の よ うな 観点 から 考え る と、 ス ケ ジ ュ ール全 体で 見た 場合 、子 作業 は 必 ずし も最 早 開始 日 で開 始 す るこ と が良い か は 分か ら ず、兄 弟 作業 の開始 を 遅ら せ るこ とで 良い ス ケ ジ ュ ールに なる 可能性 もあ る 。 しか し、 各機 械 で 各作業 の着手 順 序 の みなら ず、 兄 弟 ジョブ の関 係を 考え なが ら 各作業 の 開始 日を 決定 す る のは 、 全 ス ケ ジ ュ ール の列 挙 の メ カ ニ ズ ムが 複雑 に な り 、 か つ 列 挙 す る_{ス ケ} ジ ュ ール の数 が 膨大に な る な ど の問題 が 発生 し 得 る。 6.2 本 アプ ロ ーチが 着 目 する ス ケジ ュール の クラ ス ス ケ ジ ュール の生成 に お い ては 、1 日目か ら始 め て ガソ トチ ャ ートを 順 次左 か ら 埋 め る よ 引こ作 業 を 割 り付け てゆ く アプ ロ ーチを 採 用 す る。そ の際 に 、部 分 ス ケジ ュ ール が 与え ら れたら 、「そ れに

156 経 営 論 集 第49 号 （1999 年3 月 ） 対 し てあ る作業 を 割 り付 け る場 合 は 、最 早開始 日に開 始す る」 とい う ス ケジ ュ ール に のみ 着 目し 、 作 業 の開始 を 意図 的に 遅 ら せ るこ と は考 えな い。 親作 業 や他 の兄 弟作 業 の開始 日が 分か れば 、中 間品 在 庫がい つ 、 どれ だけ 利 用可 能 かが 分か るこ とから 、あ る部分 ス ケジ ュ ールが 与 えら れた と きの子 作業 の最 早 開始 日 は、 当 該子 作業 の中 間品 の 払 い 出し 量 と加工 日数 か ら 一 意に 計 算で きる。 6.3 割 り付 け対 象 と な る作 業と 機 械の 選択 親作業 が開始 し てか ら あ る特 定 の 日数 が経 過し たら 、少 な く とも 継続 す る子 作 業 の うち特定 の一 つ が着 手可 能 とな る（ 問 題 のデ ータ からあ ら かじ め計 算 でき る）。 そ の作 業 が 着 手 で き る 最 も 早い 時刻 に 着 目す るこ と で、 少 な くと も 当該作 業 が最 早に 開始 す るス ケジ ュ ールを 保 証 で きる。 そこ で 分枝 限定 法 の分枝 の対 象 を 、 ●第1:r 程で は 、後 続 す る手 作業 の着手 可 能 日が最 早に な る よ うな 親 作業 や 機 械 とす る ●第2 工 程で は、 最 早 終了 日C 最 早開始 日に加工 を 開始 し た場 合 の終了 日） の最 も小 さい作 業や 機械 とする とい っ た工 夫を 施 す。 6.4 下 界の 計算 法 以 下に 説 明す る2 つ の 下 界(Lfi, 、LB2） と、第1 工 程 の各機 械 そ れぞ れ の加 工 時 間 の和から 得ら れ る終了 日の最 大値 に1 を 加え た 乙乱 の最 大値 、LB ＝max{LBi 、LB^ ，LB,}を 総 所要 時 間 の下 界値 とし て、 分 枝限 定 法に よっ て ス ケジ ュ ールを 求 め る。 6.4.1 下 界l − ジa ブ に 基づ く下 界 部 分 ス ケジ ュ ール 心こ対 し て 、 第1 工程 の各 機械 の未割 り付け の ジ ョブ そ れ ぞ れに 関 して、 ●そ のジ ョブ の親 作業 は当 該 機械 上 の順 番 の最後 に 加工 さ れる とし 、 ●そ のジ ョブ の子 作業 は、 そ れぞ れが行 わ れる 機械 上で 、 そ の 子 作 業 以 外 の 作 業 が 現 部 分 ス ケ ジ ュ ール 心こ対 し て 機械 遊 休無 し で行 わ れる とい う前 提 で、 当該 ジ ョブ の子作 業 の最早 開始 日を 計 算す る。 こ の最 早 開始 日に し た がっ て 割 り 付け たと きの終 了 日は 、そ の 作業 の他 の未 割 り付げ の兄弟 作業 が無い （ 存 在を無 視 す る） とい う前 提 下 での終了 日 とみな すこ と が で きる。 こ れを 全 て の兄弟 作業 に つい て計 算 し、 そ れら 終 了 日 の最 大 の もの が、あ る 親 ジョブ を そ の機 械 の最 後 に 加工 した とき の 所 要 日数 の下 界 とな る。 そ こ で、 各 機 械 でこ の所要 日数を 最 も小 さ くな る よ うに 最後 に 加工 する親

装置産業 の スケジ ュ- リン グ問題 とそ のモ デル化 157 ジa ブ を 選び 、第1 工 程 の全 機械 の 中で もっ と も大 きな所要 日数 が、 部 分 ス ケ ジ ュ ールa の下 界に な る。 す な わち、 第1 コニ程 の機 械m^ 診 で 加工 さ れ る 未 割 り付 げ の 親 作 業 集 合 を 尺お⊂ ぷ(の と す る と き、 親 挺 尺乱を当 該 機械 の順 序 の上 で最 後 に 加工 し、 そ の子作 業(i,j)∈S＼a)の 、 未 割 り付 け の兄 弟 が あ って もそ れを 無 視し て 求め た最 早 終了 目を^(ij)とする と、 は 下 界 と な る 。

LBi ニma χminma χ^(>.; ■)m<EM ≒eR ‰(i,j)eS''(a) (1 ） 6.4.2 下 界2 − 第2 工 程 の機械 に基 づ く下 界 部 分 ス ケジ ュ ールa の 第2 工 程 の木 割 り付け 作 業に 対し て、 少 な くと もそ の作 業 を 開始 す る まで どの位 の日数 が 必要か を 計 算する こ と がで き る。 すな わち 、 部分 ス ケジ ュ ール 吋こお い て 、 第2 工 程 の各 機械 の 木割 り付け の子 作業 に対 し て 、 ●親作 業 が 割 り付け 済 なら ば、 直 接最 早 開始 日を 計 算す る ●親作 業 が 木割 り付け な ら ぼ、 現 部分 ス ケジ ュールa の後 に す ぐに続 く よ うに 該 当 す る親 を 割 り 付け た場 合 の子 作業 の最早 開始 日を 計 算す る こ と で、あ る 子 作業 の、 自 分以 外 の木 割 りつ け の兄 弟作業 の存 在を無 視 し た場 合 の 加工 を 開 始 する ま でに 必要 な 日数 が得 ら れ る。 そ の前 提 で、 総所 要 時間を 最 小に す る よ うな 順序 を 第2 工 程 の各 機 械 で決 めた と き の、そ れ ら の最 大値 が総 所 要 時 間の下 界 とな る。 すな わち 、 第2 工 程 の 末割 り付げ の全 作 業 の最 早 開始 日が得 ら れた ら、 第2 工 程 の各 機 械 毎に着 手 可 能時 刻 付 き総所 要 時 間最 小化1 機械 問 題を 解 き、 機械 心 の最 適値を ひ とす る と、 は 下 界 と な る 。 LB2 ＝ma χr ゛nKE 疹 (2) 6.5 数 値実 験 の結 果の 概 要 使 用 した 計 算機 はMMX200MHz のAT 互換 機、 使用 言語はFreeBSD2.2.1 のC 言 語(gcc)であ る。 探 索 の戦 略 は、 深 さ 優先深 索 を 採用 し て い る。 本 問題 に対 す る提 案 す る解 法 は、 概 ね精 度 の良 い 解を 高速 に 生成 でき る。 具 体的 に は 、 ●第1 工 程10機械 、第2 工 程10機 械、ジョブ が60個 、全作 業数 が270個 程度 の 問題 であ っ て も、10秒 程 度 で最 適 解を 生成 で き る場 合 がほ とん どで あ る

158 経 営 論 集 第49 号 （1999 年3 月 ） ●第1 二[程20機 械、第2 工 程20機 械、ジ ョブ が80個、全作 業数 が約320個 の問 題 の 場合 、生成 した 頂 点 数 が100,000個 に な った 時 点で 計算 打ち 切 った場 合、 最 適解 か ら1 な い し2 程 度 大 き い 値 を もつ ス ケジ ュ ールを 生成 で き、そ れ らの値 が 実際に 算 出 され る のは 計 算 開始 から1 分以 内 の 場 合 がほ と んど であ る な ど の結果 を得 た。 7 評 価 尺 度 を 総 納 期 遅 れ と し た 場 合 の 解 法 の 概 要 納 期尺 度 を有 す る ス ケ ジ ュ ーリン グ問題 は 、並 列機 械に 対す るLuhetal."^」や ジ ョブ シ ョップに 対 す るHoitomtetal 戸 の、 ラグ ラン ジ ュ緩 和に よる下 界の導 出 と上 界 の計 算を 繰 り返 す アプ ロ ーチ が あ る。 これ らは、 ラ グ ラン ジ ュ緩 和に よって 、原 問題 を于 問題 に 分解 し 最適 化 し て 下 界値を 計算 し、 同 時に そ の 子問題 の最 適 解 から 作業 の優 先順 位を決 定 し、そ の 優 先 順 位 に し た が っ て リ スト ス ケ ジ ュ ーリン グ町こよっ て 割 り付け を 行い 実行 可能 ス ケ ジュ ールを 生成 し 上 界値 を 得 る丿Luhetal 戸 やHoitomtetal 尹 の方 法 の適 用 では、対象 とす る モデ ル の違 い が あ るた め、i ）ど の よ うな 緩和 を す るか 、ii） どの ように 上 界値を 算 出す るか、 の二点 が 焦点 とな る。 7 。1 記 号の 定義5 節 の定 義に 加 え て， 以下 の よ うな 記号を 定義 す る。 集合 ○ニ 親作 業y の子 作業 の 集合 定数 μ 親作 業f の加工 日数 ＝ ち.i) 親作 業f の子作 業(ij)の加工 日数 尚,j) 親作 業f の子作 業(ij)の納 期 な お 、 m, W り) 変 数 似8(. ・,ノ)lz 亀Su., ・)C ・ じ(i.i)T(i,j) 親作 業f を 加工 す る機 械 親作 業f の子作 業(削)を 加工 する 機械 親作 業f を 機械k で 乙日に 加工す る なら ば1 、 さ もな く ば0 子作 業(舒)を 機 械Z で乙日に 加工 す るなら ば1 、 さ もな く ば0 親作 業 で の 開始 日 親 作 業 で の子 作業(l,j)の 開始 目 親 作 業f の終 了 目 親 作 業f の 子作業(濤)を 終了 目 親 作業f の子 作業(ij)の納 期遅 れ

で あ る 。 装置産業 の スケジ ューリン グ問題とそ のモデル化 Tuj) ￣max{O,c ㈲}―cf(り)} 7.2 定 式 化 以 下 で 、Σ(i.i)と は 、「全 て の(○) に つ い て 」 を 意 味 す る 目 的 関 数 min Σ ア(i,i) 亀斗,)(ij) 制 約 条件 各 日の各 機 械は、 高 々1 つ の作 業 しか 処 理 で きな い。 加 工 日 数 に 関 す る 条 件 。 Σ 心ダ1, ∀k^M ≒ ∀亡 Σ(5(;, 加<1 ， ∀1&M へ ∀Z 町)

S,＋Pi 一l=Ci, ∀i ・5'(i.;)＋Ai,/)−1 ＝ ら,y)， ∀(U)

中 間 在 庫 は 負 に な る こ と は 許 さ れ な い 。 各 作 業 は 中 断 不 可 で あ る 159 (3) (4) (5) (6) う う700 ぐ ぐ (9) (10) 7.3 緩 和の 考え 方7.3.1 原問 題 の特徴 一 般に ラ グラ ンジ ュ緩 和を す る場 合 、 ど の制 約式 を緩 和 す るか が焦点 となる。 そ の際 、 緩 和 問題 の解 きや す さ と下 界値 の精度 のバ ラン ス が問 題 と なる が、 さら に本 問題 の固 有 の特 徴 とし て、 ●兄 弟 作業 内 の組 合 せ的性 質 、す な わ ちあ る 子作 業 の開始 日が 早過 ぎる と、 中 間 在庫 を 共 有し て い る 兄弟 作 業 の開始 日に 悪影 響を 及ぼ す 可 能性 があ る 第-L二［ 程 の機械 上 で作業 間 の機 械 遊 休が 無い ス ケジ ュ ール に のみ注 目すれ ば 良い の2 点を 考慮 す る必 要があ る。 7.3.2 機 械 の能力 を緩 和 し た場合 の 子 問題 と 解 の性質 本 問題 で機 械 の能力 を緩 和 す るア プ ロ ーチを 踏 襲 する こ とを 前提 にす る場 合、 子 問 題 の 最適 解 で

160 経 営 論 集 第49 号 （1999 年3 月 ） は各 ジ ョブ（ 作業 ） に関 し て、 ●本来 の目的 関数 に相 当 す る納 期遅 れ量 ●双対 変 数 の値 （「機 械 の使 用料 」 と 解釈 がで き る町 の総和 が 最小 にな る よ うな 開始 日 が得 ら れ るは ずであ る。 中 間在 庫に 関す る制 約を 守 る よ うな緩 和 の場 合ぱ、 上 記 の要素 が全 体 で最 小 化 さ れ、 そ の結果 、 親 子作 業 や兄 弟作 業 間で バ ラ ソ スが と れた 開始 日（ 解） が得 ら れ、中 間 在 庫に つ い て の制 約も緩 和 し た場 合 は、 納期 遅 れ量 と 在 庫量 が負 に な るこ と のペナ ル テ ィ、 機械 の 使用 料 のバ ラ ン スを 加味 し た開始 日 （ 解） が 得ら れ る。 7.3.3 実 行可 能解 の生 成 方 法に 関 し て考慮 す べ き点 在庫 の非 負制 約を 緩 和 せず 機 械 の能力 の みの 緩和を 前 提に する 場 合は 、兄 弟 作 業 内 の組 合せ的 性 質 が残 る た め、 緩 和問 題 の最 適化 の手 間 は無 視 で きない。 一 方、 実行 可 能解 の生 成 の際 に は、 ●子 作業 の中 間 在庫 に対 す る 奪い 合 い が生 じ る状況 下 では 、兄 弟作 業 内で の優 先 順 位 とい う相対 的 関 係で はな く、 開始 日そ の も の の絶対 的 な関 係が 重要 であ る ●親 作業 の開始 日 が変 わ って し ま う と中 間在 庫 の時間 的推 移は 変化 し 、納 期 遅 れ 量 と機 械使用 料 の総 和 が最小 化 され兄 弟 作 業 間で 開始 日の バ ラソス が とれ たはず の緩和 問 題 の 解 か、 全 くあ て に なら な くな る可 能性 があ る な どを 考慮 す る必 要が あ る。 し た がっ て 、実 行 可能 解の 生成 時に 緩和 問題 の解 を 参 考に す る場合 、 ●親 作業 の開始 日が 子 問題 を 最適 に 解い た際 の開始 日 から変 わる ●親 子 間あ るい は兄 弟 間 の開始 日 の絶対 的 関 係が失 わ れ る よ うな 緩和 法 は、 実行 可能 解 の生成 上 は 不利 であ る と考 えら れる。 7.3.4 第1 、第2 両 工 程 の緩 和Hoitomtetal 押 のジ ョブ シ ョ ップ 問 題に 対 する ラ グラ ンジ ュ緩和 の適用 で は 、全 て の工 程 の能 力 の緩 和を 前 提に 、 リ スト ス ケジ ュー リン グとい う簡 便な方 法を 用 い て実 行可 能 ス ケジ ュールを生 成 し て い る。そ の アプ ロ ーチを そ の ま ま踏 襲 した の が、村上etal 戸 の第1 、第2 の両工 程 の緩和 であ る。 こ の緩 和は 、于 問題 に お い て、 ●各作 業 の重 な り（ 第1 、 第2 の両 工 程） ●第1 二L程で の作 業 間で の 機 械遊 休 を 許 容 する ス ケジ ュ ール とな る。 第1 工 程 の遊 休や作 業 の重 な りを許 す と、 第1 工 程 の作 業 の開始 日が、 緩 和 問題 の 解のそ れか ら 実行 可 能化 す る際 に変 わ り得 る。 こ れに よって 緩 和 問題 の親作業 の

装 置産 業 のス ケジ ューリ ング問題とそ のそデル化 161 開 始 日に 基づ く子作 業 の開始 日ま で も変 更 さ れる 可能 性 があ り、緩 和 問題 で得 た ス ケジ ュ ール にお け る 「バ ラ ン ス」 やそ の他 の情報が 失 わ れ てし ま う可 能性 が 高い。 また、 子問題 の最 適化 は 列 挙法 に 頼 ら ざ るを 得 ず、 手間 が比 較的か か る わ りに 、 実行 可能 ス ケジ ュ ールを生 成 す る 時 点 で は、 最適 化 か ら 得 ら れた 情報 が失 われ る部分 が 大 きい。 7.3.5 第2 工 程 のみ の緩 和 第1:E 程は そ の性質 から 遊 休を 考 え る必 要 は無 い ので、 第1: 工程 では 各作 業 の順 列 を 考 え れば 良 い 。 順 列 さえ 決 れば 開始 日は 各親作 業 につ い て一 意に 決定 で き、そ れに 基づ き 最適 化 を 行 い 子作 業 の開 始 日を 決 定す れば、 ●第1 工 程 は実 行可能 性を 保証 で き る ●親作 業 の開始 日は 実行 可能 解を 生成 す る 際に 変 わ るこ とは ない ので、 在庫 の時 間 的 推 移 も変 化 す るこ と はない ●親 子 間 あ るい は兄弟 間 の開始 日 の絶 対 的関 係が失 われ るこ とも な く、 実 行可 能 化 す る 際 は、 緩 和 問 題 から 得ら れ た開始 日を 基 準に し てそ れを変 更 す る アプ ロ ―チ が考 えら れ る な ど の利 点 があ る。 そ こで 、 第2 工 程 の機械 能力 のみを 緩 和 する 。 7.4 ラグ ラン ジ ュ緩和 問 題(6) に 対 し て 几なる 非負 の ラ グラン ジ ュ乗数 を 考 え緩 和 す る。

min Σ ア(iぶ十Σ Σ 又u

W I 亀,硲j)(ij)s.t. Σ 飢, 加−1(ij) (5),(7) ，(8)，(9),(10) 式 の問 題 は、 以下 の よ うに 変形 が可 能 で あ る。min Σ ΣT 朗十Σ Σ 几 s μ（・,ノ）i(i,i ）圧O,s.t. さ ら に と な る 。 Σmin 身∈ 肋“ 亀 邱、i)s.t. Z ／ Σ ΣS(ijvt 1i( ○)(三隅 (5) ，(7) ，(8)，(9),(10) 式 ユ ==ん ぐ7≒)十tI り 」 べ(5),(7),(8),(9),(10) 式 (m Σ Z Tilt (12) (13)

162 経 営 論 集 第49 号 （1999 年3 月 ） また、 ラ グラン ジ ュ双 対 問題 は 以 下 の よ うに な る。 max π Σ 乙 Σ 恥 ＋minS,S(i. ・)

2(n,＋z]>)i]

こ れ を 劣 勾 配 法(21]あ る い は 代 理 劣 勾 配 法[mを 用 い て 解 く。 7 。5 子問 題の 特 徴(13) 式 の 第1 項 は 第1 二[程 の機 械に 関 し て 分解す ると、 min Si,S(.j 〉 ［ Σ (i,j)＼m,＝k T≒)十Σ Σ 万人,必 丿 (14) と な る。 こ れは 「第1 工 程 の機 械上 では 作業 の重な りを 許 さず、 第2 工 程 の機 械 上 で は作 業 の重 な りを 許し、 納 期遅 れ と機械 使 用 料 の和 を 最 小に す る問題」 で あ る。 こ の問題 は 、 元 の問題 よ りもサ イ ズ が小 さ くなっ てい る も のの な お組 合 せ的 要 素を 有し てお り、 子 問題 は最 適 に 解 く 必要 が ある た め な んらか の厳密 解法 が必 要 で あ る。 一 般に 子 問題 を 解く際 に、 動的 計 画法 を 用 い る ア プp ーチ[11 もあ るが、 こ こで は分 枝限 定 法を 用 い る已 7.6 実 行 可能 スケ ジ ュー ル を得 る ため の 手順 緩 和 問題 の解は 在庫 の非 負 制 約を 守 りつ つ 、 第2 工程 の機 械 上で の作業 の重 な りを 許し て お り、 こ れを ど の ように して 実行 可 能 解に 直 す か が残 され た課 題で あ る。 こ こで、 子 作 業 は一 般 に は兄弟 を持 ち 在庫 を共 有 してい るの で、 既 に述 べ た よ うに 、 ●あ る子 作業 の開 始 日を 早 く す る と、中 間在 庫を 過度 に早 く食 い潰 し てし ま い 、 他 の兄 弟作 業 の 開始 日 が遅 くな る可能 性 が あ る ●あ る子 作業 の開 始 日を 遅 く す ると、 他 の兄弟 作業 の開始 日を 早 めら れ る可 能 性 が あ る ものの、 当該 作業 の開始 日 の遅 れ に よる納期 遅 れ量 の増 加を 招い た り、同 一 機械 上 の他 の作 業 の 開始 日 を遅 く して し ま う可能 性 があ る の両 者を 考慮 す る 必要 があ る。 す なわ ち、 通 常 のフ ロ ーシ ョ ップ や ジa ブ ショ ップ のモデ ルな らば 少 な くと も当 該工 程 を最 早で 行 うこ とが 同一 ジ ョブ 内で は悪 影 響を 持 だな い が、 本 モデ ルでは 同一 ジョブ 内 で 互 いに 依 存 関係を 持 っ てい る ため、 一 概に 最 早 開始 日 で着 手 で き ない とい う難 しさ があ る。 そ の 意 味 で、 既 に述 べた よ うに 、Hoitomeetal.'"iの最 早 開 始を 前 提 に し た リスト ス ケジ ュ ーリン グ の よ うな アプp ーチを 採 用 す るこ とは 困難 で あ る。 一 般 に 、緩 和 問題 の解 は第2 工 程 上で の ［作業 の 重な り］ を含 む可 能性 があ り、そ れを な んらか

装置産業 のス ケジ ューリン グ問題とそ のモデル化 163 の 形 で無 くす と、多 くの場 合そ の機械 に対 応 す る 子問 題 の 目的 関 数値 の増 加を 招 く と考 え ら れ る。 兄 弟作 業 間 の 在庫 の共 有を考 慮し、 緩 和 問題 の解 の 目的関 数 値から の悪 化を 最小 限に 抑 え る ために は、 緩 和 問 題に おい て既 に納期 遅 れが 大 きい よう な機 械 の納期 遅 れ量を 可能 な限 り大 き くし な い と い う方 針 が 考え られ る。そ の際、 可 能 な限 り他 の兄 弟作 業 に影 響を 及ぼ さず 、な お か つ 既に 開始 目 が決 定 し てい る兄 弟作 業 の開始 目を変 え ない とい う制 約 の元で 、 開始 目を 決 定し なけ れ ば なら ない 。 そ こ で、 緩 和 問題 におけ る各機 械 の納 期 遅 れ量 の大 きい 順に 、以 下 の ような手 順 で ス ケ ジ ュ ール を 決 定 す る。stepi 第2 工 程 の各機 械毎 に 子 問題 の 解 から 総納 期遅 れを 計 算し、 そ の降順 に 機 械を 並 べ( 訂［l]lμ［2]、・..,M ⊇ と し、1/J. とす る。step2Mr,, で加工 さ れる作 業を 、 子 問 題 の解 の開 始 日順に 並 べる。step3 先 頭 の作業 から 「兄 弟作 業 の 開始 目が、 確定 し てい ればそ れに し たが っ て、 ま だ 確定 し てなけ れば子 問題 の開始 日に し た がっ て親 作業 の在庫を 払い 出し 、そ れ か ら得 ら れ る当 該作 業 の最 早開始 目 と機 械が 利 用 可能 な 最早 日を 比 べて遅 い 目を 開始 目と し て確 定 す る」 とい う手 続を 、順次 施 す。step4i ＝D なら ば終了 。 さ も な くばi=i ＋1 とし てstep2 に戻 る。 本手 順 の思 想は 、「緩和 問 題にお い て、第2 工 程 の 機械 毎に 目的関数 の値を計 算 し た際 に 、もっ と も値 の悪 い 機械 の悪 化を 可 能な限 り抑 制 す る」 とい うもの であ る。 7.7 数 値 実 験の 結果 の概 要

使 用 し た計 算 機はPentiumH400MHz のAT 互換 機 、 使用 言 語 はWindows98 上 のC 十 十Builder

で あ る。 計 算時 間 の上 限を30 分 とし た場 合 、 ●第1:iミ程8 機 械、 第2 工程8 機 械、 ジョ ブ が24個、 全作 業 数 が70 個 程 度 の 問 題 の 場 合 、 双 対 ギ ャ ップ が10％から20 ％程度 の 解を ●第1 二E程10機械 、第2 工 程10機械 、 ジ ョブ が30 個、 全作 業 数 が90 個 程 度 の問 題 の 場 合 、 双 対 ギ ャ ップ が20％ から30％ 程度り 解を 生 成 で き る。 こ れら よりも全 体の作 業 数 が多 くな る と（ すな わ ち、 各親作 業 から 加工 さ れる 子作 業 数 が多 く な ると）、子 問題 を 最適化 す るた め の 時 間が長 くな り、 全 体とし て の計 算 時 間 が 多 く 必 要 とな る。 現 段 階 の実装 は まだ 改良 の余地 が あ る こ とと 、 イ ンス タン スの性 質 と得ら れる 解 の精 度 の 分 析 の 必要 性 があ る と考え ら れる ので、 そ れ に 基づ い た精 度 の改 善 の可能 性 はあ る。

164 経 営 論 集 第49 号 （1999 年3 月 ） 8 両 モ デ ル の 長 所 と 短 所 に 関 す る 考 察8.1 総 所 要時 間最小 化 モデ ル 本 モデ ルは、 良 好な 精度を 持 つ 解を 高速に 生 成 す る解法を 構 築 するに 至 った 。 そ の観 点か らす る と望 ま しい モデル化 で はあ る が、 一 方 で総所 要 時 間そ の ものが 必ず し も現 場 の 尺度を 反 映し た も の で はな い とい う批 判があ る。 本 モデ ル の場 合は 、 元 々の問題 が 、 一 定 の 計 画 期 間 内 に よ り多 く の ジ ョブを 詰 め込 む よ うな問題 で あ る た め、そ の よ うな 本来 の問 題 の趣 旨と 大 き な遊 離 は ない と考 え るも の の、 モデ ル の一般 化 や汎 用性 を 目指 す観 点 から 見 ると、 こ の ような モデ ル のみ で 色 々な場 合 に 対 応 で きる とは 限らな い。 た だし 、 こ の よ うな 比較的 高速 な 解法 は、一 方 で これを 用い て新 た な 枠 組、 例え ば多 目的 尺度 を考 慮 す る 場合 の、 一 つ の尺度 の考 慮に こ の よ うな メ カ ニズ ムを 利 用す る な どの方 向性が 考え ら れる。 8.2 総 納期遅 れ最 小化 モデ ル 本 モ デル は、 概 ね許容 で きる 精度 を 持つ 解 を 生成 す る解法 を 構築 するに 至 っ たが、 計 算 時 間につ い ては 必 ずし も高速 とは 言 えない 。 また、 子 作 業数 の増 加に 伴い 、 子問題 の最 適化 に 要す る時 間 が 増 大す る こ とが 予測 さ れる こ とが、 大 き な欠 点 であ る。 こ の欠点 は、 本 問題 の 本 質的 部分 に 依る も の と考 え ら れ、 こ のよ うな兄 弟作 業 内の競 合 が 組 合せ的 な要 因 とし て残 る こと 、 さら に 全 体 の問題 の下 界値 を 計算 する ため に、 子 問題 を 厳 密に 最 適化 しなけ れば ならず 、 こ れら のこ と が全 体 の計 算 時 間 の増 大 や精度 の悪 化を 招 く ため と考え ら れ る。 また 、 子問題 の性 質（ こ こ で は、 実 験のた めに 生成 し た 問題 の パ ラメ ータ） に よ って 、子 問 題 の最 適化 に要 す る時 間が 大 きく 変 動す るこ とが あ り、 一 定 時 間 内 での 精度保 証 が難 しい とい う問題 も あ る。 一 方 で 、 各子作 業に は 個 々に納 期 を与 え る こ と がで きる ので、 こ の ような 解 法 は顧 客 の 要望 そ れ ぞ れ に きめ 細かに 対応 で きる 可能 性 を示 唆 し てい る。 一 般に 、フ ■p―シ ョ ップ 問題 全 般 に 関し て、 納 期 関 連尺 度 の ス ケジ ュー リン グ問 題 は比 較 的 難しい こ とか ら凧 総 所 要時 間 最 小化 モデ ル と の計 算 時 間 の 比較 は一 概に は で きない 部 分 もあ る。 9 モ デ ル の 拡 張 の 方 向 性9.1 尺 度の 複 数化 本 来 の 問題 は多 尺度 の問 題 であ っ た が、 問 題を 単 純化 す るため に敢 えて 単一 尺度 化 し た。 し かし、 可 能 であ るなら ば 、本来 の尺度 全 てを 考慮 す る こ とが望 ましい 。 そこ で、 元 々 の問 題 の尺度 のうち、 考慮 対 象 とな ってい ない 尺 度、 もし くは そ の 代替 尺 度を 考慮対 象 とし 、多 目的 問題 とし て扱 う。多 目的 最適 化 ぱそ れ だけ で も様 々な 議 論 が可 能 であ る が、 生産 ス ケジ ュ ーリ ング で多 目的 問題 を 解 く

装置産業 の スケジ ュ ーリング問 題とモ のモデル化 165 場 合、 よほ ど 特殊な 構 造が無 い限 り分 枝限 定 法 を基 礎 にし たアプ ロ ―チが多 い122)。 そ こ で 、 逆 に 対 象 と なる 尺 度 が分枝 限定 法 の枠組に 当 て ぱ まる よ うな、 す なわち 下 界値計 算 など に 目処 が立 つ もの が考 慮対 象 に な り得 る。 在庫 （ 正 確に は超 過 在庫量 ）は従 来 の 研究 で も 扱わ れ る ことが ない 尺度 で、 数 学的 な 構 造 につ い て ぱ検 討 の 余地 が多 く、 好 ましい構 造を 有す る か ど うか 明ら かで はな い。そ の一 方 で段 取 り回数 は 、3.3 節 で 触 れた 今泉etal 呻 の バッチ サイ ズ 決定 問 題 で の扱い のよ うな形 があ り得 る こ とか ら 、 比 較 的 アプ ロ ーチ がしや すい と考 えら れる。 9.2 問 題 細 部の 条件 を原 問題 のそ れに 近 づけ る 例え ば 、各 ジョブ は候 補 の機械が 唯一 であ る よ うな 単純 化 を行 っ たが、 原 問題 の条 件 に 近づ け る こ とが 、 本来 の問題 を 解く上 で更に 重 要 な基 礎 的 情報 を提 供 す る可 能性 が高い 。 具 体的 に は 、以 下 の よ うな方 向が あ り得 る。 9.2.1 ジ3 ブ の 候補機 械 総 所 要 時 間を 評価 尺度 とし た場合 は 、 候補 機 械 が 複数あ って も多 少 の複雑 さは 伴 う も のの 、精 度 の問 題を 度外 視 す れば下 界値 の導 出は 可能 で あ る と考 えら れる。 一方 、総 納 期遅 れを 評 価 尺度 に し た場 合 は、 まず 本稿 におけ る アプ ロ ーチ の よ うな 第1 工 程 の 機 械 毎 の分 解 は 不 可 能 に な る 。 し た が って、 分解 の段 階 から アプ ロ ―チ の 再 構成を 余 儀な く さ れる。 ま た、 実行 可能 ス ケ ジ ュ ール の生 成方 法 に もか な りの工夫 が必 要に なる。 9.2.2 機 械 の能力 差 元 々 の問 題 に は機 械 の 能力 差 が あ っ た。 各 作 業 の候 補 機 械 内に おけ る加 工 時 間 は 所 与 な ので 、 精度 に 関 し て は 明ら か で は ない が 総 所 要 時 間 を 評 価 尺 度 と し た 場 合 の 下 界 値 の 計 算 は 可 能 で あ る と 考 え る。 た だ し、 非一 様 型 の並 列 機 械 の ス ケ ジ ュ ーリ ン グ問 題 は 存 在 する が 、 ハ イブ リ ッド フ ロ ーシ ョ ッ プ 問題 でこ の よ うな 条 件 を 持 っ て い る モデ ル は 、筆者 の知 る 限 り存 在 し ない こ とを 附 記 す る。 10 お わ り に 本 稿 で は、 現 実 のシ ステ ムのス ケジ ュ ーリ ン グ問題 を 元 に、 そ れを 抽象化 し た モデ ル の構 築 、お よびそ の解 法 に 関す る議 論を 行 った。 現実 の問 題 に は さ まざ ま な 要因 が 含 ま れ て い る こ とが ほ とん どで 、そ の本質 的 難 し さ が ど の 部

166 経 営 論 集 第49 号 （1999 年3 月 ） 分 に あ る か は す ぐに は 分か ら ない 。 仮に 、 組 合 せ 的 な 問題 に 帰 着し た とし て も 、変 数 の数 や 制 約 式 の数 、 組 合 せ数 、 あ るい はNP 困難 性 な ど で 問 題 の難 し さを 表 現 す る の が 一 般 的 で あ り 、 既 存 の理 論 モ デ ル と対 比 し て、 ど の部 分 が、 ど の よ うに 扱い に く い かを 論 じ る に は 、現 実 の問 題 を 本 稿 の よ うな 抽象 モデ ルに 帰着 さ せ た上 で 議 論 し ない 限 り、比較 は 一 般に は 容 易 で は な い と考 え ら れ る。 一般 に納 期 尺度を 有 す る問題 は 、 総所 要 時 間を 尺 度 とす るよ うな問 題に 比 べ て 解 き難 い と 言わ れ る が、 本 稿で 示し た現 時点 にお け る 結果 も 概 ねそ れを 肯定 し てい る。 そ の一 方 で、 納 期 尺度 を 有す る多 くの 問題 に対し て 適用 が試 みら れて い る ラ グラ ンジ ュ緩 和法 に よる アプ ロ ―チ が、 単純 な 適用 で は必 ず しも 良い 結果を 生 まな い よ うな 問 題 の存 在を 示 唆し てお り、 従来 の理 論 モデ ル から 見 た場 合 の、 本稿 が対 象 とし た問題 の困 難 さを 示 し てい る と考 えら れ る。 今後 の方 向性 とし て、 両 モデ ル に対 す る 数値 実 験に よる分 析に 加え て、9 節 で述 べた ような拡 張 を 施 し た モデ ルに対 す る解法 の構 築を 指 向 す るこ と 考えら れ る。 謝 辞 本 研究 の一部 は、 東洋 大学 井 上 円了 記 念 研究 助成 に よってい る。 参 考 文 献[1]J.F.Bard.Short

−termschedulingofthermaleletcticgeneratorsusinglagrangianrela χation.Opns ，Res.,Vol.36,No.5,pp.756 −766,1988.[2]K.E.Blazewicz,G.Schmidt,andJ.Weglarz.SchedulinginComputerandManufacturingSystems.Springer

−Verlag,1993 ・[3]S.A.BrahandJ.L.Hunsucker.Branchandboundalgorithmforflowshopwithmultipleprocessors.Eur

］.Opnl.Res.,Vol.51,pp.88 −99,1991.[4]R.W.Conway,W.L.Maxwell,andL.W.Miller.TheoryofScheduling.Addison −Wesley,1967.[5]S.Dauzere −PeresandJ. −B.Lasserre.LotstreaminginJob −shopscheduling.Opns.Res 。Vol.45,No.4,pp.584

−595,1997.[6]J.N.D.Gupta.Flowshopschedulingwithsequencedependentsetuptimes./,Opns.Res.Soc.Japan,Vol.29,No.3,pp.206

−219,1986.[7]J.N.D.Gupta.Two-stage,hybridflowshopschedulingproblem./.Opnl.Res.Soc ・,Vol.39,No.4,pp.359

−364,1988.[8]J.N.D.GuptaandE.A.Tune.Schedulesforatwo-stagehybridflowshopwithparallelmachinesatthesecondstage.Int.J

装置産業 のスヶ ジi − リン グ問 題とそ のモデル化 167

[9]J.N.D.GuptaandE.A.Tune.Schedulesatwo −stagehybridflowshopwithseparablesetupandremovaltimes.Eur.J.Opnl.Res.,Vol.77,pp.415 −428，1994.[10]S.K.Gupta,nJobsandmmachinesjob

−shopproblemswithsequence −dependentset 一uptimes.Int./.Prod.Res.,Vol.20,No.5,pp.643 −656バ982.[11]D.J.Hoitomt,P.B.Luh,andK.R.Pattipati.Apracticalapproachtojob −shopschedulingproblems.IEEETransactionsonRoboticsandAutomation,Vol.9,No.l ，pp.ト13 ，Feb.1993.[12]P.B.Luh,D.J.Hoitomt,E.Max,andK.R.Pattipati.Schedulinggenerationandreconfigu −rationforparallelmachines.IEEETransactionsonRoboticsandAutomation,Vol.6,No.6,pp.687 −696,Dec.1990.[13]T.E.MortonandD.W.Pentico.Heuristicschedulingsystems.JohnWiley&Sons,1993.[14]M.Pinedo.Scheduling.Prentice −Hall,1995・[15]C.RajendranandD.Chaudhuri.Amulti-stageparalle トprocessorflowshopproblemwithminimumflowtime.Eur.J 、○pnl.Res.,Vol.57,pp.111 −122,1992.[16]B.N.Srikarands.Ghosh.AMILPmodelforthen-job,w −stageflowshopwithsequencedependentset −uptimes.Int.J.Prod.Res.,Vol.24,No.6,pp,1459-1474,1986.[17] χ.Zhao,P.B.Luh,andJ.Wang.Surrogategradientalgorithmforlagrangianrelaxation.InIEEEConferenceonDecisionandControl ］997.[18] 中 川 義 之 ． 鉄 鋼 業 お け る 離 散 事 象 シ ス テ ム の 最 適 化 ． 室 田 一 雄( 編), 離 散 構 造 と ア ル ゴ リ ズ ム Ⅲ ，pp.163 −204. 日 本 応 用 数 理 学 会 ，近 代 科 学 社,1994.[19] 玉 木 欽 也 ． 戦 略 的 生 産 シ ス テ ム ．白 桃 書 房,1996.[20] 村 上 元 一 ． 今 泉 淳 ，森 戸 晋 ． ジ ョ ブ の 分 岐 の あ る2 段 階 複 数 機 械 フ ロ ー シ ョ ッ プ に おけ る 納 期 遅 れ 最 小 化 ス ケ ジ ュ ー リ ン グ ： ラ グ ラ ン ジ ュ 緩 和 に 基 づ く ヒ ュ ー リ ス テ ィ ッ ク アプ ロ ―チ ．生 産 ス ケ ジ ュ ー リ ン ダ シ ソ ポ ジ ウ ム'97, 東 京,1997.[21] 今 野 浩 ， 山 下 浩( 編). 非 線 形 計 画 法 ，OR ラ イ ブ ラ リ ー ， 第6 巻 ． 日 科 技 連 ，1978.[22] 今 泉 淳 ．多 目 的 ス ケ ジ ュ ー リ ン グ に 関 す る 概 観 一 現 在 ま で の研 究 の 流 れ と 招 来 の 展 望 ．東 洋 大 学 経 営 研 究 所 論 集 ， 第22 号,1998( 掲 載 予 定).[23] 今 泉 淳 ， 山 越 康 裕 ， 村 上 元 一 ，森 戸 晋 ， ジ ョ ブ の 分 岐 を 伴 う2 工 程 並 列 機 械 フ ロ ―シ ョ ッ プ ス ケ ジ ュ ー リ ン グ ヘ の 分 割 アプlコー チ ． オベ レ ー シ ョ ン ズ ・ リ サ ー チ ，Vol.43,No.ll,pp.624 −631,1998 ・[24] 今 泉 淳 ， 森 戸 晋.Abranchandboundapproachtotwo −stagehybridflowshopschedulingwithjobsplittingandoverlappingproduction.1996 年 度 日 本 オ ペ レ ー シ ョ ソ ズ ・ リ サ ー チ 学 会 秋 期 研 究 発 表 会 予 稿 集 ，1996.[25] 森 戸 晋 ， 今 泉 淳 ，朴 宰 完 ． 厳 し い 制 約 を 有 す る ス ケ ジ ュ ー リ ン グ に 対 す る 数 理 計 画 ア プ ロ ―チ ． 生 産 ス ケ ジ ュ ー リ ン グ シ ン ポ ジ ウ ム'96 講 演 論 文 集 ， 名 古 屋 ，1996.[26] 中 川 義 之 ， 熊 本 和 浩 ， 小 西 伸 之 ，西 田 大 ， 坂 井 伸 弘 ． 鉄 鋼 とOR ． オ ペ レ ー シ ョ ソ ズ ・ リ サ ー チ ，Vol.43,

168 経 営 論 集 第49 号 （1999 年3 月 ）

No.ll ，pp.593-597,1998.[27]

米 田 清 ． ラ グ ラ ン ジ ュ 緩 和 法 に よ る ス ケ ジ ュ ー リ ン グ ． シ ス テ ム ／ 制 御 ／ 情 報,Vol.41,No.4 ，pp.130 −138,1997.(1999