With the emergence of cloud computing, computing resources (i.e., networks, servers, storage, applications, etc.) are provisioned as metered on-demand services over net- works, and can be rapidly allocated and released with minimal management effort. In the cloud computing paradigm, the virtual machine (VM) is one of the most com- monly used resource units in which business services are encapsulated. VM schedul- ing optimization, i.e., finding optimal placement schemes for VMs and reconfigu- rations according to the changing conditions, becomes challenging issues for cloud infrastructure providers and their customers. The thesis investigates the VM scheduling problem in two scenarios: (i) single- cloud environments where VMs are scheduled within a cloud aiming at improving criteria such as load balancing, carbon footprint, utilization, and revenue, and (ii) multi-cloud scenarios where a cloud user (which could be the owner of the VMs or a cloud infrastructure provider) schedules VMs across multiple cloud providers, target- ing optimization for investment cost, service availability, etc. For single-cloud scenar- ios, taking load balancing as the objective, an approach to optimal VM placement for predictable and time-constrained peak loads is presented. In addition, we also present a set of heuristic methods based on fundamental management actions (namely, sus- pend and resume physical machines, VM migration, and suspend and resume VMs), continuously optimizing the profit for the cloud infrastructure provider regardless of the predictability of the workload. For multi-cloud scenarios, we identify key re- quirements for service deployment in a range of common cloud scenarios (including private clouds, bursted clouds, federated clouds, multi-clouds, and cloud brokering), and present a general architecture to meet these requirements. Based on this architec- ture, a set of placement algorithms tuned for cost optimization under dynamic pricing schemes are evaluated. By explicitly specifying service structure, component relation- ships, and placement constraints, a mechanism is introduced to enable service owners the ability to influence placement. In addition, we also study how dynamic cloud scheduling using VM migration can be modeled using a linear integer programming approach. The primary contribution of this thesis is the development and evaluation of al- gorithms (ranging from combinatorial optimization formulations to simple heuristic algorithms) for VM scheduling in cloud infrastructures. In addition to scientific pub- lications, this work also contributes software tools (in the OPTIMIS project funded by the European Commissions Seventh Framework Programme) that demonstrate the feasibility and characteristics of the approaches presented. / I datormoln tillhandahålls datorresurser (dvs., nätverk, servrar, lagring, applikationer, etc.) som tjänster åtkomliga via Internet. Resurserna, som t.ex. virtuella maskiner (VMs), kan snabbt och enkelt allokeras och frigöras alltefter behov. De potentiellt snabba förändringarna i hur många och hur stora VMs som behövs leder till utmanade schedulerings- och konfigureringsproblem. Scheduleringsproblemen uppstår både för infrastrukturleverantörer som behöver välja vilka servrar olika VMs ska placeras på inom ett moln och deras kunder som behöver välja vilka moln VMs ska placeras på. Avhandlingen fokuserar på VM-scheduleringsproblem i dessa två scenarier, dvs (i) enskilda moln där VMs ska scheduleras för att optimera lastbalans, energiåtgång, resursnyttjande och ekonomi och (ii) situationer där en molnanvändare ska välja ett eller flera moln för att placera VMs för att optimera t.ex. kostnad, prestanda och tillgänglighet för den applikation som nyttjar resurserna. För det förstnämnda scenar- iot presenterar avhandlingen en scheduleringsmetod som utifrån förutsägbara belast- ningsvariationer optimerar lastbalansen mellan de fysiska datorresurserna. Därtill pre- senteras en uppsättning heuristiska metoder, baserade på fundamentala resurshanter- ingsåtgärder, fö att kontinuerligt optimera den ekonomiska vinsten för en molnlever- antör, utan krav på lastvariationernas förutsägbarhet. För fallet med flera moln identifierar vi viktiga krav för hur resurshanteringstjänster ska konstrueras för att fungera väl i en rad konceptuellt olika fler-moln-scenarier. Utifrån dessa krav definierar vi också en generell arkitektur som kan anpassas till dessa scenarier. Baserat pp vår arkitektur utvecklar och utvärderar vi en uppsättning algoritmer för VM-schedulering avsedda att minimera kostnader för användning av molninfrastruktur med dynamisk prissättning. Användaren ges genom ny funktionalitet möjlighet att explicit specificera relationer mellan de VMs som allokeras och andra bivillkor för hur de ska placeras. Vi demonstrerar också hur linjär heltals- programmering kan användas för att optimera detta scheduleringsproblem. Avhandlingens främsta bidrag är utveckling och utvärdering av nya metoder för VM-schedulering i datormoln, med lösningar som inkluderar såväl kombinatorisk op- timering som heuristiska metoder. Utöver vetenskapliga publikationer bidrar arbetet även med programvaror för VM-schedulering, utvecklade inom ramen för projektet OPTIMIS som finansierats av EU-kommissionens sjunde ramprogram. metoder för VM-schedulering i datormoln, med lösningar som inkluderar såväl kombinatorisk op- timering som heuristiska metoder. Utöver vetenskapliga publikationer bidrar arbetet även med programvaror för VM-schedulering, utvecklade inom ramen för projektet OPTIMIS som finansierats av EU-kommissionens sjunde ramprogram.

Health Sciences Centre (HSC) in Winnipeg is the major healthcare facility serving Manitoba, Northwestern Ontario, and Nunavut. An evaluation of HSC’s adult surgical patient flow revealed that one major barrier to smooth flow was their Operating Room (OR) scheduling system. This thesis presents a new two-stage elective OR scheduling system for HSC, which generates weekly OR schedules that reduce artificial variability in order to facilitate smooth patient flow. The first stage reduces day-to-day variability while the second stage reduces variability occurring within a day. The scheduling processes in both stages are mathematically modelled as multi-objective optimization problems. An attempt was made to solve both models using lexicographic goal programming. However, this proved to be an unacceptable method for the second stage, so a new multi-objective genetic algorithm, Nondominated Sorting Genetic Algorithm II – Operating Room (NSGAII-OR), was developed. Results indicate that if the system is implemented at HSC, their surgical patient flow will likely improve.

Flexible job-shop scheduling problem (FJSP) is a generalization of the classical job-shop scheduling problem (JSP). It takes shape when alternative production routing is allowed in the classical job-shop. However, production scheduling becomes very complex as the number of jobs, operations, parts and machines increases. Until recently, scheduling problems were studied assuming that all of the problem parameters are known beforehand. However, such assumption does not reflect the reality as accidents and unforeseen incidents happen in real manufacturing systems. Thus, an optimal schedule that is produced based on deterministic measures may result in a degraded system performance when released to the job-shop. For this reason more emphasis is put towards producing schedules that can handle uncertainties caused by random disruptions. The current research work addresses solving the deterministic FJSP using evolutionary algorithm and then modifying that method so that robust and/or stable schedules for the FJSP with the presence of disruptions are obtained. Evolutionary computation is used to develop a hybridized genetic algorithm (hGA) specifically designed for the deterministic FJSP. Its performance is evaluated by comparison to performances of previous approaches with the aid of an extensive computational study on 184 benchmark problems with the objective of minimizing the makespan. After that, the previously developed hGA is modified to find schedules that are quality robust and/or stable in face of random machine breakdowns. Consequently, a two-stage hGA is proposed to generate the predictive schedule. Furthermore, the effectiveness of the proposed method is compared against three other methods; two are taken from literature and the third is a combination of the former two methods. Subsequently, the hGA is modified to consider FJSP when processing times of some operations are represented by or subjected to small-to-medium uncertainty. The work compares two genetic approaches to obtain predictive schedule, an approach based on expected processing times and an approach based on sampling technique. To determine the performance of the predictive schedules obtained by both approaches with respect to two types of robustness, an experimental study and Analysis of Variance (ANOVA) are conducted on a number of benchmark problems.

With the emergence of the cloud computing paradigm, we can now provide dynamic resource provisioning at unprecedented levels of scalability. This flexibility constitutes a rich environment for researchers to experiment with new designs. Such experimental novel designs can take advantage of adaptation, controllability, self- configuration, and scheduling techniques to provide improved resource utilization while achieving service level agreements. This dissertation uses control and scheduling theories to develop new designs to improve resource utilization and service level agreement satisfaction. We optimize resource provisioning using the Cutting Stock problem formulation and control theory within feedback frameworks. We introduce a model-based method of control to manipulate the scheduling problem’s formulation model to achieve desired results. We also present a control based method using Kalman filters for admission control. Finally, we present two case studies — the Yakkit media social application and the Rigi Cloud testbed for deploying virtual ma- chine experiments. The results of our investigations demonstrate that our approaches and techniques can optimize resource utilization, decrease service level agreement violations, and provide scheduling guarantees. / Graduate / 0790 / 0984 / rd@uvic.ca

No description available.

This thesis focuses on task sequencing and manpower scheduling to develop robust schedules for an aircraft manufacturer. The production of an aircraft goes through a series of multiple workstations, each consisting of a large number of interactive tasks and a limited number of working zones. The duration of each task varies from operator to operator, because most operations are performed manually. These factors limit the ability of managers to balance, optimize, and change the statement of work in each workstation. In addition, engineers spend considerable amount of time to manually develop schedules that may be incompatible with the changes in the production rate. To address the above problems, the current state of work centers are first analyzed. Then, several deterministic mathematical programming models are developed to minimize the total production labour cost for a target cycle time. The mathematical models seek to find optimal schedules by eliminating and/or considering the effect of overtime on the production cost. The resulting schedules decrease the required number of operators by 16% and reduce production cycle time of work centers by 53% to 67%. Using these models, the time needed to develop a schedule is reduced from 36 days to less than a day. To handle the stochasticity of the task durations, a two-stage stochastic programming model is developed to minimize the total production labour cost and to find the number of operators that are able to work under every scenario. The solution of the two-stage stochastic programming model finds the same number of operators as that of the deterministic models, but reduces the time to adjust production schedules by 88%.

This dissertation concerns the problem of scheduling real-time traffic in wireless TDMA channels. The most important characteristic of real-time traffic is that it has straight end-to-end delay constraint. We begin the investigation by studying a scheduling principle which naturally achieves the best delay performance in stationary channel conditions. Since the resulting scheduling algorithm maintains equal flow delays across the whole system, it is termed the equal-delay policy. There are a number of advantages associated with this scheduling method. First, it is very simple and practical to implement in real system. Secondly, it can be easily modelled mathematically and admits an analytical solution, which is very important for the construction of an admission control algorithm, we present a mathematical model describing the dynamics of the scheduling system, as well as devising a tractable analytical solution to the problem. A third advantage of the equal-delay policy is that it can be easily extended to support flows with multiple delay constraints. We propose a multiple-class scheduling scheme based on similar allocation concepts as the equal-delay technique. The extended scheme can similarly be mathematically modelled and analytically characterized. A natural objection to the above proposed techniques is that wireless transmission resources can be under-utilized, since the scheduling algorithm pays no attention to the changing individual channel conditions. The reduction in channel utilization can also adversely affect the delay performance, We explain this phenomenon and study the impacts for a variety of different channel characteristics, Specifically, we propose an alternative channel-aware scheduling policy, which aims to maximize channel utilization while keeping a minimum probability of delay violation, The proposed channel-aware policy achieves near-optimal delay performance. However, unlike in the equal-delay case, the channel-aware policy is not practical to implement in a real system. The complicated system dynamics associated with the channel-aware scheme also hamper the development of a mathematical model and analytical solution for admission control. On the other hand, we observe from simulation results that under most circumstances, the equal-delay scheme achieves close to the pertonnance obtained by the channel-aware technique, With the additional benefits of simplicity and admitting analytical analysis. the equal-delay policy appears to be a more practical and suitable choice for scheduling real-time traffic in wireless networks.

Bibliography: leaves 231-246. / xv, 246 leaves : ill. ; 30 cm. / Title page, contents and abstract only. The complete thesis in print form is available from the University Library. / Thesis (Ph.D.)--University of Adelaide, Dept. of Computer Science, 1999

This thesis addresses the scheduling and control of shop-floor production units that operate in a highly autonomous and distributed environment. The distinct feature of this environment is the heterarchical nature of the control where the scheduling function is quite independently carried out by the units. The units solve only part of the overall problem while resolving conflicts to maintain consistent global schedules. The need for communication and coordination, in such circumstances, introduces many complexities that affects the quality of the schedules produced. These include lapses of open-loop control due to uncertainty of up-to-date status information, asynchronous behaviour, and uncontrollable propagation of conflicts. / A behaviour-based approach is introduced to solve these problems. Using this approach, the organisation of the shop-floor is viewed as similar to a colony of ants or an eco-system. The units operate quite independently but continue to adapt their schedules to changes in their environment. While they may not directly negotiate to resolve conflicts, their cooperation is innate or in-built through their local adaptive actions. This individual cooperative action of the units brings about a collective behaviour that produces the desired emergent global schedules. The major focus of this research is in examining the link between the individual and collective behaviours and developing a model that realises the desired scheduling functionality at the shop level. / In order to achieve high scheduling performance (both locally and globally) a model of a unit incorporating dynamic problem decomposition, allocation algorithms and adaptation mechanisms is developed. For the latter, a reinforcement learning model is used to adapt the scheduling horizon. In fact, an important contribution if this research is the novel view we take of the problem and the manner of adaptation. In addition, a communication model for simulating the scheduling behaviours is designed using concepts of Holonic and other emerging concepts of manufacturing systems. / The model is tested for a number of scheduling problems representing a variety of production situations. Preliminary results indicate an impressive scheduling performance comparable to well-known heuristics. Further examination indicates the types of dynamic behaviour that can be expected of such a model, including the levels of unresolved conflicts, the adaptability in the face of uncertainty, consequence of alternative communication policies and the sensitivities to adaptation. / This thesis has also a strong qualitative theme in reviewing and consolidating the concepts underlying the design and operational attributes of autonomous distributed organisations of the shop-floor.

Zugl.: Hamburg, Techn. Univ., Diss., 2006