带截止期限的作业排序
作业调度算法用于在单个处理器上调度作业，以实现利润最大化。
作业调度算法的贪婪方法指出："给定'n'个作业，每个作业都有开始时间和结束时间，需要以这样的方式调度它们，以便在最长截止期限内获得最大利润。"
作业调度算法
作业调度算法将一组具有截止期限和利润的作业作为输入，并调度子集最终输出结果为利润最高的作业。
算法
步骤 1 − 从输入的作业集合中找出最大截止期限值。 步骤 2 − 确定截止期限后，按利润降序排列作业。 步骤 3 − 选择利润最高的作业，且其时间周期不超过最大截止期限。 步骤 4 − 选定的作业集合作为输出。
示例
考虑以下任务及其截止期限和利润。以执行后产生最大利润的方式安排任务 −
| S. No. | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Jobs | J1 | J2 | J3 | J4 | J5 |
| Deadlines | 2 | 2 | 1 | 3 | 4 |
| Profits | 20 | 60 | 40 | 100 | 80 |
步骤 1
从给定的截止日期中找出最大截止日期值 dm。
dm = 4.
步骤 2
按利润降序排列这些工作。
| S. No. | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Jobs | J4 | J5 | J2 | J3 | J1 |
| Deadlines | 3 | 4 | 2 | 1 | 2 |
| Profits | 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 被添加到输出集中。
总利润：100 + 40 = 140
步骤 6
由于满足了最大截止期限，算法结束。在截止期限内调度的作业输出集为 {J4, J3，最大利润为 140。
示例
以下是使用贪婪方法的作业排序算法的最终实现 −
#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; // 如果工作在截止日期前或截止日期结束，则可获利
} Jobs;
// 此函数用于根据以下条件对所有 Job 进行排序：
// 利润
int compare(const void* a, const void* b){
Jobs* temp1 = (Jobs*)a;
Jobs* temp2 = (Jobs*)b;
return (temp2->profit - temp1->profit);
}
// 找出两个数字中的最小值。
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:
");
qsort(arr, n, sizeof(Jobs), compare);
int result[n]; // 存储作业结果序列
bool slot[n]; // 跟踪空闲时间段
// 初始化所有槽为空闲
for (int i = 0; i < n; i++)
slot[i] = false;
// 遍历所有给定的作业
for (int i = 0; i < n; i++) {
// 为该作业寻找一个空闲位置
for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
// 找到空闲槽
if (slot[j] == false) {
result[j] = i;
slot[j] = true;
break;
}
}
}
// 打印结果
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); //根据利润比较工作
}
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: "<<"
";
sort(jobs, jobs+n, comp); //按利润对工作进行排序
int jobSeq[n]; // 存储结果（作业序列）
bool slot[n]; // 跟踪空闲时间段
for (int i=0; i<n; i++)
slot[i] = false; //initially all slots are free
for (int i=0; i<n; i++) { //对于所有给定的工作
for (int j=min(n, jobs[i].deadLine)-1; j>=0; j--) { //从最后一个空闲位置搜索
if (slot[j]==false) {
jobSeq[j] = i; // 将此作业添加到作业序列
slot[j] = true; // 将此插槽标记为已占用
break;
}
}
}
for (int i=0; i<n; i++)
if (slot[i])
cout << jobs[jobSeq[i]].id << " "; //显示序列
}
输出
Following is maximum profit sequence of Jobs: c a d
import java.util.*;
public class Job {
// 每个任务都有一个唯一的 ID、利润和截止日期
char id;
int deadline, profit;
// 构造函数
public Job() {}
public Job(char id, int deadline, int profit) {
this.id = id;
this.deadline = deadline;
this.profit = profit;
}
// 调度作业的函数接受两个参数
// 数组列表和要调度的作业数量
void printJobScheduling(ArrayList<Job> arr, int t) {
// 数组长度
int n = arr.size();
// 按照利润降序对所有作业进行排序
// 利润
Collections.sort(arr,(a, b) -> b.profit - a.profit);
// 跟踪空闲时间段
boolean result[] = new boolean[t];
// 存储结果（作业序列）
char job[] = new char[t];
// 遍历所有给定的作业
for (int i = 0; i < n; i++) {
// 为这项工作找到一个空闲的时间（请注意，我们
// 从最后一个可能的插槽开始）
for (int j = Math.min(t - 1, arr.get(i).deadline - 1); j >= 0; j--) {
// 找到空闲插槽
if (result[j] == false) {
result[j] = true;
job[j] = arr.get(i).id;
break;
}
}
}
// 打印序列
for (char jb : job)
System.out.print(jb + " ");
System.out.println();
}
// 驱动代码
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: ")
# 数组长度
n = len(arr)
t = 3
# 根据以下条件对所有作业进行排序
# 利润降序
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]
# 跟踪空闲时间段
result = [False] * t
# 存储结果（作业序列）
job = ['-1'] * t
# 遍历所有给定的作业
for i in range(len(arr)):
# 为该作业查找空闲时间段
#（注意，我们从
# 最后一个可能的时间段开始）
for j in range(min(t - 1, arr[i][1] - 1), -1, -1):
# 找到空闲插槽
if result[j] is False:
result[j] = True
job[j] = arr[i][0]
break
# 打印序列
print(job)
输出
Following is maximum profit sequence of Jobs: ['c', 'a', 'd']
