International Journal of Applied Engineering Research

In the rectangle-packing problem, rectangular parts are placed onto a rectangular stock sheet, which is bigger in size in comparison to items with the aim of minimizing the unused space. This problem belongs to class of NPcomplete problems where computation time for an exact solution increases with N (total items considered in the problem) and become rapidly prohibitive in cost as N increases. The solution approach to these problems lies in finding in optimal solutions while reducing the exhaustive search of all possible arrangements of nesting the parts and subsequently checking upon the execution time. Usually, various heuristic rules are proposed to generate different patterns that are near optimal. These heuristics are generally the priority rules used to allocate patterns to the stock sheet sequentially.

In this paper, the reworked rectangle-packing algorithm suggested by Cheok-AYC Nee (1991) has been used to generate 120 feasible patterns with different sheet utilisation factors. The algorithm can be used for different object sizes available in varying quantity each having many feasible patterns so as to meet the demand for items in a holistic manner. Also, the solution can be obtained by solving the LPP (Linear programming problem) that takes in most viable solutions generated by the revised heuristic, requirements of shapes and availability of sheets.

In the present study a comparison has been made that makes use of LPP to look for solution Vs. gradually meeting the demand by taking optimal feasible solutions generated by the heuristic that gives the best sheet utilization and exhausting the demand at each step till the demand is fully met.