A distributed approach to the scheduling problem

Abstract

The focus of many Artificial Intelligence approaches to solving the computer-based scheduling problem is on reducing the size of the search spaces that characterise such problems. The approach presented in this paper decomposes the scheduling problem and distributes a series of subproblems to autonomous agents which construct the schedule collectively through negotiation. Negotiation has been a key area in Distributed Artificial Intelligence research and although many applications have been developed using it as a model for cooperative problem solving, none have addressed the problem of scheduling. All scheduling problems consist of a set of objects that have to pass through a set of processes. In a job shop situation, the objects are the items being manufactured and the processes are the physical operations such as drilling, welding and so on. University timetabling is a special case of scheduling where the objects are students and the processes are the lectures which have to be attended in a given week. While the distributed approach is applicable to all classes of the scheduling problem, it is illustrated here in the area of timetabling. The system consists of a controlling agent and a network of intelligent agents which communicate through a blackboard. Each agent in the network represents a process venue, typically a lecture room. Each individual agent's knowledge consists of the all the attributes of the venue that it represents as well as the course/event allocations that have been made to it at any point during the construction of the timetable. The controlling agent keeps a list of all the events that. have to be scheduled in random order. Venue related constraint knowledge is held by the individual agents while global constraints such as event dashes is held by the controlling agent. For each time slot (session), the controller selects an event-to be scheduled and broadcasts a bid specification message over the network. Each agent representing a venue whose attributes satisfy the message requirements submits a bid. The bid is simply a value that reflects the appropriateness of the venue for the event. It is ·a cost score made up of penalties for excess capacity, distance etc. The controller evaluates all the submitted bids by sorting the values and awarding the event to the agent with the lowest bid. Since only those agents who are capable of hosting the event submit bids, the award is made to the most appropriate (cost-effective) venue. Once an agent has been awarded an event, it withdraws from the process unless a type 2 message is broadcast. When all the venues have been awarded bids, the controller repeats the process for the next time slot. There are considerable advantages in using a distributed system for timetabling. These, as well as the construction of the prototype system will be discussed.