平行机排序问题ppt课件

平行机排序问题 Parallel Machine Scheduling1；.平行机排序问题有多份文件需安排给几个打字员打印，若每个打字员的打字速度相同，应该如何安排使得这些文件在最短时间内完成。2；.问题描述设有m台完全相同的机器 ,n个互相独立的工件 ，每个工件只需在一台机器上不中断的加工一次，并设mn，则取出所有工件。o对取出的所有工件用枚举法求出最优排序。o由得到的mk个工件最优排序出发，将剩下的n-mk个工件用LS算法，安排它们的加工。kS21；.绝对性能比、时间复杂性 定理：，的时间复杂性为 1111kSmRk kS(min,log)nkmOmmnn22；.实例5台相同机器，20个工件，加工时间分别为10，13，15，8，5，9，21，17，12，7，11，3，6，16，23，22，4，19，26，31取k=223；.练习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）进行排序kS24；.