China
Africa
Explore chapters and articles related to this topic
Heuristics for Two-Dimensional Bin-Packing Problems
Published in Bogdan M. Wilamowski, J. David Irwin, Intelligent Systems, 2018
Tak Ming Chan, Filipe Alvelos, Elsa Silva, J.M. Valério de Carvalho
The hybrid best fit approach was suggested by Berkey and Wang (1987). The implementation of this approach is similar to that of hybrid first fit. The best-fit decreasing height strategy is adopted to conduct a strip packing in the first stage. The idea of this strategy is that an item is packed in the left-justified way in the level satisfying two criteria: (1) it fits the item and (2) the residual width is minimized. If no level can accommodate the item, a new level is created and the item is loaded in the left-justified way in this level. In the second stage, the one-dimensional bin-packing problem is attacked by the best-fit decreasing algorithm whose procedures are given as follows. The current strip is packed into the bin fulfilling two criteria: (1) it fits the strip and (2) the residual height is minimized. If no bin can accommodate the strip, a new bin is created.
Design of production networks for the production of floating substructures for offshore wind turbines
Published in C. Guedes Soares, Developments in Renewable Energies Offshore, 2020
B. Illgen, J. Sender, H. Herholz, W. Flügge
In order to solve such a NP-hard Bin Packing problem, there is a multitude of algorithms (usually heuristics) which follow different approaches. The most commonly used basic forms are the First Fit, the Next Fit, the Best Fit and the Worst Fit algorithms. Those assume a predefined sequence of objects and provide different rules for the assignment of a bin to the respective object in turn (Scheithauer 2018).
Introduction
Published in Joseph Y.-T. Leung, Handbook of SCHEDULING, 2004
A second main approximation approach is to use the dual form of the problem, known as bin-packing. In a bin-packing problem, a number of items of various sizes are to be packed into a minimum number of bins of a common given capacity. Note that problems of scheduling to minimize the makespan and of bin-packing share the same decision version. Naturally, bin-packing techniques are considered for scheduling.
How to benefit from order data: correlated dispersed storage assignment in robotic warehouses
Published in International Journal of Production Research, 2022
Masoud Mirzaei, Nima Zaerpour, René B.M. de Koster
The model introduced in Section 4.1 provides the optimal assignment for the stock quantities of products to pods, pods to locations, and inventory to orders. The CDA model is NP-hard because it can be reduced to a bin packing problem when the order set is reduced to one order. Suppose that pods are equivalent to bins with the same capacity and . , and the volume of the products are calculated as for all the products in the order. Now, the optimal assignment of all products in the order to pods to minimise the travel time of products is equivalent to the minimum number of bins needed to pack the products’ inventory. This is a bin packing problem, a classic NP-hard problem (Garey and Johnson 1979).
Batching and scheduling in a continuous-discrete hybrid flowshop: Lagrangian relaxation-based heuristic algorithms
Published in International Journal of Production Research, 2023
FFLR is further simplified by decoupling the batch formation and hybrid flow shop scheduling to a two-stage decision problem. Specifically, batches are obtained by the commonly used First-Fit heuristic in Bin Packing problem in the first stage. In the second stage, we still use the Lagrangian approach as discussed in Section 3, except that, as the set of jobs in the batch is already settled, dynamic programming of would solve the optimal schedule for each batch. It substantially reduces the computational efforts. The scheme of this heuristic is illustrated in Figure 6.
Aggregation of clans to speed-up solving linear systems on parallel architectures
Published in International Journal of Parallel, Emergent and Distributed Systems, 2022
Dmitry A. Zaitsev, Tatiana R. Shmeleva, Piotr Luszczek
The multi-way number partitioning problem [43] consists of dividing a given multi-set of n integers into a given number k of subsets, minimising the difference between the smallest and the largest subset sums. A specific variant called a bin packing perfectly suits our problem best. In the bin packing problem [6], objects of different volumes are packed into a finite number of bins or containers, each one of a given volume in a way that minimises the number of bins used. Both problems are known to be NP-complete though a series of fast and relatively good quality heuristic techniques are available.