帶截止日期的作業排序

Table of content
上一頁
下一頁

作業排程演算法用於在一個處理器上排程作業以最大化利潤。

作業排程演算法的貪心方法指出：“給定n個作業，每個作業都有起始時間和結束時間，需要以某種方式安排這些作業，以便在最大截止日期內獲得最大利潤”。

作業排程演算法

帶有截止日期和利潤的作業集作為輸入提供給作業排程演算法，並獲得作為最終輸出的具有最大利潤的作業排程子集。

演算法

Step1 −  Find the maximum deadline value from the input set 
of jobs.
Step2 −  Once, the deadline is decided, arrange the jobs 
in descending order of their profits.
Step3 −  Selects the jobs with highest profits, their time 
periods not exceeding the maximum deadline.
Step4 −  The selected set of jobs are the output.

示例

考慮以下任務及其截止日期和利潤。安排這些任務，以便在執行後產生最大利潤：

序號 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

按其利潤的降序排列作業。

序號 1 2 3 4 5
作業 J4 J5 J2 J3 J1
截止日期 3 4 2 1 2
利潤 100 80 60 40 20

最大截止日期dm為4。因此，所有任務必須在4之前結束。

選擇利潤最高的作業J4。它佔用最大截止日期的3個部分。

因此，下一個作業的時間段必須為1。

總利潤 = 100。

步驟3

下一個利潤最高的作業是J5。但是J5花費的時間為4，超過截止日期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']
列印頁面
上一頁
下一頁
廣告