Search

Bin packing problem (BPP) is one of the fastest-growing research issues within the field of combinatorial optimization. Over the last years, several studies carried out various BPP variants, mathematical models, and proposed methods to the BPPs. The classical BPP consists of packing a set of rectangular items in a minimum number of rectangular bins while respecting some constraints.Throughout the years, an improved typology was introduced by Wäscher et al. (2007), providing an excellent instrument for the organization and categorization criteria that defined the problem categories different from those of Dyckhoff (1990). Several early literature reviews have been conducted on various aspects of related packing problem variants.The contribution of this paper is to provide a comprehensive and refined taxonomy intended for BPPs. In addition to that, it is an up-to-date review based on a chronological taxonomy of the literature and depicts further research horizons.This systematic review allowed us to identify other characteristics and constraints, based on Wäscher's original ideas, mainly distinguished according to real cases studies. The detailed analysis provides a valuable framework for understanding the research gaps for future studies that should be acknowledged while proposing and solving new extensions. Note: The addresses of second and third authors have been corrected online. [ABSTRACT FROM AUTHOR]

Submissions of papers were open to the entire communities of Operations Research and Computer Science, and in particular from the participants to the International Conference ODS2020 on Optimization and Decision Science, held online on November 19, 2020. The main contribution of the paper I A constrained optimization model for the provision of services in a 5G network with multi-level cybersecurity investments i , by Cappello et al. ([3]), is a multi-tiered network-based optimization model, and a solution algorithm, for the provision of 5G services considering the security levels of each provider. The paper I Price of robustness optimization through demand forecasting with an application to waste management, i by Gentile et al. ([5]), studies a robust optimization approach for making effective decisions in the presence of different forms of uncertainty. [Extracted from the article]

This document is a special issue of the journal Mathematics dedicated to recent advances in discrete optimization and scheduling. The issue includes 10 papers covering a range of topics such as batch loading and scheduling, optimization algorithms, scheduling surgeries, routing problems, and mathematical models for simplification. The papers present various approaches and algorithms for solving these problems, and they have been reviewed by experts in the field. The authors express their gratitude to the contributors, reviewers, and editorial staff, and hope that the readers will find stimulating ideas for further research in this area. [Extracted from the article]

To improve cargo loading efficiency and achieve diverse needs of companies for the loading process, this paper innovatively establishes a multiple objective mixed integer programming model for the three-dimensional multiple bin-size bin packing problem (3D-MBSBPP). The model is designed to maximize container space utilization rate and cargo load balance, minimize container usage costs, and incorporates some practical constraints. On this basis, we propose a novel dynamic feedback algorithm based on spatial corner fitness (SCF_DFA) to solve this model, which consists of three stages. Specifically, Stage 1 employs a heuristic algorithm based on spatial corner fitness to optimize the search of the remaining spaces. Stage 2 employs a container type selection algorithm to dynamically adjust and optimize container types. Stage 3 uses an improved genetic algorithm to improve the quality of the solutions of the first two stages. We demonstrate the effectiveness of the proposed algorithm through comparative experiments on benchmark instances, and apply it to solve the real-life instances for the 3D-MBSBPP. The results show that the proposed algorithm can make the average container space utilization rate reach 85.38%, which is 1.48% higher than that of baseline method, while the loading results obtained are more balanced, indicating the advantages of the SCF_DFA in solving 3D-MBSBPP. Furthermore, we conduct ablation experiments to confirm the effectiveness of each component within the algorithm. [ABSTRACT FROM AUTHOR]

The bin packing problem has a wide range of applications in industry. With the upgrade of the task difficulty, the traditional 2d rectangular layout algorithm can no longer meet the needs of modern industry, such as express packing task and exoplanet ore collection task. The express or ore samples come in heterogeneous shapes so they cannot all be treated as rectangular pieces. In this paper, we propose a three-stage method called covering, corner-searching and occupying (C,S&O) to solve the two-dimensional multishape part packing problem. The objective of the packing problem variant is to ensure maximum use of the raw material and minimize the trim loss. The algorithm cannot make use of information about the sequence of future objects that are going to arrive, only knowing the shape and size of the coming one, and the coming part must be packed into the bin immediately after its arrival without buffering or readjusting. The method of C,S&O hybridizes the idea of "gold corners, silver edges and grass belly" in the Chinese game Go and the method of finding picture corners in machine vision. In the first stage, the rectangular bin and the coming part are transformed into matrix representation, and generating the position matrix that indicates possible ways of packing the part into the bin. In the second stage, the suitable layout position of the coming part is obtained using machine vision image processing technology for reference. The third stage is calculating the environment matching degree to determine the current optimal placement orientation. In order to facilitate the display of the simulation results, only three shapes of parts are considered in the simulation, rectangle, circle and triangle. The experimental results show the effectiveness of this method. Consulting the literature, it is found that this paper is the first to propose a layout method for multishape manufacturing parts. [ABSTRACT FROM AUTHOR]

Weather radar is an active remote sensing device used to monitor the full lifecycle changes in severe convective weather with high spatial and temporal resolution. Effective radar calibration is a crucial foundation for ensuring the high-quality application of observational data. This paper utilizes a UAV platform equipped with a high-precision RTK system and standard metal spheres to study the principles and methods of metal sphere calibration, constructing a complete calibration process and calibration accuracy evaluation metrics. Additionally, a collocated radar comparison observation experiment was conducted for cross-validation, and metal sphere calibration tests were performed on problematic radars. The experimental results indicate the following: (1) The combined application of a high-precision RTK system and a laser range camera can provide real-time position information on the metal sphere, improving the efficiency of radar target acquisition. (2) The calibration method based on UAV-suspended metal spheres can periodically conduct the quantitative calibration of Z and ZDR, achieving calibration accuracies within 0.5 dB and 0.2 dB, respectively, and supports the qualitative inspection of key parameters such as beamwidth and pulse width. (3) During field tests, a high success rate "coarse adjustment + fine adjustment + staring" sphere-finding technique was established, based on automatic switching between RHI, PPI, and FIX scanning modes. This method directs the UAV to adjust the metal sphere to the center of the radar distance bin, reducing the impact of uneven beam filling and bin crossing, ensuring the accuracy of scattering characteristic measurements. [ABSTRACT FROM AUTHOR]

This paper introduces the Color Histogram Contouring (CHC) method, a new training-less approach to object detection that emphasizes the distinctive features in chrominance components. By building a chrominance-rich feature vector with a bin size of 1, the proposed CHC method exploits the precise information in chrominance features without increasing bin sizes, which can lead to false detections. This feature vector demonstrates invariance to lighting changes and is designed to mimic the opponent color axes used by the human visual system. The proposed CHC algorithm iterates over non-zero histogram bins of unique color features in the model, creating a feature vector for each, and emphasizes those matching in both the scene and model histograms. When both model and scene histograms for these unique features align, it ensures the presence of the model in the scene image. Extensive experiments across various scenarios show that the proposed CHC technique outperforms the benchmark training-less Swain and Ballard method and the algorithm of Viola and Jones. Additionally, a comparative experiment with the state-of-the-art You Only Look Once (YOLO) technique reveals that the proposed CHC technique surpasses YOLO in scenarios with limited training data, highlighting a significant advancement in training-less object detection. This approach offers a valuable addition to computer vision, providing an effective training-less solution for real-time autonomous robot localization and mapping in unknown environments. [ABSTRACT FROM AUTHOR]

In this paper we present an evolutionary heuristic for the offline two-dimensional variable-sized bin packing problem. In this problem we have to pack a set of rectangles into two-dimensional variable-sized rectangular bins. The bins are divided into types, and the bins in different types have different sizes and possibly different weights (costs). There are (sufficiently) many bins from each type, and any rectangle fits into at least one bin-type. The goal is to pack the rectangles into the bins without overlap, parallel to the sides, so that the total area of the used bins (or total cost) is minimized. Our algorithm is a hybrid heuristic. It uses two different techniques to generate the descendants: either estimation of distribution algorithm and sampling the resulting probability model, or applying the usual operators of evolutionary algorithms (selection, mutation). To pack the rectangles into the bins the algorithm uses the strategy of randomly choosing one of two placement heuristics, that pack always only one group (one to three) of rectangles. It improves the quality of the solutions with three local search procedures. The algorithm has been tested on benchmark instances from the literature and has been compared with other heuristics and metaheuristics. Our algorithm outperformed the previously published results. [ABSTRACT FROM AUTHOR]

Cloud computing has become one of the most popular frameworks for big data processing and analysis. To have better performance, the data chunks and their corresponding process nodes must be near each other, which is known as data locality. Moreover, to meet the deadline constraints, the available processing power next to the data locations is crucial. Considering the time and resource constraints, designing an appropriate job scheduler is essential for the effective management of memory and processing capacity. These concerns coalesce into the problem of joint data placement and job scheduling with data locality and deadline constraints. In this paper, two kinds of job sets are determined, one with equal deadlines and the other one with various deadlines. The problem of joint data placement and job scheduling with a single deadline is formulated as the problem of bin packing with splittable items and cardinality constraints, which is strongly NP-hard. Moreover, this paper proposes the polynomial-time Meddal algorithm to find a feasible solution with a few processing nodes. Experiment results have shown that the proposed method is effective, with the number of required nodes reduced by 33 % when compared to the algorithms Cred and First Fit. [ABSTRACT FROM AUTHOR]

The rectangular packing problem has been extensively studied over the years due to its wide application in industry. However, most of the research efforts are devoted to positioning techniques of the rectangles for various problem variants, the efficient implementation of the packing procedure is relatively less studied. In this paper, we propose an efficient constructive algorithm for the rectangular packing problem with rotations. We design a preprocess procedure with four data structures to store the information used for item selection. The gaps on the skyline are categorized into three types according to their associated edges for the placement procedure, during which the item is searched and packed in a descending order of the fitness value. The entire constructive phase takes a time complexity of O(nlogn). For the packing improvement phase, we optimize the packing through random perturbation on the sequence and orientation of the item. Three classes of stochastic problems are generated ranging from small-scale to extra-large-scale, the recorded running time confirms the efficiency of the proposed algorithm. We also test the proposed algorithm on the benchmark problem C21, N13, NT, Babu and CX, the computational results show that it delivers a good performance. [ABSTRACT FROM AUTHOR]

The one-dimensional cutting-stock problem (1D-CSP) consists of obtaining a set of items of different lengths from stocks of one or different lengths, where the minimization of waste is one of the main objectives to be achieved. This problem arises in several industries like wood, glass, and paper, among others similar. Different approaches have been designed to deal with this problem ranging from exact algorithms to hybrid methods of heuristics or metaheuristics. The African Buffalo Optimization (ABO) algorithm is used in this work to address the 1D-CSP. This algorithm has been recently introduced to solve combinatorial problems such as travel salesman and bin packing problems. A procedure was designed to improve the search by taking advantage of the location of the buffaloes just before it is needed to restart the herd, with the aim of not to losing the advance reached in the search. Different instances from the literature were used to test the algorithm. The results show that the developed method is competitive in waste minimization against other heuristics, metaheuristics, and hybrid approaches. [ABSTRACT FROM AUTHOR]

In the Bin Packing problem one is given n items with weights w(1),. . . ,w(n) and m bins with capacities c1, . . ., cm. The goal is to partition the items into sets S1, . . . ,Sm such that w(Sjmn) notation omits factors polynomial in the input size). In this paper, we show that for every m N there exists a constant Σm > 0 such that an instance of Bin Packing with m bins can be solved in O (2(1 y m)n) randomized time. Before our work, such improved algorithms were not known even for m= 4. A key step in our approach is the following new result in Littlewood--Offord theory on the additive combinatorics of subset Σ: For every γ > 0 there exists an >0 such that if | { X n{ 1, . . . ,n}: w(X) =v} | 2(1)n for some v, then { w(X) :X { 1, . . . ,n\} | &#947n. [ABSTRACT FROM AUTHOR]

Synchrophasor estimation was mostly used in transmission systems in the past, and it is difficult to directly apply an existing synchrophasor algorithm to a distribution system with a more complex structure and environment. A synchrophasor estimation algorithm with a high accuracy and fast response speed is required to complete the calculation of the phasor in the face of the complex and changeable power signal of a distribution network. Therefore, an enhanced all-phase discrete Fourier transform (e-apDFT) algorithm is proposed for a distribution system in this paper, and the algorithm is deployed in a phasor measurement unit (PMU) prototype based on digital signal processing (DSP). Aiming to solve the problem of the accuracy of the traditional apDFT being reduced when the response speed is fast due to the influence of a dense spectrum, the existing algorithm is improved through iteratively compensating the spectral interferences to the main bin produced by adjacent bins. The experimental results show that the e-apDFT algorithm still has a fast response speed and that its estimation accuracy is much better than that of the traditional apDFTs in the presence of adjacent harmonic components. The proposed algorithm also complies with the IEEE standards for P-class PMUs. [ABSTRACT FROM AUTHOR]

Irregular packing in e-commerce warehouses is a special case of a three-dimensional box packing problem (3DBPP). It is necessary to select the type and quantity of boxes and determine the location and orientation of the items to maximize the use of the loading space. In this paper, a spatial particle model of the 3DBPP for multiple boxes and irregular items is constructed using the three-dimensional (3D) point cloud and granulation method. In the model, the 3D point cloud is used to describe the shapes of irregular items, and the granulation method is used for the transformation from sparse and uneven point clouds to spatial particle convex hulls. In addition, we designed an empirical simulation algorithm (ESA) based on the combination of expert rules extracted in practical packing activities and empirical simulation, and an intelligent algorithm for 3DBPPs with irregular items combined with the framework of the deep Q network (DQN) algorithm in deep reinforcement learning. An instance generator is proposed based on industry data to generate realistic projects with representative attributes for the above two algorithms, such as types of boxes, irregular items, 3D spatial plane convex hulls, and spatially granular data. The numerical results show that the ESA can quickly obtain a high-quality packing scheme, and the intelligent DQN packing algorithm in deep reinforcement learning can avoid the limitation of expert rules and achieve a better scheme with a certain time for the training process. [ABSTRACT FROM AUTHOR]

A rose diagram is a representation that circularly organizes data with the bin width as the central angle. This diagram is widely used to display and summarize circular data. Some studies have proposed the selector of bin width based on data. However, only a few papers have discussed the property of these selectors from a statistical perspective. Thus, this study aims to provide a data-based bin width selector for rose diagrams using a statistical approach. We consider that the radius of the rose diagram is a nonparametric estimator of the square root of two times the circular density. We derive the mean integrated square error of the rose diagram and its optimal bin width and propose two new selectors: normal reference rule and biased cross-validation. We show that biased cross-validation converges to its optimizer. Additionally, we propose a polygon rose diagram to enhance the rose diagram. [ABSTRACT FROM AUTHOR]

This paper addresses the two-dimensional irregular bin packing problem, whose main aim is to allocate a given set of irregular pieces to larger rectangular containers (bins), while minimizing the number of bins required to contain all pieces. To solve the problem under study a dynamic hierarchical hyper-heuristic approach is proposed. The main idea of the hyper-heuristics is to search the space of low-level heuristics for solving computationally difficult problems. The proposed approach is "dynamic" since the low-level heuristic to be executed is chosen on the basis of the main characteristics of the instance to be solved. The term "hierarchical" is used to indicate the fact that the main hyper-heuristic can execute either simple heuristics or can run in a "recursive fashion" a hyper-heuristic. The developed solution strategy is evaluated empirically by performing extensive experiments on irregular packing benchmark instances. A comparison with the state-of-the-art approaches is also carried out. The computational results are very encouraging. [ABSTRACT FROM AUTHOR]

Many algorithms that were developed for solving three-dimensional bin packing problems use generic data for either experiments or evaluation. However, none of these datasets became accepted for benchmarking 3D bin packing algorithms throughout the community. To close this gap, this paper presents the benchmarking dataset for robotic bin packing problems (BED-BPP), which is based on realistic data. We show the variety of the dataset by elaborating an n-gram analysis. Besides, we propose an evaluation function, which contains a stability check that uses rigid body simulation. We demonstrated the application of our dataset on four different approaches, which we integrated in our software environment. [ABSTRACT FROM AUTHOR]

Manufacturing systems need to be resilient and self-organizing to adapt to unexpected disruptions, such as product changes or rapid order, in supply chain changes while increasing the automation level of robotized logistics processes to cope with the lack of human experts. Deep Reinforcement Learning is a potential solution to solve more complex problems by introducing artificial neural networks in Reinforcement Learning. In this paper, a game engine was used for Deep Reinforcement Learning training, which allows visualization of view learning and result processes more intuitively than other tools, as well as a physical engine for a more realistic problem-solving environment. The present research demonstrates that a Deep Reinforcement Learning model can effectively address the real-time sequential 3D bin packing problem by utilizing a game engine to visualize the environment. The results indicate that this approach holds promise for tackling complex logistical challenges in dynamic settings. [ABSTRACT FROM AUTHOR]

In recent years, the volume of spatial data has rapidly grown, so it is crucial to process them in an efficient manner. The level of parallel processing in big data platforms such as Hadoop and Spark is determined by partitioning the dataset. A common approach is to split the data into chunks based on the number of bytes. While this approach works well for text-based batch processing, in many cases, it is preferable to take advantage of the structured information contained in the dataset (e.g., spatial coordinates) to plan data partitioning. In view of the huge amount of data and the impossibility of quickly establishing partitions, this paper designs a method for approximate partition boundary solving, which divides the data space into multiple non-overlapping symmetric bins and samples each bin, making the probability density of the sampling set bounded by the deviation of the probability density of the original data. The sampling set is read into the memory at one time for calculation, and the established partition boundary satisfies the partition threshold-setting. Only a few boundary adjustment operations are required, which greatly shortens the partition time. In this paper, the method proposed in the paper is tested on the synthetic dataset, the bus trajectory dataset, and six common spatial partitioning methods (Grid, Z-curve, H-curve, STR, Kd-tree, and R*-Grove) are selected for comparison. The results show that the symmetric bin sampling method can describe the spatial data distribution well and can be directly used for partition boundary division. [ABSTRACT FROM AUTHOR]

This paper addresses a special bin packing problem in which each item can only be assigned to a subset of the bins. We name this problem as the restricted bin packing problem (RBPP). This paper is designed to explore the relationships of RBPP with classic NP-complete problems, and to resolve the restrictions of assignment through heuristic and meta-heuristic algorithms. A new heuristic algorithm named 'Max-fit Based on Zigzag Sorting with Retained Feasibility' is proposed. In this heuristic algorithm, a feasibility retaining rule is constructed to assure the assignment of every item; a zigzag sorting method is designed to improve the performance of the algorithm. Our heuristic algorithm is able to generate better results in comparison with existing heuristics. Greedy Randomized Adaptive Search Procedure (GRASP) and Simulated Annealing (SA) are exploited to obtain better solutions for RBPP. A new construction method based on cliques and zigzag sorting are built for GRASP and SA. The proposed methods are shown to have higher efficiency than traditional ones through numeric examples. [ABSTRACT FROM AUTHOR]

Cloud computing has been studied and used extensively in many scenarios for its nearly unlimited resources and X as a service model. To reduce the latency for accessing the remote cloud data centers, small data centers or cloudlets are deployed near end-users, which is also called edge computing. In this paper, we mainly focus on the efficient scheduling of distributed simulation tasks in collaborative cloud and edge environments. Since simulation tasks are usually tightly coupled with each other by sending many messages and the status of tasks and hosts may also change frequently, it is essentially a dynamic bin-packing problem. Unfortunately, popular methods, such as meta-heuristics, and accurate algorithms are time-consuming and cannot deal with the dynamic changes of tasks and hosts efficiently. In this paper, we present Pool, an incremental flow-based scheduler, to minimize the overall communication cost of all tasks in a reasonable time span with the consideration of migration cost of task. After formulating such a scheduling problem as a min-cost max-flow (MCMF) problem, incremental MCMF algorithms are adopted to accelerate the procedure of calculating an optimal flow and heuristic scheduling algorithm, with the awareness of task migration cost, designed to assign tasks. Simulation experiments on Alibaba cluster trace show that Pool can schedule all of the tasks efficiently and is almost 5.8 times faster than the baseline method when few tasks and hosts change in the small problem scale. [ABSTRACT FROM AUTHOR]

This paper introduces the three‐dimensional case picking problem (3D‐CPP) and proposes a multistart biased‐randomized algorithm (BRA) to solve it. The 3D‐CPP combines two important topics in modern warehouse logistics: the pallet loading problem and the routing of pickers in manual warehouses. The proposed optimization procedure aims at minimizing the overall distance traveled by the pickers, and is achieved by combining a routing problem (i.e., the order in which picking positions are visited) with a loading problem (i.e., the way in which cases are placed onto the pallet). We also consider additional constraints regarding the weight, vertical support, and strength of the cases. In order to solve this problem, we first propose a constructive heuristic which combines routing and packing procedures. This initial heuristic is then extended into a multistart BRA by employing a skewed probability distribution to introduce a certain degree of randomness during the solution‐construction process. A series of computational experiments allow us to assess the quality of the proposed approach, through a comparison with other algorithms as well as using real‐life data provided by an industrial partner. [ABSTRACT FROM AUTHOR]

Given a non-decreasing sequence S = (s 1 , s 2 , ... , s k) of positive integers, an S -packing coloring of a graph G is a partition of the vertex set of G into k subsets { V 1 , V 2 , ... , V k } such that for each 1 ≤ i ≤ k , the distance between any two distinct vertices u and v in V i is at least s i + 1. In this paper, we study the problem of S -packing coloring of cubic Halin graphs, and we prove that every cubic Halin graph is (1 , 1 , 2 , 3) -packing colorable. In addition, we prove that such graphs are (1 , 2 , 2 , 2 , 2 , 2) -packing colorable. [ABSTRACT FROM AUTHOR]

In this paper three heuristic algorithms using the Divide-and-Conquer paradigm are developed and assessed for three integer optimizations problems: Multidimensional Knapsack Problem (d-KP), Bin Packing Problem (BPP) and Travelling Salesman Problem (TSP). For each case, the algorithm is introduced, together with the design of numerical experiments, in order to empirically establish its performance from both points of view: its computational time and its numerical accuracy. [ABSTRACT FROM AUTHOR]

The low-energy task scheduling of cloud computing systems is a key issue in the field of cloud computing. Nevertheless, existing works on task scheduling lack consideration of the conflict relationship between tasks and focus on heuristic and other approximate algorithms. Thus, solving the problem of minimizing energy consumption with antiaffinity constraints between tasks and designing an efficient exact algorithm for task scheduling is a major challenge. This paper abstracts the problem into a multidimensional bin packing model with conflict constraints. The model is decomposed by the Lagrange relaxation principle and Dantzig–Wolfe decomposition principle. Moreover, we propose an accurate algorithm based on branch-and-price. The algorithm benefits from a new initial solution generation scheme based on maximum cliques and dominant resource proportion, and a multipattern branching strategy. The efficiency of the proposed branch-and-price algorithm is verified by a number of numerical experiments. [ABSTRACT FROM AUTHOR]

Robots are widely used in present day situations. Since a robot consists of number of systems with different mechanisms, it needs to be planned and programmed systematically. Discrete Mathematics helps us in designing and functioning of a robotic system. For instance Robotic arm is a type of linkage and the study of which is a part of Discrete Geometry. Scheduling tasks to be completed by a set of machines use the concept of Bin-packing problem, which is a part of Discrete Optimization. Discussing functions like these, motion and path planning of the robotic system is the main concern of any industry to adapt new and modern technologies in its functioning. Literature surveys reveal that there a worldwide attempts to develop robotic systems with minimum errors and maximum efficiency. This Paper includes the usage of the Concepts of Discrete Mathematics to have a path planning for a Robotic System to work with high efficiency. [ABSTRACT FROM AUTHOR]

This paper is devoted to a class of singularly perturbed nonlinear Schrödinger systems defined on a smooth bounded domain in R N (N = 2 , 3). We use the Lyapunov–Schmidt reduction method to construct synchronized vector solutions with multiple spikes both on the boundary and in the interior of the domain. For each vector solution that has been constructed, we point out that the interior spikes locate near sphere packing points in the domain, and the boundary spikes locate near the critical points of the mean curvature function related to the boundary of the domain. [ABSTRACT FROM AUTHOR]

Many industrial processes require the nesting of 2D profiles prior to the cutting, or stamping, of components from raw sheet material. Despite decades of sustained academic effort, algorithmic solutions are still sub-optimal and produce results that can frequently be improved by manual inspection. However, the Internet offers the prospect of novel ‘human-in-the-loop’ approaches to nesting problems that uses online workers to produce packing efficiencies beyond the reach of current CAM packages. To investigate the feasibility of such an approach, this paper reports on the speed and efficiency of online workers engaged in the interactive nesting of six standard benchmark data-sets. To ensure the results accurately characterise the diverse educational and social backgrounds of the many different labour forces available online, the study has been conducted with subjects based in both Indian IT service (i.e. Rural BPOs) centres and a network of homeworkers in Northern Scotland. The results (i.e. time and packing efficiency) of the human workers are contrasted with both the baseline performance of a commercial CAM package and recent research results. The paper concludes that online workers could consistently achieve packing efficiencies roughly 4% higher than the commercial based-line established by the project. Beyond characterising the abilities of online workers to nest components, the results also make a contribution to the development of algorithmic solutions by reporting new solutions to the benchmark problems and demonstrating methods for assessing the packing strategy employed by the best workers. [ABSTRACT FROM AUTHOR]

This paper introduces a novel method for online 3-D bin packing, which is a strongly NP-hard problem, based on a space splitting and merging technique. In this scenario, the incoming box is unknown and must be immediately packed. The problem has many applications in industries that use manipulators to automate the packing process. The main idea of the approach is to divide the bin into spaces. These spaces are then categorized into one of two types of data structures: main and secondary data structures. Each node in the main data structure holds the information of a space that can be used to fit a new box. Each node in the secondary data structure holds the information of a space that cannot be used to place a box. The search algorithm based on these two data structures reduces the required search effort and simplifies the organizing and editing of the data structure. The experimental results demonstrate that the proposed method can achieve a packed volume ratio of up to 83% in the case of multiple bins being used. The position of a placed box can be found within milliseconds. [ABSTRACT FROM AUTHOR]

The online 3D bin packing problem(3D-BPP) is widely used in the logistics industry and is of great practical significance for promoting the intelligent transformation of the industry. The heuristic algorithm relies too much on manual experience to formulate more perfect packing rules. In recent years, many scholars solve 3D-BPP via deep reinforcement learning(DRL) algorithms. However, they ignore many skills used in manual packing, one of the most important skill is workers put the item aside if the item is packed improperly. Inspired by this skill, we propose a DRL algorithm with a buffer zone. Firstly, we define the wasted space and the buffer zone. And then, we integrate them into the DRL algorithm framework. Importantly, we compare the bin utilization with di erent thresholds of wasted space and di erent buffer zone sizes. Experimental results show that our algorithm outperforms existing heuristic algorithms and DRL algorithms. [ABSTRACT FROM AUTHOR]

Packing problems, also known as nesting problems or bin packing problems, are classic and popular NP-hard problems with high computational complexity. Inspired by classic reinforcement learning (RL), we established a mathematical model for two-dimensional (2D) irregular-piece packing combined with characteristics of 2D irregular pieces. An RL algorithm based on Monte Carlo learning (MC), Q-learning, and Sarsa-learning is proposed in this paper to solve a 2D irregular-piece packing problem. Additionally, mechanisms of reward–return and strategy-update based on piece packing were designed. Finally, the standard test case of irregular pieces was used for experimental testing to analyze the optimization effect of the algorithm. The experimental results show that the proposed algorithm can successfully realize packing of 2D irregular pieces. A similar or better optimization effect can be obtained compared to some classical heuristic algorithms. The proposed algorithm is an early attempt to use machine learning to solve 2D irregular packing problems. On the one hand, our hybrid RL algorithm can provide a basis for subsequent deep reinforcement learning (DRL) to solve packing problems, which has far-reaching theoretical significance. On the other hand, it has practical significance for improving the utilization rate of raw materials and broadening the application field of machine learning. [ABSTRACT FROM AUTHOR]

Ship–infrastructure cooperation, i.e., infrastructure scheduling, is significant for optimizing the utilization of spatial-temporal resources of infrastructures and improving the efficiency and safety of waterborne transportation systems. This paper carries out a systematic review of the scheduling problems of the infrastructures in waterborne transportation systems, including locks, terminals, berths, and waterway intersections. The infrastructure scheduling problems are linked to the classical optimization problems, and a generalized infrastructure scheduling problem is formulated. For lock scheduling, the ship placement sub-problem aims at minimizing the number of lockages, which is a kind of classic 2D bin packing problem; the lockage scheduling sub-problem deals with chamber assignment and lockage operation planning, which is modeled as a single or parallel machine scheduling problem. For berth and terminal scheduling, the idea of queuing theory (for discrete terminal) and 2D bin packing (for continuous terminal) are usually applied. Most research aims at minimizing the waiting time of ships and focuses on the continuous dynamic terminal scheduling problems. As a special infrastructure, the waterway intersection receives little attention. Most research focuses on traffic conflicts and capacity problems. Future research directions are provided based on the review results and problems of infrastructure scheduling in practice. [ABSTRACT FROM AUTHOR]

Edge computing plays a critical role in IoT as it potentially minimized the computation tasks response latency demanded by time-critical IoT applications. The growth of IoT users with high demanded computation power as well as ultra-low latency tasks may cause the performance degradation. One way to minimize the end-to-end (E2E) latency is to form horizontal edge federation (HEF) so that the computation resources can be shared with each participating edge node. Achieving ultra-low latency in HEF-IoT ecosystem involves setting two factor: resource allocation and task dispatching. This two factor interact with each other yet feasible solutions must provide satisfactory service level to meet latency constraints demanded by target applications. In this paper, we formulate it as E2E latency minimization problem and proposed a two-phase iterative (TPI) approach. The TPI method alternately determines optimal task dispatching and computation resource allocation. We exploit bin packing problem and, genetic algorithm (GA) to determine the edge nodes, and the required computation resources. The simulation results show that by using TPI approach, we can achieve more throughput, minimum E2E latency and optimum number of required edge nodes. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper studies the assignment problem of multi product assembly jobs to days. The problem aims to minimize the amount of overtime while avoiding assembly delays for jobs that can be fragmented into smaller sub-tasks. When sequencedependent setup times are negligible, the problem considered transforms into the bin packing problem with restricted item fragmentation where jobs represent items and days stand for bins. We present a mixed integer programming model of the problem by extending earlier formulations in the literature. Computational experiments show that the mathematical model obtained optimal solutions for majority of instances tested within reasonable computation times. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of automating the definition of feasible pallets configurations. This issue is crucial for the competitiveness of logistic companies and is still one of the most difficult problems in internal logistics. In fact, it requires the fast solution of a three-dimensional Bin Packing Problem (3D-BPP) with additional logistic specifications that are fundamental in real applications. To this aim, we propose a matheuristics that, given a set of items, provides feasible pallets configurations that satisfy the practical requirements of items’ grouping by logistic features, load bearing, stability, height homogeneity, overhang as well as weight limits, and robotized layer picking. The proposed matheuristics combines a mixed integer linear programming (MILP) formulation of the 3D-Single Bin-Size BPP (3D-SBSBPP) and a layer building heuristics. In particular, the feasible pallets configurations are obtained by sequentially solving two MILP sub-problems: the first, given the set of items to be packed, aims at minimizing the unused space in each layer and thus the number of layers; the latter aims at minimizing the number of shipping bins given the set of layers obtained from the first problem. The approach is extensively tested and compared with existing approaches. For its validation we use both realistic data-sets drawn from the literature and real data-sets, obtained from an Italian logistics leader. The resulting outcomes show the effectiveness of the method in providing high-quality bin configurations in short computational times. Note to Practitioners—This work is motivated by the intention of facilitating the transition from Logistics 3.0 to Logistics 4.0 by providing an effective tool to automate bin packing, suitable for automated warehouses. On the one hand, the proposed technique provides stable and compact bin configurations in less than half a minute per bin on average, despite the high computational complexity of the 3D-SBSBPP. On the other hand, the approach allows to consider compatibility constraints for the items (e.g., final customer and category of the items), and the use of robotized layer picking in automated warehouses. In effect, layers composed by only one type of items (i.e., monoitem layers) can be directly picked and placed on the pallet by a robotic arm without the intervention of any operator. Consequently, the adoption of this approach in warehouses could drastically improve the efficiency of the packing process. [ABSTRACT FROM AUTHOR]

Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new stabilization framework, which relies on the dynamic generation of aggregated rows from the CG master problem. To evaluate the performance of our method and its flexibility, we consider instances of three different problems, namely, vehicle routing with time windows (VRPTW), bin packing with conflicts (BPPC), and multiperson pose estimation (MPPEP). When solving the VRPTW, the proposed stabilized CG method yields significant improvements in terms of CPU time and number of iterations with respect to a standard CG algorithm. Huge reductions in CPU time are also achieved when solving the BPPC and the MPPEP. For the latter, our method has shown to be competitive when compared with a tailored method. Summary of Contribution: Column generation (CG) algorithms are among the most important and studied solution methods in operations research. CG algorithms are suitable to cope with large-scale problems arising from several real-life applications. The present paper proposes a generic stabilization framework to address two of the main issues found in a CG method: degeneracy in the master problem and massive instability of the dual variables. The newly devised method, called dynamic separation of aggregated rows (dyn-SAR), relies on an extended master problem that contains redundant constraints obtained by aggregating constraints from the original master problem formulation. This new formulation is solved in a column/row generation fashion. The efficacy of the proposed method is tested through an extensive experimental campaign, where we solve three different problems that differ considerably in terms of their constraints and objective function. Despite being a generic framework, dyn-SAR requires the embedded CG algorithm to be tailored to the application at hand. [ABSTRACT FROM AUTHOR]

This paper considers a traditional problem of resource allocation: scheduling jobs on machines. One such recent application is cloud computing; jobs arrive in an online fashion with capacity requirements and need to be immediately scheduled on physical machines in data centers. It is often observed that the requested capacities are not fully utilized, hence offering an opportunity to employ an overcommitment policy, that is, selling resources beyond capacity. Setting the right overcommitment level can yield a significant cost reduction for the cloud provider while only inducing a very low risk of violating capacity constraints. We introduce and study a model that quantifies the value of overcommitment by modeling the problem as bin packing with chance constraints. We then propose an alternative formulation that transforms each chance constraint to a submodular function. We show that our model captures the risk pooling effect and can guide scheduling and overcommitment decisions. We also develop a family of online algorithms that are intuitive, easy to implement, and provide a constant factor guarantee from optimal. Finally, we calibrate our model using realistic workload data and test our approach in a practical setting. Our analysis and experiments illustrate the benefit of overcommitment in cloud services and suggest a cost reduction of 1.5% to 17%, depending on the provider's risk tolerance. The online appendices are available at https://doi.org/10.1287/mnsc.2018.3091. [ABSTRACT FROM AUTHOR]

Cloud computing hosts large number of modern day applications using the virtualization concept. However, end-toend network latencies are detrimental to the performance of IoT (Internet of Things) applications like video surveillance and health monitoring. Although edge/fog computing alleviates the latency concerns to some extent, it is still not suitable for applications having intercommunicating tasks. Further, these applications can be elastic in nature and demand more tasks during their life-time. To address this gap, in this paper a network aware co-allocation strategy for the tasks of an individual applications is proposed. After modelling the problem using bin packing approach with additional constraints, the authors propose a novel heuristic IcAPER,(Intercommunication Aware Placement for Elastic Requests) algorithm. The proposed algorithm uses the network neighborhood machine for placement, once current resource is fully utilized by the application. Using CloudsimPlus simulator the performance IcAPER algorithm is compared with First Come First Serve (FCFS), Random and First Fit Decreasing (FFD) algorithms for the parameters (a) resource utilization (b) resource fragmentation and (c) Number of requests having intercommunicating tasks placed on to same PM. Extensive simulation results shows IcAPER maps 34% more tasks on to the same PM and also increase the resource utilization by 13% while decreasing the resource fragmentation by 37.8% when compared to other algorithms in our consideration. [ABSTRACT FROM AUTHOR]

We consider the one-dimensional skiving stock problem which is strongly related to the dual bin packing problem: find the maximum number of objects, each having a length of at least L, that can be constructed by connecting a given supply of m∈N smaller item lengths l1,…,lm with availabilities b1,…,bm. For this NP-hard discrete optimization problem, the (additive integrality) gap, i.e., the difference between the optimal objective values of the continuous relaxation and the skiving stock problem itself, is known to be strictly less than 3 / 2 if li∣L is assumed for all items, hereinafter referred to as the divisible case. Within this framework, we derive sufficient conditions that ensure the integer round-down property, i.e., a gap smaller than one, of a given instance. As a main contribution, we present improved upper bounds for the gap (of special subclasses) of the divisible case by means of combinatorial and algorithmic approaches. In a final step, possible generalizations of the introduced concepts are discussed. Altogether, the results presented in this paper give strong evidence that 22 / 21 represents the best possible upper bound for the gap of divisible case instances. [ABSTRACT FROM AUTHOR]

Concentrating on a single resource cannot efficiently cope with the overall high utilization of resources in cloud data centers. Nowadays multiple resource scheduling problem is more attractive to researchers. Some studies achieve progresses in multi-resource scenarios. However, these previous heuristics have obvious limitations in complex software defined cloud environment. Focusing on energy conservation and load balancing, we propose a preciousness model for multiple resource scheduling in this paper. We give the formulation of the problem and propose an innovative strategy (P-Aware). In P-Aware, a special algorithm PMDBP (Proportional Multi-dimensional Bin Packing) is applied in the multi-dimensional bin packing approach. In this algorithm, multiple resources are consumed in a proportional way. Structure and details of PMDBP are discussed in this paper. Extensive experiments demonstrate that our strategy outperforms others both in efficiency and load balancing. Now P-Aware has been implemented in the resource management system in our cooperative company to cut energy consumption and reduce resource contention. [ABSTRACT FROM AUTHOR]