The Research On Algorithms For The Relaxed And Longest Item At The Bottom Online Bin-Packing Problem

One-dimensional bin-packing problem has many important applications such as multiprocessor scheduling, resource allocation, real-world planning, and packing and scheduling optimization problems. In computer science, the algorithm Next Fit (NF) and First Fit (FF) algorithm have been great applied in file allocation, memory management .All the known online algorithms share the approach that no element can be moved from the bin it was first inserted in except for the algorithm by Giorgio present. Moreover the (?)(n)-space algorithms are offline on output, i.e., no algorithm releases any of the used bins until the end of the input list has been reached, while all the (?)(1)- space algorithms release all the bins except for a constant number of them.In order to obtain more efficient performances, a modified algorithm for relaxed model, called MAREL, is proposed in this paper. MAREL is based on a nonuniform partition of the interval (0,1] into eight subintervals : I₀,I₁,I₂,I₃,I₄,I₅, I₆,I₇.I₇-element can be collected together and considered as a single unit. This group can be inserted in I₁'s , I₂'s, I_'s, I₄'s or I₅'s gap.MAREL is an O(n)- space and O(n)-time algorithms with 1.25 approximation ratio. Its approximation ratio is below the theoretical 1.536... lower bound.Longest item at the bottom coloring bin packing problem (LIBCBPP) is proposed in this paper, in which larger ( or longer ) items be placed at the bottom of the bins, below smaller ( or shorter ) items. An approximation algorithm, called KC-A, to solve the LIBCBPP is proposed in this paper. It classifies the inputs first and then packs the objects in the LIB class with classical bin packing algorithm A.Also given are a lower bound of the worst-case asymptotic performance ratio of KC-A and analysis of the asymptotic worst-case ratio of KC-A algorithm when A is NF, FF.