Authors V.N. Balabanov, Y.A. Skobtsov
Month, Year 01, 2014 @en
Index UDC 519.854.2
Abstract A new metaheuristic solution method is presented for multi-objective cutting stock problem, which arises when roll materials are cut using slitting lines. The mathematical model of the combinatorial optimization problem in question is built on the basis of the existing integer linear programming model. Two objective functions are constructed one of which is related to material usage and the other to equipment changeovers. The proposed solution method is based on evolutionary computation and adaptive pattern generation. The choice of coding scheme used to represent solutions in evolutionary algorithm is influenced by the combinatorial structure of the original cutting stock problem. One of the main features of the proposed evolutionary method is the use of the complex five-component mutation operator. To obtain a fitness function original multi-objective problem is reformulated as a single-objective problem through replacement of the vector criterion with weighted sum of the two objective functions. Pattern generation is treated as a knapsack problem, which, in turn, is solved with modified version of the existing randomized algorithm. A new suite of test problems is proposed and used to evaluate performance of the method in computational experiments. The results show that the proposed approach is feasible and could be adapted to solve multi-objective cutting stock problems of similar structure.

Download PDF

Keywords Cutting stock problem; roll materials; multiobjective model; combinatorial optimization; evolutionary algorithm
References 1. Канторович Л.В. Математические методы в организации и планировании производства. – Л.: Изд-во ЛГУ, 1939. – 68 с.
2. Скобцов Ю.А., Балабанов В.Н. К вопросу о применении метаэвристик в решении задач рационального раскроя и упаковки // Вестник Хмельницкого национального университета. – 2008. – Т. 1, № 4. – С. 205-217.
3. Haessler R.W. Selection and design of heuristic procedures for solving roll trim problems // Management Science. – 1988. – Vol. 34, № 12. – P. 1460-1471.
4. Vahrenkamp R. Random search in the one-dimensional cutting stock problem // European Journal of Operational Research. – 1996. – Vol. 95, № 1. – P. 191-200.
5. Скобцов Ю.А. Основы эволюционных вычислений: Учебное пособие. – Донецк: ДонНТУ, 2008. – 326 с.
6. Michalewicz Z. Genetic algorithms + data structures = evolution programs. – 3rd ed. – Berlin [etc.]: Springer-Verlag, 1998. – 387 p.
7. Deb K. An efficient constraint handling method for genetic algorithms // Computer Methods in Applied Mechanics and Engineering. – 2000. – Vol. 186, № 2–4. – P. 311-338.
8. Martello S., Toth P. Knapsack problems: algorithms and computer implementations. – Chichester [etc.]: John Wiley & Sons Ltd., 1990. – 318 p.
9. GitHub: EA-based solver for 1.5D MSSCSP [Electronic resource]. – 2013. – [Cited 2013, 1 June]. – Available from:
10. Mladenovic N., Hansen P. Variable neighborhood search // Computers & Operations Research. – 1997. – Vol. 24, № 11. – P. 1097-1100.

Comments are closed.