本論文主要是探討貨物線上及時裝載入貯藏櫃的裝箱問題。基於運輸安全及平穩度的要求，較長(或較重)的貨物必需裝載於貯藏櫃的底部，且不得置放於較短(或較輕)的其它貨物之上。這樣的限制條件我們稱之為LIB (Longest　Item　at　the　Bottem)。裝箱問題就算沒有LIB限制式就已經是NP-hard，因此本論文將探討三種啟發示演算法(first　fit,　best fit,　harmonic　fit)計算精度的估計。我們首先對貨櫃的裝載率加以分類，從而估計出最佳裝載方式下，所需貨櫃總長度的下界值。然後再計算這三種演算法AAR值的上界(演算法所求出的值比上最佳值)。最後再利用數值結果來比較這三種演算法的效率及驗証我們所估計出的AAR值上界。

In　this　thesis,　we　study　the　online　bin　packing　problem　with　variable　bin　sizes.　Based　on　the　safety　and　stability　requirement　during　the　shipment,　longer(heavier)　items　should　be　placed　at　the　bottom　of　a　bin　and　can　not　be　placed　anywhere　above　the　shorter(lighter)　items.　We　call　this　as　the　LIB　constraint(Longest　Item　at　the　Bottom).　Bin　packing　problem　is　a　difficult　NP-hard　problem　even　with　the　absence　of　the　LIB　constraint.　Therefore,　we　try　to　estimate　the　asymptotic　approximation　ratio(AAR)(the　ratio of　the　value　by　the　algorithm　to　the　optimal　value)　for　three　heuristic　algorithms:　First　fit,　Best　fit,　and　Harmonic　fit.　To　do　this,　we　first　classify　the　used　bins　according　to　their　space　utilization　so　that　a　lower　bound　for　the　unknown　optimal　value　can　be　estimated.　Then　we　compute　an　upper　bound　for　the　AAR.　Finally,　we　implement　the　three　algorithms　to　compare　the　practical　performance　and　justify　the　upper　bound　for　the　AAR　ratio.

[1]　C.　Babel,　Algorithms　for　on-line　bin-packing　problems　with　cardinality　cinstraints,　Discrete　Applied　Mathematics　143,　238-251,　2004
[2]　R.　Burkard,　G.　Zhang,　Bounded　space　on-line　variable-sized　bin　packing,　Acta　Cybernet　13,　63-76,　1997
[3]　M.　Carlyle,　K.　Knutson,　J.　Fowler,　Bin　covering　algorithms　in　the　second　stage　of　the　lot　to　order　matching　problem,　Journal　of　the　Operational　Research　Society　52,　1232-1243,　2001
[4]　S.　A.　Cook,　The　complexity　of　theorem-proving　procedures,　Proc.　3rd　Annual　ACM　Symp.　on　the　Theory　of　Computing,　151-158,　1971
[5]　J.　Csirik,　An　on-line　algorthm　for　variable　sized　bin　packing,　Acta　Informatica　26,　697-709,　1989
[6]　P.　Dell’Olmo,　H.　Kellerer,　M.　G.　Speranza,　Z.　Tuza,　A　13/12　approcimation　algorithm　for　bin　packing　with　extendable　bins,　Information　Processing　Letters　65,　229-233,　1998
[7]　Fernandez　W　de　la　vega,　G.　S.　Lueker,　Bin　packing　can　be　solved　within　1+　in　linear　time,　Combinatorics　1,　349-355,　1981
[8]　D.　K.　Friesen,　M.　A.　Langston,　Varible　sized　bin　packing,　SIAM　J.　Comput.　15,　222-230,　1986
[9]　D.　K.　Friesen,　M.　A.　Langston,　A　storage-size　selection　problem,　Inform.　Process.　Lett.　18,　295-296,　1984
[10]　D.　S.　Johnson,　A.　Demers,　J.　D.　Ullman,　R.　L.　Graham,　Worst-Casw　performance　bounds　for　simple　one-dimensional　packing　algorthms,　SIAM　Journal　of　Computing　3,　299-325,　1974
[11]　J.　Johnson,　Fast　algorithms　for　bin　packing,　Journal　of　Computer　and　System　Science　8,　272-314,　1974
[12]　R.　M.　Karp,　Reducibility　among　combinatorial　problems,　Complexity　of　Computer　Computations,　R.　E.　Miller　and　J.　W.　Thatcher,　eds.,　Plenum　Press,　New　York,　85-104,　1972
[13]　N.　Kinnersley,　M.　Langston,　Online　varible-sized　bin　packing,　Discrete　Appl.　Math.　22,　143-148,　1989
[14]　CC.　Lee,　DT.　Lee,　A　simple　on-line　bin　packing　algorithm,　Journal　of　the　Association　for　Computing　Machinery　32,　562-572,　1985
[15]　J.　Y.　Lin,　P.　Manyem,　R.　L.　Sheu,　Performance　Estimations　of　First　Fit　Algorithm　for　Online　Bin　Packing　with　Variable　Bin　Sizes　and　LIB　constraints
[16]　A.　Lodi,　 S.　Martello,　M.　Monaci,　Two-dimensional　packing　problems:　a　survey,　European　Journal　of　Operational　Research　141,　241-252,　2002
[17]　P.　Manyem,　Bin　packing　and　covering　with　longest　items　at　the　bottom:　online　version,　ANZIAM　J.43(E),　E186-E232,　2002
[18]　P.　Manyem,　Uniformly　sized　bin　packing　and　covering:　online　version,　J.　Misra(Ed.),　Industrial　Mathematics　and　Statistics,　Narosa　Publishing　House(New　Delhi),　447-485,　2003
[19]　P.　Manyem,　Approximation　lower　bounds　in　online　LIB　bin　packing　and　covering,　J.　Automata,　Languages　and　Combinatorics　8,　663-674,　2003
[20]　P.　Ramanan,　D.　Brown,　C.　Lee,　D.　Lee,　On-line　bin　packing　in　linear　time,　J.　Algorithms　10,　305-326,　1989
[21]　M.　B.　Richey,　Improved　bounds　for　harmonic-based　bin　packing　algorithms,　Discrete　Applied　Mathematics　34,　203-227,　1991
[22]　Steven,　S.　Seiden,　An　optimal　online　algorithm　for　bounded　space　variable-sizes　bin　packing,　SIAM　J.　Discrete　Math.　Vol.　14　No.　4,　458-470,　2001
[23]　A.　V.　Vliet,　Optimal　on-line　algorithms　for　variable-sizes　bin　covering,　Information　Processing　Letters,　277-284,　1992
[24]　X.　Wenxun,　C.　Feng,　A-shaped　bin　packing:　worst　case　analysis　via　simulation,　Journal　of　Industrial　and　Management　Optiminzation　Vol.1　No.3,　323-335,　2005
[25]　W.　Xing,　A　bin　packing　problem　with　over-sized　items,　Operations　Research　Letters　30,　83-88,　2002
[26]　G.　Woeginger,　Improved　space　for　bounded-space,　on-line　bin-packing,　SIAM　J.　Discrete　Math.　6,　575-581,　1993
[27]　A.　C.　C.　Yao,　New　algorithms　for　bin　packing,　J.　ACM　27,　207-227,　1980
[28]　G.　Zhang,　Worst-case　analysis　of　the　FFH　algorithm　for　online　variable-sized　bin　packing,　Computing　56,　165-172,　1996
[29]　G.　Zhang,　Parameterized　on-line　open-end　bin　packing,　Computing　60,　267-273,　1998