Universitetet I linköping matematiska institutionen Matematisk statistik
Yüklə 92,04 Kb. Pdf görüntüsü
|
| UNIVERSITETET I LINKÖPING Matematiska institutionen Matematisk statistik John M. Noble TDDD36 Project: Queueing Simulation using micro-GPSS Simulation Consider a system where there is a control centre that allocates resources. For example, it could be an accident and emergency unit at a hospital. The control centre receives the information that a job has to be carried out, then it allocates the job to an agent. The agent reports back when the job has been completed. Then the job leaves the system and the agent may then be assigned to a dierent job. Dierent jobs will have dierent priority levels. Furthermore a job that starts with a low priority level may move to higher priority levels if it has been waiting a long time. Servers are not usually perfect and from time to time they break down. It is vital, therefore that a log is kept. Checkpointing occurs at regular intervals. A checkpoint takes a xed time to carry out and records the complete state of the system. Only the log of events between the last checkpoint and the breakdown time need to be read. The length of time required to read the log depends on the number of items in the log. Therefore, it is important to determine the optimal interval between checkpointing. If check- pointing is too frequent, then too much time is wasted checkpointing. If checkpointing is not frequent enough, then it takes a long time to read the log after breakdown. Once the log is read, the secondary server may be used until the primary server is repaired. While jobs are coming in and being allocated, the agents assigned to the jobs will be sending queries to the server (for example, is there su cient room at a particular hospital for somebody, or should they be taken elsewhere). It takes a certain time to respond to a query. The server has a certain capacity for receiving and answering queries. If it is dealing with too many queries, it puts them in storage and answers them in their due turn. If the storage is full, then the agent is told to try again later. The secondary server has a smaller capacity for storing queries than the primary server. The queries may have dierent priority levels. To prevent important queries from being turned away, the agents are therefore informed that they should not submit queries of low priority while the secondary server is in use. The system is as follows: 1
• There are n agents. • When an agent is on a job, the agent submits queries of priority class k according to a Poisson process with rate λ k (so that if there are m agents engaged, then the rate at which queries of class k arrive is mλ k ). • The primary server can deal with Q p queries simultaneously and has a storage capacity C p . The secondary server can deal with Q s queries simultaneously and has a storage capacity C s .
Jobs arrive at the centre according to a Poisson process with a certain rate. • The primary survives for an exponential time (with a certain parameter) before it breaks down. The time between checkpoints is a xed time T and checkpointing takes a time t. The time to read the log is proportional to the number of agents assigned to a job, plus the number of jobs on the waiting list, plus the number of queries in storage. There are two tasks: 1. Find (by simulation) the optimal checkpoint interval (time between checkpoints) that min- imises the total down time of the system (i.e. the amount of time spent checkpointing plus the amount of time spent reading the log). 2. Find (by simulation) which priority classes should be blocked when the secondary server is in operation to ensure that less than 1% of the rst priority class queries are turned away. Warm up Exercise The coe cient of variation of a random variable X is de ned as C X = Var(X)
E[X] 2 . This is usually the important feature in determining the properties in a queueing system. For this exercise, consider a single server problem, with no restriction on the carrying capacity, where the average time between arrivals is 5 units and the average service time is 4 units. By simulation, nd the average number in the queue for the following situations. 1. Interarrival times and service times are deterministic. 2. Interarrival times and service times are exponential. 3. Deterministic interarrival times, exponential service times. 4. Exponential interarrival times, deterministic service times. Now, with exponential service times, consider interarrival times that are uniformly distributed over some interval and sketch the average number in the system (on the y axis) against the coe cient of variation for the interarrival time (on the x axis). 2
Introductory Exercise Consider the system without the agents sending queries. That is, jobs arrive according to a Poisson process, wait in the queue and are then distributed to the next available agent. The system keeps a record of the jobs that have arrived and when the job is completed. Checkpointing happens at regular intervals. The system breaks down, with lifetime exponentially distributed. When this happens, the log has to be read; the time taken to read the log is proportional to the number of pieces of information the system has received (job arrived / job completed) since the last checkpoint. Construct a simlation that can be used to determine the optimal time between checkpoints. 3
Introduction to GPSS These are very brief introductory notes to GPSS. They are based on the programme micro-GPSS, by Ingolf Ståhl. The programme used will be WebGPSS. This may be used in two ways; either graphically by constructing a block diagram, which generates code or, simply by writing the code. These notes consider the code. The GPSS queueing simulation system is structured in blocks. GENERATE The command GENERATE A,B generates random numbers distributed uniformly between A-B and A+B. TERMINATE The TERMINATE block removes transactions from the system. It nishes when the default value of 0 is reached, or when the speci ed value is reached. The following three lines result in the stopping of the system of arrivals at a turnstyle, with interarrival times uniformly distributed between 12 and 24 minutes after 50 customers. generate 18,6 terminate 1 start 50 Try the following programme and see what happens. % simulate
generate 18,6 terminate 1 start 50 end
The % at the beginning puts the results into a results le with the su x '.RES'. In the output, the current count refers to the number of transactions still inside the block at the end of the simulation. The total count is the number of transactions that have entered the block during the simulation. The following modi cation to the programme above will stop the simulation after 8 hours, or 480 minutes, rather than after 50 customers. 4
% simulate
generate 18,6 terminate generate 480 terminate 1 start 1 end
ADVANCE The ADVANCE block allows the transactions to remain within the system for some time, possibly for busy random periods. ADVANCE A,B samples times between A-B and A+B, all times being equally likely. The following modi cation of the above programme keeps visitors at the turnstyle for a uniformly distributed time lying between 20 and 30 minutes. % simulate generate 18,6 advance 25,5 terminate generate 480 terminate 1 start 1
end SEIZE and RELEASE In order for a transaction to use a facility (for example a salesperson), it uses a SEIZE block. If the facility is busy, the SEIZE command is refused and the transaction is put in a queue, dealt with in a rst come rst served basis. For the facility to become idle again, the RELEASE command must be used. In the example below, 'SAL' represents the salesperson. A facility's name must start with at least three letters. % simulate generate 18,6 seize sal advance 25,5 release sal 5
terminate generate 480 terminate 1 start 1
end ARRIVE and DEPART The ARRIVE block must be accompanied by a DEPART block. The dierence between ARRIVE and SEIZE is that the ARRIVE block cannot refuse a transaction entry. Consider the following programme, where TIM is used as a counter to mark the time of the arrival. % simulate generate 18,6 arrive tim seize sal advance 25,5 release sal depart tim terminate generate 480 terminate 1 start 1
end Run this and see what happens. QTABLE: More detailed statistics Using `WebGPSS', one simply clicks on the box `queue statistics' after one has highlighted the `seize' icon and accessed the options menu. The form of the command is QTABLE A,B,C,D and can be illustrated as follows: QTABLE SAL,0,10,5 It divides the times that customers must wait in front of the facility SAL into 5 classes, of length 10, starting at 0. 1. < 0 2. 0.01 - 10 6 3. 10.01 - 20 4. 20.01 - 30 5. > 30.01 Run the programme % simulate
qtable sal, 0, 10,5 generate 18,6 seize sal,q advance 25,5 release sal terminate generate 480 terminate 1 start 1 end
and see what happens. The rst line of the QTABLE statistics gives the number who have nished waiting and have gone into service. Then the average waiting time, the standard deviation of the waiting time and the sum of arguments, the total amount of time spent by all the nished transactions. The statement Q causes statistics to be gathered and printed. Try the programme % simulate qtable tim, 0, 10, 20 generate 18,6 arrive tim seize sal advance 25,5 release sal depart tim terminate generate 480 terminate 1 start 1 end
and see what happens. 7
Systems with Dierent Customers and Several Servers Consider single server, with two groups of customers. Each customer group has its own segment, starting with a GENERATE block and nishing with a TERMINATE block. Consider the pro- gramme
% simulate
generate 120,30 seize sal,q advance 45,30 release sal terminate generate 360,120 seize sal advance 240,150 release sal terminate generate 50400 terminate 1 start 1 end
It models a shop serving customers of two dierent types. The shop is open for 14 hours, or 50400 seconds (the last block). One type of customers buys newspapers, who need very little time (uniform, lying between 15 and 75 seconds) for service and the other type buys food, who need uniform, between 90 and 390 seconds. The newspaper buyers arrive more frequently (uniform, between 90 and 150 seconds) than the food customers (uniform, between (240 and 480 seconds). These three segments can be put in any order. In order to obtain statistics of how long the two groups of customers have to wait, one programmes as follows: % simulate
generate 120,30 arrive newsq seize sal,q advance 45,30 release sal 8
depart newsq terminate generate 360,120 arrive foodq seize sal depart foodq advance 240,150 release sal terminate generate 50400 terminate 1 start 1
end Run the programme and see what happens. Several facilities working in series Consider a single type of customer and two facilities; service and payment. This could be modelled by the programme simulate
generate 18,6 seize sal advance 25,5 release sal seize cash advance 4,2 release cash terminate generate 480 terminate 1 start 1 end
Suppose we have two types of product, type A and type B. Type A is produced at exact intervals of 25 minutes, starting at time 1. Product B is produced at 50 minute intervals, starting at time 1. The command (for type B) is GENERATE 50,0,1 which may be written as GENERATE 501 since 0 is the default value. For nishing, these products require two operations, the lathe, then the grinder and the time spent on each is random. This is modelled by the following programme. 9
simulate * type A
generate 25,,1 seize lat advance 20,5 release lat seize gri advance 20,5 release gri terminate *type B generate 50,,1 seize lat advance 10,3 release lat seize gri advance 30,10 release gri terminate *stop segment generate 500 terminate 1 start 1 end
Parallel Servers with a Common Waiting Line Consider a store with two sales people. The CAPACITY command enables this to be set up. Look on the menu to nd this option for WebGPSS. The ENTER block allows a transaction to obtain service from capacity. For any ENTER block, there must be a corresponding LEAVE block. The following programme illustrates: simulate
stor capacity 2 generate 18,6 enter stor,q advance 25,5 leave stor terminate 10
* generate 480 terminate 1 start 1
end The GOTO block The unconditional GOTO is illustrated as follows: Once a worker has nished using the oven, he goes back to the rst ADVANCE block. This indicates making a pot. The GOTO brings the worker back to make another pot. This is illustrated by the following programme: simulate
generate ,,,4 begin
advance 30,5 seize oven advance 8,2 release oven goto begin generate 600 terminate 1 start 1
end The total count for the RELEASE block indicates the number of times the worker has taken a pot out of the oven. The conditional GOTO statement is illustrated as follows: The problem concerns quality control of TV sets produced at a factory. The sets arrive at a random time between 35 and 75 minutes apart. They are inspected by one of two inspectors, which takes between 60 and 120 minutes. Fifteen percent of sets are defective and have to be repaired by an adjustor. The set goes back for reinspection. How long are sets delayed waiting for inspection and readjustment? simulate test
capacity 2 generate 55,20 begin enter
test, q advance 90,30 leave test
goto fix, 0.15 11
terminate fix
seize fixer,q
advance 300,100 release fixer goto begin generate 4800 terminate 1 start 1
end The IF Block Consider a dentist, where the waiting room has 4 places and customers will leave immediately if all four chairs are occupied. The following programme illustrates. simulate generate
if q$sal = 4, bye seize sal,q advance 25,5 release sal terminate bye terminate generate 480 terminate 1 start 1 end
The syntax is =, <>, >, <, >=, <= with obvious meanings. Example Suppose a customer arrives at a store and decides to choose the shortest line. The following does the job. simulate
generate 8,5 if q$lin1>q$lin2, serv2 arrive lin1
seize sal1
advance 18,10 release sal1 12
depart lin1 terminate serv2 arrive
lin2 seize
sal2 advance 18,10 release lin2 depart lin2 terminate generate 480 terminate 1 start 1
end Example Assume that if the salesperson is busy then an arriving customer does not want to wait, but leaves immediately. The IF block is used as follows: simulate
generate 10,6 if sal=u, bye seize sal,q advance 25,5 release sal terminate bye terminate generate 480 terminate 1 start 1 end
The terminology is U the facility is in use NU the facility is not in use E the facility is empty NE the facility is not empty F the facility is full NF the facility is not full The WAITIF Block The WAITIF block is illustrated by the following programme 13
simulate qtable sal,0,10,20 stor capacity
generate 18,6 waitif lock=u enter stor seize sal, q advance 25,5 release sal leave stor terminate generate 480 seize lock waitif stor=ne terminate 1 start 1 end
The following example simulates tra c in a street. It contains four segments: a street lights segment, two street segments and a stop segment. First, it turns on the red light for street 1 and it stays red for 50 seconds. After this, it turns of the red light for street 1 and on for street 2, which is a busier street. Here it is only red for 30 seconds. After this, it goes back to red for street 1. Cars arrive in street 1 between 13 and 27 seconds apart, on street 2 it is between 8 and 16 seconds. A car rst arrives at DIR1, used for measuring the total time spent by cars on street 1 at the crossing. Next, the car waits if the red light for street 1 is in use, otherwise it proceeds to the next block, driving at normal speed, taking 10 ± 3 seconds. It leaves by means of the depart block. The cars that wait are separated from the cars that do not wait by means of WAIT1. If it goes through this, then it takes 30 ± 15 seconds to advance. It then goes through the depart and teminate blocks. For the syntax for generate, see the section on priority. simulate *LIGHT SEGMENT generate ,,,1 begin seize red1 advance 50 release red1 seize red2 advance 30 14
release red 2 goto begin *STREET 1 SEGMENT generate 20,7 arrive dir1 if red1=u, wait1 advance 10,3 goto join1 wait1 waitif red1=u
advance 30,15 join1 depart dir1 terminate *STREET 2 SEGMENT generate 12,4 arrive dir2 if red2=u, wait2 advance 10,3 goto join2 wait2 waitif red2=u advance 30,15 join2 depart dir2 terminate *STOP SEGMENT generate 144000 terminate 1 start 1 end
Priority and Interruption Service Consider the store selling both newspapers and food. If the newspaper buyers get priority over the food buyers, the GENERATE block for the newspaper buyer segment should read GENERATE 120, 30,1 The syntax is GENERATE A,B,C,D,E where A is the average time, B is the spread (A ± B), C is the time of the rst transaction, D is the maximum number to be treated before the simulation stops and E is the priority. The following programme models an attraction at an amusement park. Half of the children having taken the ride want to take it again. A new arrival is given higher priority than one who 15
has already taken the ride. simulate
ride capacity 8 generate 10,2,,,1 begin enter ride advance 50 leave ride priority 0 goto begin, 0.5 terminate generate terminate 1 start 1 end
Now consider the shop selling food and newspapers, where newspaper buyers are permitted to preempt the food buyers. That is, if a food buyer is being served, a newspaper buyer may push him aside and receive service. The following programme illustrates the PREEMPT block. simulate
*NEWSPAPER BUYERS generate 120,30,,,1 arrive newsq arrive totq preempt sal depart newsq depart totq advance 45,30 return sal terminate *FOOD BUYERS generate 360, 120 arrive foodq arrive totq seize sal depart foodq depart totq advance 240, 150 16
release sal terminate *STOP SEGMENT generate 50400 terminate 1 start 1
end Functions An example of a function is TIME FUNCTION RN2, D4 .15,2 / .35,5 / .75,8 / 8/1, 12 The syntax is as follows: TIME is the name of the function, RN2 means random number generator 2, which produces a random number. Dierent generators produce independent random numbers. D means discrete (other possibility is C) and 4 is the number of arguments. If C is used, then a linear interpolation is made. Consider the following example: Customers arrive at the bank and either deposit money or withdraw money, with c.d.f.'s given by the functions INN and OUT described in the programme below. The CASH from deposits is assigned to the bank the moment the customer leaves, after the RELEASE block. The bank starts with a certain amount of money in the morning, delivered by armoured truck. Is this amount su cient to prevent the bank from running out of money during the day? The CASH is in CAPACITY. Since no capacity is allowed to have negative contents, a negative value will lead to the simulation being stopped early and a complete printout being given. simulate 10 cash capacity inn function rn3, c7 0,50/.1, 100/.3, 300/.6, 500/.8, 1000/.9, 4000/1,10000 out function rn4, c8 0,100/.2, 300/.5, 600/.8, 1000/.9, 5000/.97, 10000/.99, 20000/1, 40000 *CUSTOMER SEGMENT generate 8,3 seize sal advance 5,4 release sal goto outbl,.7 17
enter cash, fn$inn terminate outbl leave cash, fn$out terminate *MORNING SEGMENT generate ,,,1 enter cash, 80000 terminate *STOP SEGMENT generate 400 terminate 1 start 1 end
Built in Standard Functions The function FN$XPDIST gives the exponential distribution. generate 18*fn$xpdis gives an exponential random variable with average 18. The command generate 18*fn$xpdis(3) uses an independent generator, labelled 3. 18 Yüklə 92,04 Kb. Dostları ilə paylaş:
|