Data Structures Algorithms 简明教程
Job Sequencing with Deadline
作业调度算法用于在单处理器上调度作业以最大化利润。
Job scheduling algorithm is applied to schedule the jobs on a single processor to maximize the profits.
作业调度算法的贪婪方法表明，“给定“n”个具有开始时间和结束时间的作业，需要以这样的方式进行调度，即在最大截止时间内获得最大利润”。
The greedy approach of the job scheduling algorithm states that, “Given ‘n’ number of jobs with a starting time and ending time, they need to be scheduled in such a way that maximum profit is received within the maximum deadline”.
Job Scheduling Algorithm
一组带有截止时间和利润的作业作为输入取自作业调度算法，并且安排有利润的作业子集作为最终输出。
Set of jobs with deadlines and profits are taken as an input with the job scheduling algorithm and scheduled subset of jobs with maximum profit are obtained as the final output.
Algorithm
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.Examples
考虑按照截止日期和利润完成的任务。规划任务，按顺序高利润任务优先完成 −
Consider the following tasks with their deadlines and profits. Schedule the tasks in such a way that they produce maximum profit after being executed −
Step 1
Step 1
从给定的截止日期中找到最大的截止日期值，dm。
Find the maximum deadline value, dm, from the deadlines given.
dm = 4.Step 2
Step 2
按利润降序排列任务。
Arrange the jobs in descending order of their profits.
最大的截止日期，dm，是 4。因此，所有任务必须在 4 之前完成。
The maximum deadline, dm, is 4. Therefore, all the tasks must end before 4.
选择利润最高的任务，J4。它占据了最大截止日期的 3 个部分。
Choose the job with highest profit, J4. It takes up 3 parts of the maximum deadline.
因此，下一个任务的时间段必须是 1。
Therefore, the next job must have the time period 1.
总利润 = 100。
Total Profit = 100.
Step 3
Step 3
下一个利润最高的任务是 J5。但 J5 花费的时间是 4，超出了截止日期 3。因此，它不能添加到输出集中。
The next job with highest profit is J5. But the time taken by J5 is 4, which exceeds the deadline by 3. Therefore, it cannot be added to the output set.
Step 4
Step 4
下一个利润最高的任务是 J2。J5 花费的时间是 2，也超出了截止日期 1。因此，它不能添加到输出集中。
The next job with highest profit is J2. The time taken by J5 is 2, which also exceeds the deadline by 1. Therefore, it cannot be added to the output set.
Step 5
Step 5
利润更高的下一个任务是 J3。J3 花费的时间是 1，不超出给定的截止日期。因此，J3 将添加到输出集中。
The next job with higher profit is J3. The time taken by J3 is 1, which does not exceed the given deadline. Therefore, J3 is added to the output set.
Total Profit: 100 + 40 = 140Step 6
Step 6
由于，满足最大的截止日期，算法结束。在截止日期内计划的任务输出集为 {J4, J3} ，最大利润为 140 。
Since, the maximum deadline is met, the algorithm comes to an end. The output set of jobs scheduled within the deadline are {J4, J3} with the maximum profit of 140.