Stochastic processes and their applications semi-markov analysis of some inventory and queuing problems

This thesis analyses certain problems in Inventories and Queues. There are many situations in real-life where we encounter models as described in this thesis. It analyses in depth various models which can be applied to production, storag¢, telephone traffic, road traffic, economics, business administration, serving of customers, operations of particle counters and others. Certain models described here is not a complete representation of the true situation in all its complexity, but a simplified version amenable to analysis. While discussing the models, we show how a dependence structure can be suitably introduced in some problems of Inventories and Queues. Continuous review, single commodity inventory systems with Markov dependence structure introduced in the demand quantities, replenishment quantities and reordering levels are considered separately. Lead time is assumed to be zero in these models. An inventory model involving random lead time is also considered (Chapter-4). Further finite capacity single server queueing systems with single/bulk arrival, single/bulk services are also discussed. In some models the server is assumed to go on vacation (Chapters 7 and 8). In chapters 5 and 6 a sort of dependence is introduced in the service pattern in some queuing models.

Variation in habitat choice and delayed reproduction: Adaptive queuing strategies or individual quality differences?

In most species, some individuals delay reproduction or occupy inferior breeding positions. The queue hypothesis tries to explain both patterns by proposing that individuals strategically delay breeding (queue) to acquire better breeding or social positions. In 1995, Ens, Weissing, and Drent addressed evolutionarily stable queuing strategies in situations with habitat heterogeneity. However, their model did not consider the non - mutually exclusive individual quality hypothesis, which suggests that some individuals delay breeding or occupy inferior breeding positions because they are poor competitors. Here we extend their model with individual differences in competitive abilities, which are probably plentiful in nature. We show that including even the smallest competitive asymmetries will result in individuals using queuing strategies completely different from those in models that assume equal competitors. Subsequently, we investigate how well our models can explain settlement patterns in the wild, using a long-term study on oystercatchers. This long-lived shorebird exhibits strong variation in age of first reproduction and territory quality. We show that only models that include competitive asymmetries can explain why oystercatchers' settlement patterns depend on natal origin. We conclude that predictions from queuing models are very sensitive to assumptions about competitive asymmetries, while detecting such differences in the wild is often problematic.

Energy-based Fair Queuing: Energy-centric Processor Scheduling Algorithm for Battery-limited Mobile Systems

Los dispositivos móviles modernos disponen cada vez de más funcionalidad debido al rápido avance de las tecnologías de las comunicaciones y computaciones móviles. Sin embargo, la capacidad de la batería no ha experimentado un aumento equivalente. Por ello, la experiencia de usuario en los sistemas móviles modernos se ve muy afectada por la vida de la batería, que es un factor inestable de difícil de control. Para abordar este problema, investigaciones anteriores han propuesto un esquema de gestion del consumo (PM) centrada en la energía y que proporciona una garantía sobre la vida operativa de la batería mediante la gestión de la energía como un recurso de primera clase en el sistema. Como el planificador juega un papel fundamental en la administración del consumo de energía y en la garantía del rendimiento de las aplicaciones, esta tesis explora la optimización de la experiencia de usuario para sistemas móviles con energía limitada desde la perspectiva de un planificador que tiene en cuenta el consumo de energía en un contexto en el que ésta es un recurso de primera clase. En esta tesis se analiza en primer lugar los factores que contribuyen de forma general a la experiencia de usuario en un sistema móvil. Después se determinan los requisitos esenciales que afectan a la experiencia de usuario en la planificación centrada en el consumo de energía, que son el reparto proporcional de la potencia, el cumplimiento de las restricciones temporales, y cuando sea necesario, el compromiso entre la cuota de potencia y las restricciones temporales. Para cumplir con los requisitos, el algoritmo clásico de fair queueing y su modelo de referencia se extienden desde los dominios de las comunicaciones y ancho de banda de CPU hacia el dominio de la energía, y en base a ésto, se propone el algoritmo energy-based fair queueing (EFQ) para proporcionar una planificación basada en la energía. El algoritmo EFQ está diseñado para compartir la potencia consumida entre las tareas mediante su planificación en función de la energía consumida y de la cuota reservada. La cuota de consumo de cada tarea con restricciones temporales está protegida frente a diversos cambios que puedan ocurrir en el sistema. Además, para dar mejor soporte a las tareas en tiempo real y multimedia, se propone un mecanismo para combinar con el algoritmo EFQ para dar preferencia en la planificación durante breves intervalos de tiempo a las tareas más urgentes con restricciones temporales.Las propiedades del algoritmo EFQ se evaluan a través del modelado de alto nivel y la simulación. Los resultados de las simulaciones indican que los requisitos esenciales de la planificación centrada en la energía pueden lograrse. El algoritmo EFQ se implementa más tarde en el kernel de Linux. Para evaluar las propiedades del planificador EFQ basado en Linux, se desarrolló un banco de pruebas experimental basado en una sitema empotrado, un programa de banco de pruebas multihilo, y un conjunto de pruebas de código abierto. A través de experimentos específicamente diseñados, esta tesis verifica primero las propiedades de EFQ en la gestión de la cuota de consumo de potencia y la planificación en tiempo real y, a continuación, explora los beneficios potenciales de emplear la planificación EFQ en la optimización de la experiencia de usuario para sistemas móviles con energía limitada. Los resultados experimentales sobre la gestión de la cuota de energía muestran que EFQ es más eficaz que el planificador de Linux-CFS en la gestión de energía, logrando un reparto proporcional de la energía del sistema independientemente de en qué dispositivo se consume la energía. Los resultados experimentales en la planificación en tiempo real demuestran que EFQ puede lograr de forma eficaz, flexible y robusta el cumplimiento de las restricciones temporales aunque se dé el caso de aumento del el número de tareas o del error en la estimación de energía. Por último, un análisis comparativo de los resultados experimentales sobre la optimización de la experiencia del usuario demuestra que, primero, EFQ es más eficaz y flexible que los algoritmos tradicionales de planificación del procesador, como el que se encuentra por defecto en el planificador de Linux y, segundo, que proporciona la posibilidad de optimizar y preservar la experiencia de usuario para los sistemas móviles con energía limitada. Abstract Modern mobiledevices have been becoming increasingly powerful in functionality and entertainment as the next-generation mobile computing and communication technologies are rapidly advanced. However, the battery capacity has not experienced anequivalent increase. The user experience of modern mobile systems is therefore greatly affected by the battery lifetime,which is an unstable factor that is hard to control. To address this problem, previous works proposed energy-centric power management (PM) schemes to provide strong guarantee on the battery lifetime by globally managing energy as the first-class resource in the system. As the processor scheduler plays a pivotal role in power management and application performance guarantee, this thesis explores the user experience optimization of energy-limited mobile systemsfrom the perspective of energy-centric processor scheduling in an energy-centric context. This thesis first analyzes the general contributing factors of the mobile system user experience.Then itdetermines the essential requirements on the energy-centric processor scheduling for user experience optimization, which are proportional power sharing, time-constraint compliance, and when necessary, a tradeoff between the power share and the time-constraint compliance. To meet the requirements, the classical fair queuing algorithm and its reference model are extended from the network and CPU bandwidth sharing domain to the energy sharing domain, and based on that, the energy-based fair queuing (EFQ) algorithm is proposed for performing energy-centric processor scheduling. The EFQ algorithm is designed to provide proportional power shares to tasks by scheduling the tasks based on their energy consumption and weights. The power share of each time-sensitive task is protected upon the change of the scheduling environment to guarantee a stable performance, and any instantaneous power share that is overly allocated to one time-sensitive task can be fairly re-allocated to the other tasks. In addition, to better support real-time and multimedia scheduling, certain real-time friendly mechanism is combined into the EFQ algorithm to give time-limited scheduling preference to the time-sensitive tasks. Through high-level modelling and simulation, the properties of the EFQ algorithm are evaluated. The simulation results indicate that the essential requirements of energy-centric processor scheduling can be achieved. The EFQ algorithm is later implemented in the Linux kernel. To assess the properties of the Linux-based EFQ scheduler, an experimental test-bench based on an embedded platform, a multithreading test-bench program, and an open-source benchmark suite is developed. Through specifically-designed experiments, this thesis first verifies the properties of EFQ in power share management and real-time scheduling, and then, explores the potential benefits of employing EFQ scheduling in the user experience optimization for energy-limited mobile systems. Experimental results on power share management show that EFQ is more effective than the Linux-CFS scheduler in managing power shares and it can achieve a proportional sharing of the system power regardless of on which device the energy is spent. Experimental results on real-time scheduling demonstrate that EFQ can achieve effective, flexible and robust time-constraint compliance upon the increase of energy estimation error and task number. Finally, a comparative analysis of the experimental results on user experience optimization demonstrates that EFQ is more effective and flexible than traditional processor scheduling algorithms, such as those of the default Linux scheduler, in optimizing and preserving the user experience of energy-limited mobile systems.

Service Capacity Reserve under Uncertainty by Hospital’s ER Analogies: A Practical Model for Car Services

We define a capacity reserve model to dimension passenger car service installations according to the demographic distribution of the area to be serviced by using hospital?s emergency room analogies. Usually, service facilities are designed applying empirical methods, but customers arrive under uncertain conditions not included in the original estimations, and there is a gap between customer?s real demand and the service?s capacity. Our research establishes a valid methodology and covers the absence of recent researches and the lack of statistical techniques implementation, integrating demand uncertainty in a unique model built in stages by implementing ARIMA forecasting, queuing theory, and Monte Carlo simulation to optimize the service capacity and occupancy, minimizing the implicit cost of the capacity that must be reserved to service unexpected customers. Our model has proved to be a useful tool for optimal decision making under uncertainty integrating the prediction of the cost implicit in the reserve capacity to serve unexpected demand and defining a set of new process indicators, such us capacity, occupancy, and cost of capacity reserve never studied before. The new indicators are intended to optimize the service operation. This set of new indicators could be implemented in the information systems used in the passenger car services.

Service capacity reserve under uncertainty by hospital's ER's analogies: a practical model for car services

El objetivo de esta investigación consiste en definir un modelo de reserva de capacidad, por analogías con emergencias hospitalarias, que pueda ser implementado en el sector de servicios. Este está específicamente enfocado a su aplicación en talleres de servicio de automóviles. Nuestra investigación incorpora la incertidumbre de la demanda en un modelo singular diseñado en etapas que agrupa técnicas ARIMA, teoría de colas y simulación Monte Carlo para definir los conceptos de capacidad y ocupación de servicio, que serán utilizados para minimizar el coste implícito de la reserva capacidad necesaria para atender a clientes que carecen de cita previa. Habitualmente, las compañías automovilísticas estiman la capacidad de sus instalaciones de servicio empíricamente, pero los clientes pueden llegar bajo condiciones de incertidumbre que no se tienen en cuenta en dichas estimaciones, por lo que existe una diferencia entre lo que el cliente realmente demanda y la capacidad que ofrece el servicio. Nuestro enfoque define una metodología válida para el sector automovilístico que cubre la ausencia genérica de investigaciones recientes y la habitual falta de aplicación de técnicas estadísticas en el sector. La equivalencia con la gestión de urgencias hospitalarias se ha validado a lo largo de la investigación en la se definen nuevos indicadores de proceso (KPIs) Tal y como hacen los hospitales, aplicamos modelos estocásticos para dimensionar las instalaciones de servicio de acuerdo con la distribución demográfica del área de influencia. El modelo final propuesto integra la predicción del coste implícito en la reserva de capacidad para atender la demanda no prevista. Asimismo, se ha desarrollado un código en Matlab que puede integrarse como un módulo adicional a los sistemas de información (DMS) que se usan actualmente en el sector, con el fin de emplear los nuevos indicadores de proceso definidos en el modelo. Los resultados principales del modelo son nuevos indicadores de servicio, tales como la capacidad, ocupación y coste de reserva de capacidad, que nunca antes han sido objeto de estudio en la industria automovilística, y que están orientados a gestionar la operativa del servicio. ABSTRACT Our aim is to define a Capacity Reserve model to be implemented in the service sector by hospital's emergency room (ER) analogies, with a practical approach to passenger car services. A stochastic model has been implemented using R and a Monte Carlo simulation code written in Matlab and has proved a very useful tool for optimal decision making under uncertainty. The research integrates demand uncertainty in a unique model which is built in stages by implementing ARIMA forecasting, Queuing Theory and a Monte Carlo simulation to define the concepts of service capacity and occupancy, minimizing the implicit cost of the capacity that must be reserved to service unexpected customers. Usually, passenger car companies estimate their service facilities capacity using empirical methods, but customers arrive under uncertain conditions not included in the estimations. Thus, there is a gap between customer’s real demand and the dealer’s capacity. This research sets a valid methodology for the passenger car industry to cover the generic absence of recent researches and the generic lack of statistical techniques implementation. The hospital’s emergency room (ER) equalization has been confirmed to be valid for the passenger car industry and new process indicators have been defined to support the study. As hospitals do, we aim to apply stochastic models to dimension installations according to the demographic distribution of the area to be serviced. The proposed model integrates the prediction of the cost implicit in the reserve capacity to serve unexpected demand. The Matlab code could be implemented as part of the existing information technology systems (ITs) to support the existing service management tools, creating a set of new process indicators. Main model outputs are new indicators, such us Capacity, Occupancy and Cost of Capacity Reserve, never studied in the passenger car service industry before, and intended to manage the service operation.

Spin glasses on the hypercube

We present a mean field model for spin glasses with a natural notion of distance built in, namely, the Edwards-Anderson model on the diluted D-dimensional unit hypercube in the limit of large D. We show that finite D effects are strongly dependent on the connectivity, being much smaller for a fixed coordination number. We solve the nontrivial problem of generating these lattices. Afterward, we numerically study the nonequilibrium dynamics of the mean field spin glass. Our three main findings are the following: i the dynamics is ruled by an infinite number of time sectors, ii the aging dynamics consists of the growth of coherent domains with a nonvanishing surface-volume ratio, and iii the propagator in Fourier space follows the p4 law. We study as well the finite D effects in the nonequilibrium dynamics, finding that a naive finite size scaling ansatz works surprisingly well.

A Kinetic Vlasov Model for Plasma Simulation Using Discontinuous Galerkin Method on Many-Core Architectures

Thesis (Ph.D.)--University of Washington, 2016-03

Unified model for performance analysis of IEEE 802.11 ad hoc networks in unsaturated conditions

IEEE 802.11 standard has achieved huge success in the past decade and is still under development to provide higher physical data rate and better quality of service (QoS). An important problem for the development and optimization of IEEE 802.11 networks is the modeling of the MAC layer channel access protocol. Although there are already many theoretic analysis for the 802.11 MAC protocol in the literature, most of the models focus on the saturated traffic and assume infinite buffer at the MAC layer. In this paper we develop a unified analytical model for IEEE 802.11 MAC protocol in ad hoc networks. The impacts of channel access parameters, traffic rate and buffer size at the MAC layer are modeled with the assistance of a generalized Markov chain and an M/G/1/K queue model. The performance of throughput, packet delivery delay and dropping probability can be achieved. Extensive simulations show the analytical model is highly accurate. From the analytical model it is shown that for practical buffer configuration (e.g. buffer size larger than one), we can maximize the total throughput and reduce the packet blocking probability (due to limited buffer size) and the average queuing delay to zero by effectively controlling the offered load. The average MAC layer service delay as well as its standard deviation, is also much lower than that in saturated conditions and has an upper bound. It is also observed that the optimal load is very close to the maximum achievable throughput regardless of the number of stations or buffer size. Moreover, the model is scalable for performance analysis of 802.11e in unsaturated conditions and 802.11 ad hoc networks with heterogenous traffic flows. © 2012 KSI.

An approximate method for the solution of an influence function foil rolling model

Fleck and Johnson (Int. J. Mech. Sci. 29 (1987) 507) and Fleck et al. (Proc. Inst. Mech. Eng. 206 (1992) 119) have developed foil rolling models which allow for large deformations in the roll profile, including the possibility that the rolls flatten completely. However, these models require computationally expensive iterative solution techniques. A new approach to the approximate solution of the Fleck et al. (1992) Influence Function Model has been developed using both analytic and approximation techniques. The numerical difficulties arising from solving an integral equation in the flattened region have been reduced by applying an Inverse Hilbert Transform to get an analytic expression for the pressure. The method described in this paper is applicable to cases where there is or there is not a flat region.