搜索

达到最高效益的调度

gecimao 发表于 2019-08-06 00:37 | 查看: | 回复:

  假设有一台机器,以及在此机器上处理的n个作业a1,a2,...an的集合。每隔作业aj有一个处理时间tj,效益pj,以及最后期限dj。机器在一个时刻只能处理一个作业,而且作业aj必须在tj连续时...

  假设有一台机器,以及在此机器上处理的n个作业a1,a2,...an的集合。每隔作业aj有一个处理时间tj,效益pj,以及最后期限dj。机器在一个时刻只能处理一个作业,而且作业aj必须在tj连续时间单位内不间断地运行。如果作业aj在最后期限dj之前完成,则获得效益pj,但如果在最后期限之后才完成,则没有效益。请给出一个动态规划算法,来寻找能获得最大量效益的调度,假设所有的处理时间都是1到n之间的整数。

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  1. 将a1,a2,…,an按照dj值排序,从小到大。假设接下来的分析中,已经保证当ij时,didj。添加d0=0。

  3. 求s[i][j]的值,select[i][j]用于记录是否选择i。这里递归包含了一种思想:如果第i个作业被调度,那么最好使其在期限时正好结束,这样能够保证i之前的作业能够在更充裕的时间内被调度。

  4. 最终s[n][d[n]]即为所求最高效益值。如果要求出所调度的作业序列,可以通过select取得。

本文链接:http://olivierlutaud.net/diaoduzuoye/921.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部