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.

Ant Colony Optimization is a relatively new meta-heuristic that has proven its quality and versatility on various combinatorial optimization problems such as the traveling salesman problem, the vehicle routing problem and the job shop scheduling problem. The paper introduces an Ant Colony Optimization approach to solve the problem of determining a job-sequence that minimizes the overall tardiness for a given set of jobs to be processed on a single, continuously available machine, the Single Machine Total Tardiness Problem. We experiment with various heuristic information as well as with variants for local search. Experiments with 250 benchmark problems with 50 and 100 jobs illustrate that Ant Colony Optimization is an adequate method to tackle the SMTTP. (author's abstract) / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

A quota-based integrated commercial fishery owns fishing trawlers, processing plants, and fish quotas. Such a fishery must decide how to schedule trawlers for fishing and landing, how to schedule processing of products, how to schedule labour for processing, and how to plan inventory of raw materials and products. This problem is of great economic significance to New Zealand, whose economy depends to a large extent on the fishery industry. To assist the fishery manager, we develop a mixed integer linear program (MILP) for optimal scheduling of fishing trawlers, production planning (processing) and labour allocation for a quota-based integrated fishery of New Zealand. The model decides when and where each trawler should go for fishing, how much fish each trawler should land, and how much product to produce in each period. Since the fishery is a private farm, its main objective will be profit maximization (or cost minimization if its demand is on contract). The government manages the conservation of fish through the quota allocation. In this thesis the objective of the fishery model is to maximise the total profit. We demonstrate our model with examples based on data from a major New Zealand fishery. We investigate ways to manage the uncertainties involved in trawler scheduling and production planning of the fishery. To manage end-of-planning-horizon effects in the fishery, we develop a simple safety stock approach. We also analyse the workability of a rolling horizon approach to solve the longer planning horizon models and to deal with the end-of-planning horizon effects. We investigate the effect of initial and final position of the trawlers on the profit. We also investigated many different challenging data sets to observe the impact on the effectiveness of our IFPM. The second objective of this thesis is to develop an efficient solution procedure for the MILP, named integrated fishery planning model (IFPM). The IFPM consists of a fishing subproblem, a processing subproblem, and complicating side constraints. We have tried techniques including LP relaxation, Lagrangean relaxation (LR), Dantzig-Wolfe decomposition (DWD) and decomposition-based pricing (DBP). We develop a new DBP method to solve the IFPM. It gives excellent computation times. We also develop a decomposition-based O'Neill pricing (DBONP) method to improve the solution obtained from DBP procedure. It improves the DBP solutions but takes longer time to solve the IFPM. Finally, we develop a simple and efficient reduced cost-based pricing (RCBP) method. It takes less time to solve the IFPM and yields excellent results. The initial formulations for several planning horizons are solved using the AMPL modelling language and CPLEX with branch and bound. Relevant results and computational difficulties are reported.

An optimal stochastic multi-crop irrigation scheduling algorithm was developed which was able to incorporate complex farm system models, and constraints on daily and seasonal water use, with the objective of maximising farm profit. This scheduling method included a complex farm simulation model in the objective function, used decision variables to describe general management decisions, and used a custom heuristic method for optimisation. Existing optimal schedulers generally use stochastic dynamic programming which relies on time independence of all parameters except state variables, thereby requiring over-simplistic crop models. An alternative scheduling method was therefore proposed which allows for the inclusion of complex farm system models. Climate stochastic properties are modelled within the objective function through the simulation of several years of historical data. The decoupling of the optimiser from the objective function allows easy interchanging of farm model components. The custom heuristic method, definition of decision variables, and use of the Markov chain equation (relating an irrigation management strategy to mean water use) considerably increases optimisation efficiency. The custom heuristic method used simulated annealing with continuous variables. Two extensions to this method were the efficient incorporation of equality constraints and utilisation of population information. A case study comparison between the simulated annealing scheduler and scheduling using stochastic dynamic programming, using a simplistic crop model, showed that the two methods resulted in similar performance. This demonstrates the ability of the simulated annealing scheduler to produce close to optimal schedules. A second case study demonstrates the ability of the simulated annealing scheduler to incorporate complex farm system models by including the FarmWi$e model by CSIRO in the objective function. This case study indicates that under conditions of limited seasonal water, the simulated annealing scheduler increases pasture yield returns by an average of 10%, compared with scheduling irrigation using best management practice. Alternatively expressed, this corresponds to a 20-25% reduction in seasonal water use (given no change in yield return).

In this thesis, we study different scheduling policies in service networks. In Chapter 2, we consider two service level (SL) measures in a two-server tandem queue system: the average sojourn time and the probability of long waits. We demonstrate that a family of Threshold Based Policies (TBP) can reduce the probability of long waits while maintaining sojourn times that are only slightly higher than those of a non-idling policy. In Chapter 3, we present a case study for improving the operations of a healthcare provider that has an open-shop queueing network. We propose an effective implementation of Dynamic Scheduling Policies (DSPs) and a generalized TBP to improve the SL in an open-shop queueing networks. Using a simulation model we demonstrate that an open-shop queueing network can be managed in a systematic fashion to deliver improved SL. In Chapter 4, we study the waiting time distribution of two different priority classes in an M/M/c queue with different service times. For the c=2 case, we provide closed form expression of the Generating Function (GF) of the number of low-priority jobs in the system, which can lead to the waiting time distribution. For c>2 case, we present an efficient numerical algorithm for deriving this GF. We discuss several insights gained from numerical results. Both Chapter 2 and 3 were supervised by Professors Opher Baron, Oded Berman, and Dmitry Krass. Chapter 4 was supervised by Professors Opher Baron and Alan Scheller-Wolf.

This thesis study focuses on the development of model-based optimization strategies for the integration of process scheduling and dynamic optimization, and applications of the integrated approaches to industrial polymerization processes. The integrated decision making approaches seek to explore the synergy between production schedule design and process unit control to improve process performance. The integration problem has received much attention from both the academia and industry since the past decade. For scheduling, we adopt two formulation approaches based on the state equipment network and resource task network, respectively. For dynamic optimization, we rely on the simultaneous collocation strategy to discretize the differential-algebraic equations. Two integrated formulations are proposed that result in mixed discrete/dynamic models, and solution methods based on decomposition approaches are addressed. A class of ring-opening polymerization processes are used for our industrial case studies. We develop rigorous dynamic reactor models for both semi-batch homopolymerization and copolymerization operations. The reactor models are based on first-principles such as mass and heat balances, reaction kinetics and vapor-liquid equilibria. We derive reactor models with both the population balance method and method of moments. The obtained reactor models are validated using historical plant data. Polymerization recipes are optimized with dynamic optimization algorithms to reduce polymerization times by modifying operating conditions such as the reactor temperature and monomer feed rates over time. Next, we study scheduling methods that involve multiple process units and products. The resource task network scheduling model is reformulated to the state space form that offers a good platform for incorporating dynamic models. Lastly for the integration study, we investigate a process with two parallel polymerization reactors and downstream storage and purification units. The dynamic behaviors of the two reactors are coupled through shared cooling resources. We formulate the integration problem by combining the state space resource task network model with the moment reactor model. The case study results indicate promising improvements of process performances by applying dynamic optimization and scheduling optimization separately, and more importantly, the integration of the two.

Recently, we have seen an increase in the deployment of safety critical embedded systems in rapidly changing environments, as well as requirement for on-site customizations and rapid adaptation. To address the extended range of requirements, adaptation mechanism are added to the systems to handle large number of situations appropriately. Although necessary, adaptations can cause inconsistent and unstable configurations that must be prevented for the embedded system to remain dependable and safe. Therefore, verifying the behavior of adaptive embedded systems during the design phase of the production process is highly desirable. A hard real time embedded system and its environment can be modeled using timed automata. Such model can describe the system at various levels of abstraction. In this thesis, we model the adaptive responses of a system in terms of tasks that are executed to handle changes in the environmental or internal parameters. Schedulability, a property that all tasks complete execution within their respective deadlines, is a key element in designing hard real-time embedded systems. A system that is unschedulable immediately compromises safety and hard real-time requirements and can cause fatal failure. Given specifications of all tasks in the system, we can model the system, an abstraction of the environment, and adaptive strategies to investigate whether the system retains safety properties, including schedulability, regardless of the changes in the environment and adaptations to those changes.

The purpose of this study was to examine the graduation rates of secondary schools in Indiana in 1989-90 and to compare those graduation rates to those of 199798, to see if those schools that adopted block scheduling had experienced a difference in graduation rates either positively or negatively. A comparison was also made of graduation rates between schools adopting block scheduling for at least three years and traditional schools during this same time period. Further examination was made to determine if any specific type of block schedule had improved graduation rates. The size school was also a consideration as to the affect of block scheduling on graduation rates. The study also sought to determine if block scheduling had an impact on attendance rates, discipline incidents, pupil teacher ratio, or full time teacher equivalency, all factors aligned to reasons why students drop out of school.The population for this study consisted of 251 Indiana public secondary schools, 203 schools which maintained a traditional schedule and 48 schools identified by the Indiana Department of Education to have adopted block scheduling prior to or including 1995-96, 1996-97, 1997-98. Nine research questions accompanied by Null Hypotheses for each were determined and tested. All data collection were from the Indiana Department of Education through reports compiled and generated from information submitted annually by all public schools in Indiana. / Department of Educational Leadership

No-wait scheduling problem refers to the set of problems in which a number of jobs are available for processing on a number of machines with the added constraint that there should be no waiting time between consecutive operations of the jobs. It is well-known that most of the no-wait scheduling problems are strongly NP-hard. Moreover, no-wait scheduling problems have numerous real-life applications. This thesis studies a wide range of no-wait scheduling problems, along with side constraints that make such problems more applicable. First, 2-machine no-wait flow shop problem is studied. Afterwards, setup times and single server constraints are added to this problem in order to make it more applicable. Then, job shop version of this problem is further researched. Analytical results for both of these problems are presented; moreover, efficient algorithms are developed and applied to large instances of these problems. Afterward, general no-wait flow shop problem (NWFS) is the focus of the thesis. First, the NWFS is studied; mathematical models as well as metaheuristics are developed for NWFS. Then, setup times are added to NWFS in order to make the problem more applicable. Finally, the case of sequence dependent setup times is further researched. Efficient algorithms are developed for both problems. Finally, no-wait job shop (NWJS) problem is studied. Literature has proposed different methods to solve NWJS; the most successful approaches decompose the problem into a timetabling sub-problem and a sequencing sub-problem. Different sequencing and timetabling algorithms are developed to solve NWJS. This thesis provides insight to several no-wait scheduling problems. A number of theorems are discussed and proved in order to find the optimum solution of no-wait problems with special characteristics. For the problems without such characteristics, mathematical models are developed. Metaheuristics are utilized to deal with large-instances of NP-hard problems. Computational results show that the developed methods in this thesis are very effective and efficient compared to the competitive methods available in the literature.