Higher order block heuristics for 2D pallet loading problems with multiple box inputs. (2021)

• Record Type: Journal Article
• Authors: Arun Prasad, S.; Krishnakumar, P.
• Is Part Of: Materials today. Volume 46:Part 10(2021)
• Page Start: 4625
• Page End: 4633
• Publication Date: 2021
• Subjects: Non guillotine cuts -- Block heuristics -- Distributer's pallet loading problem -- Multiple box inputs -- NP Hard Problems; Materials science -- Congresses -- Periodicals; 620.1
• DOI: 10.1016/j.matpr.2020.10.280
• Languages: English
• ISSNs: 2214-7853

Abstract

Abstract: Pallet Loading Problem (PLP) is an important area of study in Industrial Engineering, as it is used for applications like Robotic Palletizing, Sheet metal cutting etc. The important objective of the PLP is to arrange the given input box types within the given Pallet area, to give the least wastage area in the pallet. The Pallet loading problem is differentiated as Manufacturer's Pallet Loading Problem (MPLP) and Distributer's Pallet loading problem (DPLP) based on the number of input types for arrangement. Among the various methods to solve this class of problems, Block Heuristics is the most widely used procedure. This objective of this study to overcome the limitation in the existing procedures in the class of cutting stock problems and Pallet Loading problem (PLP) with multiple input box types, where the maximum allowable number of input box types is 4. In the existing Block Heuristics procedures for multiple box input types, there is a constraint that a single block in Block Heuristics should contain boxes of same type. The work explains how different box types can be arrangement within a single block, thus overcoming the maximum number of input box limitation. Some of the new box arrangement structures, which are unique for the multiple box input scenario, are introduced and explained on how they are implemented in Non Guillotine block Heuristics. It also includes the extension of the higher order block heuristics from single box input case to the multiple box input scenarios. In general, higher order represents the usage of more than four Non Guillotine cuts in the heuristics and throughout the work on higher order block heuristics in this paper, the number of Non-guillotine cuts used to form the Block heuristics will be 6, hence termed as second order Non Guillotine Block Heuristics. Using a Literature Pallet Loading Problem input, both first and second order Non Guillotine Block Heuristics are tested and compared and their advantages over each other are presented.