Queue reduction in discrete-event systems by relabeling

Yongmei GAN ,Ting JIAO ,W.M.WONHAM

1.School of Electrical Engineering,Xi’an Jiaotong University,Xi’an Shaanxi 710049,China；

2.Department of Automation,Shanxi University,Taiyuan Shanxi 030006,China；

3.Department of Electrical and Computer Engineering,University of Toronto,Toronto,ON M5S 3G4,Canada

Abstract The customer population of entities potentially requesting to join a queue for service often have identical structure,i.e.,the same state set and isomorphic transitions.The state size of the automaton modeling a queue will grow rapidly with increase of the size of this population.However,by relabeling the queue arrival events and service events to the same symbols respectively,the automaton model of a queue will be converted to the structure of a buffer,which is proved to be independent of the total size of the customer population,as long as the queue size is held fixed.We propose the model of a dynamic buffer to embody order and shift of a queue.The result is applied to a manufacturing facility with a dynamic buffer to manage the repair of broken down machines.

Keywords:Queue,relabeling,identical structures,invariance property,discrete-event systems

1 Introduction

Queueing theory is an important branch of computer science,encompassing methods for processing data structures and interactions between strict first in,first out(FIFO)queues.FIFO is a method for manipulating a data buffer,where the first entry of the queue is processed first.Apart from the FIFO policy,queueing theory also deals with scheduling disciplines such as priority and processing speed.Thus,various queueing models and simulation methods are proposed[1].

Reference[2]devises a method for changing the network of queues to speed up the simulation of rare events;reference[3]uses gradient estimation via smoothed perturbation to analyze the multi-class singleserver priority queue;reference[4]efficiently maps a priority queue on the hypercube architecture in a load balanced manner to achieve an optimal speed-up;reference[5]compares the performance of the FDDI token ring with the IEEE 802.6 DQDB protocols using discrete event simulation models;reference[6]constructs an analytical model based on stochastic Petrinet formalism to investigate GPRS uplink performance;reference[7]presents an approach based on queueing theory and stochastic simulation to help manage the project staffing,in order to prioritize activities and avoid conflicts;reference[8]uses queueing model and discrete event simulation to optimize staff issues at a bank;reference[9]adopts the game theory models to determine the appropriate moment to stop the stochastic queue system in order to correct its parameter;reference[10]presents an analytical approach to study the performance and availability of queueing systems with a finite queue and two service phases;and reference[11]shows that bounded fairness can be implemented by using first-input-first-output(FIFO)queues.

In summary,by employing discrete event simulation methods,references[2]to[10]aim at improving the performance of priority queue networks,including the efficient estimation of parameters in stochastic discrete event system and optimization of the processing speed;[11]uses automata to model FIFO queues to achieve bounded fairness.However,these methods ignore the identical structure of potential customers(components potentially requesting to join the queue).In this paper,we exploit the feature of identical structure to achieve queue reduction,thereby reducing controller complexity.

In our previous work[12–14],we used event relabeling to reduce system state size and controller complexity in discrete-event systems(DES)consisting of parallel arrays of machines and buffers[15,16].By relabeling the machines in a given group to a standard prototype machine,we obtained a small“template”supervisor which was proved to be independent of the total number of original components(machines),as long as the buffer sizes are held fixed.In this paper,we relabel the arrival events and service events as the same symbols respectively.Then we show that the automaton model of a queue is relabeled to an automaton model of a buffer.Therefore,the main contributions of this paper are as follows.

?We use a relabeling technique to reduce the automaton model of a queue to that of a buffer.The complexity of a queue is irrelevant to the customer population and we prove this phenomenon with a DES framework.

?We propose the model of a dynamic buffer to embody order and shift of a queue and apply the result to manage the repair of broken down machines.

The rest of this paper is organized as follows.Section 2 provides background definitions.Section 3 formalizes the process of queue reduction by relabeling and proposes the model of a dynamic buffer.Section 4 applies the dynamic buffer to a manufacturing facility to manage the repair of components.Section 5 presents our conclusions.

2 Preliminaries

2.1 Supervisory control theory

Supervisory control theory(SCT)deals with the control of discrete-event systems(DES)[17,18].The formal structure of a DES to be controlled is a generator,say

Here Σ=Σc˙∪Σuis a finite alphabet of symbols,the controllable and uncontrollable event labels,Q is the state set,δ∶Q×Σ→Q is the(partial)transition function,q0is the initial state,and Qm?Q is the subset of marked states.The transition function δ can be extended to

by induction on length of strings.The closed behavior of G is the language

in which the notation δ(q0,s)！means that δ(q0,s)is defined.The marked behavior is

Let E be a specification language and

the class of controllable languages[17,Section 3.4]contained in specification E.C(E)has the supremal1i.e.,largest,in the sense of sublanguage inclusion.element

By applying supervisor reduction[19],one can often obtain a simplified control-equivalent supervisor[17].

2.2 Relabeling

Relabeling maps events fulfilling the same task to new event symbols.Let R ∶Σ＊→ T＊be a relabeling map[14],satisfying the following conditions:

where Σ=Σc˙∪Σu.Tcand Tuare the relabeled counterparts of Σcand Σu,respectively.

A schematic of R is shown in Fig.1.

Fig.1 Schematic of relabeling function.

Let

The result of rep(·)is a generator representing the corresponding language.

In TCT[20],procedure RG=relabel(G)is employed to implement R such that

What relabel(·)does is first directly relabel all transitions of G and then convert the result(a possibly nondeterministic automaton)to its deterministic counterpart by the subset construction algorithm(SCA)[21].

The time complexity of the relabel(·)algorithm is the same as the SCA,i.e.,O(2n)in the worst case,where n denotes the state size of G.

However,thanks to the symmetry of identical components,all events fulfilling the same task are relabeled to the same symbol.Thus,the result of this algorithm often has(many)fewer states than the original automaton.For the manufacturing facility shown in Fig.2,let events 1i1,1i2 be relabeled as 11,12 respectively.Let

where “||”denotes synchronous product[17].

The state numbers of MIN and RMIN are 2mand m+1 respectively[14].

Fig.2 Schematic of manufacturing facility in Section 5.1.

3 Queue reduction by relabeling

In this section,we first show that a queue can be relabeled to a buffer if we treat all the arrival events and service events as the same symbols respectively.We then propose the model of a dynamic buffer and apply it to the system shown in Fig.2 after adjoining to each component the features of breakdown and repair.

3.1 Proof that a queue is relabeled to a buffer

In this paper,we call the set of potential customers the customer population.Let Q(2,k)represent an automaton for a queue with capacity of 2,in which k≥2 represents the size of this population.For any i∈{1,...,k},ri,si represent the arrival event and service event of component i respectively.Relabel events ri and si as r and s,respectively.Denote RQ(2,k)as the direct transition relabeling of Q(2,k).We use the SCA to convert the nondeterministic RQ(2,k)to the equivalent deterministic automaton DRQ(2,k).

For example,let the queue size be 2.The automaton Q(2,2)shown in Fig.3 models the queue with a customer population of size 2.At the initial state,both events r1and r2are eligible to occur.After the occurrence of string r1.r2,only event s1is eligible to occur as event r1is the first arrival event.It is a similar case for the occurrence of string r2.r1.After directly relabeling events ri,si,i∈{1,2}to r,s respectively,we obtain the nondeterministic automaton RQ(2,2)asshown in Fig.3.By applying the SCA to RQ(2,2),its deterministic counterpart DRQ(2,2)is obtained.We rename DRQ(2,2)as BUF(2)(shown in Fig.3)because DRQ(2,2)can be interpreted as an automaton modeling the behavior of a buffer with 2 slots.The main difference between a queue and a buffer is that a queue preserves both the identity and order of arriving customers,but a buffer provides only their storage.

To show that DRQ(2,k)equals to BUF(2)for any k≥2,we need to introduce the definition of isomorphic automata.

Let

Automaton GBis an epimorphic image[19]of automaton GAunder epimorphism θ ∶QA→ QBif

If θ ∶QA→ QBis bijective,then GBis isomorphic to GA[19].Two isomorphic automata are identical up to renumbering of states(but with initial state held fixed at 0).In the software package TCT[20]2While the approach and results of this paper do not depend on any specific software package,it is convenient to use the notation of TCT for brevity.,if procedure Isomorph(GA,GB)returns “true”,then GBis isomorphic to GA;otherwise,they are not isomorphic.

Theorem 1For any k≥2,DRQ(2,k)is isomorphic to BUF(2).

ProofThe proof is by induction.

Basis:k=2.Q(2,2),RQ(2,2)and BUF(2)are shown in Fig.3.By applying the SCA to RQ(2,2),we obtain the transition table of DRQ(2,2),as shown in Table 1.

The result is isomorphic to BUF(2)with the state correspondences[{0},0],[{1,2},1],[{3,4},2].

Inductive step:In the transition graph for Q(2,k)and Q(2,k+1)shown in Fig.4,the service events are omitted for clarity of display.Assume that the SCA result for RQ(2,k),i.e.,DRQ(2,k),has the state transition table shown in Table 2,in which

Fig.3 Process of relabeling queue to buffer with capacity 2.

Table 1 Transition table of DRQ(2,2).

Fig.4 Transition graph of Q(2,k)and Q(2,k+1).

Hence,

Table 2 Transition table of DRQ(2,k).

We need to show that the SCA result for RQ(2,k+1),i.e.,DRQ(2,k+1),has the state transition table shown in Table 3,in which

Table 3 Transition table of DRQ(2,k+1).

With one more machine added,we need to add 2k+1 states and 4k+2 transitions into Q(2,k)to obtain Q(2,k+1).The newly added states are shown in shaded circles;the details of newly added transitions are as follows(using δ to denote the transition function in Q(2,k+1)):

where 1 ≤ i≤ k,rk′,sk′are the arrival event and service event of the newly added component k′.

Relabeling the newly added transitions we have for 1≤i≤k,

where δ′denotes the transition function of RQ(2,k+1).

Denote the transition functions in DRQ(2,k)and DRQ(2,k+1)by δdand δ′drespectively.By the inductive assumption,we have

which coincides with the transitions shown in Table 3.□

At the initial state of Q(2,k),the occurrence of event ri,i∈{1,...,k}will cause entrance to state i.Each of these states will be followed by one of k?1 states when one of the other k?1 components joins the queue.Thus,Q(2,k)has 1+k+k(k?1)=1+k2states,while BUF(2)has only 3 states with the queue size fixed at 2.The contrast between the state size of Q(2,k)and BUF(2)becomes more obvious with the increase of k.

Let Q(l,k)denote the automaton model for a queue with size l≥1,where k≥l is the size of the customer population.The relabeling result of Q(l,k)is denoted as DRQ(l,k).Let BUF(l)shown in Fig.5 denote the automaton model for a buffer with size l.We have a direct generalization of Theorem 3.1 as follows.

Corollary 1 For any k≥l≥1,DRQ(l,k)is isomorphic to BUF(l).

By the same reasoning as applied to Q(2,k),we have that the state size of Q(l,k)is

If k＜l,then the queue model can be represented by Q(k,k)as the size of the customer population is less than the queue size.Correspondingly,only states 0 to k will be reached in BUF(l).

Fig.5 Transition graph of BUF(l).

3.2 Dynamic buffer

By Theorem 1,we know that the automaton model of a queue can be relabeled to an automaton model of a buffer.In this subsection,we propose a dynamic buffer DB with size l as shown in Fig.6 to embody order and shift,in which “?1”denotes event symbols to be instantiated dynamically when new components join the queue.

In DB,for any event σ,write σ as σ(q1,q2),to represent σ exiting q1and entering q2.Let G=(Q,Σ,δ,q0,Qm)and assume that G has just executed string s∈L(G).We call state qc∈Q reached by s the currently activated state,i.e.,qc=δ(q0,s).

Fig.6 Initial structure of dynamic buffer.

With the occurrences of the arrival events and service events,events of DB will be instantiated accordingly by the Enqueue and Dequeue algorithms as displayed in Fig.7.

Fig.7 Examples of enqueueing and dequeueing.

Assume that the currently activated state is marked as a black circle.Let event r′be the new arrival event(its corresponding service event is s′)and instantiate event σ(2,3)as r′.As the first arrival event is r1,re-instantiate σ(3,2),σ(2,1)as s1,s2respectively to ensure that event s1is the first service event to be executed.As event r′is the last arrival event,it will be serviced after both s1,s2have been executed.Thus,σ(1,0)is re-instantiated as s′.The Dequeue algorithm is a reverse process.As r1is the first arrival event,the first event to be executed is its corresponding service event s1.With event s1being executed,σ(3,2),σ(2,3)are re-instantiated as ?1 and σ(1,2),σ(0,1)as r′,r2,respectively.

As there exists only one for loop in the Enqueue and Dequeue algorithms respectively,the time complexities of both algorithms are O(n),where n is the state size of DB.

Hence,equipped with the Enqueue and Dequeue mechanisms,the dynamic buffer manages the order of service events.Although the state size of the automaton modeling a queue will grow sharply with increase of the size of the customer population,its relabeled version will remain invariant and behave as a buffer if the queue size is fixed.

Algorithm(Enqueue(r′,s′))

Input:Events r′,s′represent the arrival event and service event of the new component.

Output:Updated DB.

1 ∶σ(qc,qc+1)=r′

2∶If qc＞ 0,then

3∶For i=qc+1 to 2

4∶ σ(i,i?1)= σ(i?1,i?2)

5∶End For

6∶End If

7∶qc=qc+1

8 ∶σ(1,0)=s′

Algorithm(Dequeue())

Output:Updated DB.

1∶For i=1 to qc?1

2∶ σ(i?1,i)= σ(i,i+1)

3∶End For

4∶σ(qc?1,qc)= ?1

5∶σ(qc,qc?1)= ?1

6∶qc=qc?1

4 Application of the dynamic buffer

Next,we show that the concurrent operation of relabeling and dynamic buffer reduces controller complexity.Let the components shown in Fig.2 incorporate the actions of breakdown(arrival event)and repair(service event).The updated components MINiand MOUTjare shown in Fig.8,where the physical meaning of events is listed in Table 4.The specifications are as follows:

1)Avoid underflow and overflow of BUF.

2)Repair the broken down machines in the order of breakdown.

Fig.8 Machines with breakdown and repair.

Let events 1i1,1i2,1i3,1i4,1i5,2 j1,2 j2,2 j3,2 j4,2 j5 be relabeled as11,12,13,14,15,21,22,23,24,25 respectively.Let the size of BUF be 2.

Table 4 Physical meaning of events in components shown in Fig.8.

By TCT computation,we have

MACH(m,n)=sync3DES=sync(DES1,DES2,...,DES k)is the(reachable)synchronous product of DES1,DES2,...,DES k[17].(MIN1,...,MIN m,MOUT1,...,MOUT n),

RMACH(m,n)=relabel(MACH(m,n)),

RBUF=relabel(BUF),

SUP(m,n)=supcon4DES3=supcon(DES1,DES2)is a generator for the supremal controllable sublanguage of the specification generated by DES2 w.r.t.the plant DES1[17].(MACH(m,n),BUF),

XRSUP(m,n)=supcon(RMACH(m,n),RBUF),

XRSUP(m,n).dat=condat5DAT2=condat(DES1,DES2)returns control data DAT2 for the supervisor DES2 of the controlled system DES1[17].(RMACH(m,n),XRSUP(m,n)),

XRSIM(m,n)=supreduce6DES3=supreduce(DES1,DES2,DAT2)is a reduced control-equivalent counterpart of DES2[17].(RMACH(m,n),XRSUP(m,n),XRSUP(m,n).dat).

In[12],we showed that for arbitrary m and n,the reduced supervisor XRSIM(m,n)shown in Fig.9 remains unchanged(i.e.,invariant).For the specification to avoid overflow of the buffer,events 1i1 are enabled if the number of workpieces in the buffer plus the number of working input machines MINiis less than the buffer size.This condition is independent of the number of components,as long as the buffer size is held fixed;thus,the invariance property of the reduced supervisor holds.From Fig.9 we see that the occurrence of events 1i3,1i5,2 j3,2 j5 is irrelevant to the specification to avoid the overflow of the buffer.Every time a machine breaks down,the currently activated state xijin XRSIM(m,n)will be updated to xi,j?1,0 ≤ i＜ 2,0 ＜ j≤ 2 by the occurrence of event 14.Namely,the occurrence of a breakdown event 1i4 will erase one 11 from the evolution history of XRSIM(m,n).

Fig.9 Reduced supervisor XRSIM(m,n).(Events 13,15,22,23,24,25 are self looped at each state).

Next,we discuss the concurrent operation of the dynamic buffer and the reduced relabeled-level supervisor XRSIM(m,n).Let the repair queue size be l=2.If qc=l,since no additional slot is available for a requested broken down machine,qcremains constant until a slot becomes available.If machine MINior MOUTjbreaks down,the dynamic buffer will be updated by the Enqueue(1i5,1i3)or Enqueue(2 j5,2 j3)respectively.If machine MINior MOUTjis repaired,the dynamic buffer will be updated by the Dequeue algorithm.

The concurrent operation of the repair queue and XRSIM(m,n)reduces complexity in two aspects:

1)The automaton model for the repair queue updates with the details of the customer population.Without the dynamic buffer model,we need to update the repair queue model frequently.Moreover,the state size of the repair queue increases with the size of the customer population,while the state size of the dynamic buffer only depends on the queue capacity.

2)The state size of the monolithic supervisor is not only dependent on the size of the customer population,but is also larger than the state size of the dynamic buffer and XRSIM(m,n).

For example,let m=2,n=1.The transition table for repair queue Q(2,3)is shown in Table 5,where symbol“×”denotes that a transition is not defined and state 0 is both the initial and marked state.

Table 5 Transition table of Q(2,3).

By TCT computation,we have

SPEC=sync(BUF,Q(2,3)),

SUP=supcon(MACH(2,1),SPEC)(162,481),

SUP.dat=condat(MACH(2,1),SUP),

SIM=supreduce(MACH(2,1),SUP,SUP.dat)(19,162).

For a customer population of size 3,the monolithic supervisor SUP has 162 states;its reduced control equivalent counterpart SIM still has 19 states.However,the dynamic buffer and XRSIM(m,n)have only 3 and 6 states respectively(independent of the values of m and n).The contrast of state sizes between them will become more obvious with increase of the size of the customer population.

5 Conclusions

We have shown that the automaton model of a queue can be reduced to the structure of a buffer,which is independent of the individuals of the customer population,as long as the queue size is fixed.To incorporate the features of order and shift into the buffer structure,we propose the model of a dynamic buffer with Enqueue and Dequeue mechanisms.Then we apply dynamic buffer to a DES with broken down components.The computation results show that the concurrent operation of dynamic buffer and reduced supervisors reduces the controller complexity.