Japan Advanced Institute of Science and Technology

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

Kilseok Roh

Scho ol of InformationScience,

Japan Advanced Instituteof Scienceand Technology

February, 15, 2000

Keywords: discreteeventsystems,sup ervisor,languagestability,timed discreteeventsystems,

stabilizability.

A system in which asynchronous o ccurring of discrete eventschanges the state is called a discrete

eventsystems(DES).ADESisadynamicsystemthatevolvesinaccordancewiththeabrupto ccurrence,

atpossiblyunknownirregularintervals,ofphysicalevents. DESsariseinthedomainsofmanufacturing,

robotics, vehicular trac, logistics(conveyanceand storageof go ods, organizationand deliveryof ser-

vices),andcomputerandcommunicationnetworks. Typicalapplicationsarefoundincomputernetworks,

exible manufacturing system(FMS), op eratingsystems, database systems, and so on. An event may

correspondto thearrivalordeparture ofa customer in aqueue, thecompletion ofa task orthefailure

of a machine in a manufacturing system, transmissionof a packet in a communication system, or the

occurrenceofa disturbanceor changeof setp ointin a complexcontrol system. By therequirement for

theeectivecontrolofsuch DESs, there haveb een manyresearchesonDESs from various viewpoints.

Especially,manyof themare dealing withmo deling andanalysis ofDESs. Manytechniqueshaveb een

proposedforsomeindividualproblemssuchasthemutualexclusionproblemandtheconcurrencycontrol

problem. Inaccordance withthedevelopmentofthecomputer applicationtechnology,large-scale DESs

appear in real applications. It has b een required to develop a unied methodology for the mo deling

andcontrolofsuchlargeand complicatedDESs. Therefore,manyresearcherspayattentionto system-

theoreticapproachestotheanalysisofDESs. Asmo delsofDESs,therearep erformancemo delssuchas

queuingnetworks,andlogicalmodelssuchas formallanguage,automaton,andPetrinets. Ingeneral,if

weanalyzethecontrolprobleminwhichonlytheorderofoccurringeventsisimportant(e.g.,themutual

exclusion problemand theconcurrencycontrol problem), logicalmodelsare suitableforthetheoretical

analysis.

A theoretical framework for controlling discrete event systems (DESs) was given by Ramege and

Wonham in the latter half of the 1970'sand their framework is called the sup ervisory controlscheme.

In thisframework, a DES iscontrolledby a controller, called a sup ervisor. A DES is described by an

automaton,andthesp ecicationforitisgivenasalanguageoverthesetofevents. Thenthecontrolling

istorestrictbehaviorofthesystemsothatitagreeswiththesp ecication. Forexample,wecanapplythe

supervisorycontrolschemetothemutualexclusionprobleminsuchamannerthatthesupervisorrestricts

statetransitionstoeverystateinwhichmorethanthegivennumberofresourcesaresharedbyprocesses.

Thesup ervisorycontrolschemeprop osedbyRamadgeandWonhamhaschangedthesituationofadhoc

design/analysis of DESs, and gives an approach similar to that by the control theory for continuous

systems. This frameworkis now a basis in the theoreticalstudy of DESs. Inthis pap er, wefo cus on

thestabilityofDESs. Westudy eectivedenition ofstabilityof DESsbasedontheRamage-Wonham

scheme,andshowanalgorithmtocomputeacontrollerthatmakesthesystemstable. Thereareroughly

twokindsofideasonstabilityofDESs,oneisdenedonthesetoflegalstates,andtheotherisdenedon

thesetoflegaltrajectoryofevents. Thersttypeofstabilities,calledstatestabilities,wereproposedby

Copyright c

2000byKilseokRoh

by Kumar et al. Breveet al. proposed thefollowing conceptof stabilityand stabilizability forDESs:

thesystemis stableifit visitsone ofthelegalstatesafternitely manystatetransitionsfrom arbitrary

initialstateandstaysforeverinthesetoflegalstates;astabilizablesystemisone forwhichthereexists

asupervisorsothat thesup ervisedsystemis stable.

Ozveren et al. prop osed the following concept of stability for DESs: the system is stable if after

startingfrom anyarbitraryinitial stateit visitthelegal subsetof statesinnitelyoften; a systemthat

canbemadestableintheabovecontextbythesynthesisofanappropriatesup ervisoriscalledstabilizable.

Therequirementofthisstabilityisweakerthanthat byBraveet al.

ThesenotionofstabilityandstabilizabilityofDESshasbeenpresentedintermsofthelegalandillegal

statesofthesystem. Kumaretal. aredenedstabilityandstabilizabilityin termoftheb ehaviorofthe

systems. Theirdenitionisas follows: thesystemislanguage-stableifitsb ehavior eventuallycoincides

with thelegal b ehavior; ifa sup ervisor exists suchthat thesupervised system is language-stable,then

systemiscalledlanguage-stabilizable. Inrealapplications,weoftenneedtodealwithtimingconstraints,

suchas time delay anddeadline. For thispurpose,a DESmo del with timing constraints,called timed

discreteeventsystems(TDESs),isrecentlyprop osed. Thereareonlyafewresearchesonthestabilityof

TDESs. It hasnotsucientlybeendiscovered Yanget al. prop oseda denition ofstabilityforTDESs

as an extension of one by Brave et al. for DESs. This stabilityrequires the system to convergeto a

given set of legal states,but itdoesnottake timing informationinto consideration. Mo chiyama et al.

proposed a newconceptof stabilityfor TDESsbasedonthe Ozveren's stability. In this stability, they

requirethesystemtovisitagivensetoflegalstatefrequently. Moreover,degreeofstabilityismeasured

bythemaximumtimenecessaryforreturningtothesetoflegalstates. However,thedescriptionability

ofthisstabilityseemsstillinsucientbecausethestabilityisdenedonlyonthestates. Inthispaper,we

proposednewconceptofstabilityforDESsandTDESs. Intheproposedstability,werequirethesystem

to executeoneof thenexteventsofthelegal languagewithinnitely manytimes. Moreover,degreeof

stalibilityismeasuredbythemaximumtimenecessaryforexecutingthenexteventofthelegallanguage.

The pap er is organized as follows. Basic notation of DESs and TDESs is describ ed in Section 2.

Existingdenitionsofstabilitydenedintermsofstatesandlanguage,andthenewdenitionofstability

for DESs are shown in Section 3. Existing denitions of stabilitydened in terms of states, the new

denition of stability for TDESs, and an algorithm for checking the stability of TDESs are shown in

Section 4. Control policies that make the system stable are discussed and an example is shown for

illustrating the stabilizationin Section 5. Weshowan optimal controller guaranteeing a given degree

of stabilityin thesense of minimallyrestrictive. Finally in Section 6,a briefsummary of this paper is

provided.