Research On Approximation Algorithms For Online Bin Packingand Hybrid Flow Shop Scheduling

Packing and scheduling are two classical combinatorial optimization problems,which have been playing very important roles in many industries,such as industrial production,logistics management,traffic planning.A lot of research work has been done with regard to this domain and it has laid solid foundation for analyzing the performance of approximation algorithms of other combinatorial optimization problems.In recent years,online bin packing with buffer has become a research hotspot.To the best of our knowledge,online bin packing algorithm with buffer of size two is the asymptotic competition ratio of 1.4444 given by Zheng et al.when the upper limit of item size is no more than 1/2.For the two-stage hybrid flow shop scheduling problem with a single machine at one stage and m identical machines at the other stage,Sun et al.provided an approximate algorithm with approximate ratio of 3 under specific conditions.Our work mainly improves and extends these results.For packing problem,two kinds of online models with constant size buffer and bounded space are studied.Online bin packing with buffer means that items can be put into the buffer when arriving.Firstly we classify all the items into serval types based on the idea of item size partition.The bins are categorized according to the combination characteristics of the final items while the packing decision selects the appropriate items from the buffer by category and load them into specific categories of bins.Then an online algorithm is proposed with buffer of size two A1 based on a weighting function approach,we prove that the APR of A1 was 1.4375 which is better than the previous result 1.444.Meanwhile we give a 1.4243-competition ratio approximation algorithm with buffer of size three.By constructing a new problem example,the lower bound of bin packing problem with buffer is improved from 1.3333 to 1.4230,which further tightens the bound between upper and lower bounds.For online packing of bounded space,two approximate algorithms with asymptotic competition ratio of 1.4243 and 1.4236 are given when 5 and 7 bins are opened.This improves the results of classical harmonic algorithm when using the same bounded space.Furthermore,two stage hybrid flow shop scheduling model which combines flow shop and parallel scheduling is studied.In this model there are a single machine at the first stage and m parallel machines at the second stage.Each task can be processed by multiple parallel machines simultaneously.We propose several approximation algorithms with approximate ratio less than or equal to 3 by using the existing parallel machine scheduling and strip packing results.Mean-while two special cases are discussed when the machines number of the second stage is 2 and3 respectively.Two approximation algorithms with approximation ratios of 2.5 and 2.67 un-der linear time complexity are proposed.Finally a new lower bound of the model is provided according to the classical Johnson algorithm.