This thesis presents the LiquiMedia operating system architecture. LiquiMedia is specialized to schedule multimedia applications. Because they generate output for a human observer, multimedia applications such as video games, video conferencing and video players have both unique scheduling requirements and unique allowances: a multimedia stream must synchronize sub-streams generated for different sensory modalities within 20 milliseconds, it is not successfully segregated until it has existed for over 200 milliseconds and tolerates occasional scheduling failures. LiquiMedia is specialized around these requirements and allowances. First, LiquiMedia synchronizes multimedia tasks by invoking them from a shared realtime timer interrupt. Second, owing to multimedia's tolerance of scheduling failures, LiquiMedia schedules tasks based on a probabilistic model of their running times. Third, LiquiMedia can infer per-task models while a user is segregating the streams that the tasks generate. These specializations provide novel capabilities: up to 2. 5 times higher utilization than RMS scheduling, use of an atomic task primitive 9. 5 times more efficient than preemptive threading, and most importantly, the ability to schedule arbitrary tasks to a known probability of realtime execution without a priori knowledge of their running times.

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.

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%.

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.

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.

Daily drayage operations involve moving loaded or empty equipment between customer locations and rail ramps. Drayage orders are generally pickup and delivery requests with time windows. The repositioning of empty equipment may also be required in order to facilitate loaded movements. The drayage orders are satisfied by a heterogeneous fleet of drivers. Driver routes must satisfy various operational constraints. In the first part of the dissertation, our goal is to minimize the cost of daily drayage operations in a region on a given day. We present an optimization methodology for finding cost-effective schedules for regional daily drayage operations. The core of the formulation is a set partitioning model whose columns represent routes. Routes are added to the formulation by column generation. We present numerical results for real-world data which demonstrate that our methodology produces low cost solutions in a reasonably short time. The second part of the dissertation addresses minimizing total empty mileage when driver capacity is not restrictive and new orders are added to the problem in an online fashion. We present a lower bound for the worst case guarantee of any deterministic online algorithm. We develop a solution methodology and provide results for the performance of different scheduling policies and parameters in a simulated environment. In the third part of the dissertation, we study a system with one rail ramp and one customer location which is served by a single driver. The problem has discrete time periods and at most one new order is released randomly each time period. The objective is to maximize the expected number of orders covered. With this simple problem, we seek to learn more about route planning for a single driver under uncertainty. We prove that carrying out an order ready to be picked up at the driver's current location is optimal for the case with one customer location. We show that the structure of the optimal policies is not simple and depends on various parameters. We devise a simple policy which yields provably near-optimal results and identify a case for which that policy is optimal.

For a commercial port, to efficiently schedule the public berths is an important issue. Since a berth schedule would affect the usage of the commercial port, in this thesis, we apply a genetic algorithm to schedule the public berths in order to minimize the total waiting time of vessels. When in the initialization process, we encode the chromosome based on wharf characteristics in order to avoid assigning vessels to inappropriate wharves. After mutation process, we also adjust the usage of wharves to improve the speed of convergence speed. Simulation results show that the proposed algorithm can assign vessels to proper berths as soon as vessels arrive. Compared to the other genetic algorithms, the proposed algorithm obtains better performance in convergence speed and the quality of the solutions.

none