This paper concerns guarantees on system performance through Service Level Agreement (SLA) compliance and focuses on devising energy aware resource management techniques based on Dynamic Voltage and Frequency Scaling ...
详细信息
ISBN:
(纸本)9781450341479
This paper concerns guarantees on system performance through Service Level Agreement (SLA) compliance and focuses on devising energy aware resource management techniques based on Dynamic Voltage and Frequency Scaling (DVFS) used by resource management middleware in clouds that handle MapReduce jobs. This research formulates the resource management problem as an optimization problem using constraint programming (CP). Experimental results presented in the paper demonstrate the effectiveness of the technique.
The stockyard management problem in a cargo assembly terminal mainly focuses on finding an efficient allocation of limited resources such as stockyard space, stacking and reclaiming machines to stockpiles such that th...
详细信息
ISBN:
(纸本)9783319459394;9783319459400
The stockyard management problem in a cargo assembly terminal mainly focuses on finding an efficient allocation of limited resources such as stockyard space, stacking and reclaiming machines to stockpiles such that the waiting time of a vessel fleet at port can be minimized. This highly complex problem involves scheduling with resource constraints in a dynamic environment and is a typical NP-hard problem in general. In this study, we present a constraint programming (CP) based approach to address the problem with utilizing the strength of CP in its flexibility in formulating various complex and nonlinear constraints for industrial applications. In addition, we explore the ability of the CP solver with trying different combinations of constraint propagation and constructive search strategies and report our best findings from an extensive computational study.
In this work we investigate the application of optimization-based scheduling technologies to two mobile robot task planning problems. We develop and apply mixed-integer programming (MIP) and constraint programming (CP...
详细信息
Recently, land has been exploited extensively for onshore wind farms and turbines are frequently located in proximity to human dwellings, natural habitats, and infrastructure. This proximity has made land use constrai...
详细信息
ISBN:
(纸本)9780791857076
Recently, land has been exploited extensively for onshore wind farms and turbines are frequently located in proximity to human dwellings, natural habitats, and infrastructure. This proximity has made land use constraints and noise generation and propagation matters of increasing concern for all stakeholders. Hence, wind farm layout optimization approaches should be able to consider and address these concerns. In this study, we perform a constrained multi-objective wind farm layout optimization considering energy and noise as objective functions, and considering land use constraints arising from landowner participation, environmental setbacks and proximity to existing infrastructure. The optimization problem is solved with the NSGA-II algorithm, a multi-objective, continuous variable Genetic Algorithm. A novel hybrid constraint handling tool that uses penalty functions together with constraint programming algorithms is introduced. This constraint handling tool performs a combination of local and global searches to find feasible solutions. After verifying the performance of the proposed constraint handling approach with a suite of test functions, it is used together with NSGA-II to optimize a set of wind farm layout optimization test cases with different number of turbines and under different levels of land availability (constraint severity). The optimization results illustrate the potential of the new constraint handling approach to outperform existing constraint handling approaches, leading to better solutions with fewer evaluations of the objective functions and constraints.
We study a cumulative scheduling problem where a task duration and resource consumption are not fixed. The consumption profile of the task, which can vary continuously over time, is a decision variable of the problem ...
详细信息
We study a cumulative scheduling problem where a task duration and resource consumption are not fixed. The consumption profile of the task, which can vary continuously over time, is a decision variable of the problem and the task duration depends on this profile. For the discrete case, the paper presents a mixed integer linear program as well as a constraints programming model. Furthermore, valid inequalities deduced from constraint programming are also provided. Both models are then compared through computational experiments.
We propose a constraint programming approach for the optimization of inventory routing in the liquefied natural gas industry. We present two constraint programming models that rely on a disjunctive scheduling represen...
详细信息
We propose a constraint programming approach for the optimization of inventory routing in the liquefied natural gas industry. We present two constraint programming models that rely on a disjunctive scheduling representation of the problem. We also propose an iterative search heuristic to generate good feasible solutions for these models. Computational results on a set of large-scale test instances demonstrate that our approach can find better solutions than existing approaches based on mixed integer programming, while being 4-10 times faster on average. (C) 2014 Elsevier B.V. All rights reserved.
As the number of processors integrated on a single chip increases with the fast pace dictated by Moore's Law, multicore systems-on-chip (MPSoCs) are becoming truly distributed systems at the micro-scale. From the ...
详细信息
As the number of processors integrated on a single chip increases with the fast pace dictated by Moore's Law, multicore systems-on-chip (MPSoCs) are becoming truly distributed systems at the micro-scale. From the application viewpoint, requirements for high performance and low power have increased at a breakneck speed in many embedded computing domains like wireless communication, audio and video processing. Applications in these areas are highly parallelizable and feature significant functional parallelism. In the past decades several programming models and tools aimed at easing the task of efficiently coding and mapping parallel applications. Most of them are tied to a specific platform or find far from optimal solutions due to the hardness of the allocation and scheduling problem. In this paper we presents (1) a constraint programming-based solver generating optimal scheduling and mapping decisions for such applications, optimized for maximal throughput, and (2) the framework used to validate the solver on a real multicore platform.
This paper presents an efficient algorithm for an integrated operating room planning and scheduling problem. It combines the assignment of surgeries to operating rooms and scheduling over a short-term planning horizon...
详细信息
This paper presents an efficient algorithm for an integrated operating room planning and scheduling problem. It combines the assignment of surgeries to operating rooms and scheduling over a short-term planning horizon. This integration results in more stable planning through consideration of the operational details at the scheduling level, and this increases the chance of successful implementation. We take into account the maximum daily working hours of surgeons, prevent the overlapping of surgeries performed by the same surgeon, allow time for the obligatory cleaning when switching from infectious to noninfectious cases, and respect the surgery deadlines. We formulate the problem using a mathematical programming model and develop a branch-and-price-and-cut algorithm based on a constraint programming model for the subproblem. We also develop dominance rules and a fast infeasibility-detection algorithm based on a multidimensional knapsack problem to improve the efficiency of the constraint programming model. The computational results show that our method has an average optimality gap of 2.81% and significantly outperforms a compact mathematical formulation in the literature.
In the car-sequencing problem, a number of cars have to be sequenced on an assembly line respecting several constraints. This problem was addressed by both Operations Research (OR) and constraint programming (CP) comm...
详细信息
In the car-sequencing problem, a number of cars have to be sequenced on an assembly line respecting several constraints. This problem was addressed by both Operations Research (OR) and constraint programming (CP) communities, either as a decision problem or as an optimization problem. In this paper, we consider the decision variant of the car sequencing problem and we propose a systematic way to classify heuristics for solving it. This classification is based on a set of four criteria, and we consider all relevant combinations for these criteria. Some combinations correspond to common heuristics used in the past, whereas many others are novel. Not surprisingly, our empirical evaluation confirms earlier findings that specific heuristics are very important for efficiently solving the car-sequencing problem (see for instance Smith, 1996), in fact, often as important or more than the propagation method. Moreover, through a criteria analysis, we are able to get several new insights into what makes a good heuristic for this problem. In particular, we show that the criterion used to select the most constrained option is critical, and the best choice is fairly reliably the "load" of an option. Similarly, branching on the type of vehicle is more efficient than branching on the use of an option. Overall, we can therefore indicate with a relatively high confidence which is the most robust strategy, or at least outline a small set of potentially best strategies. Last, following a remark in Regin and Puget (1997) stating that the notion of slack used in heuristics induces a pruning rule, we propose an algorithm for this method and experimentally evaluate it, showing that, although computationally cheap and easy to implement, this is in practice a very efficient way to solve car-sequencing benchmarks. (C) 2014 Elsevier Ltd. All rights reserved.
In this study we consider the mapping of the main characteristics, i.e., the structural properties, of a classical job shop problem onto well-known combinatorial techniques, i.e., positional sets, disjunctive graphs, ...
详细信息
In this study we consider the mapping of the main characteristics, i.e., the structural properties, of a classical job shop problem onto well-known combinatorial techniques, i.e., positional sets, disjunctive graphs, and linear orderings. We procedurally formulate three different models in terms of mixed integer programming (MIP) and constraint programming (CP) paradigms. We utilize the properties of positional sets and disjunctive graphs to construct tight MIP formulations in an efficient manner. In addition, the properties are retrieved by the polyhedral structures of the linear ordering and they are defined on a disjunctive graph to facilitate the formulation of the CP model and to reduce the number of dominant variables. The proposed models are solved and their computational performance levels are compared with well-known benchmarks in the job shop research area using IBM ILog Cplex software. We provide a more explicit analogy of the applicability of the proposed models based on parameters such as time efficiency, thereby producing strong bounds, as well as the expressive power of the modeling process. We also discuss the results to determine the best formulation, which is computationally efficient and structurally parsimonious with respect to different criteria. (C) 2014 Elsevier Inc. All rights reserved.
暂无评论