This report examines the widely acceptable Heuristic and Exact procedures for solving the problem of project scheduling and control under constrained resources. Heuristic approaches are more practical, however they depend on the type of the project as well as the resources involved. Exact procedures are illustrated using an Integer Linear Programming formulation of the problem, and also solving it using the Branch and Bound Technique. Impracticality of the exact methods stews from the fact that the computations expand to an unmanageable amount.

Traditional critical path methods imply the assumption of unlimited availability of resources. Mathematical models and heuristic techniques are two alternatives that consider resource limitation to sequence the activities of a project. This research explores the consideration of project scheduling under resource constraints for the specific case of single resource, single project scheduling. A computer model called GENRES-II search model is developed using a modification of Brooks' algorithm to develop project schedules. The criteria used are various weighted combinations of ACTIM, ACTRES and ACTFOL. An improvement of GENRES-II solutions is obtained when the best set of GEN-II values is input to a computer model called COMSOAL simulation model. The criteria developed generates a large number of feasible solutions rapidly. The probability of generating optimal solutions is related to the size of the generated sample. Eight network cases were considered to validate both computer models. Special attention was given to those activities that were considered critical at a specific time. The number of resources available was increased to a new higher limit in order to schedule activities that became critical. The GENRES-II model was effective in finding project durations equal to or less than ACTIM, ACTRES, GENRES or ACTFOL. The COMSOAL model was found very effective in most of the cases in improving the GEN-II solutions.

<p> Hybrid task-lists are sets of periodic and asynchronous processes. To verifiably schedule hybrid tasks-lists with hard and soft real-time requirements, Xu and Lam proposed Integrated Pre-Run-Time scheduling (IPRTS) [13], a two phase method that first makes use of pre-run-time scheduling techniques, converting some asynchronous tasks with hard deadlines to periodic tasks and reserving processor capacity for the remaining hard deadline asynchronous tasks. These remaining asynchronous tasks are scheduled by a novel run-time scheduler that enforces arbitrary exclusion relations between any combination of periodic and asynchronous processes. The technique has two significant drawbacks: (i) a custom run-time scheduler is required that is not available on existing Real-Time Operating Systems (RTOS) and (ii) in many circumstances the reservation of processor capacity is overly pessimistic, causing the failure of the method for many simple task lists. To overcome these drawbacks, this thesis narrows the set of task-lists considered to those where the asynchronous tasks exclude periodic tasks and periodic processes do not exclude asynchronous tasks. A high priority polling server is then used to handle all hard asynchronous tasks. In cases where the method succeeds, it is easily implementable on any RTOS that has priority based scheduling with phased release times, and inherits the error handling and soft real-time process scheduling capabilities of the RTOS. A set of software tools which partially automates the technique, including an open source implementation of the Xu-Parnas pre-run-time scheduling algorithm [14], has been developed and applied to the examples in the thesis.</p> / Thesis / Master of Applied Science (MASc)

The objective of the hot rolling mill is to transform slabs of steel into thin strips which conform to specific dimensional and metallurgical customer requirements. High performance and flexibility in the operation is required due to strict customer demands, variable market conditions, and the drive for continuous improvement. Historically human schedulers have performed the scheduling and sequencing tasks, however it is not a reasonable expectation that they consider all the complex objectives required in optimal production of a hot mill. Therefore, there are significant opportunities for improvement in this area through the application of mathematical optimization models and solution algorithms. This work presents a set of models and a solution algorithm for optimal scheduling and sequencing of production within a hot rolling steel mill. The models and algorithms presented within this thesis are specifically developed for ArcelorMittal Dofasco’s Hot Strip Mill in Hamilton, Ontario, Canada. First, a graph theoretic representation of the production block is developed along with an asymmetric travelling salesman formulation of the sequencing problem. A slab transition cost function comprised of the hot rolling process objectives is formalized. The objective of the optimization is to generate a complete block sequence which minimizes the cost of transitions between slabs thus minimizing the overall cost of production. The Concorde exact solver is leveraged for the sequencing problem. Second, the scheduling of slabs from inventory into blocks is considered in addition to sequencing. A methodology for slab clustering is defined. The novel concept of width-groups is developed and a heuristic algorithm is devised to calculate an objective for the MILP slab scheduling model. The objective of the scheduling optimization is to construct a set of blocks which minimize deviation from the calculated width-group design. A revised sequencing model, updated to reflect the relaxations enabled by the width-group design, is formulated. Industrial production and offline trials show that the proposed scheduling-sequencing framework outperforms the human scheduler in all critical performance metrics for both scheduling and sequencing. A conservative estimate of the reoccurring monetary benefits available from use of the proposed scheduling-sequencing optimization framework is greater than $1.2M CAD per year. / Thesis / Master of Applied Science (MASc)

Yes / This paper proposes the application of a hybrid genetic algorithm (GA) for scheduling storage tanks. The proposed approach integrates GAs and heuristic rule-based techniques, decomposing the complex mixed-integer optimization problem into integer and real-number subproblems. The GA string considers the integer problem and the heuristic approach solves the real-number problems within the GA framework. The algorithm is demonstrated for three test scenarios of a water treatment facility at a port and has been found to be robust and to give a significantly better schedule than those generated using a random search and a heuristic-based approach.

Yes / This paper proposes the application of a genetic algorithm based methodology for the scheduling of storage tanks. The proposed approach is an integration of GA and heuristic rule-based techniques, which decomposes the complex mixed integer optimisation problem into integer and real number subproblems. The GA string considers the integer problem, and the heuristic approach solves the real number problems within the GA framework. The algorithm is demonstrated for a test problem related to a water treatment facility at a port, and has been found to give a significantly better schedule than those generated using a heuristic-based approach.

Yes / Proposes the application of a genetic algorithm (GA) and simulated annealing (SA) based hybrid approach for the scheduling of generator maintenance in power systems using an integer representation. The adapted approach uses the probabilistic acceptance criterion of simulated annealing within the genetic algorithm framework. A case study is formulated in this paper as an integer programming problem using a reliability-based objective function and typical problem constraints. The implementation and performance of the solution technique are discussed. The results in this paper demonstrate that the technique is more effective than approaches based solely on genetic algorithms or solely on simulated annealing. It therefore proves to be a valid approach for the solution of generator maintenance scheduling problems

No / In many production processes real time information may be obtained from process control computers and other monitoring systems, but most existing scheduling models are unable to use this information to effectively influence scheduling decisions in real time. In this paper we develop a general framework for using real time information to improve scheduling decisions, which allows us to trade off the quality of the revised schedule against the production disturbance which results from changing the planned schedule. We illustrate how our framework can be used to select a strategy for using real time information for a single machine scheduling model and discuss how it may be used to incorporate real time information into scheduling the complex production processes of steel continuous caster planning.

Search and Rescue (SAR) operations are necessary during times of natural disaster or when individuals go missing. These missions mobilize individuals, both paid and volunteer, to find lost persons and are often carried out in treacherous areas. It is important for teammates to be focused and prepared. Specifically, the search coordinator's role and the head of command directing their teammates is vital to the outcome of a SAR mission. Their workload is significant, however, inviting the opportunity for autonomy to work in tandem with the search coordinator to ensure optimal, timely decisions are made for task scheduling. There has been a significant amount of investigation into task scheduling for human-autonomy teams, but there is a gap in the ordering methods used. One possible framework to investigate uses Rasmussen's SRK framework to classify individual responses to assigned tasks. There is also a significant body of work on this framework, but very little in a proactive task scheduling context. This thesis proposes a new approach to task scheduling utilizing Rasmussen's SRK framework. Scheduling tasks in this manner allows the characteristics of the tasks themselves to be considered as well as a more streamlined approach to reducing overall cognitive load for SAR teammates. An experimental study was conducted to determine the effectiveness of the proposed task scheduling methods based on the SRK framework. Initial results suggest there is an impact on scheduling tasks with respect to SRK, but further investigation is warranted to determine more specific factors. / Master of Science / Search and Rescue (SAR) operations are necessary during times of natural disaster or when individuals go missing. These missions mobilize individuals, both paid and volunteer, to find lost persons and are often carried out in treacherous areas. It is important for teammates to be focused and prepared. Specifically, the search coordinator's role and the head of command directing their teammates is vital to the outcome of a SAR mission. They have a significant number of responsibilities, however, inviting the potential for becoming overloaded with information and decisions. This does, however, suggest a significant opportunity for autonomy to work in tandem with the search coordinator to ensure optimal, timely decisions are made for task scheduling. There has been a significant amount of investigation into task scheduling for human-autonomy teams, but there is a gap in the ordering methods used. One possible framework to use to fill this gap is Rasmussen's Skill-Rule-Knowledge (SRK) framework to categorize and predict how individuals will respond to their assigned tasks. There is also a significant body of work on this framework, but very little in a proactive task scheduling context. This thesis proposes a new approach to task scheduling utilizing Rasmussen's SRK framework. Scheduling tasks in this manner allows the characteristics of the tasks themselves to be considered. In addition, the possibility of overwhelming SAR team members can be reduced by scheduling tasks intelligently. An experimental study was conducted to determine the effectiveness of the proposed task scheduling methods based on the SRK framework. Initial results suggest there is an impact on scheduling tasks with respect to SRK, but further investigation is warranted to determine more specific factors.

The US Department of Energy has set an ambitious goal of replacing 30% of current petroleum consumption with biomass and its products by the year 2030. To achieve this goal, various systems capable of handling biomass at this magnitude have to be designed and built. The transportation system for a cotton gin was studied and modeled with the current management policy (FIFO) used by the gin to gain understanding of a logistic system where the processing plant (gin) pays for the transportation of the feedstock. Alternate management policies for transporting cotton modules showed significant time savings of 24% in days-to-haul. To design a logistics system and management strategy that will minimize the cost of biomass delivery (round bales of switchgrass), a seven-county region in southern Piedmont region of Virginia was selected as the location for a 50 Mg/h bioprocessing plant which operates 24 h/day, 7 days/week. Some of the equipment are not be commercially available and need to be developed. The transport equipment (trucks, loaders and unloaders) was defined and the operational parameters estimated. One hundred and fifty-five secondary storage locations (SSLs) along with a 3.2-km procurement area for each SSL were determined for the region. The travel time from each SSL to the plant was calculated based on a network flow analysis. Seven different policies (strategies) for scheduling loaders were studied. The two key variables were maximum number of trucks required and the maximum at-plant inventory. Five policies were based on "Shortest Travel Time - Longest Travel Time" allocation and two policies were based on "Sector-based" allocation. Policies generating schedules with minimum truck requirement and at-plant storage were simulated. A discrete event simulation model for the logistic system was constructed and the productive operating times for system equipment and inventory was computed. Lowest delivered cost was $14.68/Mg with truck cost averaging $8.44/Mg and loader cost averaging $2.98/Mg. The at-plant inventory levels were held to a maximum of 390 loads. The loaders operated less than 9,500 hours and the unloaders operated for a total of 2,700 hours for both systems simulated. / Ph. D.