python使用贪心算法解决作业调度问题

这篇具有很好参考价值的文章主要介绍了python使用贪心算法解决作业调度问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

对于作业调度问题,其实至今都还不能找到一个最优的解决方案,对与如何将任务和机器进行一个合理安排和分配,让其能够在最短时间内将所有任务全部完成,和计算机操作系统的任务调度过程相类似。

这里主要是给定n个作业和m台相同的机器,使用这些机器来对给定的作业进行处理,则作业k所需要的处理时间是time[k],任一作业可以在任意的一台机器上进行处理,但是在未完成正在完成的作业之前不允许中断当前作业操作,同时任何作业都不可以进行拆分,这里需要给出一种作业调度的方案,使得对这n个作业进行操作,在尽可能短的时间内由这m台机器加工处理完成。

如下例子:

python使用贪心算法解决作业调度问题,贪心算法,算法

添加图片注释,不超过 140 字(可选)

python使用贪心算法解决作业调度问题,贪心算法,算法

添加图片注释,不超过 140 字(可选)

对如上的两个例子进行最短时间求解,考虑使用贪心算法得出一个较好的近似最优解。如果说将用时最短的任务优先分配给机器,可能会出现其他任务均已经完成,最终就剩下的是用时最长的任务,也就剩下它还处在正在运行中的情况,以第一个例子为例,如果将耗时为10,26,30这三个任务优先分配给3台机器,此时的最终总耗时为45,这样就可以看出当3个作业都已经完成的时候,耗时最长的作业35却仍在运行,这样就导致了时间的加长和浪费,所以就需要考虑对贪心算法的策略进行调整,就需要优先考虑将耗时最长的作业进行分配。

python使用贪心算法解决作业调度问题,贪心算法,算法

添加图片注释,不超过 140 字(可选)

优先将耗时最长的作业进行分配如下图所示:

python使用贪心算法解决作业调度问题,贪心算法,算法

添加图片注释,不超过 140 字(可选)

这个时候的最终的耗时为36,相比于上一种策略的使用耗时大大降低了时间成本,而对于这种贪心算法的策略之所以会生效,主要是因为优先分配耗时最长的作业的时候,在这个作业的运行过程当中,其他耗时相比较短的作业也可以同时进行运行,这样也就体现除了一种并行的策略,实现了各机器的并行,节约时间。

使用python实现的代码如下:文章来源地址https://www.toymoban.com/news/detail-809180.html

def work(time,m):
    tmp=[0 for _ in range(m)]
    if len(time)<=m:
        return max(time)
    else:
        time.sort(reverse=True)
        tmp[0:m]=time[0:m]
        for t in time[m:]:
            min_=tmp.index(min(tmp))
            tmp[min_]+=t
    return max(tmp)

到了这里,关于python使用贪心算法解决作业调度问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法题:摆动序列(贪心算法解决序列问题)

    这道题是一道贪心算法题,如果前两个数是递增,则后面要递减,如果不符合则往后遍历,直到找到符合的。(完整题目附在了最后) 代码如下: 完整题目: 376. 摆动序列 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为  摆动序列 。 第一个差(如果

    2024年02月07日
    浏览(60)
  • Java 贪心算法经典问题解决

    题目 一块金条切成两半,是需要花费和长度数值一样的铜板的。比如 长度为20的 金条,不管切成长度多大的两半,都要花费20个铜 板。一群人想整分整块金 条,怎么分最省铜板? 例如,给定数组{10,20,30},代表一共三个人,整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分

    2024年02月16日
    浏览(52)
  • 算法 主持人调度-(双指针+贪心)

    牛客网: BM96 题目: 一个主持人只能参加一个活动,至少需要多少主持人 思路: 对start, end排序从小到大;初始化指针l, r = 0, 0;start[r]= end[l]时需要累加人数同时r++,否则l++,r++同时移动;直至不再满中ln r n 代码:

    2024年02月07日
    浏览(35)
  • <算法>贪心策略设计并解决会场安排问题

    🎉  每个不曾起舞的日子都是对生命的辜负 🎉 写在前面 期末考试邻近,为了更好的应对《算法设计与分析》这门课程,我把书上以及老师讲过的案例都详细的做一个重现及解剖,让你熟记每一个潜在的考点,希望能给大家帮助。 🎉 目录 问题描述  贪心策略  算法设计

    2024年02月08日
    浏览(91)
  • 贪心算法解决背包问题和动态规划解决0-1背包问题(c语言)

    运行结果如下: 运行结果如下: 总结: 贪心算法: 每一步都做出当时看起来最佳的选择,也就是说,它总是做出局部最优的选择。 贪心算法的设计步骤: 对其作出一个选择后,只剩下一个子问题需要求解。 证明做出贪心选择后,原问题总是存在最优解,即贪心选择总是安

    2024年02月04日
    浏览(53)
  • 基于遗传算法解决流水车间调度问题

    问题描述 n 个工件要在 m 台机器上加工,每个工件需要经过 m 道工序,每道工序要求不同的机器,n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的,设为 t i j ( i = 1.... , n ; j = 1 , . . . , m ) t_{ij}(i = 1....,n; j = 1,...,m) t ij ​ ( i = 1.... , n ; j = 1 , ... , m ) 问

    2024年02月07日
    浏览(38)
  • 带有期限的作业排序问题(贪心)

    转载【算法设计】带有期限的作业排序(贪心算法)_带时限的作业排序贪心算法-CSDN博客 主要是给自己加注释   已知:         n个作业,每个作业都有一个截止期限di,当且仅当作业i在它的期限截止以前被完成时,可获得pi的效益。 求:         可行解集合J   测试

    2024年02月05日
    浏览(48)
  • 详解遗传算法与生产作业调度

    🍎道阻且长,行则将至。🍓 根据遗传学的理论,生物的进化发展来源于三大动力:自然选择、遗传和突变。自然选择就是自然环境对不同表现型生物有不同的影响,使用适应度来度量这种影响,适应度较好的生物个体对环境亲和力较高,有较大的几率可以存活下来,而适应

    2023年04月23日
    浏览(40)
  • 遗传算法GA解决混合流水车间调度问题HFSP

    混合流水车间调度问题(HFSP)是传统流水车间调度问题(FSP)的拓展,本文针对HFSP问题进行描述、建模和求解。 通常模型做如下假设: HFSP符号描述: 决策变量: 主要约束: 优化目标: 本节使用带精英保留的遗传算法GA对HFSP问题进行求解。求解结果如下: 自定义算例如下:

    2024年02月11日
    浏览(45)
  • 操作系统有关进程调度算法(含先来先服务,短作业优先,优先级调度算法和时间片轮转调度算法)

    本文采用的进程调度算法有:先来先服务,短作业优先,优先级调度算法和时间片轮转调度算法。 针对这四种算法,我采用的是建立数组结构体,如: 先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。采用FCFS算法,每次从

    2024年02月03日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包