Exact Algorithms for a Loading Problem with Bounded Clique Width

References

• Baker B. S., Coffman E. G. Mutual exclusion scheduling. Theoret. Comput. Sci. (1996) 162:225–245Crossref, Google Scholar
• Barnhart C., Johnson E. D., Nemhauser G. L., Salvelsbergh M. W. P., Vance P. H. Branch-and-price: Column generation for solving huge integer programs. Oper. Res. (1998) 46:316–329Link, Google Scholar
• Bischoff E. E. Stability aspects of pallet loading. OR Spektrum (1991) 13:189–197Crossref, Google Scholar
• Boudhar M. Scheduling a batch processing machine with bipartite compatibility graphs. Math. Methods Oper. Res. (2003) 57:513–527Crossref, Google Scholar
• Brandstädt A., Lozin V. V. On the linear structure and clique-width of bipartite permutation graphs. Ars Combinatoria (2003) LXVII:273–281Google Scholar
• Brandstädt A., Dragan F. F., Le H.-O., Mosca R. New graph classes of bounded clique-width. Theory Comput. Systems (2005) 38:623–645Crossref, Google Scholar
• Byun C. Lower bounds for large-scale set partitioning problems. (2001) . ZIB-Report 01-06, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Berlin, GermanyGoogle Scholar
• Courcelle B., Olariu S. Upper bounds to the clique-width of graphs. Discrete Appl. Math. (2001) 101:77–114Crossref, Google Scholar
• Courcelle B., Engelfriet J., Rozenberg G. Handle-rewriting hypergraph grammars. J. Comput. System Sci. (1993) 46:218–270Crossref, Google Scholar
• Desrosiers J., Dumas Y., Desrochers M., Soumis F., Sanso B., Trudeau P. A breakthrough in airline crew scheduling. (1991) Proc. 26th Annual Meeting of the Canadian Transportation Res. ForumMontreal, Québec, Canada:464–478Cahiers du GERAD G-91-11Google Scholar
• Dilworth R. P. A decomposition theorem for partially ordered sets. Ann. Math. (1950) 51:161–166Crossref, Google Scholar
• Dyckhoff H. A typology of cutting and packing problems. Eur. J. Oper. Res. (1990) 44:145–159Crossref, Google Scholar
• Espelage W., Gurski F., Wanke E. How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. Proc. 27th Workshop on Graph-Theoretic Concepts in Comput. Sci. (WG 2001), Lecture Notes in Comput. Sci. (2001) 2204(Springer Verlag, Heidelberg, Germany)117–128Crossref, Google Scholar
• Felsner S., Wernisch L. Maximum k-chains in planar point sets: Combinatorial structure and algorithms. SIAM J. Comput. (1998) 28:192–209Crossref, Google Scholar
• Finke G., Jost V., Queyranne M. Batch processing with interval graph compatibilities between tasks. Proc. Discrete Optim. Methods in Production and Logist. (2004) Omsk-Irkutsk, Russia:88–94Google Scholar
• G Y.-G., Kang M.-K. A fast algorithm for two-dimensional pallet loading problems of large size. Eur. J. Oper. Res. (2001) 134:193–202Crossref, Google Scholar
• Golumbic M. C.Algorithmic Graph Theory and Perfect Graphs (1980) (Academic Press, New York) Crossref, Google Scholar
• Jansen K. The mutual exclusion scheduling problem for permutation and comparability graphs. Inform. Comput. (2003) 180:71–81Crossref, Google Scholar
• Letchford A. N., Amaral A. Analysis of upper bounds for the pallet loading problem. Eur. J. Oper. Res. (2001) 132:582–593Crossref, Google Scholar
• Moonen L. S. Optimaliseren van een productieproces. (2001) . Master’s thesis, Department of Mathematics, Maastricht University, Maastricht, The Netherlands (in Dutch)Google Scholar
• Morabito R., Morales S. A simple and effective procedure for the manufacturer’s pallet loading problem. J. Oper. Res. Soc. (1998) 49:819–828Crossref, Google Scholar
• Ryan D. M., Foster B. A., Wren A. An integer programming approach to scheduling. Computer Scheduling of Public Transport: Urban Passenger, Vehicle and Crew Scheduling (1981) (North-Holland, Amsterdam, The Netherlands) 269–280Google Scholar
• Scheithauer G., Terno J. The G4-heuristic for the pallet loading problem. J. Oper. Res. Soc. (1996a) 47:511–522Crossref, Google Scholar
• Scheithauer G., Terno J. A heuristic approach for solving the multi-pallet packing problem. (1996b) . Working paper, Institute for Numerical Mathematics, Dresden University of Technology, Dresden, GermanyGoogle Scholar
• Shum H., Trotter L. E. Cardinality-restricted chains and antichains in partially ordered sets. Discrete Appl. Math. (1996) 65:421–439Crossref, Google Scholar
• Terno J., Scheithauer G., Sommerweiß U., Riehme J. An efficient approach for the multi-pallet loading problem. Eur. J. Oper. Res. (2000) 123:372–381Crossref, Google Scholar
• Vance P. H., Atamtürk A., Barnhart C., Gelman E., Johnson E. L., Krishna A., Mahidhara D., Nemhauser G. L., Rebello R. A heuristic branch-and-price approach for the airline crew pairing problem. (1997) . Technical Report LEC-97-06, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GAGoogle Scholar
• Vanderbeck F. Decomposition and column generation for integer programs. (1994) . Ph.D. thesis, Faculté des Sciences Appliquées, Université Catholique de Louvain, Louvain-la-Neuve, BelgiumGoogle Scholar
• Wanke E. k-NLC graphs under polynomial algorithms. Discrete Appl. Math. (1994) 54:251–266Crossref, Google Scholar