Sequence based heuristics for two-dimensional bin packing problems

This article addresses several variants of the two-dimensional bin packing problem. In the most basic version of the problem it is intended to pack a given number of rectangular items with given sizes in rectangular bins in such a way that the number of bins used is minimized. Different heuristic approaches (greedy, local search, and variable neighbourhood descent) are proposed for solving four guillotine two-dimensional bin packing problems. The heuristics are based on the definition of a packing sequence for items and in a set of criteria for packing one item in a current partial solution. Several extensions are introduced to deal with issues pointed out by two furniture companies. Extensive computational results on instances from the literature and from the two furniture companies are reported and compared with optimal solutions, solutions from other five (meta)heuristics and, for a small set of instances, with the ones used in the companies.     

An integrated formulation for hierarchical cast design problems in the steel making industry

Production design is a key decision problem of steel making industry but due to its complexity, solution properties are not well understood. The design problem can be viewed as a multi-stage problem of bin packing, matching and sequencing sub-problems. Traditionally a sequential approach which treats each sub-problem separately has been applied to the simple case where mould width change is not allowed. However, for more general cases where casting with width change and different width is allowed, the sequential approach fails to generate good solutions. In this paper, we propose a mathematical programming formulation which can solve the design problem in an integrative way. By introducing multi-layer network representation of the cast design problem, it is now possible to generate an integrated formulation for the proposed problem. Based on the formulation, we derive a heuristic algorithm. The algorithm is adopted and tested at a large international integrated steel mill. The computational tests with real data-sets show that the proposed algorithm is quite effective and practical.