Solving Multi-objective Two Dimensional Rectangle Packing Problem
The work presented here solves rectangular packing problem in which rectangular items are packed on a rectangular stock sheet. Multiple objectives have been considered which are optimized using rectangle packing algorithm with different heuristics. A math
- PDF / 324,413 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 181 Views
Sri Guru Granth Sahib World University, Fatehgarh Sahib, India [email protected] 2 University Computer Centre, Punjabi University, Patiala, India
Abstract. The work presented here solves rectangular packing problem in which rectangular items are packed on a rectangular stock sheet. Multiple objectives have been considered which are optimized using rectangle packing algorithm with different heuristics. A mathematical formulation has been presented to solve the problem. Computational experiments have been conducted to find the best packing layout for the problem. Keywords: Nesting problem cutting
Multi-objective optimization
Non-guillotine
1 Introduction Nesting problems are two-dimensional cutting and packing problems which select the best possible arrangement for two-dimensional regular or irregular shapes on a larger stock sheet such that minimum stock sheet material is wasted. These problems have been a classic subject in computer science research. Nesting problems find wide applicability in many industries ranging from small scale industries like leather[1], paper [2, 3], glass, wood, sheet metal cutting to large scale industries related to ship building, automobiles and VLSI design. The two-dimensional nesting problems belong to the class of NP-complete problems [4–6] where finding exhaustive solutions becomes difficult as the size of the problem increases. Thus, heuristic techniques are used to find optimum arrangement for pieces on a stock sheet. In this paper, a special variation of nesting problem, two-dimensional non-guillotine rectangular stock cutting problem with multiple objectives is considered. The rectangle packing algorithm used by Singh and Jain in 2009 [7] has been redrafted to generate 60 feasible patterns using heuristics. The remainder of the paper is organized as follows: Sect. 2 discusses the problem definition, Sect. 3 covers the multiobjective nature of the problem, Sect. 4 describes the mathematical formulation, Sect. 5 discusses the results and conclusion and future scope is covered in Sect. 6.
© Springer Nature Singapore Pte Ltd. 2017 K. Deep et al. (eds.), Proceedings of Sixth International Conference on Soft Computing for Problem Solving, Advances in Intelligent Systems and Computing 547, DOI 10.1007/978-981-10-3325-4_19
Solving Multi-objective Two Dimensional Rectangle Packing Problem
189
2 Problem Definition The two-dimensional non-guillotine rectangle packing problem consists of a large rectangular stock sheet of given length L and width W and an order list of small rectangular items i of specified length li and width wi, i = 1,2,3…n, to be cut from stock sheet such that no two items overlap each other. The items are allowed to rotate by 90◦. The cuts are non-guillotine which means that the cuts may not go from one end of the stock sheet to another end [8] (Fig. 1). The primary objective of this problem is to find a layout of items on stock sheet which maximizes the utilization of stock sheet. Wascher et al. in 2007 [9] gave a typology of cutting and packing problems. Th
Data Loading...
