装箱问题与排序问题.ppt

装箱间题和排序间题 雨安定通大字 XIAN JIAOTONG UNIVERSITY 装箱问题( Bin Packing) 。最小完工时间安排(排序问题)( Minimun Makespan Scheduling) 本讲主要内容 装箱问题:给定n个物件,大小为a1,a2,4n∈(0 用单位体积的箱子来装这些物件,找一个装箱方 案使得所用的箱子数目最少? 通俗地说,把a1,2…4n∈(0,分成最少的组数, 使得每组数的和不超过1 。在工业中有许多应用,譬如在下料问题中,箱子 代表标准木料的长度,而a;表示实际问题中需要 裁截成的木料长度。当然,需要的标准料越少越 好 Bin Packing First-Fit Alg orithm 1.将物件按任意顺序排列譬如 1,l2,… 2.在算法第步,假定a1,a2…41已经装箱 B1,B2…,B2现考虑1,若其不能装入任B1(≤j≤k) 则打开一个新的箱子B1,将a1装入其中。 3.直到所有物件装完。 个2倍近似算法 假定算法中用了m个箱子,则至少有n-1个箱子 装了不少于其容量的一半,即/2。(为什么?)因此, 又因为所有物件的大小之和是最优解opt的下界,即 a1≤Opt, 1-12opt即m≤2opt.