There Are Several Classes Of Problems Related To Boxing

Bin Packing is one of the fundamental problems in combinatorial optimiza-tion, which plays an important role in the algorithmic area. Since David John-son's PhD thesis on bin packing appeared in 1973, there have been a large number of related models and fruitful results, and such a situation never ends. Not an exception, in this thesis., we will concentrate on three bin packing models as follows.?Scheduling on a minimum numbers of machines:We are given a job set L={J1,J2,...,Jn}, each job Ji with a release time ri, a deadline di and a processing time pi. Ji can be denoted by (ri,di,Pi). The goal is to find a non-preemptive schedule such that all jobs meet their release times and deadlines and the number of machines used to process all jobs is minimum. If all jobs have equal release times and equal deadlines, we have the classical bin packing problem. So it is a generalization of the bin packing problem. Cieliebak et al. [4] presented an approximation algorithm GBF and proved that the asymptotic worst-case ratio is at most 9 if all the processing time are equal. For the case that all the release times are equal, they provided an approximation algorithm DBF whose asymptotic worst-case ratio is at most 4.6. We revisit the above two cases. For the case that all the release times are equal, we give a simple approximation algorithm and show a tight absolute worst-case ratio of two. For the case that all the processing times are equal, we achieve a new upper bound of 6 for GBF. We also present an instance showing a lower bound of 4 for GBF.?Bin packing game:The classical bin packing system has only one decision maker who assigns items into bins without considering the own interest of each item. However, in many systems the users (or items) are likely to behave selfishly, namely each user aims to optimize his own performance without coordination with the other users. We assume that all the bins have the same cost of one and the cost of a bin is shared by all of its items. If no item can benefit by changing its bin while the other items stay at their bins, then the current state constitutes a Nash equilibrium. Bilo[2] proved that the price of anarchy of bin packing game is in [1.6,1.667]. We improve his result and prove that the value is in [1.6416,1.6475]. We also provide a lower bound and an upper bound of the price of anarchy for the parametrical bin packing game. Bilo[2] showed that a Nash equilibrium can always be obtained after a finite number of migrations (bounded by an exponential number) starting from any feasible packing. He further noted that there is always an optimal packing which is a Nash equilibrium, and thus computing a best Nash equilibrium is N P-hard. However it was open if computing a Nash equilibrium is hard or not. In this paper we derive a polynomial time bin packing algorithm finding a Nash equilibrium, thus solving this problem.?Bin packing with precedence constraints:Given a finite set L and a partial order (known as a precedence relation) defined on L, we wish to find an ordered partition of L. For two arbitrary items with precedence a(?) b, if b is not allowed to packed in the bins opened before the bin contains a, then it is (?) bin packing problem; if b is only allowed to packed in the bins opened after the bin contains a, then it is a (?) bin packing problem. For the (?) bin packing problem, Wee and Magazine[33] proved that the the generalized FF algorithm is a 2-factor approximation algorithm. We generalize their result to the parameterized (?) bin packing problem and prove that RGFF?= 2 if1/2?x?1 and RGFF?=1/(1-x) if 1/(k+1)?x<1/k(k?2). We also prove that the asymptotic worst-case ratio of any online (?) bin packing algorithm is at least 2. For the (?) bin packing problem, Garey et al.[12] estimated the asymptotic worst-case ratio of the generalized FF algorithm. Similarly we generalize their result to the parameterized (?) bin packing problem and prove that RGFF?=2.7 if 1/2<x?1 and RGFF?= 2+1/k if 1/(k+1)?x?1/k(k?2). We prove that the asymptotic worst-case ratio of any online (?) bin packing algorithm is at least 2.6910. The above three problems are studied, respectively, in Chapters 2-4, while Chap-ter 1 gives an introduction on bin packing and its related models.