winney117 2013-10-31 15:05 采纳率: 0%
浏览 3075

怎么证明多机调度问题具有最优子结构和贪心选择性质?

问题描述:
设有n个独立的作业,由m台相同的机器进行加工处理。作业i所需的处理时间为t[i]。任何作业可以在任何一台机器上面加工处理,但未完工之前不允许中断处理。任何作业不能 拆分成更小的作业。 要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

算法分析: 采用最长处理时间作业优先的贪心选择策略,可以设计出解多机调度问题较好的近似算法。分n<=m(作业数小于机器数),n>m(作业数大于机器数)求解。假定有7个独立作业,所需处理时间分别为{2,14,4,16,6,5,3},由三台机器M1,M2,M3加工。按照贪心算法产生的作业调度如下图所示,所需总加工时间为17.

  • 写回答

0条回答

    报告相同问题?

    悬赏问题

    • ¥50 永磁型步进电机PID算法
    • ¥15 sqlite 附加(attach database)加密数据库时,返回26是什么原因呢?
    • ¥88 找成都本地经验丰富懂小程序开发的技术大咖
    • ¥15 如何处理复杂数据表格的除法运算
    • ¥15 如何用stc8h1k08的片子做485数据透传的功能?(关键词-串口)
    • ¥15 有兄弟姐妹会用word插图功能制作类似citespace的图片吗?
    • ¥200 uniapp长期运行卡死问题解决
    • ¥15 latex怎么处理论文引理引用参考文献
    • ¥15 请教:如何用postman调用本地虚拟机区块链接上的合约?
    • ¥15 为什么使用javacv转封装rtsp为rtmp时出现如下问题:[h264 @ 000000004faf7500]no frame?