检索结果-内蒙古大学图书馆

Continuous filling and emptying of storage systems in constraint-based scheduling

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2005年第2期165卷 510-524页

作者： Sourd, F Rogerie, J CNRS LIP6 F-75252 Paris France ILOG F-94253 Gentilly France

In constraint-based scheduling, storage systems are modeled by a class of resources called reservoirs. Activities can either produce a quantity of product to be stored in the reservoir or consume it, removing the quantity from the reservoir. Most of the models presented in the literature assume that the production and the consumption is instantaneous but it can be a very bad approximation for some problems, for example those dealing with tanks of fluid. This paper introduces the continuous reservoir model in which the activity fills or empties the reservoir at a constant rate from its start time to its end time. This model is generalized to deal with additional constraints, such that leaks or overflows, that cannot be modeled by activities. Timetabling, a classical technique for the propagation of resource constraints in constraint-based scheduling, is adapted and extended to this new model. (c) 2004 Elsevier B.V. All rights reserved.

关键词： constraint-based scheduling continuous reservoir

来源：评论

学校读者我要写书评

暂无评论

Continuous filling and emptying of storage systems in constraint-based scheduling

Continuous filling and emptying of storage systems in constr...

引用

8th International Workshop on Project Management and scheduling

作者： Sourd, F Rogerie, J CNRS LIP6 F-75252 Paris France ILOG F-94253 Gentilly France

关键词： constraint-based scheduling continuous reservoir

来源：评论

学校读者我要写书评

暂无评论

A survey of constraint based scheduling systems using an artificial intelligence approach

引用

Artificial Intelligence in Engineering 1991年第2期6卷 58-73页

作者： Atabakhsh, H. National Research Council of Canada Systems Lab. Ottawa Ont. K1A 0R6 M-2 Montreal Road Canada

Recently, Artificial Intelligence approaches have been used to solve the problem of constraint based scheduling. The aim is to find a feasible solution which satisfies a maximum number of constraints within a reasonable amount of time. An AI system in this domain should not replicate the human scheduler but extend his capabilities by doing more problem solving than was manually possible. The constraints are used to help reduce the search space. This paper reviews various AI techniques used in constraint based scheduling, by comparing existing systems. The aim is to help future research concerning the application of AI to constraint based scheduling, by evaluating the progress that has been made in this area. © 1991.

关键词： Artificial Intelligence blackboard model constraint-based scheduling dynamic scheduling frames heuristics opportunistic reasoning relaxation rules

来源：评论

学校读者我要写书评

暂无评论

Distributed Approaches for Solving constraint-based Multiagent scheduling Problems

Distributed Approaches for Solving Constraint-based Multiage...

引用

作者： Boerkoel, James C., Jr. University of Michigan

学位级别：Ph.D.

This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments in which tempo and complexity outstrip people's cognitive capacity. The critical challenge is that, as individuals decide how to act on their scheduling goals, scheduling agents should answer queries regarding the events in their interacting schedules while respecting individual privacy and autonomy to the extent possible. I formally define both the Multiagent Simple Temporal Problem (MaSTP) and Multiagent Disjunctive Temporal Problem (MaDTP) for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. My hypothesis is that combining a bottom-up approach—where an agent externalizes constraints that compactly summarize how its local subproblem affects other agents' subproblems, with a top-down approach—where an agent proactively constructs and internalizes new local constraints that decouple its subproblem from others', will lead to effective solution techniques. I confirm that my hypothesized approach leads to distributed algorithms that calculate summaries of the joint solution space for multiagent scheduling problems, without centralizing or otherwise redistributing the problems. In both the MaSTP and MaDTP domains, the distributed algorithms permit concurrent execution for significant speedup over current art, and also increase the level of privacy and independence in individual agent reasoning. These algorithms are most advantageous for problems where interactions between the agents are sparse compared to the complexity of agents' individual scheduling problems. Moreover, despite the combinatorially-large and unwieldy nature of the MaDTP solution space, I show that agents can use influence spaces, which compactly capture the impact of agents' interacting schedules, to tractably converge on distributed summaries of the joint solution space. Finally, I apply the

关键词： Multiagent scheduling constraint-based scheduling Simple Temporal Problem Disjunctive Temporal Problem Temporal Decoupling Multiagent Coordination Thesis

来源：评论

学校读者我要写书评

暂无评论

An object-oriented, constraint-based heuristic for a class of passenger-train scheduling problems

引用

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS 2000年第1期30卷 12-21页

作者： Isaai, MT Singh, MG Univ Manchester Inst Sci & Technol Dept Computat Manchester M60 1QD Lancs England

A constraint-based heuristic technique for predictive scheduling of passenger trains is presented in this paper. The algorithm, which is lookahead, has been designed using an object-oriented methodology and is suitable for a single-track railway with some double-track sections. It is shown that the heuristic tends to minimize total waiting time of the trains concerned. Simulation experiments with real data show the superiority of the schedules created to those by human experts with reference to data provided from predictive timetables and specifications of Iran Railways.

关键词： constraint-based scheduling constraint satisfaction problems decision-support systems heuristics modeling optimization timetabling train scheduling

来源：评论

学校读者我要写书评

暂无评论

A constraint-based method for project scheduling with time windows

引用

JOURNAL OF HEURISTICS 2002年第1期8卷 109-136页

作者： Cesta, A Oddi, A Smith, SF CNR IP I-00137 Rome Italy Carnegie Mellon Univ Inst Robot Pittsburgh PA 15213 USA

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.

关键词： constraint-based scheduling procedence constraint posting project scheduling

来源：评论

学校读者我要写书评

暂无评论

Solve-and-robustify Synthesizing partial order schedules by chaining

引用

JOURNAL OF scheduling 2009年第3期12卷 299-314页

作者： Policella, Nicola Cesta, Amedeo Oddi, Angelo Smith, Stephen F. European Space Agcy D-64293 Darmstadt Germany CNR ISTC CNR I-00185 Rome Italy Carnegie Mellon Univ Inst Robot Pittsburgh PA 15213 USA

Goal separation is often a fruitful approach when solving complex problems. It provides a way to focus on relevant aspects in a stepwise fashion and hence bound the problem solving scope along a specific direction at any point. This work applies goal separation to the problem of synthesizing robust schedules. The problem is addressed by separating the phase of problem solution, which may pursue a standard optimization criterion (e.g., minimal makespan), from a subsequent phase of solution robustification in which a more flexible set of solutions is obtained and compactly represented through a temporal graph, called a Partial Order Schedule (POS). The key advantage of a POS is that it provides the capability to promptly respond to temporal changes (e. g., activity duration changes or activity start-time delays) and to hedge against further changes (e.g., new activities to perform or unexpected variations in resource capacity). On the one hand, the paper focuses on specific heuristic algorithms for synthesis of POSs, starting from a pre-existing schedule (hence the name Solve-and-Robustify). Different extensions of a technique called chaining, which progressively introduces temporal flexibility into the representation of the solution, are introduced and evaluated. These extensions follow from the fact that in multi-capacitated resource settings more than one POS can be derived from a specific fixed-times solution via chaining, and carry out a search for the most robust alternative. On the other hand, an additional analysis is performed to investigate the performance gain possible by further broadening the search process to consider multiple initial seed solutions. A detailed experimental analysis using state-of-the-art RCPSP/max benchmarks is carried out to demonstrate the performance advantage of these more sophisticated solve and robustify procedures, corroborating prior results obtained on smaller problems and also indicating how this leverage increases as problem

关键词： Iterative improvement techniques scheduling under uncertainty constraint-based scheduling

来源：评论

学校读者我要写书评

暂无评论

A quadratic edge-finding filtering algorithm for cumulative resource constraints

引用

constraintS 2014年第3期19卷 243-269页

作者： Kameugne, Roger Fotso, Laure Pauline Scott, Joseph Ngo-Kateu, Youcheu Univ Maroua Dept Math Higher Teachers Training Coll Maroua Cameroon Univ Yaounde I Dept Math Fac Sci Yaounde Cameroon Univ Yaounde I Dept Comp Sci Fac Sci Yaounde Cameroon Uppsala Univ Div Comp Sci Dept Informat Technol SE-75105 Uppsala Sweden

The cumulative scheduling constraint, which enforces the sharing of a finite resource by several tasks, is widely used in constraint-based scheduling applications. Propagation of the cumulative constraint can be performed by several different filtering algorithms, often used in combination. One of the most important and successful of these filtering algorithms is edge-finding. Recent work by Vilim has resulted in a oe'(a) (kn log n) algorithm for cumulative edge-finding (where n is the number of tasks and k is the number of distinct capacity requirements), as well as a new related filter, timetable edge-finding, with a complexity of oe'(a)(n (2)). We present a sound oe'(a)(n (2)) filtering algorithm for standard cumulative edge-finding, orthogonal to the work of Vilim;we also show how this algorithm's filtering may be improved by incorporating some reasoning from extended edge-finding, with no increase in complexity. The complexity of the new algorithm does not strictly dominate previous edge-finders for small k, and it sometimes requires more iterations to reach the same fixpoint;nevertheless, results from Project scheduling Problem Library benchmarks show that in practice this algorithm consistently outperforms earlier edge-finding filters, and remains competitive with timetable edge-finding, despite the latter algorithm's generally stronger filtering.

关键词： constraint-based scheduling Edge-finding Global constraints Cumulative resource Task intervals

来源：评论

学校读者我要写书评

暂无评论

Redundant cumulative constraints to compute preemptive bounds

引用

DISCRETE APPLIED MATHEMATICS 2018年 234卷 168-177页

作者： Baptiste, Philippe Bonifas, Nicolas Ecole Polytech LIX F-91128 Palaiseau France IBM Corp 9 Rue Verdun F-94250 Gentilly France

We introduce a reformulation of the cumulative resource in scheduling. This reformulation yields a lower bound on the makespan which is at least as good as that of a preemptive schedule on the original resource. Its computation relies on a linear program whose size depends on the resource capacity but not on the number of tasks, which enables to precompute the reformulations. It provides a significant improvement for all algorithms which rely on energy-based reasonings for propagating cumulative constraints, such as edge-finding and energy reasoning techniques. We improve the lower bounds of some RCPSP instances from the PSPLIB. (C) 2017 Elsevier B.V. All rights reserved.

关键词： constraint-based scheduling Cumulative constraint Reformulation Preemptive bound

来源：评论

学校读者我要写书评

暂无评论

Toward interactive scheduling systems for managing medical resources

引用

ARTIFICIAL INTELLIGENCE IN MEDICINE 2000年第2期20卷 113-138页

作者： Oddi, A Cesta, A CNR IP Natl Res Council Italy I-00137 Rome Italy

Managers of medico-hospital facilities are facing two general problems when allocating resources to activities: (1) to find an agreement between several and contrasting requirements;(2) to manage dynamic and uncertain situations when constraints suddenly change over time due to medical needs. This paper describes the results of a research aimed at applying constraint-based scheduling techniques to the management of medical resources. A mixed-initiative problem solving approach is adopted in which a user and a decision support system interact to incrementally achieve a satisfactory solution to the problem. A running prototype is described called Interactive Scheduler which offers a set of functionalities for a mixed-initiative interaction to cope with the medical resource management. Interactive Scheduler is endowed with a representation schema used for describing the medical environment, a set of algorithms that address the specific problems of the domain, and an innovative interaction module that offers functionalities for the dialogue between the support system and its user. A particular contribution of this work is the explicit representation of constraint violations, and the definition of scheduling algorithms that aim at minimizing the amount of constraint violations in a solution. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： management of medico-hospital resources constraint-based scheduling mixed-initiative problem solving

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：