《平行机排序问题》PPT课件.ppt

平行机排序问题 Parallel Machine Scheduling,平行机排序问题,有多份文件需安排给几个打字员打印，若每个 打字员的打字速度相同，应该如何安排使得这 些文件在最短时间内完成。,问题描述,设有m台完全相同的机器 , n个互相独立的工 件 ，每个工件只需在一台机器上不中断的加工 一次，并设mn。设工件 的加工时间为 ，n个工 件在零时刻到达且所有机器在零时刻即可以加工，并要求 工件一旦在某个机器上加工就必须完毕，不允许中断。 问，如何安排这些工件的加工方案，才能使预定的目标函 数达到最优。,目标函数,假设在某种排序下 为工件 的加工结束时间，记 我们想要的目标函数为 ，它表示所有的工件加工工 作在最短时间内完成。若记 为机器 所要加工的所有 工件所需的总的时间，那么显然有 。 讨论这种所需加工时间最小的平行机排序问题也称为使时 间跨度最小的平行机排序问题。,整数线性规划（PMS）,说明,整数线性规划的解中不能说明次序，但是由于平行机排序 问题中，每台机器加工的总时间不受这台机器的加工次序 影响，所以这个整数线性规划的最优解即也就给出了最优 排序.,平行机排序问题与装箱问题,这两个问题成为对偶问题。把这两个问题中的箱子和机器 对应，物品与工件对应。那么装箱问题就是箱子长度固 定，目标是使箱子数最小；而平行机排序问题是箱子数固 定，目标是使得箱子长度最短。,平行机排序问题最优解的下界,定理：最优解值的一个下界为 。,近似算法,LS算法（List Scheduling） LPT算法（Largest Processing Time) Multifit算法 多项式时间近似方案,LS算法,将每一个工件分给最早空闲的机器。 为在线算法，时间复杂度 。,算法描述,绝对性能比,定理： 。,实例,5台相同机器，20个工件，加工时间分别为 10，13，15，8，5，9，21，17，12，7， 11，3，6，16，23，22，4，19，26，31,LPT算法,先将物品按照加工时间从大到小排序，然后按照LS算法排 序。 此算法为离线算法，时间复杂度,绝对性能比,定理： 。,实例,5台相同机器，20个工件，加工时间分别为 10，13，15，8，5，9，21，17，12，7， 11，3，6，16，23，22，4，19，26，31,Multifit算法,将m台机器看成m个箱子，n个工件看成有长度的物 品，其长度为该工件在机器上所需的加工时间。 先确定箱子容量的上下界 ，然后用FFD算法 判断是否能将所有物品放入容量为 的m个 箱子中，以调整上下界，迭代k次后以上界作为输出。,算法描述,该算法初始上界为CU取LPT算法所得到的解值，初始下界 为CL.,绝对性能比,定理：当Multifit算法中FFD算法迭代了k次，则对任意实 例I , 且常数部分 不可改进，即 。,实例,5台相同机器，20个工件，加工时间分别为 10，13，15，8，5，9，21，17，12，7， 11，3，6，16，23，22，4，19，26，31 迭代2次,多项式时间近似方案,取出mk个加工时间最长的工件，若mkn，则取出所有工件。 对取出的所有工件用枚举法求出最优排序。 由得到的mk个工件最优排序出发，将剩下的n-mk个工件用LS算法，安排它们的加工。,绝对性能比、时间复杂性,定理 ： ， 的时间复杂性为,实例,5台相同机器，20个工件，加工时间分别为 10，13，15，8，5，9，21，17，12，7， 11，3，6，16，23，22，4，19，26，31 取k=2,练习,6台相同机器，25个工件，加工时间分别为 10，13，15，27，18，8，5，9，21， 17，12，7，11，3，6，16，23，22，4， 19，26，31，1，2，9 分别用LS算法，LPT算法， Multifit算法 （迭 代3次）， 算法（取k=3）进行排序,