185,561 research outputs found
Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints
No full textThe paper examines a new problem in the irregular packingliterature that has existed in industry for decades;two-dimensional irregular (convex) bin packing with guillotineconstraints. Due to the cutting process of certain materials, cutsare restricted to extend from one edge of the stock-sheet toanother, called guillotine cutting. This constraint is commonplace in glass cutting and is an important constraints intwo-dimensional cutting and packing problems. In the literature,various exact and approximate algorithms exist for finding the twodimensional cutting patterns that satisfy the guillotine cuttingconstraint. However, to the best of our knowledge, all of thealgorithms are designed for solving rectangular cutting where cutsare orthogonal with the edges of the stock-sheet. In order tosatisfy the guillotine cutting constraint using these approaches,when the pieces are non-rectangular, practitioners implement a twostage approach. First, pieces are enclosed within rectangle shapesand then the rectangles are packed. Clearly, imposing this condition is likely to lead to additional waste. Thispaper aims to generate guillotine-cutting layouts of irregularshapes using a number of strategies. The investigation comparestwo two-stage approaches; one approximates pieces by rectangles,the other approximates pairs of pieces by rectangles usingphi-functions for optimal clustering. Both these approaches usestate of the art rectangle bin packing with guillotineconstraints. Further, we design and implement a one-stage approachusing a self-adapted forest search algorithm. Experimental resultsshow the one-stage strategy to produce good solutions in less timeover the two-stage approach
Worst-case analysis for new online bin packing problems
No full textWe consider two new online bin packing problems, the online Variable Cost and Size Bin Packing Problem (o-VCSBPP) and the online Generalized Bin Packing Problem (o-GBPP). We take two well-known bin packing algorithms to address them, the First Fit (FF) and the Best Fit (BF). We show that both algorithms have an asymptotic worst-case ratio bound equal to 2 for the o-VCSBPP and this bound is tight. When there are enough bins of a particular type to load all items, FF and BF also have an absolute worst-case ratio bound equal to 2 for the o-VCSBPP, and this bound is also tight. In addition, we prove that no worst-case ratio bound of FF and BF can be computed for the o-GBPP. Therefore, we consider a natural evolution of these algorithms, the First Fit with Rejection and the Best Fit with Rejection, able to reject inconvenient bins at the end of the process. Similarly, we prove that no worst-case ratio of these algorithms can be computed for the o-GBPP. Finally, we give sucient conditions under which algorithms do not admit any performance ratio, and conclude that the worst-case results obtained for the o-VCSBPP and the o-GBPP also hold for the oine variant of these two problem
Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem
No full textWe present a new approximation algorithm for the two-dimensional bin-packing problem. The algorithm is based on two one-dimensional bin-packing algorithms. Since the algorithm is of next-fit type it can also be used for those cases where the output is required to be on-line (e. g. if we open an new bin we have no possibility to pack elements into the earlier opened bins). We give a tight bound for its worst-case and show that this bound is a parameter of the maximal sizes of the items to be packed. Moreover, we also present a probabilistic analysis of this algorithm.worst-case analysis;probabilistic analysis;bin-packing;heuristic algorithm;on-line algorithm;two-dimensional packing
Probabilistic analysis of algorithms for dual bin packing problems
No full textIn the dual bin packing problem, the objective is to assign items of given size to the largest possible number of bins, subject to the constraint that the total size of the items assigned to any bin is at least equal to 1. We carry out a probabilistic analysis of this problem under the assumption that the items are drawn independently from the uniform distribution on [0, 1] and reveal the connection between this problem and the classical bin packing problem as well as to renewal theory.
A heuristic procedure for one dimensional bin packing problem with additional constraints
No full textWe proposed a heuristic algorithm to solve the one-dimensional bin-packing problem with additional constraints. The proposed algorithm has been applied to solve a practical vehicle-allocation problem. The experimental results show that our proposed heuristic provides optimal or near-optimal results, and performs better than the first fit decreasing algorithm modified to incorporate additional constraints.
Ant colony optimisation and local search for bin-packing and cutting stock problems
No full textThe Bin Packing Problem and the Cutting Stock Problem are two related classes of NP-hard combinatorial optimization problems. Exact solution methods can only be used for very small instances, so for real-world problems, we have to rely on heuristic methods. In recent years, researchers have started to apply evolutionary approaches to these problems, including Genetic Algorithms and Evolutionary Programming. In the work presented here, we used an ant colony optimization (ACO) approach to solve both Bin Packing and Cutting Stock Problems. We present a pure ACO approach, as well as an ACO approach augmented with a simple but very effective local search algorithm. It is shown that the pure ACO approach can compete with existing evolutionary methods, whereas the hybrid approach can outperform the best-known hybrid evolutionary solution methods for certain problem classes. The hybrid ACO approach is also shown to require different parameter values from the pure ACO approach and to give a more robust performance across different problems with a single set of parameter values. The local search algorithm is also run with random restarts and shown to perform significantly worse than when combined with ACO
TS2PACK: A Two-Level Tabu Search for the Three-dimensional Bin Packing Problem
No full textThree-dimensional orthogonal bin packing is a problem NP-hard in the strong sense where a set of boxes must be orthogonally packed into the minimum number of three-dimensional bins. We present a two-level tabu search for this problem. The first-level aims to reduce the number of bins. The second optimizes the packing of the bins. This latter procedure is based on the Interval Graph representation of the packing, proposed by Fekete and Schepers, which reduces the size of the search space. We also introduce a general method to increase the size of the associated neighborhoods, and thus the quality of the search, without increasing the overall complexity of the algorithm. Extensive computational results on benchmark problem instances show the effectiveness of the proposed approach, obtaining better results compared to the existing one
Przejęcie władzy przez następcę tronu Mohammada Bin Salmana. Szanse na zmiany w Arabii Saudyjskiej?
No full textThe aim of this paper is to present the outline of planned and already implemented social, political and economic changes in the context of gradual transition of power in the Kingdom of Saudi Arabia. The main thesis put in this paper relates to Mohammed bin Salman’s leading project – “Vision 2030” which assumed gradual multi-dimensional transition in Saudi Arabia. Many of changes implemented already, including the limitation of clergy’s activity will not bring about quick social-political transition due to long-lasting and deeply rooted alliance between Saudi ruling clan and radical movement of Wahhabis, that determines conservative regime in the country. Basing on the main thesis Author tries to give the answer to research questions correlated with the thesis and touching the issue of possibility for implementation political, economic changes in Saudi Arabia by Mohammed bin Salman.
In the paper following research methods has been applied: historical method, which refers to analysis of historical process of shaping and development Saudi monarchy; documentary analysis - relating to governmental project “Vision 2030” particularly; elements of systemic approach in which system is constituted by political regime of Saudi Arabia; elements of statistical method employed in the context of variable economic or social data and elements of predictive referring to the model of Saudi Arabia’s development under the rule of Mohammed bin Salman.Celem artykułu jest przestawienie zarysu planowanych i wprowadzonych już zmian społecznych, politycznych i gospodarczych w Arabii Saudyjskiej w kontekście generacyjnej zmiany władzy. Główna hipoteza jest ściśle powiązana z flagowym projektem zmian pod tytułem „Wizja 2030” i bezpośrednio dotyczy następcy tronu Mohammeda bin Salmana, który stoi za tym przedsięwzięciem. Wiele zmian w różnych sferach życia społecznego, gospodarczego i także politycznego zostało już wprowadzonych, w tym m.in. ograniczenie roli duchowieństwa i instytucji religijnych takich jak Mutaween. Należy przy tum zaznaczyć, że daleko idące przemiany polityczno-religijne wymagają długiej perspektywy czasowej, choćby z uwagi na ist niejący już od 250 lat układ polityczny pomiędzy klanem rodowym Saudów a religijnymi fundamentalistami Wahhabitami. Powiązanie wahhabicko-saudyjskie determinuje konserwatywny ustrój państwa i może być główną przeszkodą w planowanej jego modernizacji. Do hipotezy badawczej postawiono kilka pytań badawczych związanych z szansami implementacji planowanych zmian w sferze gospodarczo-społecznej i tym samym politycznej w Arabii Saudyjskiej.
W tekście wykorzystano następujące metody badawcze: metoda genetyczna, która odnosi się do procesu historycznego kształtowania państwowości Arabii Saudyjskiej; analiza źródłowa dokumentów, w szczególności odnosząca się do flagowego dokumentu „Wizja 2030”. Wykorzystano również elementy metody systemowej, w ramach której określonym systemem jest ustrój polityczny Arabii Saudyjskiej oraz skorzystano z elementów metody statystycznej w zakresie posługiwania się danymi liczbowymi w odniesieniu do zjawisk ekonomicznych i społecznych. W tekście zastosowano również elementy metody predyktywnej w odniesieniu do prognozy dalszego rozwoju zmian wdrażanych przez następcę tronu Arabii Saudyjskiej
Three-dimensional bin packing : a heuristic approach
No full textA three-dimensional bin-packing problem is considered using the heuristically-controlled search methods of artificial intelligence. The problem is stated as follows: Given a set of n three-dimensional rectangular boxes, where each dimension is in the range (0, 1], and a set of cubical bins, where each dimension is 1, pack the boxes into as few bins as possible. The orientation of each box within a bin is unrestricted (except that box faces must be parallel to bin faces), and the weight capacity of each bin is unlimited. The formulation of the solution consists of three major components: a box-selection process, an orientation process, and a slicing process. Heuristic search methods are employed which reduce the search space by guiding the backtracking process. Empirical bin-packing data for several different box lists has been collected. The three-dimensional bin-packing problem has practical applications in an industrial environment. Presented with the task of packing a group of boxes into larger bins, a robot can determine the location and dimensions of each box, select the packing arrangement of the bins, plan the packing order for all of the boxes, transport each box to a bin, and, if necessary, reorient each box prior to placing it into the bin.California State University, Northridge. Department of Computer Science.Includes bibliographical references (pages 84-88
Two-photon interference at telecom wavelengths for time-bin-encoded single photons from quantum-dot spin qubits
No full textThis work was supported by the JST through its ImPACT Program, NICT, NSF CCR-08 29694, NIST 60NANB9D9170, Special Coordination Funds for Promoting Science and Technology, and the State of Bavaria. C.L. and M.M.F. acknowledge support through the AFOSR. C.M.N. acknowledges a SU2P Entrepreneurial Fellowship and R.H.H. acknowledges a Royal Society University Research Fellowship.Practical quantum communication between remote quantum memories rely on single photons at telecom wavelengths. Although spin-photon entanglement has been demonstrated in atomic and solid-state qubit systems, the produced single photons at short wavelengths and with polarization encoding are not suitable for long-distance communication, because they suffer from high propagation loss and depolarization in optical fibres. Establishing entanglement between remote quantum nodes would further require the photons generated from separate nodes to be indistinguishable. Here, we report the observation of correlations between a quantum-dot spin and a telecom single photon across a 2-km fibre channel based on time-bin encoding and background-free frequency downconversion. The downconverted photon at telecom wavelengths exhibits two-photon interference with another photon from an independent source, achieving a mean wavepacket overlap of greater than 0.89 despite their original wavelength mismatch (900 and 911 nm). The quantum-networking operations that we demonstrate will enable practical communication between solid-state spin qubits across long distances.Peer reviewe
- …
