最適化・シミュレーション演習 第１０回 ラベル，リソース，シミュレー ション実験の進め方と結果の表示・分析 • 授業サポートページ http://www.morito.mgmt.waseda.ac.jp/optsim/ • 数理計画による最適化と（離散事象型）シミュレーションに 関する演習を行う．使用するソフトウェアは，AMPL（＋ GurobiまたはCPLEX)，および，Simul8を想定している． • 演習では，数理計画による最適化やシミュレーションの実践 的能力を身につけることを目指す。履修者は，Cを使用でき る環境を有するPCを持参すること。受講者は，実験室にて， 演習で使用する C，AMPL，Simul8をダウンロードできる。 1 本日のトピックス • 応用モデリングテクニック – ラベル – 移動先 – リソース • シミュレーションの設定と実験の進め方 – シミュレーションクロック – 立ち上がり期間と結果集計期間 – 「試行」（ラン）の繰り返し（独立標本法） • 実行結果とその分析 – 結果の参照と結果マネージャ • 有限バッファ直列システムのシミュレーションに よる特性分析（今泉先生） 2 離散（事象）型シミュレーション Discrete (Event) Simulation • 待ち行列型のモデルで表現されるシステム のシミュレーション • 混雑現象のシミュレーション • 応用例 – 銀行のキャッシュマシン、生協食堂、コールセン ター、病院、工場のショップ（ジョブショップ等）、 電話、通信ネットワーク、．．． • 商用ソフトウェア（国内で代表的なもののみ） WITNESS、Simul8、S^4、SLAM 3 離散事象シミュレーションの特徴 • 時間は（通常）連続時間を考慮 • システム内を動き回る要素（entity）を考慮 – 例：顧客、工場内を流れる製品、ジョブ、注文 • 要素にサービスを提供する静的な要素と考えられる、 広義のリソース(resource）の存在 – 例：キャッシュマシン、機械、CPU、事務処理者 • システムの状態（state） – 例：待ち人数、サーバーの状態(idle/busy） • システムの状態変化が離散的に（事象発生時に）の み変化すると見る捉え方 – 例：顧客の到着時、サービス終了時 • 時間の進め方は、事象ー事象進行方式 • 離散事象シミュレーションのベースとなっているモデル は待ち行列モデル 4 待ち行列モデル Queueing Models • 待ち行列モデルは何で規定されるんだろう？ • 待ち行列モデルの分類 A/B/X/Y/Z – A: – B: – X： – Y： – Z： 到着パターン（到着時間分布） サービスパターン（サービス時間分布） 並列サーバー数 システム容量（=サービス中＋待機中）上限 待ち行列規律 • 例： M/M/1，M/G/m，M/D/2/∞/FCFS 𝑀 𝑋 /G/𝑐/𝑐 5 待ち行列モデルの分類 A/B/X/Y/Z （A）（B）: M＝指数分布、D＝一定、G＝一般 𝐸𝑘 ＝タイプ𝑘アーラン分布 PH＝相型分布 （X）： 並列サーバー数 1,2,…,∞ （Y）： システム容量（=サービス中＋待機中） 1,2,…,∞ （Z）： 待ち行列規律 FCFS、LCFS RSS（ランダム）、PR（優先規律） GD（一般） 6 ラベル • モデルの中を動き回るワークアイテムには 「属性」を持たせることができる • ワークアイテムの属性をラベルと呼ぶ • ラベルの使い方 – ワークアイテムの移動の制御 – ワークアイテムのアクティビティの時間 • ラベルは，数値，または，テキスト 7 ラベルによる行き先の制御 8 移動先の制御 • • • • • • • 巡回（順番に，１→２→３→１→２→・・・） 一様（均等な確率で，ただし，ランダムに） 割合（指定された確率でランダムに） 優先度（指定された優先度の順番に） ラベル（ラベルの値に応じて） ・・・ 分割（＝コピーを作る） 9 分割＝コピーの作成 （batching） Activity 1は時間0のダミーアクティビティ 「ワークセンター」で「分割（batching)」をクリック 分割数を（たとえば）「固定値」2に指定 10 リソース • ワークセンター（＝アクティビティ）は，「固定的」 なリソース • つまり，ワークアイテムが特定のワークセンター に入ったときにワークセンター（機械など）という リソースを占有する • 「流動的」なリソースを考えたい，というケースが 出てくるのに対応するのがリソース – 例： 機械で加工するが，機械だけでなく，作業者が 必要，しかし，作業者は他の機械も掛け持ちしている 11 リソースの使用例（１） worker（一人しかいないリソース）は，二つの ワークセンターを掛け持ち 12 リソースの使用例（２） 検査工程で検査； X%は要調整； (100－X） は系外に移動 （確率による行き先決定） 検査，調整とも同一の作業者（一人）が実施13 シミュレーションクロック （「データとルール」の「属性」） 14 「何を調べたいか」による シミュレーションの分類 1. 定常状態のシミュレーション(steady state simulation) – システムの稼働率のように、安定な動きをして いるシステムのふるまいのシミュレーション 2. 条件停止のシミュレーション(terminating simulation) – システムがダウンするまでの時間とか、立ち上 がりの1時間のシステム特性のように、ある条件 を満たすまでの間のシステムのふるまいのシ ミュレーション 15 定常状態のシミュレーションにおける シミュレーションの実行方法と統計収集 • 点推定と区間推定 – たとえば、待ち時間の推定 – シミュレーションの実行ごとに推定値はばらつく – ばらつきの大きさの評価が必要 → 区間推定 • 中心極限定理に基づく区間推定 • 立ち上げの問題 • 独立な標本をとるための実行方法 – 独立標本法(independent replications) – 塊平均法(batch means) 16 独立標本法（上）と塊平均法（下） 1 2 3 ・ ・ ・ ・ 初期立ち上げ期間 n 両方法の狙い： 独立な標本を得ること 1 2 3 ・・・・ n 「試行」（ラン）の繰り返し （独立標本法） 18 実行結果（結果マネージャ） 19 有限バッファ直列システムの シミュレーションによる特性分析 担当 今泉 淳 対象のシステム • 5段階の有限バッファ直列システム 無限供給 実験の目的と評価尺度 • システムの性能評価 バッファ容量の影響 加工時間の変動の吸収 vs 失うものは何か? 定量的にどうか? 加工時間の変動の影響 加工時間の変動を直接抑えこむメリットは? • 評価尺度 – 産出されたアイテム数：多いほうが性能良い – タイムインシステム：短いほうが望ましい 実験上の設定 • 共通の設定 バランスドライン：各センターの加工時間の特性は同一 （iid） ランタイムは一ヶ月、ランは一回のみ 初期状態は「システムは空」 • バッファ容量 バッファ容量は一様で1,2,3,5,10,20,30 加工時間は各センターとも指数分布で平均10 • 加工時間の変動 平均10の指数分布、アーラン分布k=2,3,5,10,20,30（k大な るほど分散小、k=1は指数分布） バッファ容量は1に固定 アーラン分布 • • • • パラメタとしての「相数」（k） k個の独立の指数分布を重ねあわせたもの k＝１は指数分布 kが大きいほど分散（標準偏差）が小さい k個 1/k λ 1/k λ 1/k λ それぞれは平均1/kλ 1/k λ トータルで平均1/λ 結果（１）：バッファ容量の影響 バッ ファ 1 2 3 5 10 20 30 完了ワークアイ テム数 561 640 685 732 819 849 875 タイムインシステム 平均 標準偏差 106.68 30.28 130.7 34.48 151.24 38.93 191.28 52.75 274.37 74.51 422.82 150.23 511.29 219.77 結果（１）：バッファ容量の影響 アイテム数・タイムインシステム 1000 900 800 700 600 500 400 300 200 100 0 完了アイテム数 タイムインシステム 0 10 20 バッファ容量 30 結果（１）：バッファ容量の影響 アイテム数・タイムインシステム 1000 900 800 700 600 500 400 300 200 100 0 完了アイテム数 容量小のときの改善幅は大きいが、漸減 タイムインシステム タイムインシステムも増加（悪化） 0 10 20 バッファ容量 30 バッファ容量の影響のまとめ • 容量30の際におおむね完了数900弱 • バッファは加工時間の変動の吸収に有 効 小容量の際の増加の効果は顕著 しかし、次第に効果は減少 • タイムインシステムの悪化を伴う 結果（2）：加工時間の変動の影響 k 完了ワークアイ テム数 1 2 3 5 10 20 30 561 669 720 780 835 885 908 タイムインシステム 平均 106.68 94.92 66.1 83.16 80.78 77.22 74.44 標準偏差 30.28 18.73 14.47 12.62 9.95 8.5 6.91 完了アイテム数・タイムインシステム 結果（2）：加工時間の変動の影響 1000 900 800 700 600 500 400 300 200 100 0 完了アイテム数 タイムインシステム 0 5 10 15 k 20 25 30 完了アイテム数・タイムインシステム 結果（2）：加工時間の変動の影響 1000 900 800 700 600 500 400 300 200 100 0 完了アイテム数 安定化で改善、特に初期の効果は絶大 タイムインシステムは減少し、また安定化 タイムインシステム 0 5 10 15 k 20 25 30 加工時間の変動のまとめ • K=30の際におおむね完了数900弱 • 加工時間のばらつきの除去は完了アイテム 数・タイムインシステムの両者に有効 • タイムインシステムは安定化：加工時間が安 定傾向にある以上当然 全体のまとめ • バッファ容量増加・加工時間の安定化はいず れも完了アイテム数の向上に貢献 • しかし、タイムインシステムへの挙動は正反 対 • バッファ容量30とアーランのk=30はおおむね 等価（しかし厳密ではない。ややこじつけ か）、しかしタイムインシステムの平均・標準 偏差は比較にならず 宿題１０ （必要に応じて，プログラム，結果，考察を提示すること） • 宿題１０．１ （今泉先生の分析例に関して） （1）本分析における方法にツッコミを入れよ（良く ないところ，直すべきところがあれば指摘せよ）． （2）上記（1）とは別の本質的な意味で，本分析を もっと緻密に行う拡張としてどんなことが考えられ るか考えよ． 34 宿題１０（続き） （必要に応じて，プログラム，結果，考察を提示すること） • 宿題１０．２ 検査と調整工程のライン[2，3] 組み立てられた製品が最終工程である検査工程に入ってくる．検査工程にお いてセッティングミスが発見されると，製品はセッティングを再調整するために調 整工程に送られる．調整工程を終えた製品は検査工程のバッファエリアに戻さ れ，再び検査を待つ．検査工程において検査にパスした製品は梱包工程に送り 出される． 製品の到着時間間隔は，最低3.5分から最高7.5分の一様分布に従う．検査工 程には2人の作業員がいて，別々に作業を行うことができる．検査時間は，6分 から12分までの一様分布に従う．平均的に考えて，85%の製品が検査工程をパ スし梱包工程に送られる．残りの15%は作業員が1人の調整工程に送られる．調 整に要する時間は，最低20分から40分までの一様分布に従う．480分のシミュ レーションを繰り返し行い，製品が検査と調整の工程に要する時間，および，検 査，調整工程の稼働率を推定しなさい．また，検査と調整工程に要する時間（＝ 製品が到着してから，梱包工程に送られるまでの時間）の95%信頼区間を示しな さい． 35 参考文献 ［１］森戸晋，逆瀬川浩孝，システムシミュレーショ ン，朝倉書店，2000． ［２］A. A. B. Pritsker and C. D. Pegden, Introduction to Simulation and SLAM, Halsted Press, 1979. ［３］森戸晋，中野一夫，相沢りえ子，SLAMⅡによ るシステム・シミュレーション入門（改訂版），1993． ［４］森戸晋，黒澤隆，大久保寛基，仕事のやり方 を変えるヒント：シミュレーションによる効率化， Parade Books，2015． 36
© Copyright 2024 ExpyDoc
