A dynamic programming-based heuristic for the variable sized two-dimensional bin packing problem

This paper addresses a variable sized two-dimensional bin packing problem. We propose two heuristics, H1 and H2, stemming from the dynamic programming idea by aggregating states to avoid the explosion in the number of states. These algorithms are elaborated for different purposes: H1 builds a general packing plan for items, while H2 can provide solutions by considering a variety of customer demands, such as guillotine cutting style and rotation of items. The performance of both algorithms is evaluated based on randomly generated instances reported in the literature by comparing them with the lower bounds and optimal solutions for identical bins. Computational results show that the average gaps are 8.97% and 13.41%, respectively, for H1 and H2 compared with lower bounds, and 5.26% and 6.26% compared with optimal solutions for identical bins. We also found that we can save 6.67% of space, on average, by considering variable sized bins instead of a bin packing problem with identical bins.     

Aggregated state dynamic programming for a multiobjective two-dimensional bin packing problem

This paper studies a real-life multi-objective two-dimensional single-bin-size bin-packing problem arising in industry. A packing pattern is defined by one bin, a set of items packed into the bin and the packing positions of these items. A number of bins can be placed with the same packing pattern. The objective is not only to minimise the number of bins used, as in traditional bin-packing problems, but also to minimise the number of packing patterns. Based on our previous study of a heuristic stemming from dynamic programming by aggregating states to avoid the exponential increase in the number of states, we further develop this heuristic by decomposing a pattern with a number of bins at each step. Computational results show that this heuristic provides satisfactory results with a gap generally less than 20% with respect to the optimum.     

Solving non-oriented two dimensional bin packing problem using evolutionary particle swarm optimisation

The non-oriented two-dimensional bin packing problem (NO-2DBPP) deals with a set of integer sized rectangular pieces that are to be packed into identical square bins. The specific problem is to allocate the pieces to a minimum number of bins allowing the pieces to be rotated by 90° but without overlap. In this paper, an evolutionary particle swarm optimisation algorithm (EPSO) is proposed for solving the NO-2DBPP. Computational performance experiments of EPSO, simulating annealing (SA), genetic algorithm (GA) and unified tabu search (UTS) using published benchmark data were studied. Based on the results for packing 3000 rectangles, EPSO outperformed SA and GA. In addition; EPSO results were consistent with the results of UTS indicating that it is a promising algorithm for solving the NO-2DBPP.     

A two-dimensional bin-packing problem with conflict penalties

In this paper, we address the two-dimensional bin-packing (2BP) problem with variable conflict penalties, which incur if conflicting items are loaded into the same bin. Such a problem is observed in applications such as supermarket chains and automobile components transportation. The problem not only focuses on minimisation of number of bins used, but also deals with the conflict penalties at the same time. We propose a heuristic method based on the IMA algorithm and adapt it to solve this problem. A local search procedure is also designed to further improve the solutions. For instances derived from benchmark test data, the computational results indicate that the adapted IMA heuristic algorithm with local search effectively balances the number of bins used and the conflict penalties. The algorithm outperforms several adapted approaches that are well known for the 2BP problems.     

Lower bounds for three-dimensional multiple-bin-size bin packing problems

The three-dimensional multiple-bin-size bin packing problem (MBSBPP) is the problem of packing a set of boxes into a set of bins when several types of bins of different sizes and costs are available and the objective is to minimize the total cost of the bins used for packing the boxes. We present a study of lower bounds for this packing problem. We have developed new bounds based on integer programming formulations of some relaxations of the original problem. These formulations are enhanced with logical considerations. The proposed bounds are compared with other existing bounds in an extensive computational study, including two- and three-dimensional instances with up to 100 boxes, some of them taken from the literature and others adapted from the classical Bin Packing Problem. The proposed bounds improve the results of previous bounds by more than 10%, though at a higher computational cost.     

A heuristic,dynamic programming-based approach for a two-dimensional cutting problem with defects

This paper deals with a two-dimensional cutting problem in which small rectangular items of given types are to be cut from a rectangular large object which contains several defects. It is assumed that the number of pieces of each small item type which can be cut from the large object is not limited. In addition, all cuts are restricted to be of the guillotine-type and the number of stages necessary to perform all cuts is not limited. Furthermore, no small item must overlap with a defective region. The objective is to maximize the value of the cut small items. For the solution of the above-described problem, a heuristic, dynamic programming-based approach is presented which overcomes the structural and computational limitations of previously-proposed methods. In the presence of defects, the representation of the defective regions and the definition of discretization sets are revisited. This allows for an improvement of the computational efficiency as well as of the storage space requirements for solving the given problem with any number of defects in this approach. We further analyze the computational complexity of the algorithm and identify the factors which affect its running time. The proposed method is evaluated by means of a series of detailed numerical experiments which are performed on problem instances extracted from the literature, as well as on randomly generated instances. The experiments do not only illustrate how the suggested method is able to identify optimal solutions of the test problem instances, but they also explain why already existing methods fail to do so. Furthermore, the computational results indicate that the proposed method, equipped with the newly-proposed discretization sets, is capable of efficiently generating a high percentage of optimal solutions to the corresponding problem with defects.     

A Combined Approach to the Pallet Loading Problem

In this paper the two-dimensional pallet loading problem is considered: that is, the problem of loading a rectangular pallet of size L by W, drawing from a set of n rectangular boxes. The objective is to maximize the area covered on the pallet by the boxes loaded. The problem is approached using a combination of dynamic programming and heuristics. The structured solutions resulting from the application of the dynamic program have two serendipitous characteristics: any item may be placed on the periphery of the pallet for easy access, and some control may be retained over the center of gravity of the pallet. Computational results are given.     

The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation,a Benders decomposition and a CP-based algorithm

This paper addresses a variant of two-dimensional cutting problems in which rectangular small pieces are obtained by cutting a rectangular object through guillotine cuts. The characteristics of this variant are (i) the object contains some defects, and the items cut must be defective-free; (ii) there is an upper bound on the number of times an item type may appear in the cutting pattern; (iii) the number of guillotine stages is not restricted. This problem commonly arises in industrial settings that deal with defective materials, e.g. either by intrinsic characteristics of the object as in the cutting of wooden boards with knotholes in the wood industry, or by the manufacturing process as in the production of flat glass in the glass industry. We propose a compact integer linear programming (ILP) model for this problem based on the discretisation of the defective object. As solution methods for the problem, we develop a Benders decomposition algorithm and a constraint-programming (CP) based algorithm. We evaluate these approaches through computational experiments, using benchmark instances from the literature. The results show that the methods are effective on different types of instances and can find optimal solutions even for instances with dimensions close to real-size.     

Efficient heuristics for robot acquisition planning for a CIM system

In this paper, a planning model and three efficient heuristics are developed for equipment acquisition planning for a CIM system using multiple-type robots. Our planning model considers selection of a proper mix of multiple-type robots such that operational requirements (i.e., time and space) from a given number of work stations are satisfied at minimal system cost. In specific, each robot is characterized by its fixed charge and subject to two capacity constraints on machine time and work space; and each work station has known demands for both machine time and work space, and is to be served by only one robot. The model is formulated as a pure 0–1 mathematical program and is shown to be harder than two-dimensional bin packing, a well-known NP-hard problem. The three heuristics developed are: a greedy heuristic, tabu thresholding, and simulated annealing. All heuristics are tested by solving 450 randomly generated problems. Computational results indicate that all three heuristics are effective and efficient in solving problems of a practical size (i.e., 50 work stations and a maximum of 20 robots). However, none of the heuristics are overwhelmingly better than the others in terms of both solution time and quality. Future research issues are also discussed.     

Global optimization for the three-dimensional open-dimension rectangular packing problem

This article addresses the three-dimensional open-dimension rectangular packing problem (3D-ODRPP), which aims to pack a given set of unequal-size rectangular boxes within an enveloping rectangular space such that the volume of the occupied space is minimized. Even though the studied 3D-ODRPP is NP hard, the development of sophisticated global optimization methods has been stimulated. The mathematical programming formulation for the 3D-ODRPP has evolved into an effective and efficient mixed-integer linear programming (MILP) model. This study proposes an advanced exact scheme yielding a guaranteed global optimal solution given that all the instance data are non-negative rational numbers. The developed MILP retains not only fewer variables but also fewer constraints than the state-of-the-art models. The superior effectiveness and efficiency of the developed scheme are demonstrated with numerical experiments, where two sets of benchmark instances from references, real-world instances and instances with rational data are included.     

求解集装箱堆场堆垛问题的约束满足算法

集装箱堆垛问题普遍存在于港口码头堆场作业管理中,是在集装箱数目已知的前提下,要求满足交货期限制、重量限制以及垛位高度限制等约束条件,目标是实现占用垛位数最少。通过问题分析,将其归结为一类带顺序约束的装箱问题,并建立了约束满足优化模型,设计了嵌入经典装箱启发式原则的约束满足求解算法。为了验证模型和算法的可行性和有效性,根据某集装箱码头堆场的实际生产情况构造测试算例,实验结果表明,该算法对于实现垛位数最小化、求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。     

A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints

In this paper, we propose a generalisation of the bin packing problem, obtained by adding precedences between items that can assume heterogeneous non-negative integer values. Such generalisation also models the well-known Simple Assembly Line Balancing Problem of type I. To solve the problem, we propose a simple and effective iterated local search algorithm that integrates in an innovative way of constructive procedures and neighbourhood structures to guide the search to local optimal solutions. Moreover, we apply some preprocessing procedures and adapt classical lower bounds from the literature. Extensive computational experiments on benchmark instances suggest that the developed algorithm is able to generate good quality solutions in a reasonable computational time.     

On solving three-dimensional open-dimension rectangular packing problems

In this article, a recently proposed three-dimensional open-dimension rectangular packing problem is considered, in which the objective is to find a minimal volume rectangular container that packs a set of rectangular boxes. The literature has tackled small-sized instances of this problem by means of optimization solvers, position-free mixed-integer programming (MIP) formulations and piecewise linearization approaches. In this study, the problem is alternatively addressed by means of grid-based position MIP formulations, whereas still considering optimization solvers and the same piecewise linearization techniques. A comparison of the computational performance of both models is then presented, when tested with benchmark problem instances and with new instances, and it is shown that the grid-based position MIP formulation can be competitive, depending on the characteristics of the instances. The grid-based position MIP formulation is also embedded with real-world practical constraints, such as cargo stability, and results are additionally presented.     

LP-based heuristics for the capacitated lot-sizing problem: The interaction of model formulation and solution algorithm

We consider here the application of trivial LP-based rounding heuristics to the capacitated lot-sizing problem (CLSP). The motivation behind the use of LP-based heuristics is that their extension to cope with complicating features (to be expected, for example, when dealing with a master production scheduling problem within a MRP system) is generally easier than with alternative approaches such as lagrangian relaxation. It is well known that strong model formulations, like the Plant Location Formulation (PLF) or the Shortest Path Formulation (SPF), are needed to obtain good results when working on a CLSP. Still, from a practical point of view, a few questions deserve investigation. First, the relative performance of PLF and SPF should be assessed. Second, given the increased size of the more complicated formulations, the possible benefits of using interior point methods must be considered. Third, the sensitivity of the computation times with respect to the characteristics of problem instances should be evaluated. We report some computational experiments on relatively large problems (500 items and 15 time buckets, resulting in 7500 binary variables). For the simple CLSP model, trivial heuristics can yield near-optimal solutions with a reasonable computational effort, at least for the problem instances we consider. However, there is a critical and non-obvious interaction between the model formulation, the problem instance characteristics, and the solution algorithm.     

Three-dimensional packing—solution approaches and heuristic development

Computer solutions to three-dimensional packing problems typically involve the application of one or more sets of heuristic rules in an effort to provide packings which are, primarily, volumetric efficient. This paper examines various strategies which may be adopted in the development/improvement of such heuristics and illustrates how analysis of the two-dimensional problem may be used to advantage.     

FINDING PLACEMENT SEQUENCES AND BIN LOCATIONS FOR CARTESIAN ROBOTS

We model the repetitive placement by a Cartesian robot of n parts on a rectangular workpiece. There are n bins or feeders (one per part), to be placed around the boundary of the workpiece, which contain the parts. The robot picks a part from a bin, places it, picks another part, places it, etc.; any placement sequence is possible. The problem, to find bin locations and a placement sequence to minimize total assembly time, is formulated as a traveling salesman problem (on a graph with n nodes) with special structure. This structure allows the computation of a lower bound on the minimum total assembly time in order n effort. The lower bound improves as n increases, and leads to a simple solution algorithm which gives asymptotically optimal solutions in order n log n effort. For die case where parts are uniformly distributed on the workpiece, we give simple closed-form expressions for the expected value of the lower bound. These expressions should be helpful for design decisions; for example, holding n constant, they indicate that square workpieces require more assembly time than non-square, rectangular workpieces of the same area. Most of our results are relatively insensitive to the inclusion of robot acceleration/deceleration effects.     

The strip-packing problem for a boat manufacturing firm

This paper addresses the problem of minimizing the amount of wasted space when cutting a set of rectangular pieces from a single rectangular sheet of stock material. A simulated annealing algorithm is developed and is shown to significantly outperform three existing heuristics on a set of 37 real-world data sets. In addition, a mathematical programming formulation of the problem and several theoretical lower bounds are developed and used to demonstrate that the simulated annealing solutions are within 9.5% of the optimal solution, on average.     

Capacity-constrained reorder intervals for materials requirements planning systems

This paper develops a model for the reorder interval problem for general production systems with constant demand, multiple capacity constraints, commonality, non-instantaneous production, and non-nested reorder intervals. We present this model in the context of a materials requirements planning (MRP) system.

Four simple greedy heuristics are presented to find solutions to the model. A six-factor experiment with 192 test problems is used to evaluate the heuristics. The factors in the experiment included the procedures, number of items, capacity tightness, degree of commonality, setup cost to carrying cost ratio, and setup time to run time ratio. For smaller problems the heuristics are compared with optimal solutions found with an exact branch-and-bound algorithm. For larger problems, the heuristics are compared with a lower bound.

The results of the experiment show that the heuristics provide excellent solutions across all experimental factors. Computing times for the proposed heuristics appear to be practical even for realistic MRP environments with many thousands of items.     

Capacitated single machine scheduling and its on-line heuristics

The capacitated single machine scheduling problem arises from a manufacturing system. The machine works periodically and is capacitated in each period. This is a variant of the bin packing problem. We theoretically compare two types of production settings: in the first type, the machine processes each demand without splitting and in the second, splitting is allowed but a setup time occurs. From the worst case viewpoint, we show that the optimal schedule length of the production without splitting may be nearly twice as long as that of the production with splitting. The ratio of two is asymptotically tight. Then we adapt the well-known bin packing heuristics for the on-line version of the capacitated single machine scheduling problem and give their worst case analysis.     

Solution algorithms for dynamic lot-sizing in remanufacturing systems

We consider the problem of determining the lot sizes that satisfy the demands of remanufactured products over a given planning horizon with discrete time periods. Remanufacturing, in which used or end-of-life products are restored to like-new condition, typically consists of disassembly, reprocessing and reassembly processes, and hence the lot sizes are determined for each of the three processes. The objective is to minimise the sum of setup and inventory holding costs occurring at the three processes. To represent the problem mathematically, we suggest a mixed integer programming model by combining the existing ones for disassembly and assembly systems. After proving that the problem is NP-hard, we suggest two dynamic programming based heuristics, called the aggregation and the decomposition type heuristics in this paper. Computational experiments were done on various test instances, and the results show that the two heuristics give near-optimal solutions in a short amount of computation time. Also, the performances of the heuristics are compared according to different values of problem parameters.