求一个关于作业调度的算法问题的解!!

来源：百度知道 编辑：UC知道 时间：2024/05/15 00:17:05
具体问题如下：假设有n个要执行的作业，但只有k个可以并行的处理器，作业i用ti时间可以完成。试设计一个算法，找出完成这n个任务的最佳调度，使得完成全部任务的时间最早，即确定哪些作业按照什么次序在哪些处理器上运行，使得完成全部作业的最后时间最早。
能否用C写出一个源程序参考参考!!

n个任务的总执行时间：total=t1+t2+...+tn;
分配到每个CPU的执行时间：avarage=total/k;
显然最佳情况是每个CPU的执行时间相等，如果要求作业只能在一次调度，一个CPU上完成，那么这种最佳情形是未必能够满足的。
____________________________
所以我在下面提供几个尽可能提高资源利用的算法
1.把所有的输入的任务按照执行时间的长短从小到大进行内部排序,得到新的有序序列s1,s2...sn;
2.在任务的执行时间有序后，按照首尾顺序选择作业，为每个CPU选择(n/k)个作业左右(必不小于n/k);
还有：
1.把所有的输入的任务按照执行时间的长短从小到大进行内部排序,得到新的有序序列s1,s2...sn;
2.按照S形为每个CPU分配作业，即第一个作业交付给c1,第二个作业交付给c2,...第k个作业交付给ck,第k+1个作业交付给ck,第k+2个作业交付给c(k-1)...直到所有作业全部交付。

……