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 KEG-8-93

October 15, 1993

Abstract

In this paper, an Integrated Distributed Scheduler (IDS) is introduced. IDS integrates various distributed and parallel computing approaches, namely distributed-agent-based, parallel-agentbased, and function-agent-based 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 NP-hard, 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)