
An Integrated Distributed Scheduler
Q. Y. Luo P. G. Hendry J. T. Buchanan
Department of Computer Science
University of Strathclyde
Glasgow G1 1XH, UK
Research Report KEG893
October 15, 1993
Abstract
In this paper, an Integrated Distributed Scheduler (IDS) is introduced. IDS integrates various
distributed and parallel computing approaches, namely distributedagentbased, parallelagentbased,
and functionagentbased problem solving strategies, to solve distributed scheduling problems.
These different approaches are presented and discussed.
Key words: Distributed Scheduling Problems, Distributed Constraint Satisfaction Problems
and Parallel Search Algorithms
1 INTRODUCTION
Based on [Baker74], a scheduling problem can be defined as the allocation of resources over time to perform a collection of operations. Scheduling problems (SPs) are very computationally intensive to solve with many relatively small problems requiring considerable processing time. Many approaches have been used to solve scheduling problems, one of which is to cast it as a constraint satisfaction problem (CSP). A CSP consists of variables, domains and constraints where the task is to assign each variable a value from its domain so that all constraints acting between variables are satisfied.
Real world scheduling problems often have the property of being naturally logically or physically
distributed (e.g. factory scheduling). Distributed problem solving (DPS) techniques to solve
distributed CSPs (DCSPs) may be applied to solve distributed scheduling problems (DSPs).
A distributed scheduling problem (DSP) is defined as a scheduling problem in which multiple
agents (software processes) are involved.
[Burke91] pointed out that schedulers can be classified as predictive or reactive. Predictive schedulers
are created in a closed world and assume that events are predictable. However, in a real world
many events are unpredictable. Reactive scheduling addresses the problem of maintaining a schedule
in a dynamic and stochastic world. Such a world offers up both conflicts and opportunities. In order
to successfully react to conflict the scheduling system must be able to identify the sources of conflicts
and must have the tools to resolve these conflicts. In order to exploit opportunities the system must
somehow represent the current set of all possible schedules.
As a scheduling problem is computationally NPhard, it cannot be solved by an algorithm whose
execution time is bounded by a polynomial function [Rodammer89] [Atabakhsh91].
Various approaches have been used to solve scheduling problems such as ISIS [Fox83], OPIS [Smith86], S2 [Elleby88], ENTERPRISE [Malone83], CONTRACT NET [Davis83], YAMS [Parunak88], CSS [Ow88], CORTES [Sadeh89] and DAS [Buchanan89] [Burke91]. DAS may be considered a logical progression from all of the above systems. DAS does not differentiate between prediction and reaction.
This paper presents work on the Integrated Distributed Scheduler (IDS) which is currently being developed. The work builds on previous research on the Distributed Asynchronous Scheduler (DAS)