行使者请注明文章出处

Dr. Bo Zhao,  Prof. Dr. Yushun Fan

Department of Automation, Tsinghua University

Tsinghua Yuan, Beijing 100084   P. R. China ABSTRACT: Up to date more and more research of scheduling use Multi-agent System (MAS) technique. In this paper MAS is used to realize integration of scheduling algorithms. Firstly, Multi-agent Scheduling System (MASS) is divided into two types: Entity-type MASS and Process-type MASS. Some of the researches are introduced. Secondly, the concept of integration of scheduling algorithms is put forward. Thirdly, the models of agents, computing agent and manager, are proposed. Then a Process-type MASS of multi-agent based integration of scheduling algorithms, which compose above two sorts of agents, is built. Finally, we conclude by describing the significance of our research and highlighting future extensions.
KEY WORDS: Scheduling, Multi-agent System, Integration of Scheduling Algorithms, Multi-agent Scheduling System

 1. Introduction

 Algorithm is the key for the scheduling theory. The principle of scheduling is to find an optimal scenario of job allocation or resource distribution with scheduling algorithms. In the past decades many algorithms originated from other fields have been used in scheduling research and therefore formed the so-called scheduling algorithms. These works have enriched scheduling theory. However, any single algorithm that people have used so far are only applicable to a few special environments and can not adapt to dynamic production environment. This makes scheduling algorithms have not exerted all of their power in practical production. It is often the case that the plan formulated by scheduling algorithms is disabled because of some disturbance such as machine failure, unexpected jobs coming into workshop, material shortage. The inconsistency of scheduling theory with the scheduling practice has remained a big issue in manufacturing. 

To solve the problems one may think of two solutions:

 1)     Finding an all-purpose scheduling algorithm that is applicable to almost all sorts of scheduling cases.

 2)     Finding a mechanism by which appropriate algorithms of scheduling algorithms library can be called dynamically and integrated rapidly to respond to the change of production environment.

 Unfortunately there is no one-fits-all algorithm that meets the requirement of solution 1. The promising and recommendable approach would be the latter. The purpose of this paper is to find such a mechanism named Integration of Scheduling Algorithms (ISA) and use MAS technique to realize it.

 MAS (Multi-agent System) technique, which is a branch of distribute artificial intelligence, has been regarded as one of the most promising approaches to solve scheduling problems under dynamic environments and has attracted a lot of attention recently. In this paper, the MAS technique is used to realize dynamic integration of scheduling algorithm. And the solution will ensure either theoretical efficiency or operation robustness.

 We may call a scheduling system that uses multi-agent technique as Multi-agent Scheduling System (MASS). By reviewing some important literatures, we find that MASS can be divided into two types:

 1)     Entity-type MASS

Agents in such MASS map physical entities in real-life systems as jobs and resources (machine, conveyance, storage, etc.). The major feature of such MASS is the reciprocity between resource agents and job agents. Every agent has intention of itself, goal and benefit. They are capable of self-advancement and self-control. They can also be distinguished from environmental information and then take action. Resource agents and job agents, as supplier and customer in market, achieve their maximal benefits and system goals through negotiation or transaction.

Research of Entity-type MASS is very plentiful. Lin et al.[1] used agents to response functions and entities (machine, job, database, etc.) of manufacturing system in their framework. And they used mark-like model to realize negotiation among agents. Ramos[2] also put forward a scenario that compose of resource agents and job agents. Gomes et al.[3]  view a MASS as an three level organization. Agents are signed different roles and functions depending on their position within the structure of the system. Agents of the low level are classified resource agents and job agents. Ouelhadj et al.[4] defined an “actor” architecture where agents is associated with particular functions which are distributed over resource agents and use contact net protocol for dynamic scheduling. Rabelo et al.[5] studied multi-agent based scheduling in virtual enterprise environments on the base of HOLOS scheduling system, which is a framework devoted to derive “instance” of agile scheduling system. 

2)     Process-type MASS

 Predominant agents in such MASS are called process agents. They map processes that realize a function [6], a computation [7], an activity [8], etc. Each process agent can only solve part of a problem. Different agents work together by collaboration to achieve system’s goal, as people coming from different fields to a team will do.

 Unlike Entity-type MASS that mainly composes of resource agents and job agents, Process-type MASS has no typical architecture.  There is much difference among researches of such system by now. Lau[6] defined a MASS for FMS scheduling, which is capable of individual learning and group learning. Agents in the system are scheduling models that have ability of predictive scheduling and making reaction toward environment or other agents. Morikawa et al.[7] use agent maps genetic algorithm in his research of scheduling in process of CIM. The whole process of solving problem is divided into several stages. Each agent responses one stage. They work one by one. One agent gets input from upriver agents and output result to downriver agents. Gary Knotts[8] present a multi-agent scheduling method to solve multimode, resource-constrained project scheduling problem. Agents map activities of project.

[1] [2]  下一页