|
High-multiplicity Bin Packing
High-multiplicity bin packing is a special case of the bin packing problem, in which the number of different item-sizes is small, while the number of items with each size is large. While the general bin-packing problem is NP-hard, the high-multiplicity setting can be solved in polynomial time, assuming that the number of different sizes is a fixed constant. Problem definition The inputs to the problem are positive integers: * ''d'' - the number of different sizes (also called the ''dimension'' of the problem); *''B'' - the bin capacity. * ''s''1, ..., s''d'' - the sizes. The vector of sizes is denoted by s. * ''n''1, ..., n''d'' - the multiplicities; n''i'' is the number of items with size ''si''. The vector of multiplicities is denoted by n. **''n'' denotes the total number of items, that is, ''n = n''1+...+''nd''. **''V'' denotes the largest integer appearing in the description of the problem, that is, ''V'' = max(''s''1, ..., s''d'', ''n''1, ..., ''nd'', B) The output is a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bin Packing Problem
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media and technology mapping in FPGA semiconductor chip design. Computationally, the problem is NP-hard, and the corresponding decision problem - deciding if items can fit into a specified number of bins - is NP-complete. Despite its worst-case hardness, optimal solutions to very large instances of the problem can be produced with sophisticated algorithms. In addition, many approximation algorithms exist. For example, the first fit algorithm provides a fast but often non-optimal solution, involving placing each item into the first bin in which it will fit. It requires '' Θ''(''n'' log ''n'') time, where ''n' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard problem is the subset sum problem. A more precise specification is: a problem ''H'' is NP-hard when every problem ''L'' in NP can be reduced in polynomial time to ''H''; that is, assuming a solution for ''H'' takes 1 unit time, ''H''s solution can be used to solve ''L'' in polynomial time. As a consequence, finding a polynomial time algorithm to solve any NP-hard problem would give polynomial time algorithms for all the problems in NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial-time algorithms for NP-hard problems, but that has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class. Defi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Configuration Linear Program
The configuration linear program (configuration-LP) is a particular linear programming used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem.Gilmore P. C., R. E. Gomory (1961). A linear programming approach to the cutting-stock problem'. Operations Research 9: 849-859 Later, it has been applied to bin packing and job scheduling. In the configuration-LP, there is a variable for each possible ''configuration'' - each possible multiset of items that can fit in a single bin (these configurations are also known as ''patterns'') . Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations. In bin packing The integral LP In the bin packing problem, there are ''n'' items with different sizes. The goal is to pack the items into a minimum number of bins, where each bin can contain at most ''B''. A ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Identical-machines Scheduling
Identical-machines scheduling is an optimization problem in computer science and operations research. We are given ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' of varying processing times, which need to be scheduled on ''m'' identical machines, such that a certain objective function is optimized, for example, the makespan is minimized. Identical machine scheduling is a special case of uniform machine scheduling, which is itself a special case of optimal job scheduling. In the general case, the processing time of each job may be different on different machines; in the case of identical machine scheduling, the processing time of each job is the same on each machine. Therefore, identical machine scheduling is equivalent to multiway number partitioning. A special case of identical machine scheduling is single-machine scheduling. In the standard three-field notation for optimal job scheduling problems, the identical-machines variant is denoted by P in the first field. For example, " P, , ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Unrelated-machines Scheduling
Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule ''n'' jobs ''J''1, ''J''2, ..., ''Jn'' on ''m'' different machines, such that a certain objective function is optimized (usually, the makespan should be minimized). The time that machine ''i'' needs in order to process job j is denoted by ''pi,j''. The term ''unrelated'' emphasizes that there is no relation between values of ''pi,j'' for different ''i'' and ''j''. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which ''pi,j'' = ''pi'' / ''sj'' (where ''sj'' is the speed of machine ''j''), and identical-machines scheduling - in which ''pi,j'' = ''pi'' (the same run-time on all machines). In the standard three-field notation for optimal job scheduling problems, the unrelated-machines variant is denoted by R in the first field. For example, the problem denoted by " R, , C_\max" i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Next-fit Bin Packing
Next-fit is an online algorithm for bin packing. Its input is a list of items of different sizes. Its output is a ''packing'' - a partition of the items into bins of fixed capacity, such that the sum of sizes of items in each bin is at most the capacity. Ideally, we would like to use as few bins as possible, but minimizing the number of bins is an NP-hard problem. The next-fit algorithm uses the following heuristic: * It keeps a ''current bin'', which is initially empty. * When an item arrives, it checks whether the item fits into the current bin. ** If it fits, it is placed inside it. ** Otherwise, the current bin is closed, a new bin is opened and the coming item is placed inside this new bin. Next-Fit is a bounded space algorithm - it requires only one partially-filled bin to be open at any time. The algorithm was studied by David S. Johnson in his doctoral thesis in 1973. Run time The running time of NextFit can be bounded by \mathcal(n), where n is the number of items in th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cutting Stock Problem
In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem in mathematics that arises from applications in industry. In terms of computational complexity, the problem is an NP-hard problem reducible to the knapsack problem. The problem can be formulated as an integer linear programming problem. Illustration of one-dimensional cutting-stock problem A paper machine can produce an unlimited number of master (jumbo) rolls, each 5600 mm wide. The following 13 items must be cut, in the table below. The important thing about this kind of problem is that many different product units can be made from the same master roll, and the number of possible combinations is itself very large, in general, and not trivial to enumerate. The problem therefore is to find an optimum set of patterns of making pro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
