Last issue
2017 (vol. 27) - Number 2

W. Bozejko, M. Wodecki:

Discrete Systems: Theory and Applications. Special issue.

G. Bocewicz, Z. Banaszak, I. Nielsen:

Delivery-flow routing and scheduling subject to constraints imposed by vehicle flows in fractal-like networks

W. Bozejko, A. Gnatowski, R. Idzikowski, M. Wodecki:

Cyclic flow shop scheduling problem with two-machine cells

W. Bozejko, M. Uchronski,, Z. Chaczko, M. Wodecki:

Parallel patterns determination in solving cyclic flow shop problem with setups

J. Brodny, S. Alszer, J. Krystek, M. Tutak:

Availability analysis of selected mining machinery

K. Chmielewska, D. Formanowicz, P. Formanowicz:

The effect of cigarette smoking on endothelial damage and atherosclerosis development - modeled and analyzed using Petri nets

A. Galuszka, J. Krystek, A. Swierniak, T. Grzejszczak, C. Lungoci:

Information management in passenger traffic supporting system design as a multi-criteria discrete optimization task

M. Kardynska, J. Smieja:

Sensitivity analysis of signaling pathway models based on discrete-time measurements

J. Kasprzyk, P. Krauze, S. Budzan, J. Rzepecki:

Vibration control in semi-active suspension of the experimental off-road vehicle using information about suspension deflection

M. Koryl, D. Mazur:

Towards emergence phenomenon in business process management

M. Koryl:

Active resources concept of computation for enterprise software

H. Krawczyk, M. Nykiel:

Mobile devices and computing cloud resources allocation for interactive applications

W. Mitkowski, W. Bauer, M. Zagórowska:

Discrete-time feedback stabilization

J. Pempera:

An exact block algorithm for no-idle RPQ problem

K. Rzosinska, D. Formanowicz, P. Formanowicz:

The study of the influence of micro-environmental signals on macrophage differentiation using a quantitative Petri net based model

K. Skrzypczyk , M. Mellado:

Vehicle navigation in populated areas using predictive control with environmental uncertainty handling

W. Bozejko, J. Pempera, M. Wodecki:

A fine-grained parallel algorithm for the cyclic flexible job shop problem

ACS Abstract:

2008 (Volume 18)
Number 2
1. Constraint satisfaction techniques in planning and scheduling: An introduction
2. Filtering algorithms for the unary resource constraint
3. Modification strategies for SAT-based plan adaptation
4. Unifying planning and scheduling as timelines in a component-based perspective

Constraint satisfaction techniques in planning and scheduling: An introductionDownload full PDF article
R. Bartak
(Charles University, Czech Republic)

Planning and scheduling are two closely related areas that, despite their similarity, deal with different problems. While the planning ask is to decide which actions are necessary to achieve a given goal, the scheduling task is to allocate known activities to scarce resources, such as machines, over time. Typically planning and scheduling problems are solved separately using different solving techniques. However, real-life problems require a more integrated approach. Constraint satisfaction seems to be such a unifying solving technology for both planning and scheduling problems. This paper describes how constraint satisfaction techniques can be applied to planning and scheduling problems.

keywords: constraint satisfaction, problem modeling, planning, scheduling


Filtering algorithms for the unary resource constraintDownload full PDF article
P. Vilim
(ILOG S.A., Gentilly Cedex, France)

Scheduling is one of the most successful application areas of constraint programming mainly due to special   global constraints designed to model resource restrictions. Among scheduling constraints, the most useful and most studied constraint is probably the unary resource constraint. This paper presents state-of-the-art filtering algorithms for this important constraint. These algorithms are very fast (almost all of them has time complexity O(n log n) and furthermore they are able to take into account so called optional activities, that is, activities which may or may not appear in the schedule depending for example on a resolution of an alternative processing rule(s). In particular, this paper presents the following algorithms: overload checking, edge finding, not-first/not-last, detectable precedences and precedence energy.

keywords: constraint programming, scheduling, optional activities, unary resource, filtering algorithms


Modification strategies for SAT-based plan adaptationDownload full PDF article
R. van der Krogt
(Cork Constraint Computation Centre, University College Cork, Ireland)

Planning, the generation of a course of action to achieve a set of goals, is an important technique in the development of intelligent agents. Heretofore, planning has been largely considered as a one-shot problem. However, in practice, we are often dealing with situations in which an existing plan has to be adapted. Not only might we be facing a dynamic environment that requires a plan to be repaired, but it may also be that we recognize the new planning problem as being similar to one that we have solved before (i.e. case-based planning).
This paper investigates a plan adaptation framework based on SAT-encodings of the planning problem. Compilation techniques have been very successfully applied to planning, as evidenced by their success in recent planning competitions. So far, however, such techniques have not been used for plan adaptation purposes. This paper explores whether it is feasible to modify the generated SAT instances such as to encode information that was extracted from the solution to the original planning problem.

keywords: plan repair, planning as satisfiability


Unifying planning and scheduling as timelines in a component-based perspectiveDownload full PDF article
F. Pecora
(AASS Mobile Robotics Lab, Orebro University, Sweden)
S. Fratini
(ISTC-CNR,National Research Council of Italy)
A. Cesta
(ISTC-CNR,National Research Council of Italy)

The timeline-based approach to planning represents an effective alternative to classical planning for complex domains requiring the use of both temporal reasoning and scheduling features. This paper discusses the constraint-based approach to timeline planning and scheduling introduced in OMPS.  OMPS is a an architecture for problem solving which draws inspiration from both control theory and constraint-based reasoning, and which is based on the notion of components.
The rationale behind the component-based approach shares with classical control theory a basic modeling perspective: the planning and scheduling problem is represented by identifying a set of relevant domain components which need to be controlled to obtain a desired temporal behavior for the entire system. Components are entities whose properties may vary in time and which model one or more physical (or logical) domain subsystems relevant to a given planning context. The planner/scheduler plays the role of the controller for these entities, and reasons in terms of constraints that bound their internal evolutions and the desired properties of the generated behaviors (goals).
Our work complements this modeling assumption with a constraint-based computational framework.  Admissible temporal behaviors of components are specified as a set of causal constraints within a rich temporal specification, and goals are specified as temporal constraint preferences.  The OMPS software architecture presented in this paper combines both specific and generic constraint solvers in defining consistent timelines which satisfy a given set of goals.

keywords: planning, scheduling, timelines


<< Back