1,721,130 research outputs found
Decision Making under Uncertainty in Electricity Markets
No full textRecensione del volume Decision Making Under Uncertainty in Electricity Markets, di Conejo, Antonio J., Carrión, Miguel, Morales, Juan M. (Springer, 2010
Twelve surveys in operations research
No full textThis volume collects all twelve survey papers that appeared in volumes 10--12 (2012--2014) of the journal 4OR: A Quarterly Journal of Operations Research. We briefly introduce the collected surveys and those that were included in the first three volumes of this series
Fixed job schedule problem with working-time constraints
No full textWe considere a generalization of the fixed job schedule problem where a bound is imposed on the total working time of each processor. It is shown that the problem is NP-hard but polynomially solvable in the preemptive case. We introduce several lower bounds. One is determined through definition of a special class of graphs, for which the maximum clique problem is shown to be polynomial. Lower bounds and dominance criteria are exploited in a brach-and-bound algorithm for optimal solution of the problem. The effectiveness of the algorithm is analyzed through computational experiments
FIXED JOB SCHEDULE PROBLEM WITH SPREAD-TIME CONSTRAINTS
No full textWe consider a generalization of the fixed job schedule problem in which each processor is available only for a prefixed time interval from the release time of the earliest task assigned to it. The problem can arise in bus driver scheduling. We show that the problem is NP-hard, and introduce polynomial procedures to determine lower bounds, dominance criteria and reductions. We also develop a branch-and-bound algorithm for obtaining the optimal solution of the problem and analyze the algorithm's average performance in a series of computational experiments. Finally, we investigate the preemptive case and other polynomial special cases
Delivery man problem and cumulative matroids
No full textGiven a complete directed graph G = (V,A), the delivery man problem (DMP) consists of determining a Hamiltonian circuit minimizing the sum of distances (along the circuit) from a given vertex v1, to every vertex of V, including v1 itself. There exists a number of applications of the DMP in the fields of distribution and machine scheduling. The DMP is NP-hard. The objective of this paper is to develop new theoretical results and an exact algorithm for the problem. A new, integer linear programming formulation is provided, and results on the matroidal structure of a class of combinatorial problems are developed. These are used to derive lower bounds for the DMP. These bounds are embedded into an enumerative algorithm. The largest problems solved to optimally with the proposed algorithm involve 60 vertices. This compares favorably with previously published methods
Logic based Benders' decomposition for orthogonal stock cutting problems
Get PDFWe consider the problem of packing a set of rectangular items into a strip of fixed width, without overlapping, using minimum height. Items must be packed with their edges parallel to those of the strip, but rotation by 90° is allowed. The problem is usually solved through branch-and-bound algorithms. We propose an alternative method, based on Benders' decomposition. The master problem is solved through a new ILP model based on the arc flow formulation, while constraint programming is used to solve the slave problem. The resulting method is hybridized with a state-of-the-art branch-and-bound algorithm. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. We additionally show that the algorithm can be successfully used to solve relevant related problems, like rectangle packing and pallet loading
Models and algorithms for packing rectangles into the smallest square
No full textWe consider the problem of determining the smallest square into which a given set of rectangular items can be packed without overlapping. We present an ILP model, an exact approach based on the iterated execution of a two-dimensional packing algorithm, and a randomized metaheuristic. Such approaches are valid both for the case where the rectangles have fixed orientation and the case where they can be rotated by 90°. We computationally evaluate the performance and the limits of the proposed approaches on a large set of instances, including a number of classical benchmarks from the literature, for both cases above, and for the special case where the items are squares
Bin packing and cutting stock problems: Mathematical models and exact algorithms
No full textWe review the most important mathematical models and algorithms developed for the exact solution of the one-dimensional bin packing and cutting stock problems, and experimentally evaluate, on state-of-the art computers, the performance of the main available software tools
- …
