I. INTRODUCTION

Competence of production system becomes a key factor of the success in today's competitive manufacturing environment and industries. Productivity can be enhanced by minimizing waste, lead time and hence reducing the cost of manufacture. For that reason, Operations Research plays a major role in minimizing manufacture waste. Many people including scientists have contributed and engaged in their research and other activities to overcome above challenges. BPP is become an important way of optimization of resources in manufacturing and trading industries. BPP could be one-dimensional (1D), two-dimensional (2D) and three-dimensional (3D) packing which gives optimum layout of packing items such that to improve the utilization ratio of bins. In other words; minimizing the bin's slack without overlapping the packages. Output obtains by BPP optimize all the aspects of resources while meeting the given supply-demand by minimizing wastage leading to reduction of cost of production. The BPP can be interpreted as a finite collection of items with varying specifications to be packed into one or more box utilizing the maximum volume of the box while satisfying the supply-demand. Each container can hold any subset of the collection of objects without exceeding its capacity (customer requirements). Bin packing is known as container loading, box packing, cargo loading, knapsack, etc. A burning issue faced by the industries is how to find the optimum layout (packing arrangement) of boxes or packing items such that to improve the utilization ratio of bins or minimize the bin slack without overlapping the packages. Researchers have worked on the BPP and used different approaches to solve the existing problem.

Among them, Gilmore et al [1] conducted some of the earliest research in this area and one-dimensional cutting stock problem is solved using Linear Programming Technique. In this study, unlimited numbers of raw materials with different lengths are assumed available in stock, and a mathematical model has been developed to minimize the total cutting cost of the stock length of the feasible cutting patterns and Column Generation Algorithm has been developed to generate feasible cutting patterns. Then, Gilmore has claimed that feasible cutting patterns are increased with the required cutting items and Linear Programming Technique is not applicable to solved mathematical model with too many variables. Gilmore [2] has made an approach for one-dimensional cutting stock problem as an extended of earliest paper (Gilmore et al (1961)) and cutting stock problem has been described as a NP-hard problem. A new and rapid algorithm for the knapsack problem and changes in the mathematical formulation has been evolved and Gilmore has explained the procedure of the Knapsack Method using a test problem. Solve the one dimensional BPP with island parallel grouping genetic algorithms was the main motivation of Dokeroglu T. et al (2014). Combining state-of-the-art computation tools; parallel processing, GGAs and bin oriented heuristics to efficiently solve the intractable one-dimensional BPP. Different size case studies discussed in the paper using Minimum Bin Slack (MBS) and Best Fit Decrease (BFD) / First Fit Decrease (FFD) [3].

Christian Blum and Verena Schmid (2013) have dealt with two-dimensional BPP under free guillotine cutting, a problem in which a set of oriented rectangular items are given which must be packed into minimum number of bins of equal size. An evolutionary algorithm has been discussed and the results of the proposed algorithm are compared with some of the best approaches from the literature $[4]$. Puchinger has described a combined genetic algorithm/branch & bound approach for solving a real world glass-cutting problem. The Genetic Algorithm uses an order-based representation, which is decoded using a greedy heuristic. The Branch & Bound algorithm was applied with a certain probability enhancing the decoding phase by generating locally optimal sub patterns. Reported results indicate that the approach of occasionally solving sub patterns to optimality may increase the overall solution quality $[5]$. Rodrigo et al (2012) developed an algorithm, based on Modified Branch and Bound algorithm to determine the feasible cutting patterns for Two-Dimensional cutting stock problem with rectangular shape cutting items. The method was illustrated with the use of a case study, where the data were obtained from a floor tile company known as Mega Marble Company located in London. A computer programme was coded using Matlab inbuilt functions $[6]$. As an extension of the above study, Rodrigo et al (2012) redesigned the developed algorithm to determine the locations of each cutting item using Cartesian Coordinate Geometry $[7]$. Other than that, Octarina et al (2019) has used Branch and Bound Algorithm and Gilmore and Gomary model on two dimensional multiple stock size cutting stock problem. A case study has discussed with four stock sizes and five products. Optimum packing schedule illustrated for each stock $[8]$.

Further, Fernandez (2010) has presented a method to find Integer Solutions to One-dimensional CSP to minimize the trim loss or to minimize the number of master rolls needed to satisfy the orders. Integer linear programming models for the One-dimensional CSP with different objective cost functions have been considered. Fernandez has studied an approach based on the classical column-generation procedure by Gilmore and Gomary for solving the linear programming (LP) relaxations. Also to obtain an integer solution, a final integer CSP after using an extra column-generation procedure has been solved $[9]$. Also, Jatinder N. D. Gupta and Johnny C. (1999) have described a new Heuristic Algorithm to solve the one-dimensional Bin Packing problem. Effectiveness of the proposed algorithm has been compared with the First Fit Decreasing (FFD) and the Best Fit Decreasing (BFD) algorithms using five different data sets $[10]$.

In this paper, packing items with rectangular shapes are selected to nest into pallets with rectangular shape base. An algorithm based on MBBA and a computer program using Matlab software package to generate feasible packing patterns and to solve the formulated integer linear programming model is used. Then, the optimum packing schedule obtained from MILPP with the results of BBA with Gilmore & Gomory for BPP are compared.

Minimize $z=\sum _{k=1}^r\sum _{j=1}^n{c}_{jk}{x}_{jk}$ (Total Unused area)

Subject to $\sum _{j=1}^n{p}_{ijk}{x}_{jk}\ge d_i$ for all $i=1,2,...,m$ (Demand Constraints)

$x_{jk},p_{ijk}\ge 0$ and integer for all $i,j,k$.

where $r=\text{Number of containers}$, m = Number of items

$n=$ Number of patterns,

$p_{ijk}=\text{The number of occurrences of the }{i}^{\text{th}}\text{ item in the }{j}^{\text{th}}\text{ pattern of the }{k}^{\text{th}}\text{ container},$ $c_{jk}=\text{Unused area for each }{j}^{\text{th}}\text{ pattern of the }{k}^{\text{th}}\text{ container},$

$d_i=\text{Demand of the }{i}^{\text{th}}\text{ item},$

$x_{jk}=$ The number of containers used to be packed according to the $j^{\mathrm{th}}$ pattern.

According to the mathematical model developed by Gilmore and Gomory, total unused area is minimized with satisfying the customer requirements. Sometimes, it is impracticable to obtain the optimal packing schedule only minimizing the unused area. Because, the total number of pieces of each packing item should be satisfy at least the demand of each packing item. That is there can be more pieces than to the demand of packing items in the optimal packing schedule. In this context, allocating extra pieces of each packing item is wastage.

In order to rectify the above disparity, mathematical model has developed to meet the exact demand.

Modified Integer Linear Programming Problem (MILPP) for BPP:

Minimize $z=\sum _{k=1}^r\sum _{i=1}^m\sum _{j=1}^n[\left(a_{ijk}{x}_{jk}\right)-\left(d_i^{\prime }{x}_{jk}\right)]$

(Totalpackingitemsused fromeachitem)

Subject to $\sum _{j=1}^n{a}_{ijk}{x}_{jk}\ge d_i$ for all $i=1,2,\dots ,m$

(DemandConstraints)

$x_{jk},a_{ijk}\ge 0$ and integer for all $i,j,k$

where $r=\text{Number of containers}$,

$m=$ Number of pieces,

$n=$ Number of patterns,

$a_{ijk}=\text{The number of occurrences of the }{i}^{\text{ht}}\text{ item in the }{j}^{\text{th}}\text{ pattern of the }{k}^{\text{th}}\text{ container},$

$c_{jk}=$ Unused packing area for each $j^{\mathrm{th}}$ pattern of the $k^{\mathrm{th}}$ container,

$d_i=\text{Demand value of the }{i}^{\text{th}}\text{ item},$

$x_{jk}=\frac{\text{The number of containers should be used according to the }{j}^{\text{th}}\text{ pattern from the}}{k^{\text{th}}\text{ container.}}$

c) Modified Branch and Bound Algorithm in stepwise form:

Step 1: Arrange required lengths, Lk, k = 1, 2,..., r in decreasing order, ie , where r = number containers.

Arrange required widths, $Wk$, $k=1,2,\dots ,r$

according to the corresponding length $Lk$, $k=1,2,\dots ,r$.

Notes

Step 2: Arrange required lengths, $l_i$, i = 1, 2,..., m in decreasing order, ie , where m = number of packing items.

Arrange required widths, $w_i$, $i=1,2,\dots ,m$ according to the corresponding length $l_i$, $i=1,2,\dots ,m$.

Step 3: For $i=1,2,\dots ,m$ and $j=1$ do Steps 4 to 6.

Step 4: Set $a_{111}=\left[[L_1/l_1]\right]$;

where $L_k$ is the length of the base of the $k^{th}$ container.

Here, $a_{ijk}$ is the number of pieces of the $i^{th}$ packing items in the $j^{th}$ pattern of the $k^{th}$ container along the length of the $k^{ht}$ container and $[[y]]$ is the greatest integer les than or equal to y.

Step 5: If , then set

else set $b_{ijk}=0$, where $W_{\mathrm{k}}$ is the width of the base of the $k^{\mathrm{ht}}$ container.

Here, $b_{ijk}$ is the number of pieces of the $i^{th}$ packing item in the $j^{th}$ pattern along the width of the base of the $k^{th}$ container.

Step 6: Set $p_{ijk}=a_{ijk}\times b_{ijk}$, where $p_{ijk}$ is the number of pieces of the $i^{th}$ item in the $j^{th}$ pattern of the $k^{th}$ container.

Step 7: Unused packing area (i) Unused packing area along the length of the $k^{\mathrm{ht}}$ container:

else set $A_{ijk}=0;$

If , then

where, $A_{ijk}$ and $B_{ijk}$ are the number of pieces of the $i^{th}$ item in the $j^{th}$ pattern of the $k^{ht}$ container along the length and width of the $c_{uk}$ rectangle respectively and $C_{uk}$ and $C_{vk}$ are the total unused area along the length and width of the $c_{uk}$ rectangle respectively.

(ii) Unused area along the width of the container:

where $K_{ijk}$ is the remaining width of each item in each pattern.

For $z\ne i$

If $(a_{ijk}\times l_i)\ge l_z$ and $K_{ijk}\ge w_z$, then

where, $A_{zjk}$ and $B_{zjk}$ are the number of pieces of the $i^{th}$ item in the $j^{th}$ pattern of the $k^{ht}$ container along the length and width of the $c_{vk}$ rectangle respectively. $C_u$ and $C_v$ are the total unused area along the length and width of the $c_{vk}$ rectangle respectively.

Step 8: Set r = m - 1.

While , do Step 9.

Step 9: While

set $j=j+1$ and do Step 10.

Step 10: If $a_{rjk}\ge b_{rjk}$, then generate a new pattern according to the following conditions:

For $z=r$

else set $b_{zjk}=0$.

For $z=r+1,\dots ,m$

calculate $a_{zjk}$ and $b_{zjk}$ using Equations (2.3) and (2.4). Go to Step 5. else generate a new pattern according to the following conditions:

For $z=r$

MBBA is applied to the above examples to generate feasible packing patterns. Effectiveness of the proposed Integer Linear Programming Problem has been compared with the results given in the paper [8].

In this study, feasible packing patterns are generated using MBBA and the integer linear programming model developed by Gilmore and Gomory and MILPP are applied to generate the optimum packing schedule. According to the optimum solution obtain from MILPP, only 2 plates of 13 inches 10 inches are used to fulfil the customer demand while 3 plates of 13 inches 10 inches are used with Gilmore and Gomory model. Comparing the solutions obtained from MBBA with MILPP and BBA with Gilmore and Gomory model, it is clear that the less number of plates needed to satisfy the customer demand using the proposed method in this research than to the BBA with Gilmore and Gomory model [8].