设有带时限的作业排序问题实例(p1,p2,...,p5)=(6,3,4,8,5),(t1,t2,...)
时间: 2024-05-28 19:12:50 浏览: 175
带有限期的作业排序.docx
作业排序问题是一个经典的调度问题,它的目标是在给定作业的时限和完成时间的情况下,最小化最大延迟时间。
对于这个实例,我们可以使用贪心算法来解决。具体地,按照完成时间从小到大排序,然后依次安排作业。如果当前作业的完成时间超过了它的时限,就将它放到最后安排。
按照这个方法,我们可以得到如下的作业安排顺序:
p2,p3,p5,p1,p4
其中,每个作业的完成时间和延迟时间如下:
p2:3,0
p3:7,3
p5:12,7
p1:18,12
p4:26,18
因此,最大延迟时间为18,这也是我们的目标。
阅读全文