Search

Although blind source separation of convolutive mixtures can be efficiently solved in the frequency domain, the problem of permutation ambiguity must be solved. Thus, this paper proposes an improved permutation algorithm. Firstly, the improved algorithm uses energy correlation of the separated signal to sort the signals of each frequency bin. Then, the reliability of the sorting of the signals on the frequency bin will be judged according to the threshold. The unreliable frequency bins will be corrected in time so that we can obtain the separated signal accurately, eventually. This algorithm effectively reduces sorting errors and error propagation, thereby improving the separation effect. BSS experiments are performed on the voice signals and radar signals under different convolutive mixing models. The simulation results show that the improved algorithm has better separation performance and higher robustness than the traditional permutation algorithms, which is reflected by the increasing signal to interference ratio of separated signals. [ABSTRACT FROM AUTHOR]

With the penetration of Network Function Virtualization (NFV), network functions, traditionally deployed as proprietary physical equipment like firewalls, Network Address Translations (NATs), are gradually being implemented as software and deployed on standardized hardware. One of the crucial challenges in this paradigm is how to place the software implemented network functions to minimize the number of used physical servers. In this paper, we study the problem of how to optimally place Virtual Network Functions (VNFs) in networks where it is allowed to migrate already placed VNFs to decrease used servers. We first formulate the offline problem as an Integer Linear Programming (ILP) problem, and then propose a semi-online algorithm to solve the online variant of the problem. We name the proposed algorithm Semi-onlIne Vnf plAcement (SIVA). In particular, SIVA is based on a bin packing algorithm that solves online bin packing problem while taking care of migrations. According to our theoretical analysis, SIVA migrates at most λ VNFs each step, and it has Asymptotic Competitive Ratio (ACR) of 3/2 if k → ∞ , where λ = k · | N | , k is a tunable parameter, and | N | is the the number of supported VNF types. We conduct extensive numerical simulations to evaluate the performances of SIVA. The experiment results validate the theoretical analysis and show that SIVA outperforms the state-of-the-art algorithms by achieving near-optimal performance with minor VNF migrations. [ABSTRACT FROM AUTHOR]

Summary. The bin packing problem is a fundamental and important optimization problem in theoretical computer science [4], [6]. An instance is a sequence of items, each being of positive size at most one. The task is to place all the items into bins so that the total size of items in each bin is at most one and the number of bins that contain at least one item is minimum. Approximation algorithms have been intensively studied. Algorithm NextFit would be the simplest one. The algorithm repeatedly does the following: If the first unprocessed item in the sequence can be placed, in terms of size, additionally to the bin into which the algorithm has placed an item the last time, place the item into that bin; otherwise place the item into an empty bin. Johnson [5] proved that the number of the resulting bins by algorithm NextFit is less than twice the number of the fewest bins that are needed to contain all items. In this article, we formalize in Mizar [1], [2] the bin packing problem as follows: An instance is a sequence of positive real numbers that are each at most one. The task is to find a function that maps the indices of the sequence to positive integers such that the sum of the subsequence for each of the inverse images is at most one and the size of the image is minimum. We then formalize algorithm NextFit, its feasibility, its approximation guarantee, and the tightness of the approximation guarantee. [ABSTRACT FROM AUTHOR]

Most important scientific and engineering applications have complex computations or large data. In all these applications, a huge amount of time is consumed by nested loops. Therefore, loops are the main source of the parallelization of scientific and engineering programs. Many parallelizing compilers focus on parallelization of nested loops with uniform dependences, and parallelization of nested loops with non-uniform dependences has not been extensively investigated. This paper addresses the problem of parallelizing two-level nested loops with non-uniform dependences. The aim is to minimize the execution time by improving the load balancing and minimizing the inter-processor communication. We propose a new tiling algorithm, k-StepIntraTiling, using bin packing problem to minimize the execution time. We demonstrate the effectiveness of the proposed method in several experiments. Simulation and experimental results show that the algorithm effectively reduces the total execution time of several benchmarks compared to the other tiling methods. [ABSTRACT FROM AUTHOR]

Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) random order ratio as an alternative performance measure for online algorithms. Here, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Kenyon's result establishes lower and upper bounds of 1.08 and 1.5, respectively, for the random order ratio of Best Fit. Although this type of analysis model became increasingly popular in the field of online algorithms, no progress has been made for the Best Fit algorithm after the result of Kenyon. We study the random order ratio of Best Fit and tighten the long-standing gap by establishing an improved lower bound of 1.10. For the case where all items are larger than 1/3, we show that the random order ratio converges quickly to 1.25. It is the existence of such large items that crucially determines the performance of Best Fit in the general case. Moreover, this case is closely related to the classical maximum-cardinality matching problem in the fully online model. As a side product, we show that Best Fit satisfies a monotonicity property on such instances, unlike in the general case. In addition, we initiate the study of the absolute random order ratio for this problem. In contrast to asymptotic ratios, absolute ratios must hold even for instances that can be packed into a small number of bins. We show that the absolute random order ratio of Best Fit is at least 1.3. For the case where all items are larger than 1/3, we derive upper and lower bounds of 21/16 and 1.2, respectively. [ABSTRACT FROM AUTHOR]

Optimizing the order-fulfillment process is crucial to the logistics industry. Replacing experience-based judgment with intelligent methods in the packing process not only improves work efficiency but also eliminates resource wastage. This study focuses on the three-dimensional multiple bin-size bin packing problem with compatible categories (3D-MBSBPPCC) and different size of the boxes. An algorithm is developed to achieve the best packing pattern while minimizing the number of boxes required and the total unused space in the boxes. In the algorithm, we first use the first-fit decreasing algorithm to find an initial solution. Next, the carton configuration algorithm is applied to perform packing and evaluate the solution. Subsequently, a simulated annealing (SA)-based algorithm is employed to improve the solution by moving the products among the subsets of the solution. Finally, hybrid metaheuristics based on both SA and the genetic algorithm, are proposed to improve the solution quality. We tested the proposed packing algorithms on real-world scenarios. The experimental results demonstrate that the proposed algorithms are effective in solving 3D-MBSBPPCC. [ABSTRACT FROM AUTHOR]

Nature-inspired metaheuristic algorithms have steadily gained popularity over the last two decades. They have been applied to a plethora of optimization problems both in continuous and combinatorial domains. In this paper, the one-dimensional bin packing problem is solved through the implementation of two underlying heuristics, namely, best fit and better fit, and four representative state-of-the-art global metaheuristic algorithms, namely, firefly algorithm, genetic algorithm, adaptive cuckoo search algorithm, and artificial bee colony algorithm. The underlying best fit and better fit heuristics are employed by the four aforementioned global metaheuristic algorithms as reordering heuristics and local search improvement mechanisms are used for generating good packing schema. Furthermore, these two local heuristics possess special characteristics which, when incorporated into the global metaheuristics, allow them to escape local optimums and avoid getting stuck, and more so, enables the algorithms to generate good quality solutions. The main focus of this paper is the presentation of a systematic performance evaluation study for the representative algorithms, with some initial computational results that show the effectiveness of the respective algorithms and their ability to achieve promising solutions. The experiments conducted here were carried out using three standard bin packing problem datasets categories with over 1,210 instances in total, each with differing capacities, number of items and distributions between item weights. The numerical results of the representative algorithms were compared with the solutions achieved with the underlying heuristic techniques, in this case, the best fit and better fit heuristics, respectively. Similarly, the analysis of the initial computational results obtained revealed the superior performance of the individual algorithm implementation. Moreover, performance was established by taking into account both the algorithms computational time and the solution quality. Overall, several observations regarding the solution and the underlying heuristics were made. It is worth noting that by utilizing best fit heuristic, the algorithms attained optimal solutions for instances of the easy dataset requiring smaller capacity bins. However, as the complexity of the instances increased, the ability to produce high-quality results decreased. Nevertheless, this heuristic can produce near-optimal solutions and a good packing schema for most instances. On the other hand, utilizing better fit as the underlying heuristic results in optimal solutions almost all the time, regardless of capacity and number of items.

Copy number variation (CNV), is defined as repetitions or deletions of genomic segments of 1 Kb to 5 Mb, and is a major trigger for human disease. The high-throughput and low-cost characteristics of next-generation sequencing technology provide the possibility of the detection of CNVs in the whole genome, and also greatly improve the clinical practicability of next-generation sequencing (NGS) testing. However, current methods for the detection of CNVs are easily affected by sequencing and mapping errors, and uneven distribution of reads. In this paper, we propose an improved approach, CNV-MEANN, for the detection of CNVs, involving changing the structure of the neural network used in the MFCNV method. This method has three differences relative to the MFCNV method: (1) it utilizes a new feature, mapping quality, to replace two features in MFCNV, (2) it considers the influence of the loss categories of CNV on disease prediction, and refines the output structure, and (3) it uses a mind evolutionary algorithm to optimize the backpropagation (neural network) neural network model, and calculates individual scores for each genome bin to predict CNVs. Using both simulated and real datasets, we tested the performance of CNV-MEANN and compared its performance with those of seven widely used CNV detection methods. Experimental results demonstrated that the CNV-MEANN approach outperformed other methods with respect to sensitivity, precision, and F1-score. The proposed method was able to detect many CNVs that other approaches could not, and it reduced the boundary bias. CNV-MEANN is expected to be an effective method for the analysis of changes in CNVs in the genome. [ABSTRACT FROM AUTHOR]

Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the cost of the solution in one pass over the data, using small space. As a result, streaming algorithms produce concise input summaries that approximately preserve the optimum value. We design the first efficient streaming algorithms for these fundamental problems in combinatorial optimization. For Bin Packing, we provide a streaming asymptotic (1 + ε)-approximation with O ~ 1 ε , where O ~ hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming (d + ε)-approximation for Vector Bin Packing in d dimensions, running in space O ~ d ε . For the related Vector Scheduling problem, we show how to construct an input summary in space O ~ (d 2 ⋅ m / ε 2) that preserves the optimum value up to a factor of 2 − 1 m + ε , where m is the number of identical machines. [ABSTRACT FROM AUTHOR]

Hyperheuristics form a new concept that provides a more general procedure for optimization. Their goal is to manage existing low-level heuristics to solve a large number of problems without specific parameter tuning. In this paper, we propose three hyperheuristics based on honey bees behaviour: "Bee colony optimization HyperHeuristic" BCOH2, "Honey bee Mating Optimization HyperHeuristic" HBMOH2 and "Honey Bee Cooperative HyperHeuristic" HBCH2 which cooperates between the two mentioned hyperheuristics. The proposed hyperheuristics are implemented under the Hyflex platform. Tested on the MAX-SAT and the Bin Packing problems, our algorithms showed good results compared to hyperheuristics participating in the CHeSC competition [13]. [ABSTRACT FROM AUTHOR]

We describe the nurse to patient assignment problem that supports the operational decisions in the Neonatal Intensive Care Unit of Hedi Chaker Hospital. It implies efficiently assigning patients to nurses in their suitable unit of work, taking into consideration during assignment a set of patients having a given acuity to a set of nurses having certain capacities. A binary linear integer programming problem is formulated where each patient can be treated by an only one nurse. Due to the combinatorial complexity of the problem, a heuristic approach is developed to achieve the procedure of assignment. The Max–Max assignment heuristic is based on the development of four mathematical propositions that serve for insuring the problem size reduction. The resolution of the problem via the heuristic method has shown its pertinence for exact resolution using real instances extracted from the unit. For our real case the heuristic provided flexible modelling and gave a feasible and a good nurse to patient assignment for every shift and in each zone of assignment. [ABSTRACT FROM AUTHOR]

The two-dimensional bin packing problem calls for packing a set of rectangular items into a minimal set of larger rectangular bins. Items must be packed with their edges parallel to the borders of the bins, cannot be rotated, and cannot overlap among them. The problem is of interest because it models many real-world applications, including production, warehouse management, and transportation. It is, unfortunately, very difficult, and instances with just 40 items are unsolved to proven optimality, despite many attempts, since the 1990s. In this paper, we solve the problem with a combinatorial Benders decomposition that is based on a simple model in which the two-dimensional items and bins are just represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but we enrich it with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The resulting algorithm behaved very well on the benchmark sets of instances, improving on average on previous algorithms from the literature and solving for the first time a number of open instances. Summary of Contribution: We address the two-dimensional bin packing problem (2D-BPP), which calls for packing a set of rectangular items into a minimal set of larger rectangular bins. The 2D-BPP is a very difficult generalization of the standard one-dimensional bin packing problem, and it has been widely studied in the past because it models many real-world applications, including production, warehouse management, and transportation. We solve the 2D-BPP with a combinatorial Benders decomposition that is based on a model in which the two-dimensional items and bins are represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but it is enriched with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The algorithm we developed has been extensively tested on the most well-known benchmark set from the literature, which contains 500 instances. It behaved very well, improving on average upon previous algorithms, and solving for the first time a number of open instances. We analyzed in detail several configurations before obtaining the best one and discussed several insights from this analysis in the manuscript. [ABSTRACT FROM AUTHOR]

We improve the lower bound on the asymptotic competitive ratio of any online algorithm for bin packing to above 1.54278. We demonstrate for the first time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403. [ABSTRACT FROM AUTHOR]

We study a new variant of the bin packing problem with a color constraint. Given a finite set of items, each item has a set of colors. Each bin has a color capacity, the total number of colors for a bin is the unification of colors for its items and cannot exceed the bin capacity. We need to pack all items into the minimal number of bins. For this NP-hard problem, we present approximability results and design a hybrid matheuristic based on the column generation technique. A hybrid VNS heuristic is applied to the pricing problem. The column generation method provides a lower bound and a core subset of the most promising bin patterns. Fast heuristics and exact solution for this core produce upper bounds. Computational experiments for test instances with number of items up to 500 illustrate the efficiency of the approach. [ABSTRACT FROM AUTHOR]

Enterprise cloud data centers consume a tremendous amount of energy due to the large number of physical machines (PMs). These PMs host a huge number of virtual machines (VMs), on which a vast number of applications are deployed. Existing research uses two separate layers to manage data center resources: application assignment to VMs, and VM placement to PMs, each of which is a bin packing problem. While this consecutive two-layer bin packing (Consec2LBP) makes the problems easier to solve, it also limits further improvement in the quality of solution. To address this issue, an integrated any colony optimization approach is proposed in this paper to deal with both layers simultaneously. It formulates the two-layer resource management into an integrated two-layer bin packing (Int2LBP) optimization problem. Then, an integrated first fit-decreasing (FFD) algorithm Int2LBP_FFD is proposed to solve this optimization problem. Using the result of Int2LBP_FFD as an initial solution, an integrated ant colony system (ACS) algorithm Int2LBP_ACS is further developed to improve the quality of solution. Simulation experiments are conducted to demonstrate the effectiveness of our integrated approach. [ABSTRACT FROM AUTHOR]

The Variable Cost and Size Bin Packing Problem (VCSBPP) is a known NP-Hard problem that consists in minimizing the cost of all bins used to pack a set of items. There are many real-life applications of the VCSBPP where the focus is to improve the efficiency of the solution method. In spite of the existence of fuzzy approaches to adapt other optimization problems to real life conditions, VCSBPP has not been extensively studied in terms of relaxations of the crisp conditions. In this sense, the fuzzy approaches for the VCSBPP varies from relaxing the capacity of the bins to the items weights. In this paper we address a non-explored side consisting in relaxing the set of items to be packed. Therefore, our main contribution is a fuzzy version of VCSBPP that allows incomplete packing. The proposed fuzzy VCSBPP is solved by a parametric approach. Particularly, a fast heuristic algorithm is introduced that allows to obtain a set of solutions with interesting trade-offs between cost and relaxation of the original crisp conditions. An experimental study is presented to explore the proposed fuzzy VCSBPP and its solution. [ABSTRACT FROM AUTHOR]

In this paper we present an evolutionary heuristic for the offline one-dimensional Bin Packing Problem. In this problem we have to pack a set of items into bins of the same capacity, and the objective is to minimize the number of bins used. Our algorithm is a hybrid evolutionary algorithm where an individual is a feasible solution, and it contains the description of the bins. The algorithm works without recombination; it uses two new mutation operators and improves the quality of the solutions with local search procedures. The mutation operators' work is based on a relative pair frequency matrix, and, based on this matrix, we know the frequency of every pair of items i.e. how often they are included in the same bin in the best solutions. The frequency matrix helps to pack items into subsets of items; these subsets are the bins in our problem. The algorithm was tested on well-known benchmark instances from the literature and was compared with both evolutionary and state-of-the-art algorithms. Our algorithm achieved a valuable result with the difficult hard28 test set, and in most of the test problems it reached the optimum. [ABSTRACT FROM AUTHOR]

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

The two-dimensional loading vehicle routing problem with partial conflicts combines two NP-hard problems: the classical vehicle routing problem and the two-dimensional bin-packing problem with partial conflicts. This new variant of transportation problems is inspired from hazardous materials classification and compatibilities, where some materials can be partially conflicting. In this case, they can be loaded together but an additional constraint on the distance separating them must be respected. We propose in this paper an NSGA-II algorithm to perform a bi-objective study in which the minimization of the total cost of transportation as well as the load balancing between different routes in terms of used area of vehicles are the considered objectives. The first results for this new problem are presented, using benchmarks available in the literature that have been adapted to deal with the problem. Moreover, the adding value of path relinking is proved with different statistical measurements. [ABSTRACT FROM PUBLISHER]

This paper focuses on a real life variable size multiobjective two-dimensional bin packing problem arising in a manufacturing company. It consists of placing a given set of items into bins of different sizes (called variable size bins) to minimise not only the wasted space of bins but also the number of packing patterns generated. Although an existing heuristic (called HIB), initially developed for problems with identical bins, is able to solve this problem after slight adaptations (we call this slightly adapted version as MAHIB), it requires prohibitive amounts of computation time for large-sized instances. We thus develop a heuristic called HVSB. HVSB explores different lists of items. For each list, an approach based on dynamic programming (called ASDP) is used to obtain a feasible packing. Computational results show that HVSB is efficient. The results obtained with HVSB are very close to the so-called ‘quasi-optimal packing plan’ for large-sized instances with variable size bins. For some instances, the total cost is even less than the ‘quasi-optimal packing plan’. Compared with the above-mentioned HIB and MAHIB, HVSB provides solutions of similar quality both for instances with identical bins and small-sized instances with variable size bins, but with much shorter computation times. [ABSTRACT FROM PUBLISHER]

The problem of virtual machine (VM) live migration in self-driving systems targets reallocating resources among VMs running different self-driving services for load balance. It is of great importance to enable a running VM to be moved to another physical machine (host) seamlessly. Due to the nature of self-driving applications, it is important to select an optimal set of hosts to place VMs within an interactive time. The VM placement problem can be formalized as a bin packing problem, which is proved to be NP-hard. To solve the problem, we develop a cluster-based genetic algorithm that outputs an approximation result of the bin pack problem. In particular, our proposed algorithm clusters the population of current generation and selects individuals from different groups with reduced crossover operations. The number of crossover operations is directly related to the algorithm efficiency. We use the run-time features to evaluate the preference of VMs on hardware resources, which is utilized to generate initial solutions and avoid overload. Experimental results show that our approach is able to outperform the tradition genetic algorithm regarding both accuracy and efficiency. [ABSTRACT FROM AUTHOR]

Many scientists apply fully dynamic bin packing problem solving for resource allocation of virtual machines in cloud environments. The goal of problem-solving is to reduce the number of allocated hosts (bins) and virtual machines (items) migration rates for reducing energy consumption. This study demonstrates a greedy futuristic algorithm (proposed algorithm) for fully dynamic bin packaging with an average asymptotic approximation ratio of 1.231, better than other existing algorithms. The proposed algorithm identifies inappropriate local selections using special futuristic conditions to prevent them as much as possible. Eventually, suitable choices determine and discard the improper ones. The proposed algorithm illustrates an asymptotic approximation ratio of (t/ (t-1)) OPT, where the value of t depends on the distribution of the arrived and departed items. Also, OPT is the number of bins by an optimal solution. Finally, in experiments of datasets using a maximum utilization of 80% of each bin, the average migration rate is 0.338. Using the proposed method for allocating resources in the cloud environment can allocate hosts to a virtual machine using almost optimal use. This allocation can reduce the cost of maintaining and purchasing hosts. Also, this method can reduce the migration rate of virtual machines. As a result, decreasing migration improves the energy consumption cost in the cloud environment. [ABSTRACT FROM AUTHOR]

This paper investigates the mother plate design (MPD) problem which is a typical problem in the production planning of steel plants. The MPD problem refers to a variant of the two-dimensional variable-sized bin packing problem in which the height of a bin is in a given finite set and the width of each bin is continuous in an interval. The problem is first formulated as a mixed integer nonlinear programming model and then linearized into a mixed integer programming model. We present a column generation-based (CG-based) algorithm to approximately solve the MPD problem, in which a height combination scheme is devised to decrease the dimensions of the pricing sub-problem. We present an accelerated CG (ACG) algorithm with improved performance which adopts two heuristic accelerating strategies in the pricing process. We use practical instances collected from a Chinese steel plant to test the performance of the proposed algorithms. The results indicate that the ACG algorithm is suitable for solving real-world instances. [ABSTRACT FROM AUTHOR]

This paper is aimed at the problem of scheduling surgeries in operating rooms. To solve this problem, we suggest using some variation of the bin packing problem. The model is based on the actual operation of 10 operating rooms, each of which belongs to a specific department of the hospital. Departments are unevenly loaded, so operations can be moved to operating rooms in other departments. The main goal is to increase patient throughput. It is also necessary to measure how many operations take place in other departments with the proposed solution. The preferred solution is a solution with fewer such operations, all other things being equal. Due to the fact that the mixed-integer linear programming model turned out to be computationally complex, two approximation algorithms were also proposed. They are based on decomposition. The complexity of the proposed algorithms is estimated, and arguments are made regarding their accuracy from a theoretical point of view. To assess the practical accuracy of the algorithms, the Gurobi solver is used. Experiments were conducted on real historical data on surgeries obtained from the Burdenko Neurosurgical Center. Two decomposition algorithms were constructed and a comparative analysis was performed for 10 operating rooms based on real data.

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

Buçalışmada bir boyutlu kutulama problemi için melez yeni bir sezgisel çözümyöntemi sunulmuştur. Önerilen yaklaşımda, başlangıç çözümü oluşturmak için altsınıra dayalı sezgisel bir başlangıç çözüm algoritması önerilmiştir. Önerilensezgisel ile birlikte literatürde yer alan diğer yerleştirme algoritmaları elealınmış, elde edilen sonuçlar literatürde ulaşılan sonuçlarla karşılaştırılmıştır.Başlangıç çözümü sonrası elde edilen çözüme ağırlıklı tavlama yöntemiylebirlikte yer değiştirme algoritmaları uygulanmış ve kullanılan kutu sayısınıminimize etmek amaçlanmıştır. Literatürde yer alan test kümeleri çözülmüş,çözüm süreleri ve elde edilen sonuçlar bilinen en iyi sonuçlarla vegeliştirilen diğer yöntemlerle karşılaştırılmıştır. Literatür ile yapılankarşılaştırmalarda önerilen sezgisel yöntemin daha kısa sürede çözüme ulaştığıgözlemlenmiştir. Ayrıca çözülen test kümesinin 2 örneğinde literatürdeki en iyibilinen çözümden daha iyi bir çözüm elde edildiği gözlemlenmiştir.

Recently, the problem of Virtual Machine Placement (VMP) has received enormous attention from the research community due to its direct effect on the energy efficiency, resource utilization, and performance of the cloud data center. VMP is considered as a multidimensional bin packing problem, which is a type of NP-hard problem. The challenge in VMP is how to optimally place multiple independent virtual machines into a few physical servers to maximize a cloud provider's revenue while meeting the Service Level Agreements (SLAs). In this paper, an effective multiobjective algorithm based on Particle Swarm Optimization (PSO) technique for the VMP problem, referred to as VMPMOPSO, is proposed. The proposed VMPMOPSO utilizes the crowding entropy method to optimize the VMP and to improve the diversity among the obtained solutions as well as accelerate the convergence speed toward the optimal solution. VMPMOPSO was compared with a simple single-objective algorithm, called First-Fit-Decreasing (FFD), and two multiobjective ant colony and genetic algorithms. Two simulation experiments were conducted to verify the effectiveness and efficiency of the proposed VMPMOPSO. The first experiment shows that the proposed algorithm has better performance than the algorithms we compared it to in terms of power consumption, SLA violation, and resource wastage. The second indicates that the Pareto optimal solutions obtained by applying VMPMOPSO have a good distribution and a better convergence than the comparative algorithms. [ABSTRACT FROM AUTHOR]

We consider the bin packing problem with d different item sizes and revisit the structure theorem given by Goemans and Rothvoß about solutions of the integer cone. We present new techniques on how solutions can be modified and give a new structure theorem that relies on the set of vertices of the underlying integer polytope. As a result of our new structure theorem, we obtain an algorithm for the bin packing problem with running time | V | 2 O (d) ⋅ e n c (I) O (1) , where V is the set of vertices of the integer knapsack polytope, and e n c (I) is the encoding length of the bin packing instance. The algorithm is fixed-parameter tractable, parameterized by the number of vertices of the integer knapsack polytope | V | . This shows that the bin packing problem can be solved efficiently when the underlying integer knapsack polytope has an easy structure (i.e., has a small number of vertices). Furthermore, we show that the presented bounds of the structure theorem are asymptotically tight. We give a construction of bin packing instances using new structural insights and classical number theoretical theorems which yield the desired lower bound. [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]

Bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k ≥ 2 , items having sizes in (0 , 1 ] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem and prove a lower bound of 2 on the overall asymptotic competitive ratio. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, where no such lower bound was known even for fixed high dimensions. [ABSTRACT FROM AUTHOR]

The Variable Size and Cost Bin Packing Problem consists of minimizing the cost of all the containers used to pack a set of items. In the previous works, several algorithms have been presented and studied, to solve different instances of this problem where the weights of the elements to be packed follow Uniform Distribution. The objective of this work is to study the influence of the statistical distribution that the components of the instances of the problem follow in their complexity. For this, three sets of reference instances were designed that follow different statistical distributions and the SCIP solver was used to solve them. From these experiments, it was obtained that the instances where the weights of the elements follow the Normal Distribution and the capacities of the containers follow the Weibull Distribution are more difficult to solve than the instances with characteristics similar to those studied in the previous articles. [ABSTRACT FROM AUTHOR]

The article discusses that the authors formulate the contract design problem as a stochastic optimal control model and provide a complete characterization of the optimal solution. It mentions that their analysis suggests that the optimal dynamic contracts are simple to describe, easy to compute and implement, and intuitive to explain.

A New Algorithm for Static Bin Packing Static bin packing is the problem of partitioning a set of items (with scalar sizes) into identical bins of a given capacity, under the constraint that the total size of no partition exceeds the bin capacity. In the online variant, the list of items is revealed one at a time—an item must be assigned irrevocably to a partition at the time it is revealed. In "Interior-Point Based Online Stochastic Bin Packing," V. Gupta and A. Radovanović look at the online variant under the assumption that the item sizes are independent samples from a common unknown distribution. The authors show that a greedy heuristic that assigns items so as to minimize a carefully chosen penalized Lagrangian of the offline math program is asymptotically optimal. Since the proposed heuristic is greedy in nature, it extends readily to nonstationary item size sequences for which the authors prove a novel family of performance bounds. Bin packing is an algorithmic problem that arises in diverse applications such as remnant inventory systems, shipping logistics, and appointment scheduling. In its simplest variant, a sequence of T items (e.g., orders for raw material, packages for delivery) is revealed one at a time, and each item must be packed on arrival in an available bin (e.g., remnant pieces of raw material in inventory, shipping containers). The sizes of items are independent and identically distributed (i.i.d.) samples from an unknown distribution, but the sizes are known when the items arrive. The goal is to minimize the number of nonempty bins (equivalently waste, defined to be the total unused space in nonempty bins). This problem has been extensively studied in the operations research and theoretical computer science communities, yet all existing heuristics either rely on learning the distribution or exhibit o(T) additive suboptimality compared with the optimal offline algorithm only for certain classes of distributions (those with sublinear optimal expected waste). In this paper, we propose a family of algorithms that are the first truly distribution-oblivious algorithms for stochastic bin packing, and achieve O (T) additive suboptimality for all item size distributions. Our algorithms are inspired by approximate interior-point algorithms for convex optimization. In addition to regret guarantees for discrete i.i.d. sequences, we extend our results to continuous item size distribution with bounded density, and prove a family of novel regret bounds for non-i.i.d. input sequences. To the best of our knowledge, these are the first such results for non-i.i.d. and non-random-permutation input sequences for online stochastic packing. [ABSTRACT FROM AUTHOR]

Purpose: development of a new load optimization algorithm in order to solve the aircraft load optimization problem with further implementation it to the innovated load optimization model. Methods: heuristics, formalized approach, computer modeling. Results: the innovated load optimization algorithm was designed, which implies the containers groups' assignment with minimization of loading time. Discussion: Most of studied scientific works contain various descriptions of bin packing problem's solutions, knapsack optimization models and also outline a term of "aircraft cargo loading" as a problem of container selection, packing and cargo loading into the aircraft compartment. These models are concentrated on separate features, whereas the real load optimization problem is inextricably linked with aircraft handling and operations. This innovated load optimization model consists in decomposing the loading problem and also implementation of a new priority load planning algorithm. The following algorithm refers the predefined Unit Load Devices' assignment in the aircraft cargo compartment in priority order to unload them according to data's documentation without exceeding weight and balance constraints and with loading time reduction and consequently cutting handling and operation costs. [ABSTRACT FROM AUTHOR]

Counting and enumerating maximal and maximum independent sets are well-studied problems in graph theory. In this paper we introduce methods to count and enumerate maximal/maximum independent sets in threshold graphs and k-threshold graphs and improve former results for these problems. The results can be applied to combinatorial optimization problems, and in particular to different variations of the knapsack problem. As feasible solutions for instances of those problems correspond to independent sets in threshold graphs and k-threshold graphs, we obtain polynomial time results for special knapsack and multidimensional knapsack instances. Also, we show lower and upper bounds for the number of necessary bins in several bin packing problems. [ABSTRACT FROM AUTHOR]

Motivated by urban freight transportation practices in China, we study an optimal truck loading problem in which a fixed cost and an additional cost that depends on the number of unloading points are associated with each truck used. The truck loading problem is modeled as a one-dimensional bin packing problem, where the cost of each bin is a convex fixed-plus-linear function of the number of items in the bin. The objective is to minimize the total cost of bins used. We develop an asymptotic polynomial time approximation scheme and an efficient approximation algorithm with an asymptotic worst-case performance ratio of 1.5 to tackle the problem. Our computational experiments indicate that the approximation algorithm performs well for certain order patterns, and also reveal several important insights on using the freight charge scheme. [ABSTRACT FROM AUTHOR]

We present a two-stage methodology called Positions and Covering (P&C) to solve the two-dimensional bin packing problem (2D-BPP). The objective of this classical combinatorial NP-hard problem is to pack a set of items (small rectangles) in the minimum number of bins (larger rectangles). The first stage is the key-point of the Positions and Covering, where for each item, it is generated in a pseudo-polynomial way a set of valid positions that indicate the possible ways of packing the item into the bin. In the second stage, a new set-covering formulation, strengthen with three sets of valid inequalities, is used to select the optimal non-overlapping configuration of items for each bin. Experimental results for the P&C method are presented and compared with some of the best algorithms in the literature for small and medium size instances. Furthermore, we are considering both cases of the 2D-BPP, with and without rotations of the items by 90°. To the best of our knowledge, this is one of the first exact approaches to obtain optimal solutions for the rotation case. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Chongqing University of Posts & Telecommunications (Natural Science Edition) is the property of Chongqing University of Posts & Telecommunications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This paper looks into the steel mother plate design problem. A slab, which is an intermediate work in process, is subsequently rolled into a mother plate with the specific dimensions of thickness, length, and width. The mother plate is then cut into customer order plates. As a slab is rolled into a mother plate through a series of horizontal and vertical rolling processes, different-sized mother plates can be generated from a single-slab type. This flexibility allows for the size of a mother plate to be determined according to the order plates assigned to it. Furthermore, when the order plates are cut from a mother plate, a guillotine cut is required to reduce the production cost. The steel mother plate design problem involves the placing of order plates on the mother plates in a guillotine cut pattern and determining the sizes of the mother plates with the objective of minimising the number of slabs; thus it may be considered as a two-staged guillotine cut, two-dimensional bin packing problem with flexible bin size. This paper introduces the problem, presents several mathematical models, and proposes an iterative two-phase heuristic method consisting of several algorithms to solve the problem. Computational results for the benchmark problems show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

We examine rectangle packing problems where only the areas a 1 , ... , a n of the rectangles to be packed are given while their aspect ratios may be chosen from a given interval [ 1 γ , γ ]. In particular, we ask for the smallest possible size of a rectangle R such that, under these constraints, any collection a 1 , ... , a n of rectangle areas of total size 1 can be packed into R. As for standard square packing problems, which are contained as a special case for γ = 1 , this question leads us to three different answers, depending on whether the aspect ratio of R is given or whether we may choose it either with or without knowing the areas a 1 , ... , a n. Generalizing known results for square packing problems, we provide upper and lower bounds for the size of R with respect to all three variants of the problem, which are tight at least for larger values of γ. Moreover, we show how to improve these bounds on the size of R if we restrict ourselves to instances where the largest element in a 1 , ... , a n is bounded. [ABSTRACT FROM AUTHOR]

A homothetic packing of squares is any set of various-size squares with the same orientation where no two squares have overlapping interiors. If all n squares have the same size then we can have up to roughly 4 n contacts by arranging the squares in a grid formation. The maximum possible number of contacts for a set of n squares will drop drastically, however, if the size of each square is chosen more-or-less randomly. In the following paper we describe a necessary and sufficient condition for determining if a set of n squares with fixed sizes can be arranged into a homothetic square packing with more than 2 n − 2 contacts. Using this, we then prove that any (possibly not homothetic) packing of n squares will have at most 2 n − 2 face-to-face contacts if the various widths of the squares do not satisfy a finite set of linear equations. [ABSTRACT FROM AUTHOR]

Packing behaviors of non-spherical particles are generally far more complex than those of spherical particles. Trilobes are widely adopted as supports for catalyst in the field of chemical engineering, and thus their packing behaviors subjected to continuous vertical vibration are numerically investigated by discrete element method in this article. Geometrically exact contact detection algorithm between sphero-cylinders and multi-sphere method are coupled to describe the shape and motion of trilobed particles. It is found that there exist two preferential orientations, which are quite different from the phenomenon of sphero-cylinders. Ordered clusters of different orientations co-exist in the heterogeneous granular bed with obvious phase junctures. The initial stage of crystallization process can be explained by the nucleation growth mechanism. With the growth of the nuclei, distances between small ordered clusters decrease gradually and those ones with identical orientation can eventually get coalesced to form a larger cluster. Moreover, novel sunflower-shaped clusters composed of trilobes of different orientations are observed under vibrations of low amplitudes and high frequencies. In the meanwhile, no consistent relationship between packing densities and packing structures can be found for the dense packing of trilobes. Therefore, other packing parameters more sensitive to the local structures should be analyzed together with the overall packing densities to comprehensively understand the packing behaviors of non-spherical particles. [Display omitted] • DEM simulations with exact shape description of trilobes. • Combined sphero-cylinders are applied in multi-sphere method. • Packing of trilobes under vibration are investigated systematically. • Different packing structures have similar overall packing density. • Novel sunflower-shaped heterogeneous packing structure is observed. [ABSTRACT FROM AUTHOR]