Data Structures Algorithms 简明教程
Job Sequencing with Deadline
作业调度算法用于在单处理器上调度作业以最大化利润。
作业调度算法的贪婪方法表明，“给定“n”个具有开始时间和结束时间的作业，需要以这样的方式进行调度，即在最大截止时间内获得最大利润”。
Job Scheduling Algorithm
一组带有截止时间和利润的作业作为输入取自作业调度算法，并且安排有利润的作业子集作为最终输出。
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
考虑按照截止日期和利润完成的任务。规划任务，按顺序高利润任务优先完成 −
Step 1
从给定的截止日期中找到最大的截止日期值，dm。
dm = 4.Step 2
按利润降序排列任务。
最大的截止日期，dm，是 4。因此，所有任务必须在 4 之前完成。
选择利润最高的任务，J4。它占据了最大截止日期的 3 个部分。
因此，下一个任务的时间段必须是 1。
总利润 = 100。
Step 3
下一个利润最高的任务是 J5。但 J5 花费的时间是 4，超出了截止日期 3。因此，它不能添加到输出集中。
Step 4
下一个利润最高的任务是 J2。J5 花费的时间是 2，也超出了截止日期 1。因此，它不能添加到输出集中。
Step 5
利润更高的下一个任务是 J3。J3 花费的时间是 1，不超出给定的截止日期。因此，J3 将添加到输出集中。
Total Profit: 100 + 40 = 140Step 6
由于，满足最大的截止日期，算法结束。在截止日期内计划的任务输出集为 {J4, J3} ，最大利润为 140 。