スケジューリング最適化 東京海洋大学 久保 幹雄 1 スケジューリングとは 作業（活動，ジョブ，タスク）の時間軸上への 配置 資源制約（機械，人，原材料などの使用可能量上 限） 作業間の先行関係（ある作業が終了してからでな いと，別の作業を開始できない） 2 飛行機を早く離陸させよう！ あなたは航空機会社のコンサルタントだ． あなたの仕事は，着陸した航空機をなるべ く早く離陸させるためのスケジュールをた てることだ．航空機は，再び離陸する前に 幾つかの作業をこなさなければならない． まず，乗客と荷物を降ろし，次に機内の掃 除をし，最後に新しい乗客を搭乗させ，新 しい荷物を積み込む．さて，最短で何分で 離陸できるだろうか? 3 資源制約なしのスケジューリング(PERT) PERT: Program Evaluation and Review Technique,第 二次世界大戦のポラリス潜水艦の建造で利用 作業1 作業3 作業4 13分 15分 27分 完了時刻最小化 ダミー作業 先行制約 作業 作業2 25分 作業5 22分 作業１：乗客降ろし（１３分） 作業２：荷物降ろし（２５分） 作業３：機内清掃（１５分） 作業４：乗客搭乗（２７分） 作業５：荷物積み込み（２２分） 4 最適化結果（ガントチャート） 作業1 作業3 作業4 15分 13分 27分 作業5 作業2 25分 22分 ０ 時間 55 資源制約つき（１人で作業） 15分 ０ 作業1 作業2 作業3 25分 作業4 13分 作業5 27分 22分 時間 102 5 ピットイン時間を短縮せよ！ あなたはF1のピットクルーだ．F1レースにとって ピットインの時間は貴重であり，ピットインした レーシングカーに適切な作業を迅速に行い，なる べく早くレースに戻してやることが，あなたの使命 である．いま，あなたを含めて3人のピットクルー がいて，作業を手分けして行うものとする．作業 は途中で中断できないものとすると，なるべく早く 最後の作業を完了させるには，誰がどの作業を どういう順番で行えばよいのだろうか? 6 ピットイン時間を短縮せよ！ gas 3秒 作業１ 作業９ 11 秒 R TE WA ３人のピットクルー （資源制約） 2 作業２ 秒 作業５ 2秒 4 作業６ 作業３ 作業７ 作業８ 作業４ 2 秒 秒 4 秒 4秒 4 2 秒 作業１０ 秒 7 スケジューリングモデルの解法 近視眼的ヒューリスティクス ディスパッチングルール（作業の重要度をパラ メータとして入力；処理的IT） 遅れなしスケジュール生成法 有効スケジュール生成法 山崩し法 制約論理 メタ解法 8 遅れなしスケジュール生成法（１） 時刻0において 開始できる作業（適合作業） 0 クルー1 5 作業１ 作業２ 作業３ 作業４ 10 15 作業１ クルー2 作業２ クルー3 作業３ 現在時刻（０）における適合作業から作業を選択 各々の開始時刻を 0 に設定 作業１，２，３が活動中の作業（ピンク色の作業） 9 遅れなしスケジュール生成法（２） 時刻 2 における 適合作業 作業４ 0 クルー1 5 10 15 作業１ クルー2 作業２ 作業４ クルー3 作業３ 作業完了時刻の最早のもの（作業2,3）の完了時刻を現在時刻（2）とする． 活動作業から作業2,3を除く． 時刻 2 における適合作業から作業４を選択．開始時刻を2に設定． 10 遅れなしスケジュール生成法（３） 時刻 3 における 適合作業（ジョブ） 0 クルー1 作業９ 5 作業１ 10 15 作業９ クルー2 作業２ 作業４ クルー3 作業３ 現在時刻を 3 に進め，時刻 3 における適合作業（作業9）を選択． 作業9の開始時刻を3に設定． 11 遅れなしスケジュール生成法（４） 時刻 4 における 適合作業（ジョブ） 0 クルー1 作業５ 作業６ 作業７ 作業８ 5 作業１ 10 15 作業９ クルー2 作業２ 作業４ 作業５ クルー3 作業３ 作業６ 現在時刻を 4 に進め，時刻 4 における適合作業（作業5,6,7,8）から 適当な優先ルールにしたがって作業を選択． 12 作業5,6の開始時刻を4に設定． 遅れなしスケジュール生成法（５） 時刻 8 における 適合作業（ジョブ） 0 クルー1 作業７ 作業８ 5 作業１ 10 15 作業９ クルー2 作業２ 作業４ 作業５ 作業７ クルー3 作業３ 作業６ 作業８ 現在時刻を 8 に進め，時刻 8 における適合作業（作業7,8）から 適当な優先ルールにしたがって作業を選択． 作業7,8の開始時刻を 8 に設定． 13 遅れなしスケジュール生成法（６） 時刻 12 における 適合作業（ジョブ） 作業10 0 クルー1 5 作業１ 10 15 作業９ クルー2 作業２ 作業４ 作業５ 作業７ クルー3 作業３ 作業６ 作業８ 作業10 現在時刻を 12 に進め，時刻 12 における適合作業（作業10）選択． 作業 10 の開始時刻を 12 に設定． 14 完了時刻 14 のスケジュールの完成！ 遅れなしスケジュール生成法 （作業時間を１秒縮めた場合） 0 5 作業1 10 15 作業5 作業6 １５秒に増加！ 15 他の改善（？）法 ピットクルーを4人に増やす -> 作業時間17秒に増加！ 先行制約をすべて外す ->作業時間18秒に増加！ 近視眼的ヒューリスティクスを用いていると しばしば改善のための工夫が改悪につな がる！ 16 スケジューリング最適化システム WebSeqのデータ項目 作業データ：作業の属性を保管するデータ 作業ID，作業名，作業時間，リリース時刻，納期，最終納期， 納期遅れペナルティ，開始時刻 資源データ：資源の属性を保管するデータ 資源ID，資源名，上限 作業・資源データ：作業の資源への割り当てに関す るデータ 作業ID，資源ID，使用量 作業対データ：作業間の先行関係に関するデータ 先行作業ID，後続作業ID，段取り時間下限，段取り時間上限， 先行制約のタイプ 17 作業対（先行制約）データ 先行作業ID: 先行する作業番号 後続作業ID：後続する作業番号 段取り時間下限 段取り時間上限 終了 先行制約のタイプ ＝１：終了 ->開始 ＝２：終了->終了 ＝３：開始->開始 ＝４：開始->終了 開始 先行作業 後続作業 段取り時間下限 段取り時間上限 18 同時開始，同時終了 作業２，３の間に「開始-開始」の先行制約 ＋最小段取り＝０，最大段取り＝０ 作業４，５の間に「終了-終了」の先行制約 ＋最小段取り＝０，最大段取り＝０ 19 納期遅れを最小にしよう！ あなたは売れっ子作家だ．あなたは，A, B, C, D の4社から原稿を依頼されており，それぞれ， どんなに急いで書いても 1日，2日，3日，4日か かるものと思われる．各社に約束した納期は，そ れぞれ 5日後，9日後，6日後，4日後であり，納 期から 1日遅れるごとに 1万円の遅延ペナル ティを払わなければならない．どのような順番で 原稿を書けば，支払うペナルティ料の合計を最 小にできるだろうか? 20 納期遅れを最小にしよう！ 完了時刻最小化（メイクスパン）以外の目的関数の例 納期遅れ最小化 納期ずれ最小化 納期遅れした作業（ジョブ）数最小化 納期遅れの最大値の最小化 上の指標の重み付きの尺度最小化 ．．．． A社 B社 C社 D社 作業時間 1日 2日 3日 4日 9日後 6日後 4日後 会社名 納期 5日後 21 最適化の結果 作業4（D社） 作業1(A社） 作業3（C社） 納期遅れ 作業2（B社） 納期遅れ 時間（日） ０ 10 A社納期 C社納期 D社納期 B社納期 22
© Copyright 2024 ExpyDoc
