Дисертації з теми "Controlled Markov chain"

In this thesis, we consider optimal control problems arising in high-speed integrated communication networks with Quality of Service (QOS) constraints. Integrated networks are expected to carry a large variety of traffic sources with widely varying traffic characteristics and performance requirements. Broadly, the traffic sources fall into two categories: (a) real-time sources with specified performance criteria, like small end to end delay and loss probability (sources of this type are referred to as Type 1 sources below), and (b) sources that do not have stringent performance criteria and do not demand performance guarantees from the network - the so-called Best Effort Type sources (these are referred to as Type 2 sources below). From the network's point of view, Type 2 sources are much more "controllable" than Type 1 sources, in the sense that the Type 2 sources can be dynamically slowed down, stopped or speeded up depending on traffic congestion in the network, while for Type 1 sources, the only control action available in case of congestion is packet dropping. Carrying sources of both types in the same network concurrently while meeting the performance objectives of Type 1 sources is a challenge and raises the question of equitable sharing of resources. The objective is to carry as much Type 2 traffic as possible without sacrificing the performance requirements of Type 1 traffic. We consider simple models that capture this situation. Consider a network node through which two connections pass, one each of Types 1 and 2. One would like to maximize the throughput of the Type 2 connection while ensuring that the Type 1 connection's performance objectives are met. This can be set up as a constrained optimization problem that, however, is very hard to solve. We introduce a parameter b that represents the "cost" of buffer occupancy by Type 2 traffic. Since buffer space is limited and shared, a queued Type 2 packet means that a buffer position is not available for storing a Type 1 packet; to discourage the Type 2 connection from hogging the buffer, the cost parameter b is introduced, while a reward for each Type 2 packet coming into the buffer encourages the Type 2 connection to transmit at a high rate. Using standard on-off models for the Type 1 sources, we show how values can be assigned to the parameter b; the value depends on the characteristics of the Type 1 connection passing through the node, i.e., whether it is a Variable Bit Rate (VBR) video connection or a Continuous Bit Rate (CBR) connection etc. Our approach gives concrete networking significance to the parameter b, which has long been considered as an abstract parameter in reward-penalty formulations of flow control problems (for example, [Stidham '85]). Having seen how to assign values to b, we focus on the Type 2 connection next. Since Type 2 connections do not have strict performance requirements, it is possible to defer transmitting a Type 2 packet, if the conditions downstream so warrant. This leads to the question: what is the "best" transmission policy for Type 2 packets? Decisions to transmit or not must be based on congestion conditions downstream; however, the network state that is available at any instant gives information that is old, since feedback latency is an inherent feature of high speed networks. Thus the problem is to identify the best transmission policy under delayed feedback information. We study this problem in the framework of Markov Decision Theory. With appropriate assumptions on the arrivals, service times and scheduling discipline at a network node, we formulate our problem as a Partially Observable Controlled Markov Chain (PO-CMC). We then give an equivalent formulation of the problem in terms of a Completely Observable Controlled Markov Chain (CO-CMC) that is easier to deal with., Using Dynamic Programming and Value Iteration, we identify structural properties of an optimal transmission policy when the delay in obtaining feedback information is one time slot. For both discounted and average cost criteria, we show that the optimal policy has a two-threshold structure, with the threshold on the observed queue length depending, on whether a Type 2 packet was transmitted in the last slot or not. For an observation delay k > 2, the Value Iteration technique does not yield results. We use the structure of the problem to provide computable upper and lower bounds to the optimal value function. A study of these bounds yields information about the structure of the optimal policy for this problem. We show that for appropriate values of the parameters of the problem, depending on the number of transmissions in the last k steps, there is an "upper cut off" number which is a value such that if the observed queue length is greater than or equal to this number, the optimal action is to not transmit. Since the number of transmissions in the last k steps is between 0 and A: both inclusive, we have a stack of (k+1) upper cut off values. We conjecture that these (k + l) values axe thresholds and the optimal policy for this problem has a (k + l)-threshold structure. So far it has been assumed that the parameters of the problem are known at the transmission control point. In reality, this is usually not known and changes over time. Thus, one needs an adaptive transmission policy that keeps track of and adjusts to changing network conditions. We show that the information structure in our problem admits a simple adaptive policy that performs reasonably well in a quasi-static traffic environment. Up to this point, the models we have studied correspond to a single hop in a virtual connection. We consider the multiple hop problem next. A basic matter of interest here is whether one should have end to end or hop by hop controls. We develop a sample path approach to answer this question. It turns out that depending on the relative values of the b parameter in the transmitting node and its downstream neighbour, sometimes end to end controls are preferable while at other times hop by hop controls are preferable. Finally, we consider a routing problem in a high speed network where feedback information is delayed, as usual. As before, we formulate the problem in the framework of Markov Decision Theory and apply Value Iteration to deduce structural properties of an optimal control policy. We show that for both discounted and average cost criteria, the optimal policy for an observation delay of one slot is Join the Shortest Expected Queue (JSEQ) - a natural and intuitively satisfactory extension of the well-known Join the Shortest Queue (JSQ) policy that is optimal when there is no feedback delay (see, for example, [Weber 78]). However, for an observation delay of more than one slot, we show that the JSEQ policy is not optimal. Determining the structure of the optimal policy for a delay k>2 appears to be very difficult using the Value Iteration approach; we explore some likely policies by simulation.

In this thesis, we consider optimal control problems arising in high-speed integrated communication networks with Quality of Service (QOS) constraints. Integrated networks are expected to carry a large variety of traffic sources with widely varying traffic characteristics and performance requirements. Broadly, the traffic sources fall into two categories: (a) real-time sources with specified performance criteria, like small end to end delay and loss probability (sources of this type are referred to as Type 1 sources below), and (b) sources that do not have stringent performance criteria and do not demand performance guarantees from the network - the so-called Best Effort Type sources (these are referred to as Type 2 sources below). From the network's point of view, Type 2 sources are much more "controllable" than Type 1 sources, in the sense that the Type 2 sources can be dynamically slowed down, stopped or speeded up depending on traffic congestion in the network, while for Type 1 sources, the only control action available in case of congestion is packet dropping. Carrying sources of both types in the same network concurrently while meeting the performance objectives of Type 1 sources is a challenge and raises the question of equitable sharing of resources. The objective is to carry as much Type 2 traffic as possible without sacrificing the performance requirements of Type 1 traffic. We consider simple models that capture this situation. Consider a network node through which two connections pass, one each of Types 1 and 2. One would like to maximize the throughput of the Type 2 connection while ensuring that the Type 1 connection's performance objectives are met. This can be set up as a constrained optimization problem that, however, is very hard to solve. We introduce a parameter b that represents the "cost" of buffer occupancy by Type 2 traffic. Since buffer space is limited and shared, a queued Type 2 packet means that a buffer position is not available for storing a Type 1 packet; to discourage the Type 2 connection from hogging the buffer, the cost parameter b is introduced, while a reward for each Type 2 packet coming into the buffer encourages the Type 2 connection to transmit at a high rate. Using standard on-off models for the Type 1 sources, we show how values can be assigned to the parameter b; the value depends on the characteristics of the Type 1 connection passing through the node, i.e., whether it is a Variable Bit Rate (VBR) video connection or a Continuous Bit Rate (CBR) connection etc. Our approach gives concrete networking significance to the parameter b, which has long been considered as an abstract parameter in reward-penalty formulations of flow control problems (for example, [Stidham '85]). Having seen how to assign values to b, we focus on the Type 2 connection next. Since Type 2 connections do not have strict performance requirements, it is possible to defer transmitting a Type 2 packet, if the conditions downstream so warrant. This leads to the question: what is the "best" transmission policy for Type 2 packets? Decisions to transmit or not must be based on congestion conditions downstream; however, the network state that is available at any instant gives information that is old, since feedback latency is an inherent feature of high speed networks. Thus the problem is to identify the best transmission policy under delayed feedback information. We study this problem in the framework of Markov Decision Theory. With appropriate assumptions on the arrivals, service times and scheduling discipline at a network node, we formulate our problem as a Partially Observable Controlled Markov Chain (PO-CMC). We then give an equivalent formulation of the problem in terms of a Completely Observable Controlled Markov Chain (CO-CMC) that is easier to deal with., Using Dynamic Programming and Value Iteration, we identify structural properties of an optimal transmission policy when the delay in obtaining feedback information is one time slot. For both discounted and average cost criteria, we show that the optimal policy has a two-threshold structure, with the threshold on the observed queue length depending, on whether a Type 2 packet was transmitted in the last slot or not. For an observation delay k > 2, the Value Iteration technique does not yield results. We use the structure of the problem to provide computable upper and lower bounds to the optimal value function. A study of these bounds yields information about the structure of the optimal policy for this problem. We show that for appropriate values of the parameters of the problem, depending on the number of transmissions in the last k steps, there is an "upper cut off" number which is a value such that if the observed queue length is greater than or equal to this number, the optimal action is to not transmit. Since the number of transmissions in the last k steps is between 0 and A: both inclusive, we have a stack of (k+1) upper cut off values. We conjecture that these (k + l) values axe thresholds and the optimal policy for this problem has a (k + l)-threshold structure. So far it has been assumed that the parameters of the problem are known at the transmission control point. In reality, this is usually not known and changes over time. Thus, one needs an adaptive transmission policy that keeps track of and adjusts to changing network conditions. We show that the information structure in our problem admits a simple adaptive policy that performs reasonably well in a quasi-static traffic environment. Up to this point, the models we have studied correspond to a single hop in a virtual connection. We consider the multiple hop problem next. A basic matter of interest here is whether one should have end to end or hop by hop controls. We develop a sample path approach to answer this question. It turns out that depending on the relative values of the b parameter in the transmitting node and its downstream neighbour, sometimes end to end controls are preferable while at other times hop by hop controls are preferable. Finally, we consider a routing problem in a high speed network where feedback information is delayed, as usual. As before, we formulate the problem in the framework of Markov Decision Theory and apply Value Iteration to deduce structural properties of an optimal control policy. We show that for both discounted and average cost criteria, the optimal policy for an observation delay of one slot is Join the Shortest Expected Queue (JSEQ) - a natural and intuitively satisfactory extension of the well-known Join the Shortest Queue (JSQ) policy that is optimal when there is no feedback delay (see, for example, [Weber 78]). However, for an observation delay of more than one slot, we show that the JSEQ policy is not optimal. Determining the structure of the optimal policy for a delay k>2 appears to be very difficult using the Value Iteration approach; we explore some likely policies by simulation.

Discrete controlled Markov chains with finite action space and bounded cost per stage are studied in this dissertation. The performance index function, the exponential average cost (EAC), models risk-sensitivity by means of an exponential (dis)utility function. First, for the finite state space model, the EAC corresponding to a fixed stationary (deterministic) policy is characterized in terms of the spectral radii of matrices associated to irreducible communicating classes of both recurrent and transient states. This result generalizes a well known theorem of Howard and Matheson, which treats the particular case in which the Markov cost chain has only one dosed class of states. Then, it is shown that under strong recurrence conditions, the risk-sensitive model approaches the risk-null model when the risk-sensitivity coefficient is small. However, it is proved and also illustrated by means of examples, that in general, fundamental differences arise between both models, e.g., the EAC may depend on the cost structure at the transient states. In particular, the behavior of the EAC for large risk-sensitivity is also analyzed. After showing that an exponential average optimality equation holds for the countable state space model, a proof of the existence of solutions to that equation for the finite model under a simultaneous Doeblin condition is provided, which is simpler than that given in recent work of Cavazos-Cadena and Fernandez-Gaucherand. The adverse impact of "large risk-sensitivity" on recently obtained conditions for the existence of solutions to an optimality inequality is illustrated by means of an example. Finally, a counterexample is included to show that, unlike previous results for finite models, a controlled Markov chain with infinite state space may not have ultimately stationary optimal policies in the risk-sensitive (exponential) discounted cost case, in general. Moreover, a simultaneous Doeblin condition is satisfied in our example, an assumption that enables the vanishing discount approach in the risk-null case, thus further suggesting that more restrictive conditions than those commonly used in the risk neutral context are needed to develop the mentioned approach for risk-sensitive criteria.

Controlled Markov chains (CMC's) are mathematical models for the control of sequential decision stochastic systems. Starting in the early 1950's with the work of R. Bellman, many basic contributions to CMC's have been made, and numerous applications to engineering, operation research, and economics, among other areas, have been developed. The optimal control problem for CMC's with a countable state space, and with a general action space, is studied for (exponential) total and discounted risk-sensitive cost criteria. General (dynamic programming) results for the finite and the infinite horizon cases are obtained. A set of general conditions is presented to obtain structural properties of the optimal value function and policies. In particular, monotonicity properties of value functions and optimal policies are established. The approach followed is to show the (sub)modularity of certain functions (related to the optimality equations). Four applications studies are used to illustrate the general results obtained is this dissertation: equipment replacement, optimal resource allocation, scheduling of uncertain jobs, and inventory control.

This thesis deals with discrete-time Markov jump linear systems (MJLS) with Markov chain in a general Borel space S. Several control issues have been addressed for this class of dynamic systems, including stochastic stability (SS), linear quadratic (LQ) optimal control synthesis, fllter design and a separation principle. Necessary and sffcient conditions for SS have been derived. It was shown that SS is equivalent to the spectral radius of an operator being less than 1 or to the existence of a solution to a \\Lyapunov-like\" equation. Based on the SS concept, the finite- and infinite-horizon LQ optimal control problems were tackled. The solution to the finite- (infinite-)horizon LQ optimal control problem was derived from the associated control S-coupled Riccati difference (algebraic) equations. By S-coupled it is meant that the equations are coupled via an integral over a transition probability kernel having a density with respect to a in-finite measure on the Borel space S. The design of linear Markov jump filters was analyzed and a solution to the finite- (infinite-)horizon filtering problem was obtained based on the associated filtering S-coupled Riccati difference (algebraic) equations. Conditions for the existence and uniqueness of a stabilizing positive semi-definite solution to the control and filtering S-coupled algebraic Riccati equations have also been derived. Finally a separation principle for discrete-time MJLS with Markov chain in a general state space was obtained. It was shown that the optimal controller for a partial information optimal control problem separates the partial information control problem into two problems, one associated with a filtering problem and the other associated with an optimal control problem with complete information. It is expected that the results obtained in this thesis may motivate further research on discrete-time MJLS with Markov chain in a general state space.
Esta tese trata de sistemas lineares com saltos markovianos (MJLS) a tempo discreto com cadeia de Markov em um espaço geral de Borel S. Vários problemas de controle foram abordados para esta classe de sistemas dinâmicos, incluindo estabilidade estocástica (SS), síntese de controle ótimo linear quadrático (LQ), projeto de filtros e um princípio da separação. Condições necessárias e suficientes para a SS foram obtidas. Foi demonstrado que SS é equivalente ao raio espectral de um operador ser menor que 1 ou à existência de uma solução para uma equação de Lyapunov. Os problemas de controle ótimo a horizonte finito e infinito foram abordados com base no conceito de SS. A solução para o problema de controle ótimo LQ a horizonte finito (infinito) foi obtida a partir das associadas equações a diferenças (algébricas) de Riccati S-acopladas de controle. Por S-acopladas entende-se que as equações são acopladas por uma integral sobre o kernel estocástico com densidade de transição em relação a uma medida in-finita no espaço de Borel S. O projeto de filtros lineares markovianos foi analisado e uma solução para o problema da filtragem a horizonte finito (infinito) foi obtida com base nas associadas equações a diferenças (algébricas) de Riccati S-acopladas de filtragem. Condições para a existência e unicidade de uma solução positiva semi-definida e estabilizável para as equações algébricas de Riccati S-acopladas associadas aos problemas de controle e filtragem também foram obtidas. Por último, foi estabelecido um princípio da separação para MJLS a tempo discreto com cadeia de Markov em um espaço de estados geral. Foi demonstrado que o controlador ótimo para um problema de controle ótimo com informação parcial separa o problema de controle com informação parcial em dois problemas, um deles associado a um problema de filtragem e o outro associado a um problema de controle ótimo com informação completa. Espera-se que os resultados obtidos nesta tese possam motivar futuras pesquisas sobre MJLS a tempo discreto com cadeia de Markov em um espaço de estados geral.

Made available in DSpace on 2014-06-11T19:26:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-06-15Bitstream added on 2014-06-13T19:25:33Z : No. of bitstreams: 1 franco_bc_me_guara.pdf: 1492178 bytes, checksum: 2c201ad6660278573573b0b255349982 (MD5)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Esta pesquisa propõe o planejamento econômico de gráficos de controle ̅ para o monitoramento de uma característica de qualidade na qual as observações se ajustam a um modelo autorregressivo de primeira ordem com erro adicional. O modelo de custos de Duncan é usado para selecionar os parâmetros do gráfico, tamanho da amostra, intervalo de amostragem e os limites de controle. Utiliza-se o algoritmo genético na busca do custo mínimo de monitoramento. Para determinação do número médio de amostras até o sinal e o número de alarmes falsos são utilizadas Cadeias de Markov. Uma análise de sensibilidade mostrou que a autocorrelação provoca efeito adverso nos parâmetros do gráfico elevando seu custo de monitoramento e reduzindo sua eficiência
This research proposes an economic design of a ̅ control chart used to monitor a quality characteristic whose observations fit to a first-order autoregressive model with additional error. The Duncan's cost model is used to select the control chart parameters, namely the sample size, the sampling interval and the control limit coefficient, using genetic algorithm in order to search the minimum cost. The Markov chain is used to determine the average number of samples until the signal and the number of false alarms. A sensitivity analysis showed that the autocorrelation causes adverse effect on the parameters of the control chart increasing monitoring cost and reducing significantly their efficiency

O procedimento de controle on-line de processos por atributos, proposto por Taguchi et al. (1989), consiste em amostrar um item a cada m produzidos e decidir, a cada inspeção, se houve ou não aumento na fração de itens não-conformes produzidos. Caso o item inspecionado seja não-conforme, pára-se o processo para ajuste supondo-se que tenha ocorrido uma mudança para a condição fora de controle. Como i) o sistema de inspeção pode estar sujeito a erros de classificação e o item inspecionado ser submetido à classificações repetidas; ii) a fração de itens não-conformes no estado fora de controle pode variar em função do número de itens produzidos (x) segundo uma função y (x); iii) e a decisão de parar o processo pode ser tomada com base no resultado das últimas h inspeções, desenvolve-se um modelo que engloba estes pontos. Utilizando-se as propriedades de uma cadeia de Markov ergódica, obtém-se a expressão do custo médio do sistema de controle, que é minimizada por parâmetros que vão além do intervalo de inspeção m: o número de classificações repetidas r; o número mínimo de classificações conformes para declarar um item como conforme s, o comprimento do histórico de inspeções considerado h e o critério de parada para ajuste u. Os resultados obtidos mostram que: o uso de classificações repetidas pode ser uma alternativa econômica quando apenas um item é considerado na decisão sobre o ajuste do processo; uma cadeia da Markov finita pode ser utilizada para representar o sistema de controle na presença de uma função y (x) não-constante; tomar a decisão de ajuste com base na observação de uma seqüência de itens inspecionados é a alternativa de maior impacto sobre o custo de controle do processo.
The quality control procedure for attributes, proposed by Taguchi et al. (1989), consists in inspecting a single item at every m produced items and, based on the result of each inspection, deciding weather the non-conforming fraction has increased or not. If an inspected item is declared non-conforming, the process is stopped and adjusted, assuming that it has changed to out-of-control condition. Once: i) the inspection system is subject to misclassification and it is possible to carry out repetitive classifications in the inspected item; ii) the non-conforming fraction, when the process is out-of-control, can be described by y(x); iii) the decision about stopping the process can be based on last h inspections, a model which considers those points is developed. Using properties of ergodic Markov chains, the average cost expression is calculated and can be minimized by parameters beyond m: number of repetitive classifications (r); minimum number of classifications as conforming to declare an item as conforming (s); number of inspections taken into account (h) and stopping criteria (u). The results obtained show that: repetitive classifications of the inspected item can be a viable option if only one item is used to decide about the process condition; a finite Markov chain can be used to represent the control procedure in presence of a function y(x); deciding about the process condition based on last h inspections has a significant impact on the average cost.

Resumo: Esta pesquisa propõe o planejamento econômico de gráficos de controle ̅ para o monitoramento de uma característica de qualidade na qual as observações se ajustam a um modelo autorregressivo de primeira ordem com erro adicional. O modelo de custos de Duncan é usado para selecionar os parâmetros do gráfico, tamanho da amostra, intervalo de amostragem e os limites de controle. Utiliza-se o algoritmo genético na busca do custo mínimo de monitoramento. Para determinação do número médio de amostras até o sinal e o número de alarmes falsos são utilizadas Cadeias de Markov. Uma análise de sensibilidade mostrou que a autocorrelação provoca efeito adverso nos parâmetros do gráfico elevando seu custo de monitoramento e reduzindo sua eficiência
Abstract: This research proposes an economic design of a ̅ control chart used to monitor a quality characteristic whose observations fit to a first-order autoregressive model with additional error. The Duncan's cost model is used to select the control chart parameters, namely the sample size, the sampling interval and the control limit coefficient, using genetic algorithm in order to search the minimum cost. The Markov chain is used to determine the average number of samples until the signal and the number of false alarms. A sensitivity analysis showed that the autocorrelation causes adverse effect on the parameters of the control chart increasing monitoring cost and reducing significantly their efficiency
Orientadora: Marcela Aparecida Guerreiro Machado
Coorientadora: Antonio Fernando Branco Costa
Banca: Fernando Augusto Silva Marins
Banca: Anderson Paula de Paiva
Mestre

No contexto do mundo contemporâneo, os veículos automotores estão cada vez mais integrados ao cotidiano das pessoas, sendo mais de 1 bilhão deles circulando pelo mundo. Por serem controlados por motoristas, estão sujeitos a falhas decorrentes da inerente condição humana, ocasionando acidentes, mortes e outros prejuízos. O controle autônomo de veículos tem se apresentado como alternativa na busca de redução desses prejuízos, sendo utilizado nas mais diferentes abordagens, por distintas instituições ao redor do planeta. Deste modo, torna-se uma pauta fundamental para o estudo de sistemas de controle. Este trabalho, valendo-se da descrição matemática do comportamento veicular, busca o desenvolvimento e a implementação de um método eficiente de controle autônomo de veículos voltado, principalmente, para a modelagem em espaço de estados. Considerando que mudanças de marchas, principalmente em um cenário de dirigibilidade autônoma, são ações aleatórias, o objetivo desta dissertação é utilizar estratégias de controle baseadas em sistemas lineares sujeitos a saltos Markovianos.
In nowadays society, automobile vehicles are getting more and more integrated to people\'s daily activities, as there are more than 1 billion of them on the streets around the world. As they are controlled by drivers, vehicles are subjected to failures caused by human mistakes that lead to accidents, injuries and others. Autonomous vehicle control has shown itself to be an alternative in the pursuit of damage reduction, and it is applied by different institutions in many countries. Therefore, it is a main subject in the area of control systems. This paper, relying on mathematical descriptions of vehicle behavior, aims to develop and apply an efficient autonomous control method that takes into account state-space formulation. This goal will be achieved by the use of control strategies based on Markovian Jump Linear Systems that will describe the highly non-linear dynamics of the vehicle in different operation points.

Esta dissertação aborda o problema de redução do consumo de combustível para veículos. Com esse objetivo, realiza-se o levantamento de um modelo estocástico e de seus parâmetros, o desenvolvimento de um controlador para o veículo, e análise dos resultados. O problema considera a interação com o trânsito de outros veículos, que limita a aplicação de resultados antes disponíveis. Para isto, propõe-se modelar a dinâmica do problema de maneira aproximada, usando sistemas com saltos markovianos, e levantar as probabilidades de transição dos estados da cadeia através de um modelo mais completo para o trânsito no percurso.
This dissertation deals with control of vehicles aiming at the fuel consumption optimization, taking into account the interference of traffic. Stochastic interferences like this and other real world phenomena prevents us from directly applying available results. We propose to employ a relatively simple system with Markov jumping parameters as a model for the vehicle subject to traffic interference, and to obtain the transition probabilities from a separate model for the traffic. This dissertation presents the model identification, the solution of the new problem using dynamic programming, and simulation of the obtained control.

Esta tese de doutorado aborda os projetos robustos de controle e estimativa de estados para Sistemas Lineares sujeitos a Saltos Markovianos (SLSM) de tempo discreto sob a influência de incertezas paramétricas. Esses projetos são desenvolvidos por meio de extensões dos critérios quadráticos clássicos para SLSM nominais. Os critérios de custo quadrático para os SLSM incertos são formulados na forma de problemas de otimização min-max que permitem encontrar a melhor solução para o pior caso de incerteza (máxima influência de incerteza). Os projetos robustos correspondem às soluções ótimas obtidas por meio da combinação dos métodos de funções penalidade e mínimos quadrados regularizados robustos. Duas situações são investigadas: regular e estimar os estados quando os modos de operações são observados; e estimar os estados sob a hipótese de desconhecimento da cadeia de Markov. Estruturalmente, o regulador e as estimativas de estados assemelham-se às respectivas versões nominais. A recursividade é estabelecida em termos de equações de Riccati sem a necessidade de ajuste de parâmetros auxiliares e dependente apenas das matrizes de parâmetros e ponderações conhecidas.
This thesis deals with recursive robust designs of control and state estimates for discretetime Markovian Jump Linear Systems (MJLS) subject to parametric uncertainties. The designs are developed considering extensions of the standard quadratic cost criteria for MJLS without uncertainties. The quadratic cost criteria for uncertain MJLS are formulated in the form of min-max optimization problems to get the best solution for the worst uncertainty case. The optimal robust schemes correspond to the optimal solution obtained by the combination of penalty function and robust regularized least-squares methods. Two cases are investigated: to control and estimate the states when the operation modes are observed; and, to estimate the states when the Markov chain is unobserved. The optimal robust LQR and Kalman-type state estimates resemble the respective nominal versions. The recursiveness is established by Riccati equations in terms of parameter and weighting matrices previously known and without extra offline computations.

Made available in DSpace on 2014-12-17T14:55:16Z (GMT). No. of bitstreams: 1 LuizAC_TESE.pdf: 1792266 bytes, checksum: ec666aacc6a6bc6fc6e042bf7f0ce339 (MD5) Previous issue date: 2013-11-05
In this work, the Markov chain will be the tool used in the modeling and analysis of convergence of the genetic algorithm, both the standard version as for the other versions that allows the genetic algorithm. In addition, we intend to compare the performance of the standard version with the fuzzy version, believing that this version gives the genetic algorithm a great ability to find a global optimum, own the global optimization algorithms. The choice of this algorithm is due to the fact that it has become, over the past thirty yares, one of the more importan tool used to find a solution of de optimization problem. This choice is due to its effectiveness in finding a good quality solution to the problem, considering that the knowledge of a good quality solution becomes acceptable given that there may not be another algorithm able to get the optimal solution for many of these problems. However, this algorithm can be set, taking into account, that it is not only dependent on how the problem is represented as but also some of the operators are defined, to the standard version of this, when the parameters are kept fixed, to their versions with variables parameters. Therefore to achieve good performance with the aforementioned algorithm is necessary that it has an adequate criterion in the choice of its parameters, especially the rate of mutation and crossover rate or even the size of the population. It is important to remember that those implementations in which parameters are kept fixed throughout the execution, the modeling algorithm by Markov chain results in a homogeneous chain and when it allows the variation of parameters during the execution, the Markov chain that models becomes be non - homogeneous. Therefore, in an attempt to improve the algorithm performance, few studies have tried to make the setting of the parameters through strategies that capture the intrinsic characteristics of the problem. These characteristics are extracted from the present state of execution, in order to identify and preserve a pattern related to a solution of good quality and at the same time that standard discarding of low quality. Strategies for feature extraction can either use precise techniques as fuzzy techniques, in the latter case being made through a fuzzy controller. A Markov chain is used for modeling and convergence analysis of the algorithm, both in its standard version as for the other. In order to evaluate the performance of a non-homogeneous algorithm tests will be applied to compare the standard fuzzy algorithm with the genetic algorithm, and the rate of change adjusted by a fuzzy controller. To do so, pick up optimization problems whose number of solutions varies exponentially with the number of variables
Neste trabalho, a cadeia de Markov ser? a ferramenta usada na modelagem e na an?lise de converg?ncia do algoritmo gen?tico, tanto para sua vers?o padr?o quanto para as demais vers?es que o algoritmo gen?tico permite. Al?m disso, pretende-se comparar o desempenho da vers?o padr?o com a vers?o nebulosa, por acreditar que esta vers?o d? ao algoritmo gen?tico uma grande capacidade para encontrar um ?timo global, pr?prio dos algoritmos de otimiza??o global. A escolha deste algoritmo deve-se tamb?m ao fato do mesmo ter se tornado, nos ?ltimos anos, uma das ferramentas mais usadas para achar uma solu??o do problema de otimiza??o. Esta escolha deve-se ? sua comprovada efic?cia na busca de uma solu??o de boa qualidade para o problema, considerando que o conhecimento de uma solu??o de boa qualidade torna-se aceit?vel tendo em vista que pode n?o existir um outro algorimo capaz de obter a solu??o ?tima, para muitos desses problemas. Entretanto, esse algoritmo pode ser definido, levando em conta que o mesmo ? dependente n?o apenas da forma como o problema ? representado, mas tamb?m como s?o definidos alguns dos operadores, desde sua vers?o padr?o, quando os par?metros s?o mantidos fixos, at? suas vers?es com par?metros vari?veis. Por isso, para se alcan?ar um bom desempenho com o aludido algoritmo ? necess?rio que o mesmo tenha um adequado crit?rio na escolha de seus par?metros, principalmente da taxa de muta??o e da taxa de cruzamento ou, at? mesmo, do tamanho da popula??o. ? importante lembrar que as implementa??es em que par?metros s?o mantidos fixos durante toda a execu??o, a modelagem do algoritmo por cadeia de Markov resulta numa cadeia homog?nea, e quando permite a varia??o de par?metros ao longo da execu??o, a cadeia de Markov que o modela passa a ser do tipo n?o-homog?nea. Portanto, na tentativa de melhorar o desempenho do algoritmo, alguns trabalhos t?m procurado realizar o ajuste dos par?metros atrav?s de estrat?gias que captem caracter?sticas intr?nsecas ao problema. Essas caracter?sticas s?o extra?das do estado presente de execu??o, com o fim de identificar e preservar algum padr?o relacionado a uma solu??o de boa qualidade e, ao mesmo tempo, descartando aquele padr?o de baixa qualidade. As estrat?gias de extra??o das caracter?sticas tanto podem usar t?cnicas precisas quanto t?cnicas nebulosas, sendo neste ?ltimo caso feita atrav?s de um controlador nebuloso. Com o fim de avaliar empiriccamente o desempenho de um algoritmo n?o-homog?neo, apresenta-se testes onde se compara o algoritmo gen?tico padr?o com o algoritmo gen?tico nebuloso, sendo a taxa de muta??o ajustada por um controlador nebuloso. Para isso, escolhe-se problemas de otimiza??o cujo n?mero de solu??es varia exponencialmente com o n?mero de vari?veis

In this thesis, we present some contributions to the Markov jump linear systems theory in a context of partial information on the Markov chain. We consider that the state of the Markov chain cannot be measured, but instead there is only an observed variable that could model an asynchronous phenomenon between the application and the plant, or a simple fault detection and isolation device. In this formulation, we investigate the problem of designing controllers and filters depending only on the observed variable in the context of H2, H?, and mixed H2/H? control theory. Numerical examples and academic applications are presented for active-fault tolerant control systems and networked control systems.
Nesta tese, apresentamos algumas contribuições para a teoria de sistemas lineares com saltos markovianos em um contexto de observação parcial da cadeia de Markov. Consideramos que o estado da cadeia de Markov não pode ser medido, porém existe uma variável observada que pode modelar um fenômeno assíncrono entre a aplicação e a planta, ou ainda um dispositivo de detecção de falhas simples. Através desse modelo, investigamos o problema da síntese de controladores e filtros que dependem somente da variável observada no contexto das teorias de controle H2, H?, e misto H2/H?. Exemplos numéricos e aplicações acadêmicas são apresentadas no âmbito dos sistemas de controle tolerantes a falhas e dos sistemas de controle através da rede.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2015-10-22T16:50:07Z No. of bitstreams: 2 Dissertação - Ademir Amaro da Silveira Júnior - 2014.pdf: 8148694 bytes, checksum: d08c57d58984e109d6488e7b066e9e83 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2015-10-22T16:52:16Z (GMT) No. of bitstreams: 2 Dissertação - Ademir Amaro da Silveira Júnior - 2014.pdf: 8148694 bytes, checksum: d08c57d58984e109d6488e7b066e9e83 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Made available in DSpace on 2015-10-22T16:52:16Z (GMT). No. of bitstreams: 2 Dissertação - Ademir Amaro da Silveira Júnior - 2014.pdf: 8148694 bytes, checksum: d08c57d58984e109d6488e7b066e9e83 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-03-14
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
The aquatic plants play an important role in the dams, because help in the water ltration by removing some heavy metals, serving of sh food and shelter for some insects. However, some species are spreading and causing great inconvenience to the local population, hydroelectrics and other individuals who depend on the lakes for survival. The purpose of this work was to make an initial study of the biological control of the aquatic macrophyte Eichhornia azurea by inserting the insect predator Thrypticus sp., using mathematical modeling and Markov chains of order 1. For that, a brief historical of the aquatic plant and of the insect is presented, as well as concepts related to Markov chains and their applications in biomathematics are discussed, supporting the realization of the modeling of the problem. Actual data obtained from a survey conducted by the author between 2002 and 2003, in the city of Coxim-MS, were incorporated in the modeling process. Simulations were performed for di erent scenarios, assuming infestation by plant in interconnected dams and the results showed the amount of insects needed to control in each cycle. The use of mathematical modeling and Markov chains allows the implementation of several tests. Nevertheless, to achieve more accurate results in relation to biological control we intend, in future work, to use a predator-prey model and analyze in more detail the problem, add more hypotheses, and to discuss aspects related to the predator population in environment in question. The work is a result of the Professional Masters and was written with the intention that teachers and high school students are being able understand the resolutions of the examples presented.
As plantas aquáticas exercem papel importante nas represas, pois auxiliam na ltra ção da água retirando alguns metais pesados, servindo de alimentos para peixes e de abrigo para alguns insetos. Entretanto, algumas espécies vêm se alastrando e causando grandes transtornos à população ribeirinha, usinas hidrelétricas e outros indivíduos que dependem dos lagos para sobreviverem. O propósito deste trabalho foi fazer um estudo inicial do controle biológico da macró ta aquática Eichhornia azurea por meio da inser ção do inseto predador Thrypticus sp., utilizando modelagem matemática e Cadeias de Markov de ordem 1. Para tanto, um breve histórico sobre a planta aquática e o inseto é apresentado, assim como conceitos relacionados às Cadeias de Markov e suas aplicações na biomatemática são abordados, fornecendo subsídios para a realização da modelagem do problema. Dados reais obtidos de uma pesquisa desenvolvida pelo autor entre 2002 e 2003, no município de Coxim-MS, foram incorporados no processo de modelagem. Simulações de diferentes cenários foram realizadas, supondo infestação pela planta em represas interligadas e os resultados mostraram a quantidade de insetos necess ários para controle em cada ciclo. O uso da modelagem matemática e das Cadeias de Markov permite a implementação de vários testes. Contudo, para se alcançar resultados mais precisos em relação ao controle biológico pretende-se, em trabalhos futuros, usar um modelo presa-predador e analisar com mais detalhes o problema, acrescentar mais hipóteses, além de discutir os aspectos referentes à população do predador no ambiente em questão. O trabalho é um fruto do Mestrado Pro ssional e foi escrito com a intenção de que docentes e estudantes do ensino médio possam compreender as resoluções dos exemplos apresentados.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
Processos de produção precisam ser avaliados continuamente para que funcionem de modo mais eficaz e eficiente possível. Um conjunto de ferramentas utilizado para tal finalidade é denominado controle estatístico de processos (CEP). Através de ferramentas do CEP, o monitoramento pode ser realizado periodicamente. A ferramenta mais importante do CEP é o gráfico de controle. Nesta tese, foca-se no monitoramento de uma variável resposta, por meio dos parâmetros ou coeficientes de um modelo de regressão linear simples. Propõe-se gráficos de controle χ2 adaptativos para o monitoramento dos coeficientes do modelo de regressão linear simples. Mais especificamente, são desenvolvidos sete gráficos de controle χ2 adaptativos para o monitoramento de perfis lineares, a saber: gráfico com tamanho de amostra variável; intervalo de amostragem variável; limites de controle e de advertência variáveis; tamanho de amostra e intervalo de amostragem variáveis; tamanho de amostra e limites variáveis; intervalo de amostragem e limites variáveis e por fim, com todos os parâmetros de projeto variáveis. Medidas de desempenho dos gráficos propostos foram obtidas através de propriedades de cadeia de Markov, tanto para a situação zero-state como para a steady-state, verificando-se uma diminuição do tempo médio até um sinal no caso de desvios pequenos a moderados nos coeficientes do modelo de regressão do processo de produção. Os gráficos propostos foram aplicados a um exemplo de um processo de fabricação de semicondutores. Além disso, uma análise de sensibilidade dos mesmos é feita em função de desvios de diferentes magnitudes nos parâmetros do processo, a saber, no intercepto e na inclinação, comparando-se o desempenho entre os gráficos desenvolvidos e também com o gráfico χ2 com parâmetros fixos. Os gráficos propostos nesta tese são adequados para vários tipos de aplicações. Neste trabalho também foi considerado características de qualidade as quais são representadas por um modelo de regressão não-linear. Para o modelo de regressão não-linear considerado, a proposta é utilizar um método que divide o perfil não-linear em partes lineares, mais especificamente, um algoritmo para este fim, proposto na literatura, foi utilizado. Desta forma, foi possível validar a técnica proposta, mostrando que a mesma é robusta no sentido que permite tipos diferentes de perfis não-lineares. Aproxima-se, portanto um perfil não-linear por perfis lineares por partes, o que proporciona o monitoramento de cada perfil linear por gráficos de controle, como os gráficos de controle desenvolvidos nesta tese. Ademais apresenta-se a metodologia de decompor um perfil não-linear em partes lineares de forma detalhada e completa, abrindo espaço para ampla utilização.
Production processes need to be continually evaluated so that they are able to produce in the most effective and efficient way. Statistical process control (SPC) consists of a set of tools used for this purpose. The monitoring can be periodically performed through the SPC tools. The most important tool of SPC is the control chart. In this thesis, we focus on the monitoring of a response variable through the parameters or coefficients of a linear regression model. It is proposed adaptive χ2 control charts for monitoring the coefficients of linear regression models. More specifically, seven adaptive χ2 control charts are proposed for monitoring a simple linear regression model, being distinguished by the following properties: variable sample size; variable sampling interval; variable warning and control limits; variable sample size and sampling interval; variable sample size and limits; variable sampling interval and limits and finally, all design parameters varying. Performance measures of these charts were obtained through properties of Markov chain, for both the zero-state and the steady-state situation. It was found that the average time until a signal in the case of small to moderate shifts in the coefficients of the regression model decreased. The proposed charts were applied to an example of semiconductors manufacturing process. Moreover, a sensitivity analysis of the proposed charts is performed for different shifts magnitudes in the process parameters, namely the intercept and the slope, comparing the performance between the developed charts and also with the fixed parameter χ2 chart. The proposed charts in this thesis are suitable for several applications. In this work, it was also considered quality characteristics represented by nonlinear regression models. To the considered nonlinear regression model, the proposal is to use a method that divides the nonlinear profile in linear parts. More specifically, an algorithm for this purpose, proposed in the literature, was utilized. It approximates nonlinear profile by a set of linear profiles. It was possible to validate this technique, showing that it is robust in the sense that it allows different types of nonlinear profiles to be considered. In this way, techniques such as control charts developed here can be used to monitor each linear part. Furthermore, we present the methodology to decompose a nonlinear profile in linear parts in a detailed and complete way, allowing its widespread use.

Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2015-10-16T18:00:48Z No. of bitstreams: 2 Dissertação - Wilder Francisco Soares Costa - 2014.pdf: 2068928 bytes, checksum: 053e3f6ebe769a97bc3032d2a3af31b9 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Rejected by Luciana Ferreira (lucgeral@gmail.com), reason: Na citação 0 nome do mestrado é Mestrado Profissional em Matemática em Rede Nacional. No final da citação coloque ponto final. on 2015-10-19T13:51:53Z (GMT)
Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2015-10-20T14:51:37Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertação - Wilder Francisco Soares Costa - 2014.pdf: 2068928 bytes, checksum: 053e3f6ebe769a97bc3032d2a3af31b9 (MD5)
Approved for entry into archive by Cláudia Bueno (claudiamoura18@gmail.com) on 2015-10-20T15:15:33Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertação - Wilder Francisco Soares Costa - 2014.pdf: 2068928 bytes, checksum: 053e3f6ebe769a97bc3032d2a3af31b9 (MD5)
Made available in DSpace on 2015-10-20T15:15:33Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Dissertação - Wilder Francisco Soares Costa - 2014.pdf: 2068928 bytes, checksum: 053e3f6ebe769a97bc3032d2a3af31b9 (MD5) Previous issue date: 2014-10-30
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
Inventory control plays an important role in business because they help the financial structure and understanding of it. Due to this fact is of great value that high school students seize their definitions and applications as they are or will be included in the labor market. The purpose of this work was to unite the inventory control with stochastic process, which in this case was the Markov process, through mathematical modeling. To this end, a brief explanation of inventory control and stock was addressed, as stochastic processes and examples, arriving on the Markov Chain that was addressed in a very simple way geared more for matrix multiplication and how to get these matrices. Then took these theories and applied, through modeling, at a small supermarket in inventory control of tomato sauce using Markov chains, allowing a prediction of future orders with the supplier. The work is the result of the Professional Masters and was written with the intention that teachers and high school students can understand the resolutions of the examples presented.
O controle de estoque exerce um papel importante nas empresas, pois auxiliam na estrutura financeira e compreensão da mesma. Devido esse fato é de grande valor que estudantes do ensino médio apreendam suas definições e aplicações pois estão ou serão inseridos no mercado de trabalho. O proposito deste trabalho foi unir o controle de estoque com o processo estocástico, que nesse caso foi o processo Markoviano, através da modelagem matemática. Para tanto, uma breve explanação de controle de estoque e estoque foi abordada, bem como processos estocásticos e exemplificações, chegando nas Cadeias de Markov que foi abordada de uma forma bem simples voltada mais para multiplicação de matrizes e como chegar nessas matrizes. Depois pegou essas teorias e foi aplicada, através da modelagem, em um supermercado de pequeno porte no controle de estoque de molho de tomate usando as cadeias de Markov, possibilitando a previsão de pedidos futuros junto ao fornecedor. O trabalho é fruto do Mestrado Profissional e foi escrito com intenção de que docentes e estudantes do ensino médio possam compreender as resoluções dos exemplos apresentados.

La these comporte une partie theorique sur la stabilite des systemes dynamiques a evenements discrets, et une partie plus appliquee sur le controle de flux dans les reseaux de telecommunication, qui a motive la premiere et en utilise les techniques. Dans la premiere partie, on s'interesse tout d'abord a l'approche markovienne ou approche en espace de la stabilite des systemes a evenements discrets. On applique notamment la methode dite des limites fluides a un reseau de files d'attente mixte, a la fois ouvert et ferme. On considere ensuite l'approche trajectorielle ou approche en temps de la stabilite. Dans un premier temps, on presente la regle de saturation pour les systemes monotones-homogenes et separables, qui s'applique par exemple aux reseaux de files d'attente a une seule classe de clients. On demontre ensuite la regle de saturation en boucle fermee pour les systemes monotones-invariants, qui s'applique a certains reseaux de files d'attente a plusieurs classes de clients. La deuxieme partie se consacre au controle de flux dans les reseaux de telecommunication. On presente tout d'abord les objectifs du controle de flux et les principaux mecanismes utilises. On etudie ensuite les performances du controle de flux a fenetre statique. On considere notamment l'influence des caracteristiques statistiques du trafic transverse sur l'efficacite du controle de flux. Enfin, on s'interesse au controle de flux a fenetre dynamique, utilise par le protocole tcp dans l'internet. On etudie l'allocation et l'utilisation des ressources du reseau realisees par les versions reno et vegas de tcp.

Made available in DSpace on 2015-03-03T15:28:32Z (GMT). No. of bitstreams: 1 LenilsonPS_DISSERT.pdf: 421189 bytes, checksum: 22f993fe2b8033189672f2dec900232c (MD5) Previous issue date: 2010-06-15
In production lines, the entire process is bound to unexpected happenings which may cost losing the production quality. Thus, it means losses to the manufacturer. Identify such causes and remove them is the task of the processing management. The on-line control system consists of periodic inspection of every month produced item. Once any of those items is quali ed as not t, it is admitted that a change in the fraction of the items occurred, and then the process is stopped for adjustments. This work is an extension of Quinino & Ho (2010) and has as objective main to make the monitoramento in a process through the control on-line of quality for the number of non-conformities about the inspected item. The strategy of decision to verify if the process is under control, is directly associated to the limits of the graphic control of non-conformities of the process. A policy of preventive adjustments is incorporated in order to enlarge the conforming fraction of the process. With the help of the R software, a sensibility analysis of the proposed model is done showing in which situations it is most interesting to execute the preventive adjustment
Numa linha de produ??o, todo processo est? sujeito a ocorr?ncias de causas que venham a aparecer causando perdas na qualidade do produto e consequentemente preju?zos ao fabricante. Identificar essas causas e remov?-las ? tarefa do respons?vel pelo monitoramento do processo. Este trabalho tem como objetivo principal fazer o monitoramento num processo atrav?s do controle on-line de qualidade por atributos, considerando o n?mero de n?o-conformidades no item inspecionado. A estrat?gia de decis?o para verificar se o processo est? sob controle, est? diretamente associado aos limites de controle do gr?fico de n?o-conformidades do processo. Uma pol?tica de ajustes preventivos ? incorporada com o objetivo de aumentar a fra??o conforme do processo. Com o aux?lio do software R, ? feita uma an?lise de sensibilidade do modelo proposto mostrando em que situa??es ? mais interessante fazer o ajuste preventivo

Powder mixing is an essential operation in various industrial fields, such as pharmaceuticals, agro-food, cements, etc. Continuous powder mixing, as an alternative to conventional batch mixing, has attracted a lot of interest mainly due to its capacity in handling high volume manufacturing. This work aims at the contribution to the implementation of process control applications for powder mixing in a pilot-scale continuous mixer. Prior to developing process control strategies, new developments have been presented for better understanding continuous mixing of two components. Hold-up weight and relative hold-up weight distribution of each component in the whole mixer have been experimentally investigated under different operating conditions. An improved Markov chain model has been finally presented to predict the mean concentration of the mixtures obtained at the mixer's outlet. The implementation of a proportional-integral-derivative (PID) controller has been experimentally performed as an initial attempt to real-time control the homogeneity of the mixture produced. The rotational speed of the stirrer, identified as an important deciding factor towards the mixer's efficiency, has been considered as the manipulated variable. The closed-loop control is based on either the mean concentration or the relative standard deviation. The performances of the proposed closed-loops have been evaluated for continuous mixing subjected to step changes in feed rates of the mixer. Four case studies have been defined and presented. The main challenge in the process control system is the tuning of PID parameters. The performance of closed-loop control of either the mean concentration or the relative standard deviation has been compared to open-loop operation.

Made available in DSpace on 2015-03-03T15:22:32Z (GMT). No. of bitstreams: 1 RenataMR.pdf: 665159 bytes, checksum: 6d95fdc9fbeffbdaabe5793488839df3 (MD5) Previous issue date: 2009-03-02
Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior
The on-line processes control for attributes consists of inspecting a single item at every m produced ones. If the examined item is conforming, the production continues; otherwise, the process stops for adjustment. However, in many practical situations, the interest consist of monitoring the number of non-conformities among the examined items. In this case, if the number of non-conformities is higher than an upper control limit, the process needs to be stopped and some adjustment is required. The contribution of this paper is to propose a control system for the number of nonconforming of the inspected item. Employing properties of an ergodic Markov chain, an expression for the expected cost per item of the control system was obtained and it will be minimized by two parameters: the sampling interval and the upper limit control of the non-conformities of the examined item. Numerical examples illustrate the proposed procedure
O procedimento usual de controle on-line de processo por atributos consiste em inspecionar um item a cada m itens produzidos. Se o item examinado for conforme, a produ??o continua; caso contr?rio p?ra-se o processo. No entanto, em muitas situa??es pr?ticas, nem sempre existe interesse em classificar o item como defeituoso ou n?o defeituoso, mas sim monitorar o n?mero de n?o-conformidades no item inspecionado. Neste caso, se o n?mero de n?o-conformidades for superior a um limite de controle, p?ra-se o processo para o ajuste. A contribui??o deste trabalho est? em propor um sistema de controle on-line baseado no n?mero de n?o-conformidades do item inspecionado. Atrav?s das propriedades de uma cadeia de Markov erg?dica, obteve-se uma express?o anal?tica do custo m?dio por item produzido do sistema de controle on-line que pode ser minimizada por dois par?metros: o intervalo entre inspe??es e o limite superior de controle para o n?mero de n?o-conformidades no item inspecionado. Um exemplo num?rico ilustra o procedimento proposto

Made available in DSpace on 2014-12-17T14:53:03Z (GMT). No. of bitstreams: 1 AndreLSR_DISSERT.pdf: 1376512 bytes, checksum: 77587a4d46a8d965b17b7df02200c5a6 (MD5) Previous issue date: 2010-12-29
Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior
This paper proposes a procedure to control on-line processes for attributes, using an Shewhart control chart with two control limits (warning limit and control limit) and will be based on a sequence of inspection (h). The inspection procedure is based on Taguchi et al. (1989), in which to inspect the item, if the number of non-conformities is higher than an upper control limit, the process needs to be stopped and some adjustment is required; and, if the last inspection h, from all items inspected present a number of non-conformities between the control limit and warning limit. The items inspected will suffer destructive inspection, being discarded after inspection. Properties of an ergodic Markov chain are used to get the expression of average cost per item and the aim was the determination of four optimized parameters: the sampling interval of the inspections (m); the constant W to draw the warning limit (W); the constant C to draw the control limit (C), where W ? C, and the length of sequence of inspections (h). Numerical examples illustrate the proposed procedure
Este trabalho prop?e um procedimento de controle on-line de processos por atributos, utilizando um gr?fico de Shewhart com dois Limites de Controle (Limite de Advert?ncia e Limite de Controle) e ser? baseado numa sequ?ncia de inspe??o (h). O procedimento de inspe??o ? baseado em Taguchi et al. (1989). Assim, ao inspecionar o item, o processo ? parado para ajuste se o n?mero de n?o conformidades for superior ao Limite de Controle; como tamb?m se nas ?ltimas h inspe??es, todos os h itens inspecionados apresentarem um n?mero de n?o-conformidades entre os Limites de Advert?ncia e de Controle. Utilizando-se de propriedades de uma Cadeia de Markov Erg?dica, foi obtida uma express?o do custo m?dio do sistema de controle, que pode ser minimizada por quatro par?metros: Intervalo entre inspe??es (m), Limite de Advert?ncia (W), Limite de controle (C, em que W ≤ C) e o tamanho da sequ?ncia de inspe??o (h). Um exemplo num?rico ilustra o procedimento proposto

In this thesis, we study the problem of identifying an anomalous arm in a multi-armed bandit as quickly as possible, subject to an upper bound on the error probability. Also known as odd arm identification, this problem falls within the class of optimal stopping problems in decision theory and can be embedded within the framework of active sequential hypothesis testing. Prior works on odd arm identification dealt with independent and identically distributed observations from each arm. We provide the first known extension to the case of Markov observations from each arm. Our analysis and results are in the asymptotic regime of vanishing error probability. We associate with each arm an ergodic discrete time Markov process that evolves on a common, finite state space. The notion of anomaly is that the transition probability matrix (TPM) of the Markov process of one of the arms (the {\em odd arm}) is some $P_{1}$, and that of each non-odd arm is a different $P_{2}$, $P_{2}\neq P_{1}$. A learning agent whose goal it is to find the odd arm samples the arms sequentially, one at any given time, and observes the state of the Markov process of the sampled arm. The Markov processes of the unobserved arms may either remain frozen at their last observed states until their next sampling instant ({\em rested arms}) or continue to undergo state evolution ({\em restless arms}). The TPMs $P_{1}$ and $P_{2}$ may be known to the learning agent beforehand or unknown. We analyse the following cases: (a) rested arms with TPMs unknown, (b) restless arms with TPMs known, and (c) restless arms with TPMs unknown. For each of these cases, we first present an asymptotic lower bound on the {\color{black} growth rate of the }expected time required to find the odd arm, and subsequently devise a sequential arm selection policy which we show achieves the lower bound and is therefore asymptotically optimal. A key ingredient in our analysis of the setting of rested arms is the observation that for the Markov process of each arm, the long term fraction of entries into a state is equal to the long term fraction of exits from the state (global balance). When the arms are restless, it is necessary for the learning agent to keep track of the time since each arm was last sampled (arm's {\em delay}) and the state of each arm when it was last sampled (arm's {\em last observed state}). We show that the arm delays and the last observed states form a controlled Markov process which is ergodic under any stationary arm selection policy that picks each arm with a strictly positive probability. Our approach of considering the delays and the last observed states of all the arms jointly offers a global perspective of the arms and serves as a `lift' from the local perspective of dealing with the delay and the last observed state of each arm separately, one that is suggested by the prior works. Lastly, when the TPMs are unknown and have to be estimated along the way, it is important to ensure that the estimates converge almost surely to their true values asymptotically, i.e., the system is {\em identifiable}. We show identifiability follows from the ergodic theorem in the rested case, and provide sufficient conditions for it in the restless case.
Department of Science and Technology, Ministry of Human Resource Development, Center for Networked Intelligence, Robert Bosch Center for Cyber-Physical Systems

By equipping vehicles with the on-board wireless facility, the newly emerged vehicular networking targets to provision the broadband serves to vehicles. As such, a variety of novel and exciting applications can be provided to vehicular users to enhance their road safety and travel comfort, and finally raise a complete change to their on-road life. As the content distribution and media/video streaming, such as Youtube, Netflix, nowadays have become the most popular Internet applications, to enable the efficient content distribution and audio/video streaming services is thus of the paramount importance to the success of the vehicular networking. This, however, is fraught with fundamental challenges due to the distinguished natures of vehicular networking. On one hand, the vehicular communication is challenged by the spotty and volatile wireless connections caused by the high mobility of vehicles. This makes the download performance of connections very unstable and dramatically change over time, which directly threats to the on-top media applications. On the other hand, a vehicular network typically involves an extremely large-scale node population (e.g., hundreds or thousandths of vehicles in a region) with intense spatial and temporal variations across the network geometry at different times. This dictates any designs to be scalable and fully distributed which should not only be resilient to the network dynamics, but also provide the guaranteed quality-of-service (QoS) to users. The purpose of this dissertation is to address the challenges of the vehicular networking imposed by its intrinsic dynamic and large-scale natures, and build the efficient, scalable and, more importantly, practical systems to enable the cost-effective and QoS guaranteed content distribution and media streaming services to vehicular users. Note that to effective- ly deliver the content from the remote Internet to in-motion vehicles, it typically involves three parts as: 1.) an infrastructure grid of gateways which behave as the data depots or injection points of Internet contents and services to vehicles, 2.) protocol at gateways which schedules the bandwidth resource at gateways and coordinates the parallel transmissions to different vehicles, and 3.) the end-system control mechanism at receivers which adapts the receiver’s content download/playback strategy based on the available network throughput to provide users with the desired service experience. With above three parts in mind, the entire research work in this dissertation casts a systematic view to address each part in one topic with: 1.) design of large-scale cost-effective content distribution infrastructure, 2.) MAC (media access control) performance evaluation and channel time scheduling, and 3.) receiver adaptation and adaptive playout in dynamic download environment. In specific, in the first topic, we propose a practical solution to form a large-scale and cost-effective content distribution infrastructure in the city. We argue that a large-scale infrastructure with the dedicated resources, including storage, computing and communication capacity, is necessary for the vehicular network to become an alternative of 3G/4G cellular network as the dominating approach of ubiquitous content distribution and data services to vehicles. On addressing this issue, we propose a fully distributed scheme to form a large-scale infrastructure by the contributions of individual entities in the city, such as grocery stores, movie theaters, etc. That is to say, the installation and maintenance costs are shared by many individuals. In this topic, we explain the design rationale on how to motivate individuals to contribute, and specify the detailed design of the system, which is embodied with distributed protocols and performance evaluation. The second topic investigates on the MAC throughput performance of the vehicle-to- infrastructure (V2I) communications when vehicles drive through RSUs, namely drive-thru Internet. Note that with a large-scale population of fast-motion nodes contending the chan- nel for transmissions, the MAC performance determines the achievable nodal throughput and is crucial to the on-top applications. In this topic, using a simple yet accurate Marko- vian model, we first show the impacts of mobility (characterized by node velocity and moving directions) on the nodal and system throughput performance, respectively. Based on this analysis, we then propose three enhancement schemes to timely adjust the MAC parameters in tune with the vehicle mobility to achieve the maximal the system throughput. The last topic investigates on the end-system design to deliver the user desired media streaming services in the vehicular environment. In specific, the vehicular communications are notoriously known for the intermittent connectivity and dramatically varying throughput. Video streaming on top of vehicular networks therefore inevitably suffers from the severe network dynamics, resulting in the frequent jerkiness or even freezing video playback. To address this issue, an analytical model is first developed to unveil the impacts of network dynamics on the resultant video performance to users in terms of video start-up delay and smoothness of playback. Based on the analysis, the adaptive playout buffer mechanism is developed to adapt the video playback strategy at receivers towards the user-defined video quality. The proposals developed in the three topics are validated with the extensive and high fidelity simulations. We believe that our analysis developed in the dissertation can provide insightful lights on understanding the fundamental performance of the vehicular content distribution networks from the aspects of session-level download performance in urban vehicular networks (topic 1), MAC throughput performance (topic 2), and user perceived media quality (topic 3). The protocols developed in the three topics, respectively, offer practical and efficient solutions to build and optimize the vehicular content distribution networks.