Author name cluster

Michel Wilson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

AIJ Journal 2014 Journal Article

Flexibility and decoupling in Simple Temporal Networks

Michel Wilson
Tomas Klos
Cees Witteveen
Bob Huisman

We propose a new metric to determine the flexibility of a Simple Temporal Network (STN). After reviewing some existing flexibility metrics, we conclude that these metrics fail to capture the dependencies between events specified in the STN. As a consequence, these metrics will usually overestimate the available flexibility in such a system. We propose to use an intuitively more acceptable flexibility metric. This metric is based upon the notion of an interval schedule for an STN. Such an interval schedule specifies an interval for every event in the STN in such a way that, for every event, we are free to choose a starting time within its interval independently from the choice made for other events. We show that an interval schedule that maximizes our flexibility metric is computable in low-order polynomial time. As byproducts of this flexibility metric, we discuss simple solutions to problems in STNs with uncertainty (STNUs) and temporal decoupling in STNs. With respect to the latter we show that after computing our flexibility metric, we get a decomposition of the STN almost for free. Even more importantly, we show that contrary to popular belief, such a decomposition does not affect the flexibility of the original STN.

Details DOI

AAAI Conference 2014 Conference Paper

Optimal Decoupling in Linear Constraint Systems

Cees Witteveen
Michel Wilson
Tomas Klos

Decomposition is a technique to obtain complete solutions by assembling independently obtained partial solutions. In particular, constraint decomposition plays an important role in distributed databases, distributed scheduling and violation detection: It enables conflictfree local decision making, while avoiding communication overloading. One of the main issues in decomposition is the loss of flexibility due to decomposition. Here, flexibility roughly refers to the freedom in choosing suitable values for the variables in order to satisfy the constraints. In this paper, we concentrate on linear constraint systems and efficient decomposition techniques for them. Using a generalization of a flexibility metric developed for Simple Temporal Networks, we show how an efficient decomposition technique for linear constraint systems can be derived that minimizes the loss of flexibility. As a by-product of this decomposition technique, we propose an intuitively attractive flexibility metric for linear constraint systems where decomposition does not incur any loss of flexibility.

PDF Details

IJCAI Conference 2013 Conference Paper

Flexibility and Decoupling in the Simple Temporal Problem

Michel Wilson
Tomas Klos
Cees Witteveen
Bob Huisman

In this paper we concentrate on finding a suitable metric to determine the flexibility of a Simple Temporal Problem (STP). After reviewing some flexibility metrics that have been proposed, we conclude that these metrics fail to capture the correlation between events specified in the STP, resulting in an overestimation of the available flexibility in the system. We propose to use an intuitively more acceptable flexibility metric based upon uncorrelated time-intervals for the allowed starting times of events in an STP. This metric is shown to be computable in low-polynomial time. As a byproduct of the flexibility computation, we get a decomposition of the STN almost for free: for every possible k-partitioning of the event space, a decomposition can be computed in O(k)-time. Even more importantly, we show that contrary to popular belief, such a decomposition does not affect the flexibility of the original STP.

PDF Details DOI

ECAI Conference 2012 Conference Paper

Enhancing predictability of schedules by task grouping

Michel Wilson
Cees Witteveen
Bob Huisman

An important problem in scheduling is ensuring predictability of solutions in case of execution delays. We propose a new method, task grouping, and apply it in combination with a precedence constraint posting algorithm to solve the resource-constrained project scheduling problem. Using this method tasks that must be executed sequentially can be grouped, but their definitive order is determined at execution time such that delays can sometimes be mitigated. As a consequence, our method generates a set of execution options for a schedule. Using the well-known PSPLIB instances, we show that our method can reduce the impact of delays on the predictability of schedule execution.

Details