Many systematic methods exist for mapping algorithms to processor arrays. The algorithm is usually specified as a set of recurrence equations, and the processor arrays are synthesized by finding timing and allocation functions which transform index points in the recurrences into points in a space-time domain. The problem of scheduling (i.e. finding the timing function) of recurrence equations has been studied by a number of researchers. Of particular interest here are Systems of Affine Recurrence Equations (SAREs). The existing methods are limited to affine (or linear) schedules over the entire domain of computation. For some algorithms, there are points in the computation domain where the dependencies point in opposite directions, and an affine schedule does not exist, although a valid Piecewise Affine Schedule (PAS) can exist. The objective of this thesis is to examine these schedules and obtain a systematic method for deriving such schedules for SAREs. PAS can be found by first partitioning the computation domain and then obtaining a new SARE by renaming the variables. By partitioning the computation domain, we can obtain additional parallelism from the dependency graph, and find faster schedules over subspaces of the domain. In this paper, we describe a procedure for partitioning the domain and to generate a new SARE by renaming the variables. Some heuristics are introduced for partitioning the domain based on the properties of dependence vectors. After the partitioning and renaming, an existing method (due to Mauras et al.) is applied to find the schedules. Examples of Toeplitz System and Algebraic Path Problem are used to illustrate the results. / Graduation date: 1992

Process planning and scheduling are two important manufacturing planning functions which are traditionally performed separately and sequentially. Usually, the process plan has to be prepared first before scheduling can be performed. However, due to the complexity of manufacturing systems and the uncertainties and dynamical changes encountered in practical production, process plans and schedules may easily become inefficient or even infeasible. The concept of integrated process planning and scheduling (IPPS) has been proposed to improve the efficiency, effectiveness as well as flexibility of the respective process plan and schedule. By combining both functions together, the process plan for producing a part could be dynamically arranged in accordance with the availability of manufacturing resources and current status of the system, and its operations’ schedule could be determined concurrently. Therefore, IPPS could provide an essential solution to the dynamic process planning and scheduling problem in the practical manufacturing environment. Nevertheless, process planning and scheduling are both complex functions that depend on many factors and flexibilities in the manufacturing system, IPPS is therefore a highly complex NP-hard problem. Ant colony optimization (ACO) is a widely applied meta-heuristics, which has been proved capable of generating feasible solutions for IPPS problem in previous research. However, due to the nature of the ACO algorithm, the performance is not that favourable compared with other heuristics. This thesis presents an enhanced ACO approach for IPPS. The weaknesses and limitations of standard ACO algorithm are identified and corresponding modifications are proposed to deal with the drawbacks and improve the performance of the algorithm. The mechanism is implemented on a specifically designed multi-agent system (MAS) framework in which ants are assigned as software agents to generate solutions. First of all, the manufacturing processes of the parts are graphically formulated as a disjunctive AND/OR graph. In applying the ACO algorithm, ants are deployed to find a path on the disjunctive graph. Such an ant route indicates a corresponding solution with associated operations scheduled by the sequence of ant visit. The ACO in this thesis is enhanced with the novel node selection heuristic and pheromone update strategy. With the node selection heuristic, pheromone is deposited on the nodes as well as edges on the ant path. This is contrast to the conventional ACO algorithm that pheromone is only deposited on edges. In addition, a more reasonable strategy based on “earliest completion time” of operations are used to determine the heuristic desirability of ants, instead of the “greedy” strategy used in standard ACO, which is based on the “shortest processing time”. The approach is evaluated by a comprehensive set of problems with a full set of flexibilities, while multiple performance measurements are considered, including makespan, mean flow time, average machine utilization and CPU time, among which makespan is the major criterion. The results are compared with other approaches and encouraging improvements on solution quality could be observed. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

Not available / text

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

published_or_final_version / Mathematics / Master / Master of Philosophy

A dissertation submitted to the Faculty of Engineering and the Built Environment, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Master of Science in Engineering. University of the Witwatersrand, Johannesburg, 2016 / Given a flight schedule with fixed departure times and cost, solving the fleet assignment problem assists airlines to find the minimum cost or maximum revenue assignment of aircraft types to flights. The result is that each flight is covered exactly once by an aircraft and the assignment can be flown using the available number of aircraft of each fleet type. This research proposes a novel, non-linear integer programming fleet assignment model which differs from the linear time-space multi-commodity network fleet assignment model which is commonly used in industry. The performance of the proposed model with respect to the amount of time it takes to create a flight schedule is measured. Similarly, the performance of the time-space multicommodity fleet assignment model is also measured. The objective function from both mathematical models is then compared and results reported. Due to the non-linearity of the proposed model, a genetic algorithm (GA) is used to find a solution. The time taken by the GA is slow. The objective function value, however, is the same as that obtained using the time-space multi-commodity network flow model. The proposed mathematical model has advantages in that the solution is easier to interpret. It also simultaneously solves fleet assignment as well as individual aircraft routing. The result may therefore aid in integrating more airline planning decisions such as maintenance routing. / MT2017

No description available.

Scheduling workers in a restaurant is a difficult and time consuming task that involves matching the needs of the restaurant with respect to filling various shifts for different positions, the varying availabilities of the workers, along with their seniority levels and qualifications, among other factors. The restaurant manager/scheduler must adhere to these individual workers' restrictions, while at the same time satisfy the restaurant's needs. Another issue that a manager tries to accommodate is to equitably assign shifts to workers, attempting to balance their expressed wishes with their relative merits and qualifications; although in practice, this goal is rarely achieved. In this thesis, a mathematical model is developed to solve the scheduling problem, with attention focused on maximizing worker satisfaction levels, considering their seniority levels and their qualifications, while meeting with the restaurant's needs of filling various required shifts for various positions with capable workers. We show that this model possesses a hidden network structure that can be revealed via some simple variable substitutions. Consequently, an efficient network-flow approach can be used to solve the model and derive an optimal (integer) solution. We illustrate the model and the proposed algorithmic approach by generating a schedule using real data obtained via specially designed surveys from the Cheddar's restaurant in Newport News, Virginia. Further results on a variety of test problems are used to evaluate the performance of the algorithm, and suitable pre- and post-processor considerations are addressed to permit the use of this technology in a productive environment. / Master of Science

Uncertainty surrounds us daily, indicating the need for effective decision-making strategies. In recent years, the large amount of available data has accelerated the development of novel methods for decision-making and optimization. This thesis studies this inquiry, centering on a framework that employs predictions to enhance decision-making in various optimization problems. We investigate scheduling and routing problems, which are fundamental in the field of sequential decision-making and optimization, within the framework of algorithms with predictions. Our goal is to improve performance by integrating predictions of unknown input parameters. The central question is: “Can we design algorithms that use predictions to enhance performance when the prediction is accurate while still maintaining worst-case guarantees, even when the predictions are inaccurate?” Through theoretical and experimental analyses, we demonstrate that by incorporating appropriate predictions of unknown input parameters, we design algorithms to outperform existing results when predictions are accurate while maintaining worst-case guarantees even when the predictions are significantly erroneous.

Please read the abstract in the section 00front of this document / Dissertation (MSc (Industrial Systems))--University of Pretoria, 2006. / Industrial and Systems Engineering / unrestricted