博士論文審査報告書

早稲田大学大学院 理工学研究科

博士論文審査報告書

論   文   題   目

A Study on Load Balancing Problem Solving by Genetic Algorithm: Case Analyses on Assembly Line

and Multiprocessor Systems

遺伝的アルゴリズムを用いた負荷平準化問題の研究 : 組立 ラインシステムとマルチプロセッサシステムを例として

申    請    者

黄 来国

ReaKook HWANG

経営システム工学専攻・生産管理学研究

2 0 0 9 年 1 2 月

1

負 荷 平 準 化 問 題 は 、 複 数 の 処 理 機 能 を 含 む シ ス テ ム に お い て 複 数 の オ ペ レ ー シ ョ ン 要 素 を 効 率 的 に 処 理 す る た め に 、 各 処 理 機 能 に 各 オ ペ レ ー シ ョ ン 要 素 を 如 何 に 均 等 に 分 担 さ せ る か と い う 問 題 で あ り 、 様 々 な 分 野 に お い て 個 別 に ボ ト ル ネ ッ ク 解 消 や 最 適 化 を 目 指 し た 研 究 が 活 発 に な さ れ て い る 。 本 論 文 で は 生 産 情 報 シ ス テ ム 分 野 に お け る 2 つ の 典 型 的 な 負 荷 平 準 化 問 題 、 す な わ ち 、 物 の 流 れ に 関 わ る 問 題 と し て ラ イ ン 編 成 問 題 及 び 品 種 投 入 順 序 決 定 問 題 を 、 情 報 の 流 れ に 関 わ る 問 題 と し て マ ル チ プ ロ セ ッ サ タ ス ク 割 当 問 題 に 焦 点 を あ て て い る 。 こ れ ら は 異 な る 対 象 領 域 の 負 荷 平 準 化 問 題 で あ る が 、 そ の 問 題 構 造 に お い て 類 似 性 を 有 す る 。

第 1 の 物 の 流 れ に 関 わ る 問 題 の う ち ラ イ ン 編 成 問 題 は 、 一 定 期 間 に 生 産 す る 製 品 の 生 産 計 画 と 各 製 造 オ ペ レ ー シ ョ ン （ タ ス ク ） の 先 行 順 位 関 係 を 制 約 条 件 と し て 、 ラ イ ン 状 に な ら ん で い る 処 理 機 能 （ 工 程 ） の 集 ま り か ら な る 生 産 シ ス テ ム に お い て 夫 々 の タ ス ク を 処 理 す る 工 程 を 決 定 す る 割 当 問 題 で あ る 。 ま た 、 上 記 生 産 シ ス テ ム に お け る 品 種 投 入 順 序 決 定 問 題 は 、 多 種 類 の 製 品 の 投 入 順 序 を 決 定 す る ス ケ ジ ュ ー リ ン グ 問 題 で あ り 、 製 造 業 、 と り わ け 組 立 産 業 に お け る 典 型 的 な 管 理 問 題 と な っ て い る 。

本 論 文 で 扱 う 対 象 条 件 及 び 評 価 尺 度 は 以 下 の よ う で あ る 。す な わ ち 、1）考 察 対 象 と す る 工 程 の 条 件 と し て 典 型 的 な レ イ ア ウ ト と し て の 直 線 型 及 び U字 型 を 、2） 生 産 の 条 件 と し て 単 一 品 種 及 び 複 数 品 種 を 、 ま た 、3） 生 産 機 能 の 競 争 力 に 大 き な 影 響 を 持 つ 編 成 効 率 と 負 荷 平 準 度 を 評 価 尺 度 と し て 同 時 に 考 慮 し て い る 。1）の 理 由 は 、工 場 で よ く 見 ら れ る 直 線 状 に レ イ ア ウ ト さ れ た 直 線 型 ラ イ ン と 共 に 、 自 動 車 関 連 産 業 な ど い く つ か の 工 場 で 作 業 者 、 設 備 の 効 率 的 利 用 の 視 点 か ら U 字 型 ラ イ ン へ の 改 善 、導 入 が 進 め ら れ て い る た め で あ る 。2） の 理 由 は 、 ラ イ ン の 大 規 模 化 、 複 雑 化 を 受 け て 単 一 品 種 ラ イ ン 生 産 シ ス テ ム （ 単 一 ラ イ ン ） の 編 成 ロ ジ ッ ク の 効 率 化 も さ る こ と な が ら 、 需 要 多 様 化 へ の 対 応 策 と し て 複 数 品 種 を 同 一 の ラ イ ン で 生 産 す る 混 合 品 種 ラ イ ン 生 産 シ ス テ ム （ 混 合 ラ イ ン ） の 効 率 的 設 計 、 運 用 が 以 前 に も 増 し て 重 要 と な っ て き て い る た め で あ る 。3）の 理 由 は 、設 備 の 利 用 効 率 指 標 で あ る 編 成 効 率 の み な ら ず 、 リ ソ ー ス 消 費 ペ ー ス の 平 準 化 に よ る 安 定 的 操 業 が 重 要 と な っ て い る た め で あ る 。 上 述 の 混 合 ラ イ ン に お い て は 負 荷 平 準 化 の 視 点 か ら 、 各 工 程 へ の タ ス ク 割 当 を 定 め る 編 成 問 題 と 複 数 の 品 種 を ラ イ ン に 投 入 す る 順 序 を 定 め る 品 種 投 入 順 序 決 定 問 題 の 2 つ が あ る が 、 前 者 の 解 は 後 者 の 制 約 条 件 と な る た め 、 本 論 文 で は 、 各 工 程 へ の タ ス ク 割 当 て と 品 種 投 入 順 序 付 け の 同 時 決 定 問 題 と し て 捉 え 、 適 用 可 能 条 件 を 明 ら か に し た 上 で 各 工 程 へ の 負 荷 の ば ら つ き を 抑 え る た め の 評 価 尺 度 を 含 む 新 た な 定 式 化 を 行 っ て い る 。 ま た 、 計 画 生 産 期 間 に お け る ラ イ ン 編 成 と 品 種 投 入 順 序 付 け が 同 時 に 設 計 可 能 な ボ イ ラ ー の マ ニ ュ ア ル 組 立 ラ イ ン を 事 例 と し て 取 り あ げ 、 提 案 し た 方 法 論 の 適 用 可 能 性 を 検 証 し て い る 。

第 2 の 問 題 で あ る 情 報 の 流 れ に 関 わ る マ ル チ プ ロ セ ッ サ タ ス ク 割 当 問 題 は 、 分 散 型 コ ン ピ ュ ー タ シ ス テ ム に お い て 各 タ ス ク を 夫 々 の プ ロ セ ッ サ へ ど の よ

2

う に 割 り 当 て る べ き か と い う 問 題 で あ り 、 近 年 の 分 散 型 シ ス テ ム の 普 及 を 背 景 と し て 、 計 算 リ ソ ー ス の 効 率 的 利 用 と ボ ト ル ネ ッ ク 解 消 の た め の 喫 緊 の 課 題 と な っ て い る 。 分 散 型 シ ス テ ム に お い て は タ ス ク の 処 理 に 関 す る 先 行 順 位 制 約 を 満 た し な が ら 如 何 に 効 率 的 、 安 定 的 に タ ス ク の 並 列 処 理 を 行 う か が 課 題 で あ り 、 こ の 視 点 か ら 各 タ ス ク の プ ロ セ ッ サ へ の 割 当 と 処 理 ス ケ ジ ュ ー ル を 設 計 す る 必 要 が あ る 。 本 論 文 で は こ の 問 題 に つ い て 各 タ ス ク の 先 行 順 位 制 約 、 実 行 時 間 及 び タ ス ク 間 の デ ー タ 通 信 時 間 を 非 循 環 有 向 グ ラ フ ( D A G : D i r e c t A c y c l i c G r a p h )に よ っ て 表 現 し 、 上 述 の ラ イ ン 編 成 問 題 と 同 様 、 プ ロ セ ッ サ 使 用 効 率 と 負 荷 平 準 度 を 評 価 尺 度 と し て 、ス ケ ジ ュ ー ル を 導 出 し て い る 。

上 記 の 2 つ の 問 題 に つ い て は 、 問 題 規 模 の 急 速 な 拡 大 や 複 雑 化 の 進 展 を 背 景 と し て 、よ り 効 率 的 、効 果 的 な 方 法 論 の 開 発 、適 用 が 強 く 求 め ら れ て い る 。 例 え ば 、 ヒ ュ ー リ ス テ ィ ク ス や メ タ ヒ ュ ー リ ス テ ィ ク ス は 実 務 規 模 の 様 々 な 問 題 に 有 効 と さ れ て お り 、 広 く 応 用 さ れ て い る 。 本 論 文 で は 上 述 の 問 題 を 解 決 す る た め 、 メ タ ヒ ュ ー リ ス テ ィ ク ス の 中 で も 計 算 モ デ ル が 単 純 で 比 較 的 問 題 の 表 現 力 が 豊 か な 遺 伝 的 ア ル ゴ リ ズ ム に よ っ て 上 記 の 問 題 を 同 時 に 解 く 方 法 を 導 入 し 、 よ り 効 率 的 な 解 を 求 め て い る 。

提 案 し た 方 法 論 の 技 術 的 特 徴 は 、 優 先 度 考 慮 遺 伝 的 ア ル ゴ リ ズ ム ( P G A : P r i o r i t y - b a s e d G e n e t i c A l g o r i t h m )と 呼 ば れ る 統 合 ア ル ゴ リ ズ ム を 導 入 し 適 用 し て い る 点 及 び 、 染 色 体 表 現 の 方 法 と し て 、 優 先 度 考 慮 多 情 報 染 色 体 表 現 ( P M C : P r i o r i t y - b a s e d M u l t i - C h r o m o s o m e )と 名 づ け た 新 た な コ ー デ ィ ン グ 法 を 提 案 し 適 用 し て い る 点 に あ る 。P G A は 、 遺 伝 的 ア ル ゴ リ ズ ム の 操 作 で あ る 染 色 体 の 初 期 設 定 、 交 叉 及 び 突 然 変 異 の 際 に 実 行 可 能 解 の み の 選 択 評 価 を 可 能 に し 、 こ れ に よ っ て 解 の 探 索 性 能 を 大 幅 に 向 上 さ せ る こ と が で き る 。 ま た 、

P M C は 1 つ の 染 色 体 で 複 数 種 類 の 情 報 を 表 現 で き る よ う に し た も の で 、こ れ

に よ り タ ス ク 割 当 の た め の 優 先 順 位 情 報 と 品 種 の 投 入 順 序 情 報 の 2 種 類 の 情 報 を 効 率 的 に 表 現 す る こ と が で き 、 解 の 探 索 手 順 を 簡 略 化 す る こ と を 可 能 に し て い る 。

本 論 文 は 以 下 の 6 章 か ら な る 。

第 1 章 に お い て は 、 研 究 の 背 景 と 目 的 に つ い て 述 べ て い る 。

第 2 章 に お い て は 、 負 荷 平 準 化 問 題 の 定 義 、 ラ イ ン 編 成 問 題 、 品 種 投 入 順 序 決 定 問 題 及 び マ ル チ プ ロ セ ッ サ タ ス ク 割 当 問 題 の 構 造 に つ い て 述 べ て い る 。

第 3 章 に お い て は 、 両 問 題 に 関 わ る 従 来 の 研 究 に つ い て 調 査 し 、 遺 伝 的 ア ル ゴ リ ズ ム の 一 般 的 メ カ ニ ズ ム と 両 問 題 へ の ア プ ロ ー チ 方 法 に つ い て ま と め て い る 。 と り わ け 、 対 象 と す る 問 題 を 重 要 な 評 価 尺 度 が 複 数 存 在 す る 多 評 価 尺 度 問 題 と し て 捉 え て こ れ ら の 間 の バ ラ ン ス を 取 る こ と の で き る 多 目 的 遺 伝 的 ア ル ゴ リ ズ ム( M O G A : M u l t i - o b j e c t i v e G e n e t i c A l g o r i t h m )の 構 造 に つ い て 述 べ る と と も に 、 対 象 と し た 2 つ の 問 題 に つ い て 複 数 の 代 表 的 な ヒ ュ ー リ ス テ ィ ッ ク ル ー ル を 取 り あ げ 、 そ れ ら の 概 要 及 び 問 題 点 に つ い て 検 討 し て い る 。 第 4 章 に お い て は 、 組 立 ラ イ ン の 負 荷 平 準 化 問 題 に つ い て 、 直 線 型 単 一 ラ イ ン 及 び U 字 型 単 一 ラ イ ン 、ま た 、直 線 型 混 合 ラ イ ン 及 び U 字 型 混 合 ラ イ ン

3

の 夫 々 を 対 象 と し て 、 問 題 の 定 式 化 、 提 案 す る 遺 伝 的 ア ル ゴ リ ズ ム を 用 い た 計 算 過 程 、 結 果 及 び 考 察 を 述 べ て い る 。 単 一 ラ イ ン に つ い て は 上 述 の M O G A を 導 入 し 、 先 行 順 位 制 約 の あ る タ ス ク の 割 当 問 題 を 数 値 実 験 と し て 効 率 的 に 解 き 、 そ の 結 果 を 考 察 し て い る 。 ま た 、 最 終 工 程 が 過 少 負 荷 に な る 場 合 が 多 い こ と か ら 、 仮 の サ イ ク ル タ イ ム を 設 定 し そ の 値 を 減 少 さ せ る こ と に よ っ て 全 体 の 負 荷 を 均 等 化 さ せ る 摂 動 改 良 型 多 目 的 遺 伝 的 ア ル ゴ リ ズ ム( A S M O G A : A m e l i o r a t i o n S t r u c t u r e w i t h M O G A )を 提 案 し 、従 来 の 方 法 と の 比 較 実 験 を 行 っ て い る 。 一 方 、 混 合 ラ イ ン に つ い て は ラ イ ン 編 成 と 品 種 投 入 順 序 の 同 時 設 計 を 狙 い と し て 、優 先 順 位 情 報 と 品 種 情 報 を 同 時 に 扱 う こ と が で き る P M C を 提 案 、 導 入 し 、A S M O G A を 用 い て 同 様 に 効 率 的 に 解 を 得 て い る 。

第 5 章 に お い て は 、 マ ル チ プ ロ セ ッ サ タ ス ク 割 当 問 題 に つ い て 、 プ ロ セ ッ サ 間 の デ ー タ 通 信 時 間 を 考 慮 し て い な い 場 合 及 び そ の 時 間 を 考 慮 し た 場 合 の 夫 々 に つ い て 問 題 の 定 式 化 、提 案 し た 遺 伝 的 ア ル ゴ リ ズ ム を 用 い た 計 算 過 程 、 結 果 及 び 考 察 を 述 べ て い る 。 そ の 特 徴 は 、 対 象 と し た 問 題 を タ ス ク の 処 理 時 間 と 負 荷 平 準 度 を 評 価 関 数 と す る 多 目 的 割 当 問 題 と し て 捉 え 、 計 算 ア ル ゴ リ ズ ム を 提 案 し 数 値 実 験 を 行 う こ と に よ っ て そ の 有 効 性 を 示 し た 点 に あ る 。

第 6 章 は 結 論 で あ り 、研 究 の 成 果 を 要 約 し 今 後 の 課 題 に つ い て 述 べ て い る 。 以 上 、 本 論 文 は 、 ラ イ ン 生 産 シ ス テ ム に お け る ラ イ ン 編 成 問 題 及 び 品 種 投 入 順 序 決 定 問 題 と 分 散 型 コ ン ピ ュ ー タ シ ス テ ム に お け る マ ル チ プ ロ セ ッ サ タ ス ク 割 当 問 題 を 、 類 似 性 を 有 す る 負 荷 平 準 化 問 題 と し て 取 り あ げ 、 シ ス テ ム 効 率 と 負 荷 平 準 度 の 2 つ の 評 価 尺 度 を 同 時 に 考 慮 し 、 遺 伝 的 ア ル ゴ リ ズ ム の 遺 伝 子 生 成 法 に 工 夫 を 加 え た 新 た な 計 算 法 を 提 案 、 適 用 す る こ と に よ っ て 、 こ の 問 題 に ア プ ロ ー チ す る た め の 有 用 な 方 法 論 を 与 え て い る 。

本 論 文 で 取 り あ げ ら れ た 問 題 は 、 与 え ら れ た リ ソ ー ス を 可 能 な 限 り 有 効 活 用 し よ う と す る 産 業 界 に お け る 管 理 上 の 中 心 的 課 題 の 一 つ で あ り 、 提 案 さ れ た 定 式 化 、 計 算 ア ル ゴ リ ズ ム 及 び 解 析 結 果 は 、 そ れ に 対 す る 実 用 上 の 基 礎 を 与 え る も の と し て 高 く 評 価 さ れ る と 同 時 に 、 今 後 の 研 究 に 貴 重 な 指 針 を 提 供 し て お り 、 生 産 管 理 学 分 野 の 理 論 的 、 実 践 上 の 発 展 に 貢 献 す る と こ ろ 大 で あ る 。 よ っ て 、 本 論 文 は 博 士 （ 工 学 ） 早 稲 田 大 学 の 学 位 論 文 と し て 価 値 あ る も の と 認 め る 。

2 0 0 9 年 1 1 月

審 査 員  

(主 査) 早 稲 田 大 学 教 授 博 士 （ 工 学 ） 早 稲 田 大 学 片 山 博   早 稲 田 大 学 教 授 理 学 博 士 （ 東 京 工 業 大 学 ） 逆 瀬 川 浩 孝   早 稲 田 大 学 准 教 授 博 士 （ 情 報 学 ） 京 都 大 学 菱 山 玲 子   早 稲 田 大 学 名 誉 教 授 工 学 博 士 （ 早 稲 田 大 学 ）

首 都 大 学 東 京 名 誉 教 授 石 渡 徳 彌  

青 山 学 院 大 学 名 誉 教 授 工 学 博 士 （ 早 稲 田 大 学 ） 黒 田 充   早 稲 田 大 学 名 誉 教 授 工 学 博 士 （ 大 阪 大 学 ） 平 澤 茂 一