この問題を解決するにはあなたの助けが必要です。一連のタスクがあり、各タスクには実行時間があります。2 種類の制約があります。最初のタイプは、タスク間の優先関係です。2 番目の制約タイプでは、一連のタスクを同時に実行できます。例：6つのタスクと次のエッジ（T1、T2）、（T2、T3）、（T4、T3）、（T4、T5）、および（T6、T5）を持つグラフGがあります。T1、T4 は一緒に実行でき、T1、T6 も実行できますが、T4、T6 は実行できないとします。各タスクの実行時間を考慮します。いくつかのタスクの並列実行を考慮して、タスク間の優先関係を満たし、スケジュールの長さを最小限に抑えるスケジュールを見つける方法。
2 に答える
0
シンプルさを保つために、スケジュール生成スキームまたは SGS とも呼ばれる優先度ルールに基づく構成的ヒューリスティックを使用できます。詳細については、こちらを参照してください。ヒューリスティックは、いくつかの基準に従ってアクティビティの順序付けられたリストを生成し、SGS はこのリストを入力として受け取り、スケジュールを生成します。SGS の実装では、2 番目の制約に基づいて、2 つのタスクを並列に実行できるかどうかがわかります。
より堅牢なものが必要な場合は、基本的にソリューション (タスクのリスト) を生成し、ローカル検索手法を使用してこのソリューションを変更し、ソリューション検索スペースを探索するメタヒューリスティックを使用できます。優先ルールに基づいてソリューションを生成し、SGS 実装で評価できます。これは、メタヒューリスティックがどのように機能するかを簡単に説明したものであり、いくつかの相違点があります。Metaheuristic の良い例は、RCPSP 問題に適用される Simulated Annealing です: http://www.sciencedirect.com/science/article/pii/S0377221702007610。
于 2015-12-16T15:57:52.220 に答える
0
除外制約 (「T1、T4 は一緒に実行できる」) が存在しない場合 (および他の制約が追加されていない場合)、先行するすべてのタスクの最大終了時間を取得して、すべてのタスクを開始できます。それは最適であり、適切にスケーリングされます。最短のメイクスパンが自動的に取得されます。それは NP 完全/ハードではなく、ジョブ ショップ スケジューリングでもありません。
残念ながら、除外制約 (および将来追加される可能性のある他の制約) により、ジョブ ショップ スケジューリング (Lars が述べたように) になり、これは NP 完全/ハードです。オープン ソース Java 実装のジョブ ショップ スケジューリング バリアントのこのビデオを参照してください。このデモは、一部のタスクが先行するタスクが終了するよりも遅く開始される理由を示しています。それを解決するには、ヒューリスティック、メタヒューリスティック (タブ検索など)、またはその他の関連する手法を調べます。
于 2014-05-08T11:31:51.123 に答える