Production lines with unreliable machines have received a great amount of attention in the literature. Especially, two-station systems have mostly been studied because such systems are easier to handle when compared to the longer lines. In literature, longer lines are usually evaluated by a decomposition algorithm, whereby the long line is partitioned into chunks of two-station lines. Decomposition algorithms require intermediate buffer storages of capacity at least two or three. The trends in modern manufacturing practices, on the other hand, such as the Toyota Production System, dictate that intermediate storages be eliminated. Our work studies multi-station lines with no intermediate storage. We develop software to automate the generation of transition probability matrices to allow the analysis of system behavior. The algorithm allows the use of software packages to handle computations and to solve for exact solutions. Long-run behavior is obtained via the algorithm developed in the computational environment MATLAB. The purpose is to analyze the system performance measures such as starvation and blockage times of stations, production rate and work-in-process. In addition, the production rate and the work-in-process measures over failure and repair probabilities are curve-fit to establish simple and useful empirical formulas for lines consisting three, four and five identical stations. Numerical analyses show that the proposed algorithm is effective for exact solutions and the suggested formulas are valid for approximate solutions.

V tejto práci sa zoberáme problémom automatizovanej syntézy pravdepodobnostných programov: majme konečnú rodinu kandidátnych programov, v ktorej chceme efektívne identifikovať program spĺňajúci danú špecifikáciu. Aj riešenie tých najjednoduchších syntéznych problémov v praxi predstavuje NP-ťažký problém. Pokrok v tejto oblasti prináša nástroj Paynt, ktorý na riešenie tohto problému používa novú integrovanú metódu syntézy pravdepodobnostných programov. Aj keď sa tento prístup dokáže efektívne vysporiadať s exponenciálnym rastom rodín kandidátnych riešení, stále tu existuje problém spôsobený exponenciálnym rastom jednotlivých členov týchto rodín. S cieľom vysporiadať sa aj s týmto problémom, sme implementovali GPU orientované algoritmy slúžiace na overovanie kandidátnych programov (modelov), ktoré danú úlohu paralelizujú na stavovej úrovni pravdepodobnostých modelov. Celkové zrýchlenie doshiahnuté týmto prístupom za určitých podmienok potom prinieslo takmer teoretický limit možného zrýchlenia syntézneho procesu.

Nous considérons des processus de diffusion, définis par des équations différentielles stochastiques, et puis nous nous intéressons à des problèmes de premier passage pour les chaînes de Markov en temps discret correspon- dant à ces processus de diffusion. Comme il est connu dans la littérature, ces chaînes convergent en loi vers la solution des équations différentielles stochas- tiques considérées. Notre contribution consiste à trouver des formules expli- cites pour la probabilité de premier passage et la durée de la partie pour ces chaînes de Markov à temps discret. Nous montrons aussi que les résultats ob- tenus convergent selon la métrique euclidienne (i.e topologie euclidienne) vers les quantités correspondantes pour les processus de diffusion. En dernier lieu, nous étudions un problème de commande optimale pour des chaînes de Markov en temps discret. L’objectif est de trouver la valeur qui mi- nimise l’espérance mathématique d’une certaine fonction de coût. Contraire- ment au cas continu, il n’existe pas de formule explicite pour cette valeur op- timale dans le cas discret. Ainsi, nous avons étudié dans cette thèse quelques cas particuliers pour lesquels nous avons trouvé cette valeur optimale. / We consider diffusion processes, defined by stochastic differential equa- tions, and then we focus on first passage problems for Markov chains in dis- crete time that correspond to these diffusion processes. As it is known in the literature, these Markov chains converge in distribution to the solution of the stochastic differential equations considered. Our contribution is to obtain ex- plicit formulas for the first passage probability and the duration of the game for the discrete-time Markov chains. We also show that the results obtained converge in the Euclidean metric to the corresponding quantities for the diffu- sion processes. Finally we study an optimal control problem for Markov chains in discrete time. The objective is to find the value which minimizes the expected value of a certain cost function. Unlike the continuous case, an explicit formula for this optimal value does not exist in the discrete case. Thus we study in this thesis some particular cases for which we found this optimal value.

No description available.