染色装箱问题及其启发式算法  

Two Variations of Bin Packing and Bin Covering Problems and their Algorithms

作　　者：孙春玲[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南民族大学学报（自然科学版）》2005年第4期286-288,共3页Journal of Yunnan Minzu University:Natural Sciences Edition

基　　金：国家自然科学研究基金资助项目(10271103);云南省自然科学研究基金资助项目(2003F0015M)

摘　　要：研究了装箱问题的一个新颖的衍生问题:染色装箱问题,即在装箱问题中,给每个物件指定一个颜色,要求每个箱子中所装的物件颜色各不相同,使得所需要的箱子数目尽可能少.该问题是通常装箱问题的一种推广.笔者给出了染色装箱问题的一个启发式算法,同时研究了只有两种颜色的染色装箱问题:即2-色装箱问题,并给出了一个最优算法.A new variant of bin packing problem is studied in this paper, which is called as the bin coloring packing problem （BCPP） ： we are given a sequence L = （a1 ,a2 ,…,an） of n items, each with a size s（a,） E （0, 1 ] and a color r, （ we may have ri= rj for some i≠j）, and we are asked to pack them into a minimum number of unit -capacity bins, where the different items in the same bin must be assigned to the different colors. This problem isexpansion of the original bin packing problem and it is also NP - hard. We design a heuristic algorithm for the general version and an optimal algorithm for the special version where there are only two colors used.

关 键 词：染色装箱问题 启发式算法 最优算法 

分 类 号：O157.6[理学—数学] TP301.5[理学—基础数学]