作业调度问题

参考文献

问题描述

有n个作业需要在2台机器M1 和M2组成的流水线上完成加工。每个作业都必须先在 M1 上加工，然后在 M2 上加工。M1和M2加工作业i所需的时间分别记作 a_i和b_i，每台机器同一时间最多只能执行一个作业。

请确定这n个作业的最优加工顺序，使得从第一个作业在机器上开始加工，到最后一个作业在机器上加工完成所需的时间最少。

问题分析

算法设计

  • johnson不等式。满足min{bi,aj}>= min{bj,ai}则表示i和j满足johnson不等式。则意味着i在j前执行，不会使的结果变坏。
  • 查参考文献。

算法分析

  • 时间复杂度O(nlogn)按json不等式排序的时间复杂度。

算法实现