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.     

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.     

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.     

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 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.     

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.     

面向批量订单包装的物流箱规格优化问题研究

目的 针对面向仓储物流环境下多型号多批量产品的订单包装问题,提出一种预制物流箱规格优化模型及算法。方法 对产品订单建立订单分包规则,确定分包方案,以订单包装材料总成本最小为优化目标建立物流箱规格优化模型。针对该模型提出一种改进模拟退火算法,通过贪婪策略求解最优分包方案,降低模型计算复杂度,设计一种新型解更新算子,以提高算法寻优能力,设计一种自适应步长策略,以平衡算法前期全局搜索与后期局部搜索的能力。结果 通过实例证明,文中提出的算法相较于其他算法,具有更强的求解能力,与实例企业仓储包装现状相比,同批订单降低了17%的包装材料成本。结论 该方法可用于解决产品种类多、尺寸差异大、动态更新等应用场景下的系列运输包装纸箱规格优化问题,为企业物流运输管理提供了一种有效的包装优化思路和解决方法。     

Managing production of high-tech products with high production quality variability

We consider production systems in technology industries where output quality of a single production run has a large variance. Firms operating such systems classify products into different quality bins and sell units in one bin at the same tagged quality level and the same price. Consumers have heterogeneous quality preferences and choose that quality that maximises their net utility. We examine firms’ assortment, production and pricing problem. We present a three-stage solution procedure that optimises the production quantity, quality specification and number of bins. In that regard, we show that for a manufacturing technology with known quality distribution and known distribution of customers’ quality preference, the optimal assortment and production quantity are set such that on average, the demand of each bin is exactly fulfilled. We examine the impact of an improved manufacturing technology, variation in consumer preferences and changing price premium on the optimal assortment, lot size, market share, yield loss and the overall profitability. We further show that when the quality distribution of the manufacturing process is unknown, downward substitution leads to product offering of higher quality and higher prices. Finally, we discuss practical considerations for pricing, technology and optimal product offerings, and explain the proliferation of bins witnessed in the last decade in the processor industry.     

Job ordering and management of wearing tools

This article considers a scheduling problem arising in flexible manufacturing systems. It is assumed that a computer numerical control machine processes a set of jobs with a set of wearing tools. The tool magazine of the machine has a given capacity and each job requires some subset of tools. The goal is to minimize the average completion time of the jobs by choosing their processing order and the tool management decisions intelligently. Previous studies concerning this problem have either omitted the tool wearing or assumed only one tool type. This study gives a mathematical formulation for the problem when the tool lifetimes are deterministic. It is shown that problems of a practical size cannot be solved to optimality within a reasonable time. Therefore genetic algorithms and local search methods are considered to resolve the problem. When the solutions of these new algorithms are compared against the optimal solutions and lower bounds, they are nearly optimal.     

Development of a production inventory model with uncertainty and reliability considerations

This paper addresses a problem of an imperfect production system under fuzzy demand and inventory holding cost. Production process reliability is considered because of the imperfect production process. In this problem, reliability of the system in regards to producing defective and non-defective items is considered as a decision variable. The objective is to maximize the graded mean integration value (GMIV) of the expected average profit while considering revenues as well as any other relevant costs. The developed model belongs to the class of a geometric programming. We have developed a simple mathematical methodology to solve the model. Genetic algorithm and simulated annealing algorithms are also applied to solve and validate the results. A numerical example has been presented to interpret the solutions.     

Quay crane scheduling in container terminals

The problem of scheduling identical quay cranes moving along a common linear rail to handle containers for a ship is studied. The ship has a number of container-stacking compartments called bays, and only one quay crane can work on a bay at the same time. The objective of the scheduling problem is to find the work schedule for each quay crane which minimizes the ship’s stay time in port. Finding the optimal solution of the scheduling problem is computationally intractable and a heuristic is proposed to solve it. The heuristic first decomposes the difficult multi-crane scheduling problem into easier subproblems by partitioning the ship into a set of non-overlapping zones. The resulting subproblems for each possible partition are solved optimally by a simple rule. An effective algorithm for finding tight lower bounds is developed by modifying and enhancing an effective lower-bounding procedure proposed in the literature. Computational experiments were carried out to evaluate the performance of the heuristic on a set of test problems randomly generated based on typical terminal operations data. The computational results show that the heuristic can indeed find effective solutions for the scheduling problem, with the heuristic solutions on average 4.8% above their lower bounds.     

单一尺寸长方体三维装箱问题的一种求解算法

目的研究单一尺寸长方体物品的三维装箱问题,即在一个给定的箱子中装入尽可能多的单一尺寸长方体物品。方法采用分层装载方案简化装载操作,首先运用动态规划技术确定所有层中长方体物品的排列方式;然后求解一维背包问题确定箱中层的最优组合,得到最优装载方案。将文中算法与文献中三维装箱算法进行对比。结果文中算法生成的装载方案箱体空间利用率由文献中三维装箱算法的98.10%提高到了99.14%。结论文中算法可以在合理的时间内得到装载操作简单、箱体空间利用率较高的装载方案。     

基于分组策略的多目标三维装箱算法

目的 针对现有三维装箱算法优化目标单一、优化效率低的问题,提出适用于求解大规模货物装载问题的多目标装箱算法,以提高装箱规划效率,确保货物运输安全。方法 考虑5种现实约束条件,以体积利用率和装载垛型重心偏移量为优化目标,建立多目标货物装载优化模型。采用拟人式装箱对货物进行预分组,减小决策空间,然后结合分组信息与装箱算法生成初始解;引入数据驱动的装箱交叉算子提高算法收敛性;设计多策略变异算子提高算法结果的多样性。结果 以公共数据集和真实航空货物数据作为实验数据进行实验。实验结果表明,在满足多种约束条件下,集装箱装载强异构货物平均体积利用率达到92.0%,重心位置空间偏移从20 cm减少到7.5 cm,并且算法运行时间减少了73.5%。结论 本文所提算法应用于求解大规模多目标三维装箱问题,提高了装箱质量和效率,可为三维装箱算法的工程应用提供参考。     

An improved best-first branch-and-bound algorithm for constrained two-dimensional guillotine cutting problems

The constrained two-dimensional cutting problem involves maximising the sum of the profits obtained from small rectangular pieces cut from a large rectangular plate where the number of each type of cut piece cannot exceed a prescribed quantity. This paper proposes a best-first branch-and-bound algorithm to find the optimal solution to the problem. The proposed algorithm uses an efficient method to remove the duplicate patterns, and it improves the existing upper bounds. It also prevents the construction of dominated patterns and introduces a new bounding strategy that can prune more than one node at a time. Computational results are compared with a well-known exact algorithm to demonstrate the efficiency of the proposed algorithm. The proposed algorithm is as fast as or faster than the existing algorithm and reduces the average computing time by up to 99% for benchmark problems. For some problems, it can also find optimal solutions that existing algorithms are not able to find.     

Lot streaming and scheduling multiple products in two-machine no-wait flowshops

We consider the problem of minimizing makespan in two-machine no-wait flowshops with multiple products requiring lot streaming. A “product” (or lot) consists of many identical items. Lot streaming (lot sizing) is the process of creating sublots (or transfer batches to move the completed portion of a production )sublot to downstream machines so that operations can be overlapped. The number of sublots for each product is fixed. When the flowshop produces only a single product, we obtain optimal continuous-sized sublots. It is shown that these sublot sizes are also optimal for the problem of simultaneous lot streaming and scheduling of multiple products. The optimal scheduling of products can be accomplished by application of the algorithm due to Gilmore and Gomory [1]. Then, we devise an efficient heuristic for the problem of simultaneous lot streaming (finding optimal integer-sized sublots) and scheduling of multiple products. Computational results indicate that this heuristic can consistently deliver close-to-optimal solutions for the problem. A comparison of this heuristic is also made with a heuristic that first divides items belonging to each product into nearly equal-sized sublots and then constructs a schedule for such sublots. Finally, we extend our solution procedures to a traditional and more general lot streaming model, where the number of sublots for each product is a decision variable.     

A recursive algorithm for the rectangular guillotine strip packing problem

This article presents a recursive heuristic algorithm to generate cutting patterns for the rectangular guillotine strip packing problem in which a set of rectangular items must be cut from the strip such that the consumed strip length is minimized. The strip is placed with its length along the horizontal direction, and is divided into several segments with vertical cuts. The length of a segment is determined by the item placed at the bottom. Orthogonal cuts divide the segments into blocks and finished items. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. Rotation of the items by 90 is allowed. Both lower and upper bounds are used to prune unpromising branches. The computational results indicate that the algorithm performs better than several recently published algorithms.     

Cutting optimization with variable-sized stock and inventory status data

Many production environments require economical cutting of one-dimensional items according to bills of materials from objects of several standard lengths. However, even with optimized cutting substantial trim loss may occur. This trim loss should not be regarded as waste. It is returned to store and can be reused in future optimizations. Optimization of packing linear items into standard lengths is presented for items that cannot be packed into available lengths from inventory status data. The core of the proposed optimization tackles the variablesized bin packing problem (VBPP). The article presents a hybrid genetic algorithm that packs items into both available objects from the inventory and variablesized objects from the stock. The algorithm tries to minimize waste. Large trimloss items are returned as remnants to the inventory for subsequent optimizations.     

Airflow and temperature distribution in two-dimensional drying bins

The design of a drying or cooling store aims to provide an even airflow distribution, when aerated, for preservation purposes. The airflow in some curved bottom bins are studied in this paper. The flow is modelled, using Darcy's law. A generalized Schwarz-Christoffel transformation is employed to reduce the problem of computing streamlines and isobars of airflow to solving a single nonlinear equation for the flow angle along the wall. Corresponding to different bin shapes, a few computed streamlines and isobars of airflow are presented, showing the effect of changing bottom geometries on the air flow. Heat transfer in such bins is also investigated. Based on an analysis of the far field of airflow, finite-height bins are considered. Analytical solutions of the heat conduction equation in terms of streamlines and isobars are obtained.     

Optimal feeding profile in fed-batch bioreactors using a genetic algorithm

An optimal feeding profile for a fed-batch process was designed based on an evolutionary algorithm. Usually the presence of multiple objectives in a problem leads to a set of optimal solutions, commonly known as Pareto-optimal solutions. Evolutionary algorithms are well suited for deriving multi-objective optimisation since they evolve a set of non-dominated solutions distributed along the Pareto front. Several evolutionary multi-objective optimisation algorithms have been developed, among which the Non-dominated Sorting Genetic Algorithm NSGA-II is recognised to be very effective in overcoming a variety of problems. To demonstrate the applicability of this technique, an optimal control problem from the literature was solved using several methods considering the single-objective dynamic optimisation problem.     

Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints

This paper introduces models and algorithms for a static dial-a-ride problem arising in the transportation of patients by non-profit organizations such as the Austrian Red Cross. This problem is characterized by the presence of heterogeneous vehicles and patients. In our problem, two types of vehicles are used, each providing a different capacity for four different modes of transportation. Patients may request to be transported either seated, on a stretcher or in a wheelchair. In addition, some may require accompanying persons. The problem is to construct a minimum-cost routing plan satisfying service-related criteria, expressed in terms of time windows, as well as driver-related constraints expressed in terms of maximum route duration limits and mandatory lunch breaks. We introduce both a three-index and a set-partitioning formulation of the problem. The linear programming relaxation of the latter is solved by a column generation algorithm. We also propose a variable neighborhood search heuristic. Finally, we integrate the heuristic and the column generation approach into a collaborative framework. The column generation algorithm and the collaborative framework provide tight lower bounds on the optimal solution values for small-to-medium-sized instances. The variable neighborhood search algorithm yields high-quality solutions for realistic test instances.