装箱问题和排序问题课件

装箱问题和排序问题

1装箱问题和排序问题本讲主要内容装箱问题（Bin

Packing）最小完工时间安排（排序问题）（Minimum

Makespan

Scheduling)2本讲主要内容2BinPacking装箱问题：给定n个物件，大小为用单位体积的箱子来装这些物件，找一个装箱方案使得所用的箱子数目最少？通俗地说，把分成最少的组数，使得每组数的和不超过1。在工业中有许多应用，譬如在下料问题中，箱子代表标准木料的长度，而表示实际问题中需要裁截成的木料长度。当然，需要的标准料越少越好。3BinPacking3一个2倍近似算法4一个2倍近似算法4证明5证明5一个不可逼近性结果6一个不可逼近性结果67788NP-难问题按照其可逼近性分类没有常数倍近似比：Set-Cover，TSP，MaximumIndependentSet,有常数倍近似比但不能任意接近1：Vertex-Cover，Bin

Packing,

近似比可以为1+ε（任意逼近1）。Knapsack，Scheduling.9NP-难问题按照其可逼近性分类没有常数倍近似比：Set-C多项式时间近似方案（PolynomialTimeApproximationScheme,PTAS),渐近多项式时间近似方案10多项式时间近似方案（PolynomialTimeAppr一个渐进的PTAS11一个渐进的PTAS11限制装箱问题12限制装箱问题12限制装箱问题13限制装箱问题1314141515定理2的证明16定理2的证明161717算法总结18算法总结18排序问题排序问题（MinimumMakespanScheduling）

给定n个工件的加工时间以及一个整数m，给工件安排一个在m个相同机器上的加工顺序，使得最后的完工时间（makespan）最小。该问题是排序问题中最简单的问题。在生产调度中有广泛的应用。19排序问题排序问题（MinimumMakespanSchGraham的2-近似算法算法描述（List

Scheduling）

Step

1.将工件任意排序；

Step

2.将工件按照上述顺序分配给机器，将下一个工件安排给当前负荷最轻（剩余加工时间最少）的机器。直到所有工件加工完毕.

20Graham的2-近似算法算法描述（ListSchedu算法分析上述算法的要点是，让机器不要闲着，只要有机器加工完，就把排在最前面尚待加工的工件让该机器去做。算法分析的要点是：最小makespan取决于最后一个工件的完工时间，在最后一个活开始加工之前，没有机器是空闲的。21算法分析上述算法的要点是，让机器不要闲着，只要有机器加工完2222一个紧的例子23一个紧的例子23Lowest

Fit

Decreasing（LFD）算法描述（LFD）

Step

1.将工件按工时从高到低排列；

Step

2.将工件按照上述顺序分配给机器，将下一个工件安排给当前负荷最轻（剩余加工时间最少）的机器。直到所有工件加工完毕.24LowestFitDecreasing（LFD）算法描述2525262627272828排序问题的PTAS排序问题与装箱问题有如下紧密联系：排序问题存在最优解t，当且仅当n个大小分别为的物件可以装入m个容量为t的箱子。因此，可将排序问题自转化为装箱问题：令I表示n个物件大小；令表示能装下n个物件的容量为t的箱子的最少数目；则最小排序问题转化为：29排序问题的PTAS排序问题与装箱问题有如下紧密联系：29基本思想排序问题的最优解在[LB，2LB]内，利用二分搜索，将问题转化为装箱问题这一转化似乎不可行，因为装箱问题仍然是NP-难的但是，对于物件尺寸型号固定的限制装箱问题，有多项式算法30基本思想排序问题的最优解在[LB，2LB]内，利用二分搜索，不同物件型号数目固定的装箱问题31不同物件型号数目固定的装箱问题31动态规划32动态规划32动态规划（续）33动态规划（续）33动态规划（续）34动态规划（续）34把排序问题划归为限制装箱问题基本思想：如果我们能容忍在计算最小makespan问题的一点小的误差，则我们可把该问题在多项式时间内划归为限制装箱问题。主要有两种类型的误差：把物件的尺寸做一些调整，使得不同尺寸的数目有界。终止二分搜索，保证多项式时间算法。每种误差都可以做到任意小，但代价是计算时间的增加。但对固定的误差，我们可以得到多项式时间近似算法。35把排序问题划归为限制装箱问题基本思想：35箱子容量固定的装箱算法(核心算法）36箱子容量固定的装箱算法(核心算法）36核心算法（续）37核心算法（续）3