Algorytm podziału i ograniczeń dla problemu rozkroju niegilotynowego

• Autorzy: Kierkosz, I. , Łuczak, M.

Warianty tytułu

EN

A branch and bound algorithm for non-guillotine cutting stock problem

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono algorytm optymalizacji rozkroju prostokątnej płyty na szereg prostokątnych elementów przy założeniu cięcia niegilotynowego oraz ograniczeniu na liczbę powtórzeń danego typu elementów w generowanych wzorach rozkroju. W proponowanym algorytmie przeszukiwanie przestrzeni dopuszczalnych rozwiązań odbywa się w oparciu o metodę podziału i ograniczeń. W pracy zamieszczono również wyniki obliczeń dla przykładowych zadań rozkroju dwuwymiarowego.

EN

The paper presents an algorithm for two-dimensional non-guillotine cutting stock problem. The problem consists in cutting many rectangular pieces, from a single rectangular sheet in such a way that the amount of trim loss is minimized. Moreover, there is a constraint on the maximum number of each type of piece that is to be produced. The proposed algorithm is based on a branch and bound method. Numerical examples to illustrate the proposed algorithm are solved.

Słowa kluczowe

PL

cięcie niegilotynowe; algorytm optymalizacji; rozkrój materiału; problem NP-trudny

EN

non-guillotine cutting; optimization algorithm; cutting-stock problem; NP-hard

• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2008
• Tom: z. 150
• Strony: 158-166
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Kierkosz, I.

autor

Łuczak, M.

• Politechnika Koszalińska,

Bibliografia

• 1. Baker B. S., Coffman Jr. E. G., Rivest R. L.: Orthogonal packing in two dimensions. SIAM Journal of Computing, vol. 9, 1980, p. 846-855.
• 2. Beasley J. E.: An exact two-dimensional non-guillotine cutting tree-search procedure. Operations Research vol. 33, 1985, p. 49-64.
• 3. Caprara A., Monaci M.: On the two-dimensional knapsack problem. Operations Research Letters, vol. 32, 2004, p. 2-14.
• 4. Christofides N., Whitiock C.: An algorithm for two-dimensional cutting problems. Operations Research, Vol. 2, 1977, p. 30-44
• 5. Hadjiconstantantinou E., Christofides N.: An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, vol. 83, 1995, p. 39-56.
• 6. Hadjiconstantantinou E., Iori M.: A hybrid genetic algorithm for the two-dimensional single large object placement problem. European Journal of Operational Research, vol. 183, 2007, p. 1150-1166.
• 7. Hassler R. W., Sweeney P. E.: Cutting stock problems and solution procedures. European Journal of Operational Research, vol 54, 1991, p. 141-150.
• 8. http://people.brunel.ac.uk/~mastjjb/jeb/info.html
• 9. Jakobs S.: On genetic algorithms for the packing of polygons. European Journal of Operational Research, vol 88,1996, p. 165-181.
• 10. Kierkosz L: Ewolucyjny algorytm optymalizacji dwuwymiarowego rozkroju niegilotynowego z ograniczeniami. W: Optymalizacja dyskretna. Robotyka i sterowniki programowalne, pod. red. R. Gessinga, T. Szkodnego, WNT, Warszawa 2004.
• 11. Kierkosz I.: Optymalizacja rozkroju niegilotynowego metodą przeszukiwania z powrotami. Materiały XXV Ogólnopolskiej Konferencji "Polioptymalizacja i komputerowe wspomaganie projektowania", Mielno 2007.
• 12. Lai K. K., Chan W. M.: An evolutionary algorithm for the rectangular cutting stock problem. International Journal of Industrial Engineering, vol 7, 1997, p. 130-139.
• 13. Leung T. W., Yung C. H., Troutt M. D.: Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem. Computers & Industrial Engineering, vol. 40, 2001, p. 201-214.
• 14. Wang P. Y.: Two algorithms for constrained cutting stock problem. Operations Research, vol. 31, 1983, p. 573-586.
• 15. Wäscher G., Haußner EL, Schumann H.: An improved typology of cutting and packing problems, European Journal of Operational Research, vol 183, 2007, p. 1109-1130.