For linear construction projects, it has long been known that work continuity is important in improving efficiency. However, most existing scheduling techniques cannot satisfy the need for solving such issues. This pa...
详细信息
ISBN:
(纸本)9781424420742
For linear construction projects, it has long been known that work continuity is important in improving efficiency. However, most existing scheduling techniques cannot satisfy the need for solving such issues. This paper presents an optimization model for solving linear scheduling problems involving maintaining work continuity. The proposed model adopts constraint programming (CP) as the searching algorithm, aiming at optimizing project total cost. Through cast study, the efficiency of the proposed model is then illustrated.
A novel adaptation of impact-based search strategies for constraint-based resource scheduling is presented. Search based on impacts applies a general purpose search strategy originally from Linear Integer programming ...
详细信息
ISBN:
(纸本)9783885792284
A novel adaptation of impact-based search strategies for constraint-based resource scheduling is presented. Search based on impacts applies a general purpose search strategy originally from Linear Integer programming and recently adapted to constraint programming. To my knowledge it is shown for the first time that this strategy is properly applicable to constraint-based scheduling and performs well on the class of job-shop scheduling problems. Evidence is given empirically by comparison with a problem-specific and a random strategy.
The phrase "Planning and Scheduling" represents a class of problems where a resource in limited supply is to be optimally applied. Planning and Scheduling problems are accommodated by a branch of mathematics...
详细信息
ISBN:
(纸本)1424414881
The phrase "Planning and Scheduling" represents a class of problems where a resource in limited supply is to be optimally applied. Planning and Scheduling problems are accommodated by a branch of mathematics known as Operations Research. The goal of Operations Research technology is to find a solution to a known set of conditions such that some minimum "cost" or maximum "profit" is achieved, within some defined constraints. Several algorithms, such as Linear programming, Dynamic programming, constraint Logic programming, have arisen in the past three to four decades to solve particular classes of problems, but real-world problems continue to be extremely difficult to characterize and solve robustly. Therefore, good Operations Research is still dominated by the ability to transform the real problem into one or more simplified - and solvable - problems without sacrificing too much of the real problem's objectives and constraints. The subject technique evolved from the environment of multi-level resource management, where the decision variables represent requests for use of a given resource at a given level. Like a job-shop scheduling problem, resource management problem requests have inherent multiplicities (the part can be manufactured on any of n machines) that cause combinatorial explosions in the search for optimal resource assignments. The multi-level nature arises when the use of a resource at one level in turn requires or precludes the use of resource(s) at other levels, thus creating derived decision variables associated with the other levels. Such situations occur regularly in space (spacecraft, relays, ground antennas, and ground Telemetry, Tracking and Commanding (TT&C) hardware), airline (aircraft, flight crews, terminals, ground support crews), and railroad (locomotives, track, crews) applications. In multi-level resource problems, constraints exist not only among the decision variables at the resource level being requested, but also between levels. Becau
Assembly line balancing problems (ALBP) are of capital importance for the industry since the first assembly line for the Ford T by Henry Ford. Their objective is to optimize the design of production lines while satisf...
详细信息
The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be sol...
详细信息
The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved in polynomial time; with them, the CSPP is NP-hard and thus far no polynomial-time algorithms exist for solving it optimally. The problem arises in a number of practical situations. In the case of vehicle path planning, the vehicle may be an aircraft flying through a region with obstacles such as mountains or radar detectors, with an upper bound on the fuel consumption, the travel time or the risk of attack. The vehicle may be a submarine travelling through a region with sonar detectors, with a time or risk budget. These problems all involve a network which is a discrete model of the physical domain. Another example would be the routing of voice and data information in a communications network such as a mobile phone network, where the constraints may include maximum call delays or relay node capacities. This is a problem of current economic importance, and one for which time-sensitive solutions are not always available, especially if the networks are large. We consider the simplest form of the problem, large grid networks with a single side constraint, which have been studied in the literature. This thesis explores the application of constraint programming combined with Lagrange Relaxation to achieve optimal or near-optimal solutions of the CSPP. The following is a brief outline of the contribution of this thesis. Lagrange Relaxation may or may not achieve optimal or near-optimal results on its own. Often, large duality gaps are present. We make a simple modification to Dijkstra’s algorithm that does not involve any additional computational work in order to generate an estimate of path time at every node.%%%%We then use this information to constrain the network along a bisecting meridian. The combination of Lagrange Relaxation (LR) and a heuristic f
In this paper, we propose the use of constraint logic programming as a way of modeling contextsensitive execution-times of program segments. The context-sensitive constraints are collected automatically through static...
详细信息
ISBN:
(纸本)9783939897101
In this paper, we propose the use of constraint logic programming as a way of modeling contextsensitive execution-times of program segments. The context-sensitive constraints are collected automatically through static analysis or measurements. We achieve considerable tightness in comparison to traditional calculation methods that exceeded 20% in some cases during evaluation. The use of constraint-logic programming in our calculations proves to be the right choice when compared to the exponential behaviour recorded by the use of integer linear-programming.
We show how to efficiently model binary constraint problems (BCP) as integer programs. After considering tree-structured BCPs first, we show that a Sherali-Adams-like procedure results in a polynomial-size linear prog...
详细信息
ISBN:
(纸本)9783540723967
We show how to efficiently model binary constraint problems (BCP) as integer programs. After considering tree-structured BCPs first, we show that a Sherali-Adams-like procedure results in a polynomial-size linear programming description of the convex hull of all integer feasible solutions when the BCP that is given has bounded tree-width.
Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/ integer programming methods. We ...
详细信息
Conway's game of Life provides an interesting testbed for exploring issues in formulation, symmetry, and optimization with constraint programming and hybrid constraint programming/ integer programming methods. We consider three Life pattern- creation problems: finding maximum density still- Lifes, finding smallest immediate predecessor patterns, and finding period- 2 oscillators. For the first two problems, integrating integer programming and constraint programming approaches provides a much better solution procedure than either individually. For the final problem, the constraint programming formulation provides the better approach.
LODE is a web tool for deaf children, which aims at stimulating global reasoning on written e-stories. This paper reports on an initial prototype application of LODE. First, we motivate the need of an e-tool such as L...
详细信息
ISBN:
(纸本)9781595939760
LODE is a web tool for deaf children, which aims at stimulating global reasoning on written e-stories. This paper reports on an initial prototype application of LODE. First, we motivate the need of an e-tool such as LODE for deaf children, then we report on the assessment of the prototype with expert users and two deaf children, laying the groundwork for the final evaluation and development of LODE.
暂无评论