New Hybrid Discrete PSO for Solving Non Convex Trim Loss Problem

Introduction

The success of process or manufacturing industries such as textile, leather, paper and pulp, plastic, wood and metal, etc., depend largely on the timely and economic production of product materials ordered by different firms or customers. The main problems that arise during processing of products are assortment, cutting, packing, loading, etc., that becomes a bottleneck, if not dealt carefully on time. Therefore the aim of manufacturers is to produce desired products to meet customer’s demands economically with the maximum utilization of available raw materials, while minimizing the inevitable waste of resources. The Trim loss Problem (TLP) or Cutting Stock Problem (CSP) (Gilmore & Gomory, 1961; Hinxman, 1980) is one the most common problem encountered during the cutting of ordered products, having variable sizes that should be cut out from the available limited resources to satisfy customer demands. TLP can be categorized as deterministic or stochastic, based on the nature of its parameters. For the deterministic TLP, all the parameters are predetermined and the objective is to determine the optimum cutting scheme to minimize the waste material leading to the reduction of production cost, overproduction and thus maximizing the profit. On the other hand, for stochastic TLP, the uncertainty is associated with the parameters like customer demands, dimension of available raw paper roll due to defect caused by winding process. The objective of stochastic TLP is to take appropriate decision to maximize profit or minimize production cost, considering the uncertainty in parameters caused by various reasons.

Due to various physical and environmental restrictions imposed on production processes, the mathematical formulation of TLP’s (deterministic as well as stochastic) emerges as highly constrained, combinatorial, nonconvex and nonlinear. To lessen its complexity, different transformation methods, e.g., exponential, linear, square root, inverted, etc., have been applied that relaxes the original problem as mixed integer convex non linear programming problem (MINLP/ INLP) or integer linear programming problem (ILP/ MILP). The main problem associated with these transformation methods is the increase in the number of variables and constraints, while the expanded problem could be solved easily using any of available approximation or direct search methods that provide a relaxed solution to the original problem. Further, the objective function of different TLP or CSP models varies as per the need of manufacturers of different processing units. Now from the modelling stand point, TLP emerges as nonlinear, nonconvex and highly constrained with integer restrictions imposed on it. Being a complex combinatorial optimization problem, it is not convenient to obtain an optimal or near optimal solution employing existing traditional optimization methods. As a result, a suitable method is required for solving such real world problems. Due to their stochastic nature along with applicability to a wide range of problems, since past few decades, metaheuristics like Simulated Annealing (SA) (Lai & Chan, 1997), Genetic Algorithms(Wagner, 1999), Tabu Search (Alvares-Valdés et al., 2002), Hybrid Particle Swarm Optimization (Shen, Li, Dai, & Zheng, 2007), etc., have received much attention from manufacturers and researchers for solving such problems.

In the present study, the focus is on the TLP arising in paper industry during cutting of a set ordered paper rolls of variable widths from available raw paper rolls to satisfy customer’s demands. The considered TLP model is solved without using any transformation technique with an objective to minimize the total production cost, including the material cost and cost for changing cutting patterns. An obtained optimal cutting scheme that minimizes the production cost minimizes the trim loss as well. This work proposes a discrete variant of Particle Swarm Optimization (PSO) embedded with a mutation operator to enhance its performance for dealing the considered TLP. The proposed variant is called Hybrid discrete Particle Swarm Optimization (HDPSO) and the numerical results obtained by it are compared with some other existing metaheuristics.

The paper is organized as follows: the next section presents a brief literature review on TLP and existing methods to solve it. The mathematical formulation of the trim loss problem is then explained. A detailed description of Proposed Hybrid Discrete PSO is given. The computational results are discussed and the paper is concluded.