带截止日期的作业排序

应用作业调度算法来调度单个处理器上的作业以最大化利润。

作业调度算法的贪婪方法指出，“给定'n'个具有开始时间和结束时间的作业，需要以在最大期限内获得最大利润的方式来调度它们”。

作业调度算法

将具有截止日期和利润的作业集作为作业调度算法的输入，并获得具有最大利润的预定作业子集作为最终输出。

算法

  • 从输入的作业集中查找最大截止时间值。

  • 一旦确定了截止日期，就按照利润的降序排列工作。

  • 选择利润最高的工作，其时间段不超过最大期限。

  • 选定的一组作业就是输出。

例子

考虑以下任务及其截止日期和利润。以这样的方式安排任务，使它们在执行后产生最大的利润 -

S. 编号 1 2 3 4 5
工作 J1 J2 J3 J4 J5
截止日期 2 2 1 3 4
利润 20 60 40 100 80

步骤1

从给定的截止日期中找出最大截止日期 dm。

dm = 4.

第2步

按利润降序排列工作。

S. 编号 1 2 3 4 5
工作 J4 J5 J2 J3 J1
截止日期 3 4 2 1 2
利润 100 80 60 40 20

最大截止时间 d m为 4。因此，所有任务必须在 4 之前结束。

选择利润最高的工作，J4。它占据了最大期限的3部分。

因此，下一个作业的时间段必须为 1。

总利润 = 100。

步骤3

下一个利润最高的工作是J5。但是J5花费的时间是4，超出了deadline 3。因此，它不能添加到输出集中。

步骤4

下一个利润最高的工作是 J2。J5 所花费的时间为 2，也超出了截止时间 1。因此，无法将其添加到输出集中。

步骤5

下一个利润更高的工作是J3。J3所花费的时间为1，没有超过给定的截止时间。因此，J3 被添加到输出集中。

Total Profit: 100 + 40 = 140

步骤6

由于达到了最大期限，算法结束。在截止日期内安排的作业输出集为{J4, J3}，最大利润为140。

例子

以下是使用贪婪方法的作业排序算法的最终实现 -

C C++ Java Python 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

// A structure to represent a Jobs
typedef struct Jobs {
   char id; // Jobs Id
   int dead; // Deadline of Jobs
   int profit; // Profit if Jobs is over before or on deadline
} Jobs;

// This function is used for sorting all Jobss according to
// profit
int compare(const void* a, const void* b){
   Jobs* temp1 = (Jobs*)a;
   Jobs* temp2 = (Jobs*)b;
   return (temp2->profit - temp1->profit);
}

// Find minimum between two numbers.
int min(int num1, int num2){
   return (num1 > num2) ? num2 : num1;
}
int main(){
   Jobs arr[] = { 
      { 'a', 2, 100 },
      { 'b', 2, 20 },
      { 'c', 1, 40 },
      { 'd', 3, 35 },
      { 'e', 1, 25 }
   };
   int n = sizeof(arr) / sizeof(arr[0]);
   printf("Following is maximum profit sequence of Jobs: \n");
   qsort(arr, n, sizeof(Jobs), compare);
   int result[n]; // To store result sequence of Jobs
   bool slot[n]; // To keep track of free time slots

   // Initialize all slots to be free
   for (int i = 0; i < n; i++)
      slot[i] = false;

   // Iterate through all given Jobs
   for (int i = 0; i < n; i++) {

      // Find a free slot for this Job
      for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {

         // Free slot found
         if (slot[j] == false) {
            result[j] = i;
            slot[j] = true;
            break;
         }
      }
   }

   // Print the result
   for (int i = 0; i < n; i++)
      if (slot[i])
         printf("%c ", arr[result[i]].id);
   return 0;
}

输出

Following is maximum profit sequence of Jobs: 
c a d 

#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;
}
int main(){
   Job jobs[] = { { 'a', 2, 100 },
      { 'b', 2, 20 },
      { 'c', 1, 40 },
      { 'd', 3, 35 },
      { 'e', 1, 25 }
	  };
   int n = 5;
   cout << "Following is maximum profit sequence of Jobs: "<<"\n";
   sort(jobs, jobs+n, comp); //sort jobs 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, jobs[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 << jobs[jobSeq[i]].id << " "; //display the sequence
}

输出

Following is maximum profit sequence of Jobs: 
c a d 

import java.util.*;
public class Job {
   // Each job has a unique-id,profit and deadline
   char id;
   int deadline, profit;
   // Constructors
   public Job() {}
   public Job(char id, int deadline, int profit) {
      this.id = id;
      this.deadline = deadline;
      this.profit = profit;
   } 
   // Function to schedule the jobs take 2 arguments
   // arraylist and no of jobs to schedule
   void printJobScheduling(ArrayList<Job> arr, int t) {
      // Length of array
      int n = arr.size(); 
      // Sort all jobs according to decreasing order of
      // profit
      Collections.sort(arr,(a, b) -> b.profit - a.profit);   
      // To keep track of free time slots
      boolean result[] = new boolean[t];
      // To store result (Sequence of jobs)
      char job[] = new char[t]; 
      // Iterate through all given jobs
      for (int i = 0; i < n; i++) {     
         // Find a free slot for this job (Note that we
         // start from the last possible slot)
         for (int j = Math.min(t - 1, arr.get(i).deadline - 1); j >= 0; j--) {     
            // Free slot found
            if (result[j] == false) {
               result[j] = true;
               job[j] = arr.get(i).id;
               break;
            }
         }
      }
      // Print the sequence
      for (char jb : job)
      System.out.print(jb + " ");
      System.out.println();
   }
   // Driver code
   public static void main(String args[]) {
      ArrayList<Job> arr = new ArrayList<Job>();
      arr.add(new Job('a', 2, 100));
      arr.add(new Job('b', 2, 20));
      arr.add(new Job('c', 1, 40));
      arr.add(new Job('d', 3, 35));
      arr.add(new Job('e', 1, 25));     
      // Function call
      System.out.println("Following is maximum profit sequence of Jobs: ");
      Job job = new Job();     
      // Calling function
      job.printJobScheduling(arr, 3);
   }
}

输出

Following is maximum profit sequence of Jobs: 
c a d 

arr = [
    ['a', 2, 100], 
    ['b', 2, 20], 
    ['c', 1, 40], 
    ['d', 3, 35], 
    ['e', 1, 25]
    ]
print("Following is maximum profit sequence of Jobs: ")
# length of array
n = len(arr)
t = 3
# Sort all jobs according to
# decreasing order of profit
for i in range(n):
   for j in range(n - 1 - i):
     if arr[j][2] < arr[j + 1][2]:
       arr[j], arr[j + 1] = arr[j + 1], arr[j]

# To keep track of free time slots
result = [False] * t

# To store result (Sequence of jobs)
job = ['-1'] * t

# Iterate through all given jobs
for i in range(len(arr)):

   # Find a free slot for this job
   # (Note that we start from the
   # last possible slot)
   for j in range(min(t - 1, arr[i][1] - 1), -1, -1):

     # Free slot found
     if result[j] is False:
       result[j] = True
       job[j] = arr[i][0]
       break

# print the sequence
print(job)

输出

Following is maximum profit sequence of Jobs: 
['c', 'a', 'd']