A new implementation of the calendar queue is described in this thesis. The calendar queue as previously implemented depended upon the use of multiple linked lists for the control of queue discipline. In the calendar heap implementation, the heap has been used to replace the previous functions of the linked list. Testing of the claim of O(1) execution time for the calendar queue was done. Comparisons of execution times of the calendar queue and the calendar heap have been made. Descriptions of the implementation as well as the complete C code for the calendar heap are included.

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

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

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / abstract / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

This research is concerned with scheduling production over a finite planning horizon in a capacitated manufacturing facility. It is assumed that a second source of supply is available by means of subcontracting and that the demand varies over time. The problem is to establish the production level in the facility and/or the ordering quantity from the subcontractor for each period in the planning horizon. Firstly, the cost functions are analyzed and two types of realistic production cost models are identified. Then mathematical models are developed for two different problems. One is a single criterion problem aimed at minimizing the total production and inventory costs. The other is a bicriterion problem which seeks the efficient frontier with respect to the total cost and the number of subcontractings, both to be minimized, over the planning horizon. For each of the above, two methods, namely, a general dynamic programming approach and an improved dynamic programming approach (Shortest path method) are presented. Several results are obtained for reducing the computations in solving these problems. Based on these results, algorithms are developed for both problems. The computational complexity of these algorithms are also analyzed. Two heuristic rules are then suggested for obtaining near-optimal solutions to the first problem with lesser computation. Both rules have been tested extensively and the results indicate advantages of using them. One of these rules is useful for solving the uncapacitated problem faster without losing optimality. The above results are then extended to other cases where some of the assumptions in the original problem are relaxed. Finally, we studied the multi-item lot-sizing problem with the subcontracting option and proposed a heuristic for solving the problem by the Lagrangean relaxation approach. We demonstrated that with an additional capacity constraint in the dual problem the feasible solution and the lower bound obtained during each iteration converge much faster than without it. After testing some randomly generated problems we found that most of the solutions obtained from the heuristic are very close to the best lower bound obtained from the dual problem within a limited number of iterations.

No description available.

Crew schedules on the South African Transport Services are done by roster compilers at depots. A method that uses heuristic and mathematical programming algorithms was developed to replace existing hand methods. It is a two stage method that will use a microcomputer to assist roster compilers to draw up crew schedules. Initially timetables are subdivided into shifts and then they are combined into crew schedules. The solution, which produces a significant improvement compared with an existing crew schedule and an existing method, has been accepted in principle and computer programming has begun. In Appendix E another heuristic for the scheduling of league matches is described.