The central thesis of this dissertation is that insight from queueing analysis can effectively guide standard (combinatorial) scheduling algorithms in dynamic environments. Scheduling is generally concerned with complex combinatorial decisions for static problems, whereas queueing theory simplifies the combinatorics and focuses on dynamic systems. We examine a queueing network with flexible servers under queueing and scheduling techniques. Based on the strengths of queueing analysis and scheduling, we develop a hybrid model that guides scheduling with results from the queueing model. In order to include setup times, we create a logic-based Benders decomposition model for a static representation of the queueing network. Our model is able to find optimal schedules up to 5 orders of magnitude faster than the only other model in the literature. A hybrid model is then developed for the dynamic problem and shown to achieve the best mean flow time while also guaranteeing maximal capacity.

Service Orientation (SO) and grid computing are two computing paradigms that when put together using Internet technologies promise to provide a scalable yet flexible computing platform for a diverse set of distributed computing applications. This practice gives rise to the notion of a computing cloud that addresses some previous limitations of interoperability, resource sharing and utilization within distributed computing. <p>In such a Service Oriented Computing Cloud (SOCC), applications are formed by composing a set of services together. In addition, hierarchical service layers are also possible where general purpose services at lower layers are composed to deliver more domain specific services at the higher layer. In general an SOCC is a horizontally scalable computing platform that offers its resources as services in a standardized fashion. <p>Workflow based applications are a suitable target for SOCC where workflow tasks are executed via service calls within the cloud. One or more workflows can be deployed over an SOCC and their execution requires scheduling of services to workflow tasks as the task become ready following their interdependencies. <p>In this thesis heuristics based scheduling policies are evaluated for scheduling workflows over a collection of services offered by the SOCC. Various execution scenarios and workflow characteristics are considered to understand the implication of the heuristic based workflow scheduling.

School physical education (PE) programs are often viewed as one of the best and most effective ways to encourage children and youth to be physically active as they provide an environment ideal for the promotion of a healthy lifestyle. Due to the potentially powerful role that PE can play in the health of youth, attention needs to be given to ensure that these programs are as effective as possible. In Canada, recommendations have been made for daily physical education for students from kindergarten through grade 12 yet most high schools are not meeting this goal. At the high school level, physical education is frequently provided for students through one of two scheduling systems: (a) semestered physical education (PE class every day for half of the school year), and (b) non-semestered physical education (PE class every second day for the entire school year). To date, no research exists that investigates the influence of the scheduling of PE on the physical activity levels, participation rates, and experiences of high school students. Using a mixed methods research design, the purpose of this study was to investigate the effect that the scheduling of PE programs has on the subsequent physical activity levels and experiences of the students involved. This study was conducted in two phases. In phase one, Grade 9 students enrolled in two schools (n = 245), with one school offering semestered PE and one school offering non-semestered PE, completed an activity recall questionnaire. This questionnaire was administered three times (October, February, and May) throughout the school year. At the baseline data collection in October, the students in the two schools had comparable total physical activity levels. The most notable difference could be seen in May where students enrolled in non-semestered PE had significantly higher physical activity levels than baseline (p>.05) while students enrolled in the semestered PE program showed a trend of decreasing physical activity levels. It was also found that students enrolled in the non-semestered PE program showed significantly higher levels of participation in structured physical activity (p>.05), activities that had to be signed up or registered for, at school and away from the school. In the second phase of the study, students were organized into focus groups based on their gender and activity level. The focus group discussions explored the experiences of students in both types of PE programs. Common themes from the focus groups included the role that non-semestered PE played in the promotion of physical activity throughout the year. It was found that the non-semestered schedule fostered a continued interest in PE but that it interfered with the scheduling of other academic classes. Semestered PE appealed to those students who preferred to get PE over with and/or appreciated the familiar routine of the one-term class. Key decision-makers were also interviewed with many of the same themes emanating. Non-semestered physical education was seen as advantageous for encouraging physical activity levels in students, but being logistically difficult to schedule. Students and key decision-makers agreed that while semestered PE was more convenient for administration, non-semestered PE would encourage PA levels, enrollment in elective PE, and participation in intramural activities and school sports teams. In conclusion, this study provides support for the investigation into the effects of PE scheduling on the physical activity levels of students. The non-semestered PE program appeared to encourage students to be more involved in structured physical activities and was supported by most students and key decision-makers with the chief objection being the logistical inconveniences. However, with youth inactivity still a major problem in Canada, and changes being desperately needed, mere inconveniences should not discourage the implementation of possible physical activity-improving initiatives like non-semestered physical education.

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. / October 2008

In this paper, we consider interference networks where the connectivity is known globally while the channel gains are known up to a particular distance from each node. In this setting, we provide a new achievability, called Maximal Clique Scheduling (MCS), which is a special case of Maximal Independent Graph Scheduling (MIG Scheduling) proposed earlier. The strategy is evaluated using the notion of normalized sum rate which is a metric to evaluate performance of networks with mismatched knowledge. The achievable normalized sum rate of the proposed MCS strategy is easier to analyze for certain classes of networks and can be used to bound the normalized sum rate of MIG Scheduling. We investigate the normalized sum rate achieved by MCS for two classes of networks. The first class is formed by interference networks where each link is connected with probability $p$. The second class is derived from Wyner 1-D model of placements of base stations and mobile nodes. We find that increasing knowledge about the network leads to increasing normalized sum-rate. However, in a random network, the increase is slower as compared to Wyner network because most nodes are far away from a node and hence learning more helps less until the whole network is known.

Network Processor Units (NPUs) are a compromise between software-based and hardwired packet processing solutions. While slower than hardwired solutions, NPUs have the flexibility of software-based solutions, allowing them to adapt faster to changes in network protocols. <br /><br /> Network processors have multiple processing engines so that multiple packets can be processed simultaneously within the NPU. In addition, each of these processing engines is multi-threaded, with special hardware support built in to alleviate some of the cost of concurrency. This hardware design allows the NPU to handle multiple packets concurrently, so that while one thread is waiting for a memory access to complete, another thread can be processing a different packet. By handling several packets simultaneously, an NPU can achieve similar processing power as traditional packet processing hardware, but with greater flexibility. <br /><br /> The flexibility of network processors is also one of the disadvantages associated with them. Programming a network processor requires an in-depth understanding of the hardware as well as a solid foundation in concurrent design and programming. This thesis explores the challenges of programming a network processor, the Intel IXP2400, using a single-threaded packet scheduling algorithm as a sample case. The algorithm used is a GPS approximation scheduler with constant time execution. The thesis examines the process of implementing the algorithm in a multi-threaded environment, and discusses the scalability and load-balancing aspects of such an algorithm. In addition, optimizations are made to the scheduler implementation to improve the potential concurrency. The synchronization primitives available on the network processor are also examined, as they play a significant part in minimizing the overhead required to synchronize memory accesses by the algorithm.

Scheduling in wireless networks plays an important role. The undeterministic nature of the wireless channel is usually considered as an undesirable property. Recently, the idea of opportunistic scheduling is introduced and it takes advantage of the time-varying channel for performance improvement such as throughput and delay. Since the introduction of opportunistic scheduling, there are two main bodies of works. The first body of works assume that each user is greedy and has infinite backlog for transfer. With this assumption, fairness objective becomes an important factor in designing a scheduling algorithm to avoid severe starvation of certain users. Typical fairness involve processor sharing time fairness, proportional fairness, and minimum performance guarantee. On the other hand, delay performance is not a appropriate factor to evaluate the effectiveness of a scheduling algorithm because of the infinite backlog assumption. In reality, this assumption is not true as data arrives and leaves the network randomly in practice. The second body of works deal with the relaxation of the infinite backlog assumption. Thus, the notion of stability region arises. The definition of stability is that the queue at each source node remains finite. Stability region can be defined as the set of traffic intensities which can all be stabilized by the network. The well known throughput optimal algorithm is proven capable of achieving the largest stability region. In this thesis, two innovative opportunistic scheduling algorithms which aim to minimize the amount of resources used to stabilize the current traffics are proposed. The key feature of our algorithm is that the incoming traffic rates are available to the scheduler, whereas the throughput optimal algorithm has no such prior traffic knowledge. Performance comparisons are made by means of simulation to demonstrate that the proposed algorithms can achieve the same stability region as the throughput optimal algorithm. Moreover, the delay performance is better than that of the throughput optimal algorithm, especially under heavy traffic conditions.

In this thesis, we propose a scheduling problem for the downlink of a single cell system with multiple sectors. We formulate an optimization problem based on a generalized round robin scheme that aims at minimizing the cycle length necessary to provide one timeslot to each user, while avoiding harmful interference. Since this problem is under-constrained and might have multiple solutions, we propose a second optimization problem for which we try to find a scheduling that minimizes the cycle length while being as efficient as possible in resource utilization. Both of these problems are large integer programming problems that can be solved numerically using a commercial solver, but for real time use, efficient heuristics need to be developed. We design heuristics for these two problems and validate them by comparing their performances to the optimal solutions.

Mitrionics is a company based in Lund, Sweden. They develop a platform for FPGA-based acceleration, the platform includes a virtual processor, the Mitrion Virtual Processor, that can be custom built to fit the application that is to be accelerated. The purpose of this thesis is to investigate the possible benefits of using a centralized scheduler for the Mitrion Virtual Processor instead of the current solution which is a distributed scheduler. A centralized scheduler has been implemented and evaluated using a set of benchmark applications. It has been found that the centralized scheduler can decrease the number of registers used to implement the Mitrion Virtual Processor on an FPGA. The size of the decrease depends on the application, and certain applications are more suitable than others. It has also been found that the introduction of a centralized scheduler makes it more difficult for the place and route tool to fit a design on the FPGA resulting in failed timing constraints for the largest benchmark application. / Mitrionics är ett företag i Lund. De utvecklar en platform för FPGA-baserad acceleration av applikationer. Platformen innehåller bland annat en virtuell processor, Mitrion Virtual Processor, vilken kan specialanpassas till applikationen som ska accelereras. Syftet med detta arbete är att implementera en centraliserad schedulerare för Mitrion Virtual Processor och utvärdera vilka möjliga fördelar det kan finnas jämfört med att använda den nuvarande lösningen vilket är en distribuerad skedulerare. En centraliserad skedulerare har implementerats och utvärderas genom att avända en uppsättning testapplikationer. Det har funnits att användandet av en centraliserad skedulerare kan minska antalet register som behövs för att implementera Mitrion Virtual Processor på en FPGA. Vidare har det funnits att storleken på minskningen beror på applikationen och att vissa applikationer lämpar sig bättre än andra. Det har även visat sig att processen att placera logik på FPGAn blir svårare om man använder en centraliserad skedulerare, detta har resulterat i att vissa timing krav inte har mötts när den största testapplikation har syntetiserats.

Train dispatchers faces lots of challenges due to conflicts which causes delays of trains as a result of solving possible dispatching problems the network faces. The major challenge is for the train dispatchers to make the right decision and have reliable, cost effective and much more faster approaches needed to solve dispatching problems. This thesis work provides detail information on the implementation of different heuristic algorithms for train dispatchers in solving train dispatching problems. The library data files used are in xml file format and deals with both single and double tracks between main stations. The main objective of this work is to build different heuristic algorithms to solve unexpected delays faced by train dispatchers and to help in making right decisions on steps to take to have reliable and cost effective solution to the problems. These heuristics algorithms proposed were able to help dispatchers in making right decisions when solving train dispatching problems.