An ever increasing demand for instant and reliable information on modern communication networks forces codewords to operate in a non-asymptotic regime. To achieve reliability for imperfect channels in this regime, codewords need to be retransmitted from receiver to the transmit buffer, aided by a fast feedback mechanism. Large occupancy of this buffer results in longer communication delays. Therefore, codewords need to be designed carefully to reduce transmit queue-length and thus the delay experienced in this buffer. We first study the consequences of physical layer decisions on the transmit buffer occupancy. We develop an analytical framework to relate physical layer channel to the transmit buffer occupancy. We compute the optimal code-rate for finite-length codewords operating over a correlated channel, under certain communication service guarantees. We show that channel memory has a significant impact on this optimal code-rate. Next, we study the delay in small ad-hoc networks. In particular, we find out what rates can be supported on a small network, when each flow has a certain end-to-end service guarantee. To this end, service guarantee at each intermediate link is characterized. These results are applied to study the potential benefits of setting up a network suitable for network coding in multicast. In particular, we quantify the gains of network coding over classic routing for service provisioned multicast communication over butterfly networks. In the wireless setting, we study the trade-off between communications gains achieved by network coding and the cost to set-up a network enabling network coding. In particular, we show existence of scenarios where one should not attempt to create a network suitable for coding. Insights obtained from these studies are applied to design a distributed rate control algorithm in a large network. This algorithm maximizes sum-utility of all flows, while satisfying per-flow end-to-end service guarantees. We introduce a notion of effective-capacity per communication link that captures the service requirements of flows sharing this link. Each link maintains a price and effective-capacity, and each flow maintains rate and dissatisfaction. Flows and links update their respective variables locally, and we show that their decisions drive the system to an optimal point. We implemented our algorithm on a network simulator and studied its convergence behavior on few networks of practical interest.

Dans cette thèse, nous nous sommes consacrés au problème d'interaction d'échelles selon deux angles distincts : d'une part une approche globale et grande échelle du système climatique qui nous a permis d'étudier la modulation basse fréquence d'ENSO, d'autre part une démarche plus locale au cours de laquelle nous avons étudié plus particulièrement la dynamique du Pacifique tropical est et du système de courants de Humboldt au large du Pérou. La première partie a été motivée par une approche relativement récente dans la communauté des climatologues. Il s'agit de la question cruciale de la variabilité basse fréquence d'ENSO, et de la possibilité que celle-ci puisse émerger " simplement " du système climatique tropical, sans action extérieure qu'elle soit stochastique ou en lien avec la variabilité des plus hautes latitudesDans ce contexte particulier, il est alors question de mécanismes nonlinéaires pour expliquer comment la stabilité d'ENSO peut être influencée par la variabilité climatique. Ceci a servi d'hypothèse de travail pour l'ensemble de cette thèse. Nous avons ainsi abordé la possibilité qu'ENSO pouvait être rectifié sur des échelles de temps longues (interdécennales) par la modulation de la nonlinéarité elle-même. Pour cela, nous avons utilisé des méthodes mathématiques originales qui nous ont permis d'une part de détecter des changements brusques (statistiquement significatifs) de l'état moyen du Pacifique tropical et d'autre part d'accéder à un proxy de la nonlinéarité intégrée dans le système tropical. En combinant ces deux démarches, nous avons pu mettre en évidence une boucle de rétroaction auto entretenue sur des échelles de temps longues qui serait pilotée par des mécanismes nonlinéaires qui auraient la capacité de faire interférer diverses échelles temporelles et ainsi de transférer l'énergie des basses fréquences (état moyen du pacifique tropical) vers les hautes fréquences (oscillation australe) et vice-versa. Dans la seconde partie de cette thèse nous nous sommes focalisés sur la modélisation climatique du Pacifique tropical oriental. En effet, cette région, pourtant au cœur des préoccupations de la communauté scientifique en raison de son écosystème parmi les plus productifs de la planète, reste mal connue du point de vue des processus océanographiques et climatiques. En particulier, les modèles climatiques globaux présentent des biais importants dans cette région en terme d'état climatologique moyen. Nous avons testé, dans une approche de modélisation haute résolution, différentes sources possibles de ces biais : les caractéristiques bathymétriques des îles Galápagos (mal représentées dans les modèles globaux) capables de par leur position équatoriale de modifier la circulation régionale moyenne et donc le bilan thermodynamique; ou alors les processus associés aux mélanges turbulents (et par extension les processus nonlinéaires) à l'aide d'un modèle régional. Pour ce faire, nous avons procédé à des expériences de sensibilité qui nous ont permis d'une part de relativiser le rôle de l'archipel des Galápagos comme source de biais et d'autre part de mettre en exergue le rôle de la variabilité intra-saisonnière dans la rectification de l'état moyen du Pacifique tropical est.

An investigation into the impact of generalised maximum entropy solutions on the study of queues with or without arrival balking and their applications to congestion management in communication networks Keywords: Queues, Balking, Maximum Entropy (ME) Principle, Global Balance (GB), Queue Length Distribution (QLD), Generalised Geometric (GGeo), Generalised Exponential (GE), Generalised Discrete Half Normal (GdHN), Congestion Management, Packet Dropping Policy (PDP) Generalisations to links between discrete least biased (i.e. maximum entropy (ME)) distribution inferences and Markov chains are conjectured towards the performance modelling, analysis and prediction of general, single server queues with or without arrival balking. New ME solutions, namely the generalised discrete Half Normal (GdHN) and truncated GdHN (GdHNT) distributions are characterised, subject to appropriate mean value constraints, for inferences of stationary discrete state probability distributions. Moreover, a closed form global balance (GB) solution is derived for the queue length distribution (QLD) of the M/GE/1/K queue subject to extended Morse balking, characterised by a Poisson prospective arrival process, i.i.d. generalised exponential (GE) service times and finite capacity, K. In this context, based on comprehensive numerical experimentation, the latter GB solution is conjectured to be a special case of the GdHNT ME distribution. ii Owing to the appropriate operational properties of the M/GE/1/K queue subject to extended Morse balking, this queueing system is applied as an ME performance model of Internet Protocol (IP)-based communication network nodes featuring static or dynamic packet dropping congestion management schemes. A performance evaluation study in terms of the model’s delay is carried out. Subsequently, the QLD’s of the GE/GE/1/K censored queue subject to extended Morse balking under three different composite batch balking and batch blocking policies are solved via the technique of GB. Following comprehensive numerical experimentation, the latter QLD’s are also conjectured to be special cases of the GdHNT. Limitations of this work and open problems which have arisen are included after the conclusions.

Den här studien görs som avslutande del av universitetsutbildning, kandidatprogram i Industriell teknik inom ämnesområdet kvalitetsteknik. Studien kan användas för vidare verksamhetsutveckling och analys av röntgenavdelningens behov av produktivitetsmått, vid Visby lasarett. På grund av restriktioner relaterade till covid-19, samt det geografiska avståndet mellan Göteborg och Visby, utfördes studien på distans genom datainsamling från intervjuer och enkätundersökning. Vidare samlades information från vetenskaplig litteratur, lagar, förordningar och dokumentanalys. I studien användes ett abduktivt arbetssätt genom att induktivt analysera insamlad data och utifrån det formulera lämplig teoretisk bakgrund som sedan på ett deduktivt sätt kunde användas för att generera ett resultat och förbättringsförslag. För att analysera och argumentera för erhållna resultat användes vetenskapliga forskningsstudier, kvantitativ data från organisationen och statistiska verktyg. Använda teorier för studien baseras på offensiv kvalitetsutveckling, processledning och Lean Healthcare. DASIAS modell användes som metod för att på ett systematiskt sätt arbeta med data från diagnostisering av problemet till implementerings- och uppföljningsförslag. Genom studien beaktades de etiska aspekter och alla inblandade subjekt informerades med hänsyn till informations-, konfidentialitets-, anonymitets-, objektivitets-, nyttjandes- och samtyckeskraven. Erhållna resultat i form av produktivitetsmått relaterar till processkartläggning, produktivitet, flödeseffektivitet, vårdbehov, kapacitetberäkning, patientsäkerhet och kötider. Analysen visar att valda indikatorer kan användas för att förbättra verksamheten men förutsättning till detta är bättre verksamhetsplanering och effektivare resursutnyttjande för att uppnå en hög flödeseffektivitet och produktivitet. Slutsatsen är att valda indikatorer kan nyttjas för förbättringsåtgärder samt att prioriteringsområden bör väljas enligt 10M analysen. Studien lämnar vissa obesvarade frågeställningar som presenteras som förslag till framtida studier.Nyckelord: / This study is conducted as a final part of the University candidate program Industrial engineering and within the field of study quality technology. This study is suitable for business development as well for the analysis of the X-ray department's needs for productivity measures, at Visby Hospital. The study was carried out at a distance by data collection from the interviews, questionnaire survey and document analysis. An abductive approach was used to generate a result and suggestions for improvement. To analyse and argue for results obtained, scientific research studies, quantitative data from the organization, statistical tools, tables and diagrams were used. The theories for this work are based on TQM, BPM and Lean Healthcare. DASIA's model was used as a method to work in a systematic way with data from diagnosing the problem to implementation and follow-up proposals. The study took into account the ethical aspects and all the subjects involved were informed regarding ethical requirements. Results obtained in the form of productivity measures relate to process mapping, productivity, flow efficiency, care needs, capacity calculation, patient safety and healthcare waiting time. The analysis shows that selected indicators can be used to improve the business, but a condition for this is better business planning and more efficient resource utilization. The conclusion is that selected indicators can be used for improvement measures and that priority areas should be selected according to the 10M analysis. The study leaves some unanswered issues that are presented as proposal for future studies in the discussion chapter.

In my dissertation, I present ATLAS — the Auto-Training Look-Ahead Scheduler. ATLAS improves service to applications with regard to two non-functional properties: timeliness and overload detection. Timeliness is an important requirement to ensure user interface responsiveness and the smoothness of multimedia operations. Overload can occur when applications ask for more computation time than the machine can offer. Interactive systems have to handle overload situations dynamically at runtime. ATLAS provides timely service to applications, accessible through an easy-to-use interface. Deadlines specify timing requirements, workload metrics describe jobs. ATLAS employs machine learning to predict job execution times. Deadline misses are detected before they occur, so applications can react early.:1 Introduction 2 Anatomy of a Desktop Application 3 Real Simple Real-Time 4 Execution Time Prediction 5 System Scheduler 6 Timely Service 7 The Road Ahead Bibliography Index

An investigation into the impact of generalised maximum entropy solutions on the study of queues with or without arrival balking and their applications to congestion management in communication networks Keywords: Queues, Balking, Maximum Entropy (ME) Principle, Global Balance (GB), Queue Length Distribution (QLD), Generalised Geometric (GGeo), Generalised Exponential (GE), Generalised Discrete Half Normal (GdHN), Congestion Management, Packet Dropping Policy (PDP) Generalisations to links between discrete least biased (i.e. maximum entropy (ME)) distribution inferences and Markov chains are conjectured towards the performance modelling, analysis and prediction of general, single server queues with or without arrival balking. New ME solutions, namely the generalised discrete Half Normal (GdHN) and truncated GdHN (GdHNT) distributions are characterised, subject to appropriate mean value constraints, for inferences of stationary discrete state probability distributions. Moreover, a closed form global balance (GB) solution is derived for the queue length distribution (QLD) of the M/GE/1/K queue subject to extended Morse balking, characterised by a Poisson prospective arrival process, i.i.d. generalised exponential (GE) service times and finite capacity, K. In this context, based on comprehensive numerical experimentation, the latter GB solution is conjectured to be a special case of the GdHNT ME distribution. ii Owing to the appropriate operational properties of the M/GE/1/K queue subject to extended Morse balking, this queueing system is applied as an ME performance model of Internet Protocol (IP)-based communication network nodes featuring static or dynamic packet dropping congestion management schemes. A performance evaluation study in terms of the model’s delay is carried out. Subsequently, the QLD’s of the GE/GE/1/K censored queue subject to extended Morse balking under three different composite batch balking and batch blocking policies are solved via the technique of GB. Following comprehensive numerical experimentation, the latter QLD’s are also conjectured to be special cases of the GdHNT. Limitations of this work and open problems which have arisen are included after the conclusions

I Sverige har vårdköerna varit hett debatterade under större delen av 2000-talet. Detta berorpå att vårdköerna har blivit långa, vilket har lett till att politikerna stiftat lagar som stipulerarhur lång tid en patient ska få vänta på vård. Detta är den så kallade Vårdgarantin, som innebärbland annat att patienten inte ska behöva vänta längre än 90 dagar på kirurgisk vård efterfastställd diagnos. Trots Vårdgarantin har vårdköerna inte minskat, utan snarare ökat. Utifrån denna problematik är syftet att undersöka alternativkostnaden för samhället av att inteprioritera vårdkön. Vi gör detta genom att analysera operationer som har längre väntetid änvad Vårdgarantin föreskriver, och undersöker hur kostnadseffektiva operationerna är för attberäkna hur många år i full hälsa som går förlorade på grund av väntetiderna. Slutligendiskuterar vi vad regionens kostnader blir av att inte prioritera vårdköerna. För att svara på frågeställningarna gör vi en litteratursökning likt en tidigare studie nyligengenomförd i Irland för att undersöka kostnadseffektiviteten av kirurgiska behandlingar, ochdärefter jämföra kostnadseffektiviteten mot ett tröskelvärde för kostnadseffektivitet på 300000 SEK. Resultatet visar att en större investering i den svenska vårdkön vore mycketkostnadseffektivt, då operationernas kostnadseffektivitet är betydligt lägre än tröskelvärdet på300 000 SEK. I studien visar vi exempelvis att ingen av de sex interventionerna somundersöks kostar mer än 50 000 SEK per år i full hälsa, medan svenska beslutsfattare inomvårdsektorn är villiga att acceptera en kostnad uppemot 2 miljoner SEK under vissaförutsättningar. Det ska dock tilläggas att patienterna som står i vårdkö får vård till slut, ävenom det kan dröja flera år tills de får det. Vår slutsats är att patienter som väntar på vård är en nedprioriterad grupp i sjukvården, ochatt de representerar en alternativkostnad som beslutsfattare bör ta i beaktande vid andrainvesteringsmöjligheter gällande hälsa- och sjukvård. Vidare forskning bör bland annatutreda möjligheterna att förkorta väntetiderna. / The waiting lists for healthcare have been heavily debated in Sweden during the 21st century.It has been so because patients have been waiting for healthcare much longer than expected,which has led politicians to change the healthcare laws, promising to decrease the queuingtime for patients. This is the so-called Vårdgarantin (Healthcare Warranty), which, amongother things, says that a patient should not have to wait longer than 90 days for surgery, afterreferral. Despite Vårdgarantin, the waiting lists have not decreased, but rather increased. Based on this problem we have chosen to examine the opportunity cost for society of notprioritizing the healthcare waiting lists by analyzing which surgeries have longer waiting liststhan the Vårdgaranti prescribes. We will also examine how cost effective each surgery is andcalculate how many years at full health is lost in the population when society does notprioritize addressing the queues. Furthermore, we will discuss the Swedish regions’ (which isthe administrative unit in Sweden that is responsible for providing health care to its citizens)opportunity costs by not prioritizing the waiting list. To answer these issues, have we done a literature study, in the same fashion as researchers inIreland recently, to examine the cost effectiveness of surgeries and compare it to a 300 000SEK cost-effectiveness threshold. Our results show that it would be cost effective forSwedish regions to invest in reducing their waiting lists, due to relatively low costs per yearwith full health of surgeries with long waiting lists. In our study, all of the six includedinterventions cost less than 50 000 SEK per year in full health. This can be compared to theSwedish decision makers who sometimes are willing to pay up to 2 million SEK per year atfull health for the very ill under extraordinary circumstances. It should be noted that thepatients who are in the healthcare queue receive care in the end, even if it can take severalyears until the patients receive it. Conclusively, patients waiting for care is a deprioritized group in the healthcare sector andcan be seen as an opportunity cost when considering new investment opportunities. Furtherresearch should investigate the possibilities of how waiting times can be reduced.

Les files d'attente fluides sont des processus markoviens à deux dimensions, où la première composante, appelée le niveau, représente le contenu d'un réservoir et prend des valeurs continues, et la deuxième composante, appelée la phase, est l'état d'un processus markovien dont l'évolution contrôle celle du niveau. Le niveau de la file fluide varie linéairement avec un taux qui dépend de la phase et qui peut prendre n'importe quelle valeur réelle.<p><p>Dans cette thèse, nous explorons le lien entre les files fluides et les processus QBD, et nous appliquons des arguments utilisés en théorie des processus de renouvellement pour obtenir la distribution stationnaire de plusieurs modèles fluides.<p><p>Nous commençons par l'étude d'une file fluide avec un réservoir de taille infinie; nous déterminons sa distribution stationnaire, et nous présentons un algorithme permettant de calculer cette distribution de manière très efficace. Nous observons que la distribution stationnaire de la file fluide de capacité infinie est très semblable à celle d'un processus QBD avec une infinité de niveaux. Nous poursuivons la recherche des similarités entre les files fluides et les processus QBD, et nous étudions ensuite la distribution stationnaire d'une file fluide de capacité finie. Nous montrons que l'algorithme valable pour le cas du réservoir infini permet de calculer toutes les quantités importantes du modèle avec un réservoir fini.<p><p>Nous considérons ensuite des modèles fluides plus complexes, de capacité finie ou infinie, où le comportement du processus markovien des phases peut changer lorsque le niveau du réservoir atteint certaines valeurs seuils. Nous montrons que les méthodes développées pour des modèles classiques s'étendent de manière naturelle à ces modèles plus complexes.<p><p>Pour terminer, nous étudions les conditions nécessaires et suffisantes qui mènent à l'indépendance du niveau et de la phase d'une file fluide de capacité infinie en régime stationnaire. Ces résultats s'appuient sur des résultats semblables concernant des processus QBD.<p><p>Markov modulated fluid queues are two-dimensional Markov processes, of which the first component, called the level, represents the content of a buffer or reservoir and takes real values; the second component, called the phase, is the state of a Markov process which controls the evolution of the level in the following manner: the level varies linearly at a rate which depends on the phase and which can take any real value.<p><p>In this thesis, we explore the link between fluid queues and Quasi Birth-and-Death (QBD) processes, and we apply Markov renewal techniques in order to derive the stationary distribution of various fluid models.<p><p>To begin with, we study a fluid queue with an infinite capacity buffer; we determine its stationary distribution and we present an algorithm which performs very efficiently in the determination of this distribution. We observe that the equilibrium distribution of the fluid queue is very similar to that of a QBD process with infinitely many levels. We further exploit the similarity between the two processes, and we determine the stationary distribution of a finite capacity fluid queue. We show that the algorithm available in the infinite case allows for the computation of all the important quantities entering in the expression of this distribution.<p><p>We then consider more complex models, of either finite or infinite capacities, in which the behaviour ff the phase process may change whenever the buffer is empty or full, or when it reaches certain thresholds. We show that the techniques that we develop for the simpler models can be extended quite naturally in this context.<p><p>Finally, we study the necessary and sufficient conditions that lead to the independence between the level and the phase of an infinite capacity fluid queue in the stationary regime. These results are based on similar developments for QBD processes. / Doctorat en sciences, Spécialisation mathématiques / info:eu-repo/semantics/nonPublished

H διατριβή διερευνά προβλήματα αποδοτικής οργάνωσης χωροταξικών δεδομένων, προτείνει συγκεκριμένες δενδρικές δομές για τη διαχείρισή τους και, τέλος, δίνει παραδείγματα χρήσης τους σε ειδικές περιοχές εφαρμογών. Το πρώτο κεφάλαιο ασχολείται με το γεωμετρικό πρόβλημα της εύρεσης των ισo-προσανατολισμένων ορθογωνίων που περικλείουν ένα query αντικείμενο που μπορεί να είναι ένα ισο-προσανατολισμένο ορθογώνιο είτε σημείο ή κάθετο / οριζόντιο ευθύγραμμο τμήμα. Για την επίλυσή του προτείνεται μια πολυεπίπεδη δενδρική δομή που βελτιώνει τις πολυπλοκότητες των προηγούμενων καλύτερων λύσεων. Το δεύτερο κεφάλαιο εξετάζει το πρόβλημα της ανάκτησης σημείων σε πολύγωνα. H προτεινόμενη γεωμετρική δομή είναι επίσης πολυεπίπεδη και αποδοτική όταν το query πολύγωνο έχει συγκεκριμένες ιδιότητες. Το τρίτο κεφάλαιο ασχολείται με την εφαρμογή δενδρικών δομών σε δύο βιομηχανικά προβλήματα. Το πρώτο αφορά στη μείωση της πολυπλοκότητας ανίχνευσης συγκρούσεων κατά την κίνηση ενός ρομποτικού βραχίονα σε μια επίπεδη σκηνή με εμπόδια. Ο αλγόριθμος επίλυσης κάνει χρήση μιας ουράς προτεραιότητας και μιας UNION-FIND δομής ενώ αξιοποιεί γνωστές δομές και αλγόριθμους της Υπολογιστικής Γεωμετρίας όπως υπολογισμός κυρτών καλυμμάτων, έλεγχος polygon inclusion, κλπ. Το δεύτερο πρόβλημα ασχολείται με το σχεδιασμό απαιτήσεων υλικών (MRP) σε ένα βιομηχανικό σύστημα παραγωγής. Για το σκοπό αυτό αναπτύχθηκε ένας MRP επεξεργαστής που χρησιμοποιεί διασυνδεμένες λίστες και εκτελείται στην κύρια μνήμη για να είναι αποδοτικός. Το τελευταίο κεφάλαιο εξετάζει το πρόβλημα του ελέγχου της παραγωγής και συγκεκριμένα της δρομολόγησης εργασιών. Στο πλαίσιο αυτό σχεδιάστηκε και υλοποιήθηκε ένα ευφυές σύστημα δρομολόγησης σε περιβάλλον ροής που συνδυάζει γνωσιακή τεχνολογία και προσομοίωση με on-line έλεγχο προκειμένου να υποστηρίξει το διευθυντή παραγωγής στη λήψη αποφάσεων. / Τhe dissertation examines problems of efficient organization of spatial data, proposes specific tree structures for their management, and finally, gives examples of their use in specific application areas. The first chapter is about the problem of finding the iso-oriented rectangles that enclose a query object which can be an iso-oriented rectangle either a point or a vertical / horizontal line segment. A multilevel tree structure is proposed to solve the problem which improves the complexities of the best previous known solutions. The second chapter examines the problem of point retrieval on polygons. The proposed geometric structure is also multileveled and efficient when the query polygon has specific properties. The third chapter is about the application of tree structures in two manufacturing problems. The first one concerns the reduction in the complexity of collision detection as a robotic arm moves on a planar scene with obstacles. For the solution a priority queue and a UNION-FIND structure are used, whereas known data structures and algorithms of Computational Geometry such as construction of convex hulls, polygon inclusion testing, etc. are applied. The second problem is about material requirements planning (MRP) in a manufacturing production system. To this end an MRP processor was developed, which uses linked lists and runs in main memory to retain efficiency. The last chapter examines the production control problem, and more specifically the job scheduling problem. In this context, an intelligent scheduling system was designed and developed for flow shop production control which combines knowledge-based technology and simulation with on-line control in order to support the production manager in decision making.