THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.     

TSPACK: A two-level tabu search for the three-dimensional bin packing problem

Three-dimensional orthogonal bin packing is a problem NP-hard in the strong sense where a set of boxes must be orthogonally packed into the minimum number of three-dimensional bins. We present a two-level tabu search for this problem. The first-level aims to reduce the number of bins. The second optimizes the packing of the bins. This latter procedure is based on the Interval Graph representation of the packing, proposed by Fekete and Schepers, which reduces the size of the search space. We also introduce a general method to increase the size of the associated neighborhoods, and thus the quality of the search, without increasing the overall complexity of the algorithm. Extensive computational results on benchmark problem instances show the effectiveness of the proposed approach, obtaining better results compared to the existing ones.     

A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows

This paper deals with several bicriteria open-shop scheduling problems where jobs are pre-emptable and their corresponding time-windows must be strictly respected. The criteria are a performance cost and the makespan. Network flow approaches are used in a lexmin procedure with a bounded makespan and the considered bicriteria problems are solved. Finally, the computational complexity of the algorithm and a numerical example are reported.     

New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems

We consider two types of orthogonal, oriented, rectangular, two-dimensional packing problems. The first is the strip packing problem, for which four new and improved level-packing algorithms are presented. Two of these algorithms guarantee a packing that may be disentangled by guillotine cuts. These are combined with a two-stage heuristic designed to find a solution to the variable-sized bin packing problem, where the aim is to pack all items into bins so as to minimise the packing area. This heuristic packs the levels of a solution to the strip packing problem into large bins and then attempts to repack the items in those bins into smaller bins in order to reduce wasted space. The results of the algorithms are compared to those of seven level-packing heuristics from the literature by means of a large number of strip-packing benchmark instances. It is found that the new algorithms are an improvement over known level-packing heuristics for the strip packing problem. The advancements made by the new and improved algorithms are limited in terms of utilised space when applied to the variable-sized bin packing problem. However, they do provide results faster than many existing algorithms.     

Constrained order packing: comparison of heuristic approaches for a new bin packing problem

Bin packing problems consist of allocating a set of small parts to a set of large bins by minimizing the number of used bins. Although several boundary conditions have been stated in the past, for example conflicts or restrictions on cutting and rotations, we introduce a set of constraints, which lead to a new problem structure. These constraints are motivated by the precast-concrete-part industry and represent requirements on the ordering of parts and their positions, machinery restrictions and due dates. Furthermore, we solve the problem using several heuristic approaches that are based on algorithms for the standard bin packing problem. Therefore, existing concepts are classified and adapted to fit the new problem, including Simulated Annealing, Genetic Algorithms, Tabu Search methods and SubSetSum based search routines. Finally, all proposed algorithms are tested and obtained results are discussed.     

Simple but effective heuristics for the 2-constraint bin packing problem

The 2-constraint bin packing problem consists in packing a given number of items, each one characterised by two different but not related dimensions, into the minimum number of bins in such a way to do not exceed the capacity of the bins in either dimension. The development of the heuristics for this problem is challenged by the need of a proper definition of the criterion for evaluating the feasibility of the two capacity constraints on the two different dimensions. In this paper, we propose a computational evaluation of several criteria, and two simple but effective algorithms—a greedy and neighbourhood search algorithms—for solving the 2-constraint bin packing problem. An extensive computational analysis supports our main claim.     

Bibliographie zur geometrischen optimierung

A probabilistic scheduling period inventory system is considered for items that deteriorate continuously in time. The demand is assumed to occur instantaneously at the beginning of the scheduling period. Shortages are not allowed. A model with a non-zero lead time is developed first and, then, its special case is considered in which the lead time is a multiple of the scheduling period. The inventory models are developed using a general deterioration function. Their particular cases, when the rate of deterioration is constant, are also developed. Numerical examples are given to illustrate the models.     

一类带多重核元集在线装箱问题

本文讨论了一类在线变尺寸装箱问题,假定箱子的尺寸可以是不同的.箱子是在线到达的,仅当箱子到达后其尺寸才知道.给定一个带有核元的物品表及其上的核元关系图.我们的目标是要将表中元素装入到达的箱子中,保证任何箱子所装物品不互为核元,即所装物品对应的点所导出的子图是个空图,并使得所用的箱子总长最小.我们证明了该问题是NPHard的,并给出了基于图的点染色、图的团分解和基于背包问题的近似算法,给出了算法的时间复杂度和性能界.     

Single machine scheduling with controllable release and processing parameters

This paper considers single machine scheduling problems in which the job processing times and/or their release dates are controllable. Possible changes to the controllable parameters are either individual or done by controlling the relevant processing or release rate. The objective is to minimize the sum of the makespan plus the cost for changing the parameters. For the problems of this type, we provide a number of polynomial-time algorithms and give a fairly complete complexity classification.     

箱子是在线到达的带核元变尺寸装箱问题

本文考虑了一类箱子在线到达的带核元变尺寸装箱问题．假定箱子的尺寸可以是不同的．箱子是在线到达的，仅当箱子到达后其尺寸才知道．给定一个带有核元的物件表，目标是要将表中元素装入到达的箱子中，使得所用的箱子总长最小．我们首先证明了该问题是强NP—Hard，其次分析了经典算法NF(D)和FF(D)的性能界，指出NF(D)和FF(D)算法的性能界可以任意大．最后我们给出了相应的修改算法MNF(D)和MFF(D)，证明了它们的性能界都是3，此界是紧的．     

Hardness of approximation for orthogonal rectangle packing and covering problems

Bansal and Sviridenko [N. Bansal, M. Sviridenko, New approximability and inapproximability results for 2-dimensional bin packing, in: Proceedings of the 15th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 189–196] proved that there is no asymptotic PTAS for 2-dimensional Orthogonal Bin Packing (without rotations), unless P=NP. We show that similar approximation hardness results hold for several 2- and 3-dimensional rectangle packing and covering problems even if rotations by ninety degrees are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm. Our hardness results apply to the most studied case of 2-dimensional problems with unit square bins, and for 3-dimensional strip packing and covering problems with a strip of unit square base.     

A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing

The three-dimensional bin packing problem consists of packing a set of boxes into the minimum number of bins. In this paper we propose a new GRASP algorithm for solving three-dimensional bin packing problems which can also be directly applied to the two-dimensional case. The constructive phase is based on a maximal-space heuristic developed for the container loading problem. In the improvement phase, several new moves are designed and combined in a VND structure. The resulting hybrid GRASP/VND algorithm is simple and quite fast and the extensive computational results on test instances from the literature show that the quality of the solutions is equal to or better than that obtained by the best existing heuristic procedures.     

Experimental study of scheduling with memory constraints using hybrid methods

In this paper we study divisible load scheduling in systems with limited memory. Divisible loads are parallel computations which can be divided into independent parts processed in parallel on remote computers, and the part sizes may be arbitrary. The distributed system is a heterogeneous single level tree. The total size of processor memories is too small to accommodate the whole load at any moment of time. Therefore, the load is distributed in many rounds. Memory reservations have block nature. The problem consists in distributing the load taking into account communication time, computation time, and limited memory buffers so that the whole processing finishes as early as possible. This problem is both combinatorial and algebraic in nature. Therefore, hybrid algorithms are given to solve it. Two algorithms are proposed to solve the combinatorial component. A branch-and-bound algorithm is nearly unusable due to its complexity. Then, a genetic algorithm is proposed with more tractable execution times. For a given solution of the combinatorial part we formulate the solution of the algebraic part as a linear programming problem. An extensive computational study is performed to analyze the impact of various system parameters on the quality of the solutions. From this we were able to infer on the nature of the scheduling problem.     

Resource augmented semi-online bounded space bin packing

We study on-line bounded space bin-packing in the resource augmentation model of competitive analysis. In this model, the on-line bounded space packing algorithm has to pack a list L of items with sizes in (0, 1], into a minimum number of bins of size b, b≥1. A bounded space algorithm has the property that it only has a constant number of active bins available to accept items at any point during processing. The performance of the algorithm is measured by comparing the produced packing with an optimal offline packing of the list L into bins of size 1. The competitive ratio then becomes a function of the on-line bin size b. Csirik and Woeginger studied this problem in [J. Csirik, G.J. Woeginger, Resource augmentation for online bounded space bin packing, Journal of Algorithms 44(2) (2002) 308-320] and proved that no on-line bounded space algorithm can perform better than a certain bound ρ(b) in the worst case. We relax the on-line condition by allowing a complete repacking within the active bins, and show that the same lower bound holds for this problem as well, and repacking may only allow one to obtain the exact best possible competitive ratio of ρ(b) having a constant number of active bins, instead of achieving this bound in the limit. We design a polynomial time on-line algorithm that uses three active bins and achieves the exact best possible competitive ratio ρ(b) for the given problem.     

An agent-based approach to the two-dimensional guillotine bin packing problem

The two-dimensional guillotine bin packing problem consists of packing, without overlap, small rectangular items into the smallest number of large rectangular bins where items are obtained via guillotine cuts. This problem is solved using a new guillotine bottom left (GBL) constructive heuristic and its agent-based (A–B) implementation. GBL, which is sequential, successively packs items into a bin and creates a new bin every time it can no longer fit any unpacked item into the current one. A–B, which is pseudo-parallel, uses the simplest system of artificial life. This system consists of active agents dynamically interacting in real time to jointly fill the bins while each agent is driven by its own parameters, decision process, and fitness assessment. A–B is particularly fast and yields near-optimal solutions. Its modularity makes it easily adaptable to knapsack related problems.     

Space defragmentation for packing problems

One of main difficulties of multi-dimensional packing problems is the fragmentation of free space into several unusable small parts after a few items are packed. This study proposes a defragmentation technique to combine the fragmented space into a continuous usable space, which potentially allows the packing of additional items. We illustrate the effectiveness of this technique using the two- and three-dimensional bin packing problem, where the aim is to load all given items (represented by rectangular boxes) into the minimum number of identical bins. Experimental results based on well-known 2D and 3D bin packing data sets show that our defragmentation technique alone is able to produce solutions approaching the quality of considerably more complex meta-heuristic approaches for the problem. In conjunction with a bin shuffling strategy for incremental improvement, our resultant algorithm outperforms all leading meta-heuristic approaches based on the commonly used benchmark data by a significant margin.     

An asymptotically exact algorithm for the high-multiplicity bin packing problem

The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C=2 the problem can be solved in time O( log D). For the general case, we give an algorithm which provides a solution requiring at most C−2 bins more than the optimal solution, i.e., an algorithm that is asymptotically exact. For fixed C, the complexity of the algorithm is O(poly( log D)), where poly(·) is a polynomial function not depending on C.     

Integrated simulation and optimization models for tracking international fixed income indices

Portfolio managers in the international fixed income markets must address jointly the interest rate risk in each market and the exchange rate volatility across markets. This paper develops integrated simulation and optimization models that address these issues in a common framework. Monte Carlo simulation procedures generate jointly scenarios of interest and exchange rates and, thereby, scenarios of holding period returns of the available securities. The portfolio manager’s risk tolerance is incorporated either through a utility function or a (modified) mean absolute deviation function. The optimization models prescribe asset allocation weights among the different markets and also resolve bond-picking decisions. Therefore several interrelated decisions are cast in a common framework. Two models – an expected utility maximization and a mean absolute deviation minimization – are implemented and tested empirically in tracking a composite index of the international bond markets. Backtesting over the period January 1997 to July 1998 illustrate the efficacy of the optimization models in dealing with uncertainty and tracking effectively the volatile index. Of particular interest is the empirical demostration that the integrative models generate portfolios that dominate the portfolios obtained using classical disintegrated approaches. Received: November 24, 1998 / Accepted: October 1, 2000?Published online December 15, 2000     

Selfish Square Packing

We consider a game-theoretical bin packing problem. The 1D (one dimensional) case has been treated in the literature as the ʼselfish bin packing problemʼ. We investigate a 2D version, in which the items to be packed are squares and the bins are unit squares. In this game, a set of items is packed into bins. Each player controls exactly one item and is charged with a cost defined as the ratio between the area of the item and the occupied area of the respective bin. One at a time, players selfishly move their items from one bin to another, in order to minimize the costs they are charged. At a Nash equilibrium, no player can reduce the cost he is charged by moving his item to a different bin. In the 2D case, to decide whether an item can be placed in another bin with other items is NP-complete, so we consider that players use a packing algorithm to make this decision. We show that this game converges to a Nash equilibrium, independently of the packing algorithm used. We prove that the price of anarchy is at least 2.27. We also prove that, using the NFDH packing algorithm, the asymptotic price of anarchy is at most 2.6875.     

An approximation algorithm for square packing

We consider the problem of packing squares into bins which are unit squares, where the goal is to minimize the number of bins used. We present an algorithm for this problem with an absolute worst-case ratio of 2, which is optimal provided P≠NP.