Markov-proces, efter Andrei A. Markov (1856-1922), er i sandsynlighedsregning en stokastisk proces, fx en følge (X1,X2,...) af tilfældige tal, med den egenskab, at kendskabet til Xt for t ≤ t0 kun påvirker den fremtidige tilfældige udvikling gennem den seneste kendte værdi, Xt0.
Eksempler på Markov-processer omfatter Markov-kæder (hvor hvert Xt typisk er et tilfældigt, helt tal), processer med uafhængige tilvækster, herunder nogle af de vigtigste Markov-processer, fx random walks, Poisson-processen og Wienerprocessen, samt diffusionsprocesser, som er kontinuerte, med Wienerprocessen som hovedeksempel.
Markov-processer anvendes til opstilling af modeller for data, der beskriver tilfældige fænomener fulgt gennem et tidsforløb: befolkningsudviklinger, økonomiske forløb som aktiekurser, overlevelsesanalyser inden for sundhedsvidenskab, udvikling af epidemier m.m. Teorien for Markov-processer er et væsentligt redskab i forsikringsmatematik og køteori. Den moderne teori er tæt knyttet til teorien for martingaler og stokastiske differentialligninger og udnytter matematiske metoder fra især funktionalanalyse.
Teorien blev grundlagt af Markov, der 1906-07 offentliggjorde to artikler med eksempler på Markov-kæder. Grundlaget for den moderne teori (1930-40) skyldes især A. Kolmogorov og den amerikanske matematiker W. Feller (1906-70).
En Markov-kæde er en stokastisk proces hvis fjerne fortid er irrelevant, eftersom det næste der sker kun afhænger af hvad der er sket for nylig. I den simpleste Markov-kæde afhænger enhver begivenhed kun af den foregående. Når vi tænker i diskret tid (dvs. ikke-kontinuert, men trinvis tid), kan vi beskrive det således: Processen består af en serie stokastiske variabler; X1, X2, X3 …. Værdien af Xn er så processens tilstand til tiden n. Når sandsynlighedsdistributionen af Xn+1kun afhænger af Xn og ikke påvirkes af tidligere variabler, har vi en kæde med Markov-egenskaben:
P(Xn + 1 │ X0, X1, X2, X3 ... Xn) = P(Xn + 1│Xn)
Sagt med jævne ord, har vi altså at gøre med en trinvis proces hvor sandsynligheden for hvad der sker på et givet trin, kun afhænger af hvad der skete på det umiddelbart foregående. I analogi hermed kan man tænke sig processer med længere »hukommelse« hvor f.eks. de tre umiddelbart foregående trin har indflydelse, etc.
Markov-processer indtager en interessant mellemstilling mellem helt tilfældige og helt bundne processer. Tænk f.eks. på en serie terningkast. Hvis der ikke er snyd med i spillet, bliver vi ikke spor bedre til at gætte det næste udfald af at kende de tidligere udfald. Det er en række uforbundne stokastiske variabler, processens historie er irrelevant. Tænk så på at finde frem til en adresse ved at følge en række instrukser (gå til det første lyskryds, drej til højre, gå ned ad den tredje sti, drej til venstre ...). Her spiller hele processens historie med i resultatet. Hvis du gik forkert et sted i processens begyndelse, hjælper det ikke hvor godt du end følger de senere instrukser. Markovkæder ligger midt mellem disse to poler, det historieløse og det historisk determinerede.
Eksponentialfordelingen
Eksponentialfordeling er en sandsynlighedsfordeling, som bruges i statistik og sandsynlighedsteori, bl.a. til at beskrive ventetiden T mellem begivenheder, der indtræffer til tilfældige tidspunkter, fx den tid der går, til et radioaktivt atom henfalder. Den er givet ved tæthedsfunktionen f(t) = λe−λt (t ≥ 0) med middelværdien 1/λ, variansen 1/λ2 og medianen 1/λ∙ln2.
Eksponentialfordelingen har ingen hukommelse; vides det, at T (fx henfaldstiden) er større end t0, følger restventetiden igen en eksponentialfordeling med middelværdien 1/λ.
Eksponentialfordeling er fundamental for teorien for Markov-processer og i køteori og bruges desuden ved opstilling af modeller til vurdering af driftssikkerhed af tekniske systemer. Se også fordelingsfunktion.
I sandsynlighedsregning og statistik er den eksponentielle fordeling (alias negative eksponentielle fordeling), en familie af kontinuerlig sandsynlighedsfordelinger. Den beskriversom sagt tiden mellem begivenhederne i en Poisson proces, en proces hvor hændelser forekommer kontinuerligt og altså uafhængigt af hinanden ved en konstant gennemsnitlig sats.
Bemærk, at den eksponentielle fordeling ikke er det samme som klassen af eksponentielle familier af fordelinger, som er en stor klasse af sandsynlighedsfordelinger, der omfatter den eksponentielle fordeling som et af sine medlemmer, men også omfatter normalfordelingen , binomialfordelingen , gamma fordeling , Poisson , Weibull og mange andre.
Ligefordelingen
Ligefordeling (eller rektangulær fordeling, uniform fordeling) er en sandsynlighedsfordeling, hvor alle udfald har lige stor sandsynlighed. Der findes diskret og kontinuert ligefordeling. For den diskrete ligefordeling kan udfald være enten en mængde (f.eks. {spar es, hjerter dame, klør 2}) eller heltallene inden for et eller flere intervaller (f.eks. 1,2,3,4,5,6). For den kontinuerte ligefordeling kan udfald være alle reelle tal i et eller flere intervaller (f.eks. de reelle tal i intervallet 0 til 10).
Et eksempel på en diskret ligefordelt stokastisk variabel er en ærlig 6 sidet terning, der har lige stor sandsynlighed for at lande på alle sider. Her er sandsynligheden for at lande på en side 1/6. Et andet eksempel er kulør og værdi for trækning af spillekort fra et spil kort, hvor det trukne kort lægges tilbage efter trækning og blandes med de andre kort.
Den diskrete ligefordeling kan være for heltal eller en mængde. Generelt er sandsynligheden for hvert udfald lig 1 divideret med antallet af mulige udfald. For en ikke numerisk mængde (som {spar es,hjerter dame, klør 2}) kan man ikke regne middelværdi og andre statiske mål.
Den kontinuerte ligefordeling bruges oftest for et enkelt interval [a;b], men kan bruges for et vilkårligt antal intervaller. Hvis andet ikke nævnes, antages det, at intervallet er [0;1]. Som med alle andre kontinuerte sandsynlighedsfordelinger er sandsynligheden for et specifikt udfald lig nul. Sandsynligheden for et delinterval er lig længden af intervallet divideret med den samlede længde af alle intervaller.Transformation til andre fordelinger. Den kontinuerte ligefordeling mellem 0 og 1 udgør i mange tilfælde basis inden for generering af pseudo-tilfældige tal på en computer. For at kunne lave tilfældige tal fra andre fordelinger, transformerer man tallene fra den kontinuerte ligefordeling.
Binomialfordelingen
Binomialfordelingen er en diskret fordeling inden for sandsynlighedsregning og beskriver en af de mest fundamentale og samtidig meget grundlæggende fordelinger. Meget kort fortalt beskriver den sandsynligheden for at få k succeser i n forsøg. Ordet diskret kommer af det latinske discretus, som direkte oversat betyder adskilt.
En diskret mængde er, jævnfør det latinske, inden for matematik en tællelig mængde, og repræsenterer dermed en diskontinuert mængde, som i en vis forstand kan siges at være det modsatte af kontinuert.
På denne måde betegner noget diskret som oftest noget med heltal. Et glimrende eksempel herpå kunne være en stokastisk variabel der beskriver antal øjne en terning viser. Denne variabel ville være diskret. Diskrete mængder benyttes i adskillige sammenhænge, her er blot et lille udvalg:
Diskret matematik
Kombinatorik
Logik
Sandsynlighedsregning
Statistik
Talteori
Eksempel:
Vi slår med en fair sekssidet terning 10 gange, men inden terningen bliver slået ønsker vi at bestemme sandsynligheden for at få 4 kast, som viser 5 eller 6 øjne.
Ud af denne tekst ved vi nu, at vi har n=10 uafhængige forsøg, hvor vi ønsker at bestemme sandsynligheden for, at x=4 af kastene opfylder succeskriteriet. Vi mangler blot p for at kunne bestemme denne sandsynlighed, men vi ved, at 5 og 6 udgør 2 ud af terningens 6 sider, hvormed p bliver lig 1/3.
Vi betrager n uafhængige forsøg, hvor n er konstant. I hvert enkelt forsøg kan udfaldet/hændelsen blive enten succes eller fiasko Sandsynligheden for succes er p (og er den samme for alle n forsøg)
Lad den stokastiske variabel X angive antal “succes’er” i n Bernoulli forsøg. Fordelingen af X kaldes en binomial fordeling med antalsparameter n og sandsynlighedsparameter p, hvor p = P(“succes”). Notation: X ~ bn(n,p)
Normalfordelingen
Normalfordelingen er en af de vigtigste sandsynlighedsfordelinger og benævnes også Gaussfordelingen. Den er kontinuert og kan principielt omfatte alle reelle tal. Den er symmetrisk og kan entydigt bestemmes ved observationssættets middelværdi og varians. Normalfordelingen bruges som en "model" af hvordan et stort antal statistiske elementer fordeler sig omkring deres gennemsnit. Hvis man for eksempel måler højden eller vægten af hver enkelt i en stor, ensartet gruppe af mennesker, vil de fleste ligge omkring et vist gennemsnit, mens meget store eller små personer er mere sjældne.
Poissonfordelingen
Poisson fordelingen anvendes ofte som en fordeling (model) for tælletal, hvor der ikke er nogen naturlig øvre grænse. Poisson fordelingen kan ofte karakteriseres som intensitet, dvs på formen antal/enhed Parameteren Lambda angiver intensiteten i poisson fordelingen. Lad den stokastiske variabel X angive antal hændelser i tidsintervallet t fra en Poisson proces, hvor gennemsnitlig # hændelser pr. tidsenhed er λ. Fordelingen af X kaldes en Poisson fordeling med parameter μ = λt.
Weibullfordelingen
Tæthedsfunktionen for en stokastisk variabel betegnes ved f(x) Ofte bruger man også betegnelsen frekvensfunktion eller hyppighed om tæthedsfunktionen f(x) siger noget om hyppigheden af udfaldet x for den stokastiske variabel X
Et godt plot af f(x) er et bar chart (diskret) eller et histogram (kontinuert)
Kort om deterministiske produktionssystemer
Antagelser: 1. Deterministiske ankomster (x enheder/time). 2. Deterministiske produktionstider. 3. Uendeligt mange køpladser per maskine. 4. Ligevægt – ingen ophobning af enheder i system - kan i så fald benytte fluid modeller:
• Produktionssystem som deterministisk ‘fluid model’ – Produkter ‘strømmer’ gennem system med fast hastighed. – Produktionslinier som ‘rør’, hvor ∗ Længden er et mål for produktionstiden ∗ Tykkelsen er et mål for maksimalt throughput.
Kort om stokastiske modeller for køsystemer
Køsystem: • Ankomstproces T1, T2, . . . (ankomsttid per kunde). • Kødisciplin (rækkefølge for ekspedition). Vi vil normalt antage FIFO (first-in-first-out) man også LIFO eller • Ekspeditionstidsproces S1, S2, . . . (ekspeditionstid per kunde).
Kønetværk: Flere køsystemer “sat sammen”. Eks. • Patienter på venteliste – opereration/reoperation. • Produktionssystem med kvalitetskontrol.
Ankomstprocesser
Bank. Kunder til pengeautomat. Hospital. Patienter på venteliste. Produktionssystem. Ordretilgang, råvaretilgang.
Vi skal se på ankomstprocesser, som er fornyelsesprocesser:
Tn = summaUi hvor Ui er uafhængige og identisk fordelte, n = 1, 2, . . .
Yderpunkter i denne klasse: • Fuldstændig tilfældige ankomster (Poissonproces). • Deterministiske ankomster
Ekspeditionstidsprocesser
Bank. Tid for transaktion. Hospital. Transport, narkose, operation, opvågning. Produktionssystem. Forarbejdningstid, transport, reparation/omstilling af maskiner, kvalitetskontrol, shipping.
Yderpunkter: • Eksponentialfordelingen (ingen hukommelse). • Deterministisk proces (konstant ekspeditionstid).
Markov-processer
Markov-proces, efter Andrei A. Markov (1856-1922), er i sandsynlighedsregning en stokastisk proces, fx en følge (X1,X2,...) af tilfældige tal, med den egenskab, at kendskabet til Xt for t ≤ t0 kun påvirker den fremtidige tilfældige udvikling gennem den seneste kendte værdi, Xt0.
Eksempler på Markov-processer omfatter Markov-kæder (hvor hvert Xt typisk er et tilfældigt, helt tal), processer med uafhængige tilvækster, herunder nogle af de vigtigste Markov-processer, fx random walks, Poisson-processen og Wienerprocessen, samt diffusionsprocesser, som er kontinuerte, med Wienerprocessen som hovedeksempel.
Markov-processer anvendes til opstilling af modeller for data, der beskriver tilfældige fænomener fulgt gennem et tidsforløb: befolkningsudviklinger, økonomiske forløb som aktiekurser, overlevelsesanalyser inden for sundhedsvidenskab, udvikling af epidemier m.m. Teorien for Markov-processer er et væsentligt redskab i forsikringsmatematik og køteori. Den moderne teori er tæt knyttet til teorien for martingaler og stokastiske differentialligninger og udnytter matematiske metoder fra især funktionalanalyse.
Teorien blev grundlagt af Markov, der 1906-07 offentliggjorde to artikler med eksempler på Markov-kæder. Grundlaget for den moderne teori (1930-40) skyldes især A. Kolmogorov og den amerikanske matematiker W. Feller (1906-70).
En Markov-kæde er en stokastisk proces hvis fjerne fortid er irrelevant, eftersom det næste der sker kun afhænger af hvad der er sket for nylig. I den simpleste Markov-kæde afhænger enhver begivenhed kun af den foregående. Når vi tænker i diskret tid (dvs. ikke- kontinuert, men trinvis tid), kan vi beskrive det således: Processen består af en serie stokastiske variabler; X1, X2, X3 …. Værdien af Xn er så processens tilstand til tiden n. Når sandsynlighedsdistributionen af Xn+1kun afhænger af Xn og ikke påvirkes af tidligere variabler, har vi en kæde med Markov-egenskaben:
P(Xn + 1 │ X0, X1, X2, X3 ... Xn) = P(Xn + 1│Xn)
Sagt med jævne ord, har vi altså at gøre med en trinvis proces hvor sandsynligheden for hvad der sker på et givet trin, kun afhænger af hvad der skete på det umiddelbart foregående. I analogi hermed kan man tænke sig processer med længere »hukommelse« hvor f.eks. de tre umiddelbart foregående trin har indflydelse, etc.
Markov-processer indtager en interessant mellemstilling mellem helt tilfældige og helt bundne processer. Tænk f.eks. på en serie terningkast. Hvis der ikke er snyd med i spillet, bliver vi ikke spor bedre til at gætte det næste udfald af at kende de tidligere udfald. Det er en række uforbundne stokastiske variabler, processens historie er irrelevant. Tænk så på at finde frem til en adresse ved at følge en række instrukser (gå til det første lyskryds, drej til højre, gå ned ad den tredje sti, drej til venstre ...). Her spiller hele processens historie med i resultatet. Hvis du gik forkert et sted i processens begyndelse, hjælper det ikke hvor godt du end følger de senere instrukser. Markovkæder ligger midt mellem disse to poler, det historieløse og det historisk determinerede.
Model-opbygning
Pba forskellige typer af stokastiske processer vurderes hvilken modelklasse, der kan være relevant for et givet dynamisk fænomen.
Simulering af realisationer af en given Markov- eller renewal-process
Klassificerering af en given Markov-proces og dens tilstande med hensyn til periodicitet og persistens.
Bestemmelse af stationære fordelinger i en Markov-process, og vurdere hvornår stationaritet er en rimelig approksimation.
Bestemmelse af den transiente dynamik af overgangssandsynlighederne i en Markov-process, og identificere karakteristiske tidsskalaer.
Opstille og løse ligninger for sandsynligheden for, eller den forventede tid til, absorption i en Markov-kæde.
Bestemme tidsdiskrete Markov-process der opstår ved forskellige typer sampling af en tidskontinuert process.
Genkende og analysere specielle typer af Markov-processer, såsom fødsels-dødsprocesser og køprocesser.
baseSim model af fremstillingsproces
Denne demo model beskriver en to-trins divergent fremstillingsproces, hvor 4 forskellige produkter er fremstillet til lager. Den første fase er fælles for alle varianter, og opsamles en fase 1-lagerbuffer. De efterfølgende processer er produktspecifikke og uafhængige af hinanden - alle er normalfordelte. Produktet venter i fase 1-bufferen, indtil en kunde efterspørgsel på dette produkt er modtaget.
Kundernes efterspørgsel er modelleret ved hjælp af en eventgenerator, der har et normalt fordelt tidsinterval mellem begivenhederne. En efterspørgsels-begivenhed forårsager bestilling af et antal af en bestemt færdigvare, der skal trækkes fra det respektive bufferlager. Dette vil til gengæld udløse en produktion og en genopfyldning med tilsvarende antal. Hvis en bestilling ikke kan opfyldes bliver dette faktum logget i en undtagelse tabel. Der er ingen back-logning af kundernes forespørgsel.
Nøglefunktioner
Den primære motivation bag modellen er at vise, hvordan en "realistisk" opgørelse system hurtigt kan modelleres, overvejende med prædefinerede komponent properties[variable]. Hvor yderligere modelspecifik logik er påkrævet, som her til at modellere kundeefterspørgsel at trække produktet fra buffere, kan dette tilføjes via brugerens handlinger tilføjet i i Object Pascal. Et eksempel på en sådan handling er vist nedenfor.
Eksemplet viser opbygningen af en hierarkisk model struktur.
Bruger definerede handlinger
Brugerdefinerede handlinger kan knyttes til mange model events. I det aktuelle eksempel bliver en bruger handling kaldt af en SimGenerator-komponent. Tidsintervallet mellem sådanne kald defineres ved værdien af interval-property for SimGenerator komponenten.
Når SimGenerator 'CustomerDemand(n)' udløser en event[begivenhed], en brugerdefineret handling 'StdGenerate_Int' kaldes passerer de parametre Sender (den kaldende generator) og SimTime (simulerings-tiden). Denne handling enten trækker et færdigt del fra den relevante buffer, eller hvis der er ingen tilgængelige dele i buffer, den logger dette faktum i tabellen 'DemandMissed'. En kommenteret liste af aktionen er vist nedenfor. Kommentarerne (i grønt) er blevet tilføjet her for klarhedens skyld:
Kørsel af modellen
For at køre den model skal dobbeltklikke på stopuret [EventController].
Denne komponent er ansvarlig for at foretsge synkronisering og udførelse af alle de begivenheder, der tilsammen repræsenterer dynamikken i systemet. For at starte modellen først trykke på 'Init' knappen. Denne initialiserer udgangsværdierne i modellen og udføre en kontrol af konsistens og fuldstændighed (for eksempel den sikrer, at hver eneste komponent på formularen er en forbindelse til EventController.
Tre kategorier af advarsel eksisterer. "Fatal" fejl viser alvorlige fejl eller uoverensstemmelser i den model, de skal udbedres inden simuleringen kan køre. "Advarsler" advare brugeren mod potentielle uoverensstemmelser eller ufuldstændige specifikation af model parametre; advarsler kan ignoreres. 'Gode råd' antyder til brugeren parametre, der ikke er blevet tildelt en værdi tip kan også blive ignoreret.
Dernæst skal du trykke på knappen 'Start'. Simuleringen skal nu starte, med enheder ses at flyde fra
'InfiniteRawMaterial' til venstre til »ModelDrain 'til højre. Listen over begivenheder, som EventController er behandlingen kan ses ved at trykke på "Liste"-knappen. Denne visning viser simuleringen tid, hvor den begivenhed er planlagt, Component påvirket, og dens placering. Den 'Step-knappen kan bruges til at fremme simuleringen af én begivenhed ad gangen (du skal stoppe simuleringen først).
Har ladet modellen køre i kort tid, tryk på 'Stop'.
Visning af statistik
I en opgørelse simulering brugeren er typisk interesseret i at etablere, om systemet er i stand til at opfylde kundernes efterspørgsel. Demonstrationen Modellen giver to forskellige statistikker, at løse dette problem.
Den første kan findes ved at dobbeltklikke på en af de 'CustomerDemand' generatorer og gå til fanen properties[Egenskaber]. Egenskaberne af særlig interesse er det samlede antal kundeefterspørgsel (numDemands) og den procentdel af dem, der blev opfyldt (pcfulfilled).
Den anden opgørelse bestemte statistiske oplysninger kan findes inde i sekundær forarbejdning 'Produkt Store Form ", hvor der er SimTable kaldet' ProfileTable ', der registrerer alle ændringer i antallet af færdige dele af den angivne type i bufferen butikken. Disse data kan ses i SimTable eller kan eksporteres til Microsoft Excel ® ved at dobbeltklikke på 'Excel' SimImage-komponent, der ligger i nederste højre hjørne.
Derudover er der også nogle standard tilgængelige statistikker fra modellen. Dobbeltklik på bestanddelen
'BaseProductionStat ' eller ' BaseStockStats'. Højre side over dialogruden viser den standard statistik, der indsamles til disse komponenter. Den primære statistik er den mængde tid, at komponenten har tilbragt i hver af de seks stater. De stater, er logisk grupperet i par som følger: ledigt. / utilgængelige, besat / tomme, og blokerede / frigives. På ethvert tidspunkt kan en komponents tilstand beskrives som, for eksempel, fås + optaget + blokeret. En alternativ, grafisk, indblik i resultaterne kan opnås ved at trykke figuren fanen 'Vis'.
Drop-down listefeltet, ved foden af den højre rude, kan bruges til at vælge et omdrejningspunkt omkring hvilke data kan ses. For eksempel, årsager vælger besatte både besatte og ubesatte at være grå i resultat tabellen. De resterende værdier viser den tid, i hvert af de fire resterende stater, mens komponenten var besat.
Ud over tiden i tilstands statistikken, viser resultat tabellen antallet af flyttede enheder med til- og afgang fra komponenten under hele varigheden af simuleringen.
Diskret Proces Simulation
Tomas Resources - http://www.tomasweb.com
Hvor traditionelle diskrete event simulation tilbyder metoder til at reagere på at en tilstand ændres, fokuseres der med diskret proces simulation på at tilstanden i et element ikke ændrer sig i en kortere eller længere tidsperiode.
Resources are ment to model limited capacity problems in an elegant way. For this purpose two object classes are introduced:
the class TomasSemaphore
the class TomasResource
TomasSemaphore is a basic class representing some kind of object with limited capacity. Each TomasElement can 'claim' some amount of capacity and the TomasSemaphore itself will handle all succeeding claims. The process of a TomasElement is suspended until the claim is honoured. If so, the element 'passes' the semaphore and resumes it's process. A TomasSemaphore is typically a data element dividing capacity among competing active TomasElements.
Tomas Resource is a descendant class of TomasElement with it's own process and limited capacity. For each arbitrary object some amount of capacity of the TomasResource can be 'claimed' for some amount of time. The TomasResource determines the moment, when a claim can be honoured, assigns the capacity claimed to the object and releases the capacity again after the requested period. So a TomasResource is typically an active Tomaselement dividing capacity among competing data elements.
Application A TomasSemaphore is normally used by active TomasElements. Especially traffic system can make good use of this facility. A TomasResource will mostly be needed in production environments to easily model machines, production lines etc.
To show the ease of a TomasResource the following example describes the processes in a single machine environment. On the left hand side of the table the machine's and generator's process are described using only TOMAS. On the right hand side the machine is defined as a TomasResource with capacity 1 and the user only needs a generator's process to make the same simulation.
Procedure TGenerator.Process; Var Job: TJob; Begin While TRUE Do Begin Job:=TJob.Create('Job'); Job.JobTime:=JobTimes.Sample; Machine.Jobs.AddToTail(Job); If Machine.Status = Passive Then Machine.Resume(TNow); Hold(InterArrivals.Sample); End; End;
Procedure TMachine.Process; Begin While TRUE Do Begin While Jobs.Length > 0 Do Begin Job:=Jobs.FirstElement; Hold(Job.JobTime); Jobs.Remove(Job); Job.Free; End; Suspend; End; End;
Each process description belongs to an element class. At any moment during a simulation one and only one process is 'current' (the 'current process') belonging to the 'current element'.
The process oriented approach of TomasWeb incorporates five methods for the current process:
Hold(T): to suspend the current process for T time units
StandBy: to suspend the current process until some condition is met
Suspend: to suspend the current process indefinitely
Stop: to stop the current process
StopAndLeave: to stop the current process and remove the element involved from the system.
The use of process descriptions is strongly supported for active elements instead of process descriptions for elements being handled. This last approach is referred to as "flow oriented approach". Our process approach can easily be linked to the modeling concept of "systems approach". This can best be explained by an example.
Example Suppose a job shop receives every day an average of 3 new jobs. This number is exponentially distributed. Every job consists of 5 tasks on the average, to be executed sequentially. The number of tasks is normally distributed with standard deviation 1. During preparation of a job prescriptions of the tasks are made. This takes always 1 day. A transportation department delivers the tasks to the department where the next task must be executed. Transportation takes about 0.5 day. Execution of a task takes on average 4 days. The execution time follows a uniform distribution between 1 and 7 days. When the last task is finished, the job is transported to packaging and delivered. Packaging takes about 2 days.
Questions:
Determine the number of jobs in the job shop
Determine the leadtimes of jobs
Although this example can easily be solved analytically, we make a simulation model as a first step for further research of scheduling mechanisms. We distinguish 4 active elements:
An element to prepare jobs.
An element to transport jobs.
An element to execute tasks
An element for packaging.
See the figure below.
And of course we need a generator element. This leads to 5 process descriptions. They are given below in a kind of pseudo Delphi code. You can find a syntactically correct and working model in the examples section.
Procedure Generator.Process Begin While TRUE Do Begin Hold(Exponential(1/3).Sample); NewJob:=Job.Create('Job'); NrOfTasks:=Round(Normal(5,1).Sample); While NrOfTasks > 0 Do Begin NewTask:=Task.Create('Task'); NewTask.Duration:=Uniform(1,7).Sample; Put NewTask to tail of NewJob.TaskList; Dec(NrOfTasks); End; Put NewJob to tail of Prepare.JobList; End; End;
Procedure Prepare.Process Begin While TRUE Do Begin While Length of JobList = 0 StandBy; Job:=First of JobList; Hold(ArrivalTime of Job in JobList + 1 - Now); Remove Job from JobList; Put Job to tail Of Transport.JobList; End; End;
Procedure Transport.Process Begin While TRUE Do Begin While Length of JobList = 0 StandBy; Job:=First of JobList; Hold(ArrivalTime of Job in JobList + 0.5 - Now); Remove Job from JobList If Length Of Job.TaskList = 0 Then Put Job to tail of Package.JobList Else Begin Task:=First Of Job.TaskList Put Job in Execute.JobList sorted on Now + Task.Duration; If Job is First of Execute.JobList Then Begin Cancel Execute; Start Execute; End; End; End; End;
Procedure Execute.Process Begin While TRUE Do Begin While Length of JobList = 0 StandBy; Job:=First of JobList; Task:=First of Job.TaskList; Hold(ArrivalTime of Job in JobList + Task.Duration - Now); Remove Task From TaskList; Free Task; Remove Job from JobList; Put Job toBegin tail Of Tnbsp; ransport.JobList; End; End;
Procedure Package.Process Begin While TRUEnbsp; br / Do Begin While Length of JobList = 0 StandBy; Job:=First of JobList; Hold(ArrivalTime of Job in JobList + 2 - Now); Remove Job from JobList; "Deliver" Job End; End;
Kapacitets-budgettering ved simuleringer i større process-netværker
