Optimization Methods For Cutting Stock And Bin Packing Problems Based On Hybrid Algorithms

Cutting stock and bin packing are a class of optimization problems that are NP-hard and reducible to knapsack problem.These problems can be formulated using integer linear programming model.There are a huge number of variables involved,thus exact algorithms are improbable to obtain good,let along optimal solutions in practical use cases.The same difficulty persists when only an approximate solution is being sought by linear programming.Because of the complicity of generating multi-dimensional geometric patterns.Heuristics are typically easy to implement and sufficient for reaching an approximation in relative short time.But they are not guaranteed to be optimal,in some cases,the solution quality of heuristic is lacking because they do not really cover much of the solution space and are prone to be stuck in local optimum.In this thesis,hybrid algorithms that implement both heuristics and exact algorithms are explored.The goal of hybrid algorithms is taking advantage of the lesser computational expanse of heuristics and the optimality of integer programming based exact approaches,while lessen the short comings.Three sub class of the cutting stock / bin packing problems are picked,and hybrid algorithms are presented,respectively.In the classical one-dimensional cutting stock problem(1DCSP),a set of item types with specified demand is cut from stock bars of the same length to maximize material utilization,where the demand of each item type must be met.This thesis investigates the 1DCSP with underproduction,where a few item types can be left out and considered in the next production run to improve material utilization,with the constraint that the total length of the missed item types must be no larger than a specified threshold.An integer nonlinear programming model is developed and solved heuristically in two stages.First a large set of cutting patterns is generated by a sequential method,then the model is solved over the patterns.Successive production runs are considered in the computational test.The results show that the proposed approach can lead to significant improvement in material utilization and simplify the cutting process.In the case of rectangular level strip packing problem,where multiple types with specified demands are packed in levels into a strip with definite width and infinite height to minimize the occupied height,with the constraint that the items in the same level cannot be placed one on top of the other.A triple-solution approach for the rectangular level strip packing problem is presented.The approach contains two phases and considers three types of solutions.In phase one,two types of solutions,obtained respectively from solving residual problems using column generation and from looking ahead,are considered and the best is selected as phase-one solution.In phase two,an integer programming model is solved over the levels generated in phase-one to obtain phase-two solution.Finally,the better one of the phase-one and phase-two solutions are selected.Computational results indicate that in most cases,our approach superior to algorithms reported in literature in term of salutation quality.And compare to exact algorithms,our approach requires little computational time.In the cased of two-dimensional bin packing problem with guillotine constrains.The presented hybrid algorithm considers a novel combination of three procedures.The first is a pattern-generation procedure that generates a set of triple-block patterns on each call.The second is a plan-generation procedure that uses some of these patterns to compose the solution.The third is an improvement procedure that solves an integer linear programming model over a given set of patterns generated previously to improve the solution.According to the computational results,the hybrid algorithm can obtain good solution quality.For some classes of instances,the gap to lower bound is reduced by more than 30% compared to algorithms recently published.