Doctoral Dissertations

Date of Award

5-1991

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Management Science

Major Professor

Kenneth C. Gilbert

Committee Members

Charles E. Noon, James K. Ho, Bruce A. Ralston

Abstract

In this dissertation research we have investigated solution approaches for the problem of scheduling of instructors (ISP) in the executive development programs offered by the Institute of Productivity through Quality at the College of Business Administration, University of Tennessee, Knoxville. There has been two principal thrusts in this research. First, we have developed and tested three different solution approaches for the Instructor Scheduling Problem (ISP). Second, we have carried out the design, development, testing, and implementation of a comprehensive decision support system (DSS) for the ISP. In the first solution approach, the ISP has been formulated as a linear integer programming problem. Strategies based on variable/constraint elimination have been developed to reduce the problem size so that it is solvable by commercial software. The solution time of the mathematical program exceeds forty minutes. Hence a knowledge based heuristic has been developed and implemented. The heuristic acts as an "intelligent and smart" assistant that has the initial knowledge and computing ability to find quick answers. The assistant, however, lacks the experience of the human user who must therefore guide the computer based DSS in finalizing the schedule. The knowledge based heuristic takes less than 25 seconds to generate a final schedule. Three approaches for schedule generation and four approaches for schedule improvement are investigated. This gives rise to twelve heuristics that are tested on 81 randomly generated problems and two real problems. Average Percentage Deviation of the best heuristic from the optimal solution is found to be 1.14% for random problems and 5.93% for real problems. In the third approach, lagrangian relaxation of ISP based on a subproblem that can be solved efficiently has been used to develop strong upper bounds and heuristic solutions. It is shown that this subproblem is an example of a special active resource scheduling problem (SARS). Three efficient solution procedures based on (a) transforming the problem to one that has a totally unimodular constraint matrix, (b) formulating the problem as a minimum cost network flow problem, and (c) formulating the problem as a transportation problem are presented for the SARS problem. Four Lagrangian Relaxations of the ISP utilizing efficient solutions of SARS as a network have been developed to yield strong upper bounds and good quality heuristic solutions. For random problems these procedures have found upper bounds that were within 100.12% of the optimal and heuristic solutions that were within 99.72% of the optimal on an average. A hierarchical strategy for responding to the planning needs of the scheduler is proposed. This strategy suggests use of the optimal solution for generation of the first plan, monthly updating by use of the lagrangian heuristics and more frequent updating by use of the knowledge based heuristics. The scheduling environment changes frequently due to changes in faculty availability and course offerings. Provision has been made to respond to the changes. As output, the DSS develops a final schedule, a statement of teaching assignments, a statement of work performed by instructors, and a summary statement for management control and planning.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS