期限付きのジョブシーケンス問題

この問題では、与えられた仕事のリストがあります。リストには、各ジョブの期限と利益も示されています。すべてのジョブには1単位の時間がかかるため、ジョブの最小期限は1です。一度に1つのジョブしかスケジュールできない場合は、利益を最大化します。

この問題を解決するために、一連のジョブのすべてのサブセットが生成され、個々のサブセットが実行可能かどうかがチェックされます。また、生成されたすべての実行可能なサブセットの最大利益を追跡します。

このアルゴリズムの時間計算量はO（n ^ 2）

入力と出力

Input:
A list of jobs with job id, deadline and profit. And the number of jobs n.
{('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)}
n = 5
Output:
Following is maximum profit sequence of job sequence: c a e

アルゴリズム

jobSequence(jobList, n)

入力- ジョブのリストとリストに存在するジョブの数。

出力- 順序、仕事の進め方。

Begin
   sort the jobs in jobList according to their profit create a list of job sequence and slot to track free time slots
   initially make all slots are free
   for all given jobs i do
      for all jobs in the list from ending of the list do
         if slot[j] is free then
            jobSequence[j] := i
            make slot[j] := fill
            break the loop
      done
   done

   for all slots when it is not free do
      print id of job using jobList[jobSequence[i]]
   done
End

例

#include<iostream>
#include<algorithm>
using namespace std;

struct Job {
   char id;
   int deadLine;
   int profit;
};

bool comp(Job j1, Job j2) {
   return (j1.profit > j2.profit);    //compare jobs based on profit
}

int min(int a, int b) {
   return (a<b)?a:b;
}

void jobSequence(Job jobList[], int n) {
   sort(jobList, jobList+n, comp);    //sort jobList on profit

   int jobSeq[n];     // To store result (Sequence of jobs)
   bool slot[n];      // To keep track of free time slots

   for (int i=0; i<n; i++)
      slot[i] = false; //initially all slots are free

   for (int i=0; i<n; i++) {    //for all given jobs
      for (int j=min(n, jobList[i].deadLine)-1; j>=0; j--) {   //search from last free slot
         if (slot[j]==false) {
            jobSeq[j] = i;   // Add this job to job sequence
            slot[j] = true;  // mark this slot as occupied
            break;
         }
      }
   }

   for (int i=0; i<n; i++)
      if (slot[i])
         cout << jobList[jobSeq[i]].id << " ";    //display the sequence
}

int main() {
   Job jobList[] = {{'a',2,100}, {'b',1,19}, {'c',2,27},{'d',1,25},{'e',3,15}};
   int n = 5;
   cout << "Following is maximum profit sequence of job sequence: ";
   jobSequence(jobList, n);
}

出力

Following is maximum profit sequence of job sequence: c a e