メイクスパン

オペレーションズリサーチでは、プロジェクトのメイクスパンは、作業の開始から終了までに経過する時間の長さです。このタイプのマルチモードリソース制約プロジェクトスケジューリング問題 (MRCPSP) は、プロジェクトリソースを効率的に使用し、追加リソースを可能な限り少なくしてメイクスパンを最小化することで、最短の論理プロジェクトスケジュールを作成することを目指します。^{[1]この用語は、}スケジューリングのコンテキストでよく使用されます。

複数のサブタスクで構成される複雑なプロジェクトがあります。プロジェクトが可能な限り短時間で終了するように、作業者にタスクを割り当てます。例として、ヤギに餌を与えるという「プロジェクト」があるとします。餌を与えるヤギは 3 頭いますが、1 人の子供が一度に餌を与えることができるのは 1 頭のヤギだけです。餌を与えることができる子供は 2 人います。Shmuel は 10 分でヤギ 1 頭に餌を与え、Shifra は 12 分でヤギ 1 頭に餌を与えます。次のような複数のスケジュールが可能です。

1. シュムエルにすべてのヤギの餌を与えた場合、メイクスパンは 30 (シュムエルの場合は 3×10、シフラの場合は 0) になります。
2. シフラにヤギ 1 頭を、シュムエルにヤギ 2 頭を飼育させる場合、メイクスパンは 20 です (シュムエルの 2×10、シュムエルの横で並行して働くシフラの 12)。
3. シフラにヤギ 2 匹、シュムエルにヤギ 1 匹を飼わせると、メイクスパンは 24 になります (シフラの 2×12、シフラの横で並行して働くサミュエルの 10)。
4. シフラにすべてのヤギの餌を与えた場合、メイクスパンは 36 (シフラの場合は 3×12、シュムエルの場合は 0) になります。

したがって、この場合、2 番目のスケジュールでは最短メイクスパンである 20 が達成されます。

• ジョンソンのルール- n 個のジョブと2 つの異なるステーションがあります。両方の作業センターを通過する必要があるジョブを順序付けるには、このルールの使用を検討してください。
• ジョブショップ スケジューリング- n 個のジョブとm 個の同一ステーションがあります。各ジョブは 1 つのステーションで実行する必要があります。これは通常、オンライン問題と見なされます。
• オープンショップ スケジューリング- n 個のジョブとm 個の異なるステーションがあります。各ジョブは、自由な順序で各ステーションで一定の時間を費やす必要があります。
• フローショップ スケジューリング- n 個のジョブとm 個の異なるステーションがあります。各ジョブは、事前に決められた順序で、各ステーションで一定の時間を費やす必要があります。
• 公正なメイスパンの最小化 - エージェントにタスクを割り当てる際には、メイスパンを最小化すると同時に、嫉妬を避ける必要があります。最速の労働者に仕事が与えられた場合、その労働者は余分な労力に対して報酬を受けなければなりません。Mu'alemは、金銭的支払いを使用して嫉妬のないことを保証する最適化問題の一般的なフレームワークを提示しています。^[2]