L. V. Kantorovich and cutting-packing problems: new approaches to combinatorial problems of linear cutting and rectangular packing

E. A. Mukhacheva   ; A. S. Mukhacheva

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems. Part XI, Tome 312 (2004), pp. 239-255

Résumé

In the middle of the XXth century L. V. Kantorovich and V. A. Zalgaller suggested to solve the problems of thrifty material using while cutting it with the help of linear programming. This resulted in permanent relaxation of planning the rational cutting problem and, as a matter of fact, closed up the problem in mass production. The paper briefly describes the ways of realization of the method for one-dimensional cutting. The problem is extended to integer cases typical for any cutting problem. The block structure technology has been worked out for two-dimensional cutting-packing problems. This technology reduces to solution of some special planning problem of one-dimensional cutting that can be solved by linear programming with the help of simple heuristics. Some calculating schemes and results of numerical experiments with wasteless packing are also shown in the paper. The comparison with other algorithms proves the efficiency of the block method.

Bibliographie

[1] M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[2] L. V. Kantorovich, V. A. Zalgaller, Ratsionalnyi raskroi promyshlennykh materialov, Nauka SO, Novosibirsk, 1971

[3] L. V. Kantorovich, V. A. Zallgaller, Raschet ratsionalnogo raskroya materialov, Lenizdat, L., 1951

[4] A. S. Mukhacheva, S. Kh. Kurelenkov, M. A. Smagin, R. R. Shirgazin, “Metody lokalnogo poiska optimuma pryamougolnoi upakovki s ispolzovaniem dvoistvennoi skhemy”, Informatsionnye tekhnologii, 10 (2002), 26–31

[5] A. S. Mukhacheva, A. V. Chiglintsev, M. A. Smagin, E. A. Mukhacheva, “Zadachi dvumernoi upakovki: razvitie geneticheskikh algoritmov na baze smeshannykh protsedur lokalnogo poiska optimalnogo resheniya”, prilozhenie, Informatsionnye tekhnologii, 9 (2001)

[6] E. A. Mukhacheva, Ratsionalnyi raskroi promyshlennykh materialov. Primenenie v ASU, Mashinostroenie, M., 1984

[7] E. A. Mukhacheva, A. I. Ermachenko, T. M. Sirazetdinov, A. R. Usmanova, “Metod poiska minimuma s zapretami v zadachakh dvumernogo gilotinnogo raskroya”, Informatsionnye tekhnologii, 6 (2001), 25–31

[8] E. A. Mukhacheva, A. S. Mukhacheva, A. V. Chiglintsev, “Geneticheskii algoritm blochnoi struktury v zadachakh dvumernoi upakovki”, Informatsionnye tekhnologii, 11 (1999), 13–18

[9] E. A. Mukhacheva, A. S. Mukhacheva, A. F. Valeeva, V. M. Kartak, “Metody lokalnogo poiska optimuma v zadachakh ortogonalnogo raskroya i upakovki: analiticheskii obzor i perspektivy razvitiya”, prilozhenie, Informatsionnye tekhnologii, 5 (2004), 2–17

[10] A. S. Mukhacheva, “Tekhnologiya blochnykh struktur lokalnogo poiska optimuma v zadachakh pryamougolnoi upakovki”, prilozhenie, Informatsionnye tekhnologii, 2004, no. 5, 18–31

[11] I. P. Norenkov, “Evristiki i ikh kombinatsii v geneticheskikh metodakh diskretnoi optimizatsii”, Informatsionnye tekhnologii, 1 (1999), 2–7

[12] I. V. Romanovskii, Algoritmy resheniya ekstremalnykh zadach, Nauka, M., 1977 | MR

[13] G. Belov, G. Scheithauer, “A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths”, European Journal of Operational Research, 141 (2002), 274–294 | DOI | MR | Zbl

[14] H. Dyckhoff, G. Scheithauer, J. Terno, “Cutting and packing”, Annotated Bibliographies in Combinatorial Optimization, eds. M. Dell'Amico, F. Maffioli, S. Martello, John Wiley, 1997, 393–412 | MR

[15] H. Dykhoff, “A typology of cutting and packing problems”, European Journal of Operational Research, 44 (1990), 145–159 | DOI | MR

[16] P. C. Gilmore, R. E. Gomory, “A linear programming approach to the cutting-stock problem”, Operations Research, 9 (1961), 849–859 | DOI | MR | Zbl

[17] E. Hopper, B. Turton, “An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem”, EJOR, 128 (2001), 34–57 | DOI | Zbl

[18] S. Imahori, M. Yaguira, T. Ibaraki, “Local search heuristics for the rectangle packing problem with general spatial costs”, MIC'2001, 4th Metaheuristics International Conference, 2001, 471–476

[19] O. Marcotte, “The cutting stock problem and integer rouding”, Math. Program., 33:1 (1985), 82–92 | DOI | MR | Zbl

[20] E. A. Mukhacheva, G. N. Belov, V. M. Kartak, A. S. Mukhacheva, “Linear one-dimensional cutting-packing problems: numerical experiments with sequential value correction method (SVC) and a modified branch-and-bound method (MBB)”, Pesquisa Operacional, 20:2 (2000), 153–168 | DOI | Zbl

[21] E. A. Mukhacheva, V. A. Zalgaller, “Linear programming cutting problems”, International Journal of Software Engineering and Knowledge Engineering, 3:4 (1993), 463–476 | DOI

[22] J. Terno, R. Lindeman, G. Scheithauer, Zuschnitprobleme und Ihre Praktische Losung, Leipzig, 1987