summarize results for a business analytics study

MANAGEMENT SCIENCE Vol. 22. No. 12. August. 1976

Printed in U.S.A.

AN INTEGRATED - OPTIMIZATION/INFORMATION SYSTEM FOR ACADEMIC DEPARTMENTAL PLANNING*!

JAMES S. DYERJ AND JOHN M. MULVEY§

This paper describes the integration of a network optimization algorithm with a decision and information system for the Graduate School of Management at UCLA. This optimiza- tion algorithm plays an important role in the determination of the annual teaching schedule by assigning faculty to courses and other activities on the basis of their responses to course preference questionnaires. In addition, the network structure provides an ideal framework for a compact information system for the department. The system can also provide some assistance in determining faculty recruiting priorities or in studying the impacts of changes in student enrollments. Our actual experiences in implementing and using this system are described.

1. Introduction

This paper describes the formulation, implementation, and actual use of an in- tegrated optimization/information system to aid in the task of allocating and assign- ing faculty resources in an academic department. The heart of this system is a network optimization model. Its practical usefulness however, is dependent on imbed- ding the network optimization algorithm within a flexible information system. This integrated system was implemented during the 1973-4 academic year in the Graduate School of Management (GSM) at UCLA, and represents a natural extension of previous work (see Geoffrion, Dyer, and Feinberg [4], Mulvey [8], and the summary by Dyer [3]).

The problem of creating a faculty/course teaching schedule involves numerous considerations. The desires of the faculty members must be balanced against the needs and desires of the students, while acknowledging administrative policies and resource constraints. In small departments, this problem may be solved manually, with the scheduler incorporating all of these considerations into his solution based on his intuition and experience. In larger departments this task is much more difficult, and the ability of even an experienced person to determine and maintain a good schedule may be questionable.

At UCLA, the Graduate School of Management includes approximately 90 FTE (full-time equivalent) faculty members, several part-time lecturers, and some appren- tice personnel (graduate students performing teaching duties). In addition, almost 400 course sections are offered during a three quarter academic year. Prior to the development of the present system, the task of manually creating a schedule took several days. Certainly, this manual approach was not conducive to creating alterna- tive schedules for evaluation, to easily revising schedules on the basis of new information, or to answering "what if" questions regarding programmatic or staffing changes.

• Processed by Professor W. W. Cooper, former Departmental Editor for Public Administration; received March 12, 1975, revised August 2, 1975. This paper has been with the authors 2 months for revision.

+ This research was partially supported by the Graduate School of Management at UCLA. The authors wish to thank Professor David K. Eiteman, Chairman of the Department of Management, and Ms. Ida Fisher, Administrative Analyst, for their encouragement and assistance during the implementation of this system. They have also benefited from the comments of Mr. Glenn Miyataki and Mr. Robert Gray of the National Center for Higher Education Management Systems.

^ University of California, Los Angeles. ^ Harvard University.

1332

Copyright ® 1976, The Institute of Management Sciences

INTEGRATED OPTIMIZATION INFORMATION SYSTEM 1333

This situation suggested that a computer-based system could be helpful if certain simplifying assumptions were made. When the overall scheduling problem was solved manually at GSM, the assignment of faculty members to courses in particular quarters was first determined, and then the faculty/course/quarter combinations were assigned to classrooms and times. We elected to focus on the first task in this two-stage solution strategy, the faculty/course assignment problem.

The use of mathematical programming for faculty/course assignment has been proposed by others, including Andrew and Collins [1], Shih and Sullivan [II], and Swart [12], although only Andrew and Collins report an actual implementation. Andrew and Collins used the traditional assignment model as the basis for their system, which was limited to a single semester (or quarter). We propose a more general network formulation of this problem which creates a faculty/course assign- ment for all three quarters of an academic year. As a necessary* prerequisite for its routine use by administrators, we imbedded, this optimization model within an information system with extremely flexible input/output features. It is important to emphasize that this system is not intended to solve the problem in a single run, but rather to serve as a tool which assists the user in creating alternative schedules, in evaluating these schedules, and in maintaining a schedule once it has been deter- mined.

The plan of this paper is as follows. The network formulation of the faculty/course scheduling problem is presented in §2. and its limitations are discussed. The informa- tion system designed to support this formulation is described in §3. The two primary uses of the system—detailed scheduling and short-range planning— are reviewed in §4. Examples from the implementation at GSM are presented. §5 contains suggestions for extensions of the system and areas for further research.

2. The Optimization Model

In this section, we describe the network formulation which represents the optimiza- tion portion of the faculty/course scheduling system. This network formulation offers a level of detail which, we believe, provides the best compromise among computa- tional considerations, information requirements, and user needs.

A Network Formulation

The mathematical formulation of the faculty/course scheduling problem uses the following notation:

/ = number of faculty members, m = number of courses,

^iik = number of sections of course y taught b> faculty member / during time period (semester or quarter) k,

u^ = measure of the preference of faculty member / for teaching course y, r^(r.) = minimum (maximum) number of course section offerings by faculty

member / during the academic year, .̂̂ (5,-̂ ) = minimum (maximum) number of course section offerings by faculty

member / during time period k, q. (a ) = minimum (maximum) number of offerings of course y during the aca-

demic year, t k (^jk) =niinimum (maximum) number of offerings of coursey' during time period

k, ' fj = maximum number of offerings of coursey" by faculty member / in any one

time period, J, =set of courses that can be taught by faculty member /,

1334 JAMES S. DYER AND JOHN M. MULVEY

/ =set of faculty members that can teach course y, K. = set of time periods which are relevant to faculty member /, K =set of time periods which are relevant to course offering 7.

The network model can now be written:

Maximize /=!

jSJ,

,̂< 2 2

subject to

(1)

(2)

(3)

kik< 2 ^nk < j=\,...,m;ke Kj,

= 0, 1,2, . . .

(4)

(5)

(6)

One important advantage of this formulation is that constraints ( l ) - ( 5 ) can be represented as a pure network model; hence the problem is unimodular. This means that the optimal (and any intermediate) solution will be naturally integer-valued, as long as the lower and upper bounds in the constraints are integer-valued. Thus constraints (6) can be omitted from the explicit formulation. Rather than having the bipartite structure of the assignment model proposed by Andrew and Collins [1], this formulation is equivalent to a transshipment network. Another advantage is that its pictorial representation can be understood by nontechnical users, as illustrated in Figure 1.

The flow on the arcs in this network is in "course section equivalents," one unit of which is defined as the time and effort equal to the actual teaching of one course (e.g..

FACULTY QUARTERS QUARTERS COURSES

BUFFA MGT100

- - ^ D E M A N D

. 50)

SABBATICALS

15.20)

(0,20

FIGURE 1. Network Representation.

INTEGRATED OPTIMIZATION INFORMATION SYSTEM 1335

see Geoffrion, Dyer and Feinberg [4]). The numbers in parentheses on the arcs represent lower and upper bounds on the number of course section equivalents that must flow through the associated arcs. Network nodes are either faculty or course related. For each faculty member, there are up to four nodes corresponding to the annual, fall, winter, and spring schedules, respectively.' However, if a faculty member is not teaching during a particular quarter, the corresponding node is deleted; there are similar sets of nodes for the course offerings.

Figure 2 portrays several example configurations and arc restrictions. These arc flow restrictions can be useful in achieving various objectives. As illustrated in Figure 2a, the total number of course sections to be offered by apprentice personnel during the year is restricted to between twenty and thirty. However, any one quarter cannot have more than fifteen course sections offered by apprentice personnel because of the capacity restrictions on the other arcs.

Similar restrictions determine the offerings of the courses. For example. MGT 2(X)A will be offered either two or three times during the academic year (see Figure 2b). One section will be offered during the fall as indicated by the corresponding minimum and maximum flow restrictions of one. At least one section will be offered during the spring quarter, and a third section may be offered during either the winter or the spring. The determination of whether this third section will actually be offered, and during which of the two quarters, will be made by the model based on the availability of faculty resources. Figure 2c indicates that the faculty resources allocated to certain nonteaching duties, such as sabbaticals, can also be determined by the model as long as these activities are expressed in course section equivalents. Thus, the user is able to incorporate many options within the context of a simple network model.

The desires of the faculty members receive consideration in the model in two ways: First, the optimization of the network model is carried out with respect to the "preference weights'' (M^'S) of the faculty members for teaching various courses. This

(2,3)

TEACHING ASSISTANTS

Ca)

MGT200A

( b )

SABBATICALS JONES

(c) fd)

FIGURE 2. Examples of Individual Faculty/Course Nodes and Associated Arcs.

* For ease of exposition, this description is tailored to the GSM application. However, the system is sufficiently flexible to be adapted to semesters or include other variations.

1336 JAMES S. DYER AND JOHN M. MULVEY

objective function corresponds to the additive collective choice rule, which requires interpersonal utility comparisons (see Sen [10]). Within GSM, the preferences of all individuals are weighted equally, although this is not necessary.

When the additive collective choice rule is used, it is possible for a few individuals to receive schedules composed entirely of undesirable courses, and yet the sum of the preferences will be maximized. Strategies explicitly incorporated into the model for avoiding such results would introduce burdensome computational difficulties. There- fore, we rely on an iterative solution strategy to avoid serious inequities for individual faculty members.

Faculty desires are also considered through flow restrictions on the faculty/quarter arcs (constraints (2)). Subject to administrative policies, a faculty member may determine the number of courses he will teach each quarter, as illustrated in Figure 2d.

Similarly, some administrative pohcies can be satisfied through flow restrictions. The annual teaching load of each faculty member can be determined with equal or with unequal upper and lower bounds (constraints (1)). In addition, the administra- tion may elect to impose upper and lower bounds on the number of courses taught by each faculty member during each quarter (constraints (2)). It may require, for example, that each faculty member teach at least one course per quarter. Likewise, it may set restrictions on the total number of sabbatical leaves that are granted during any one year.

Information concerning the needs and desires of the students can be used to determine the upper and lower bounds on the number of sections of each course offered per academic year, and by quarter (constraints (3) and (4)). However, we have not utilized student preferences explicitly in the model to influence the assignment of individual faculty members to particular courses.

From a practical standpoint, it is much easier to obtain faculty preferences than reliable measures of how students liked professors in different courses, especially when a course is new or has not been offered by a particular faculty member in several years. In addition, we assumed that the objectives of maximizing faculty "happiness" and student ^^satisfaction" are complementary. Faculty members gener- ally prefer teaching courses that are consistent with their professional abilities and teaching styles. Likewise, students generally prefer instructors who are enthusiastic about a course and its contents. While there may be some exceptional cases, we do not feel that these occurrences justify the burden of collecting additional information beyond simple expressions of faculty preference. Of course, the preferences should be reviewed by the scheduler. For a different view of this problem see Andrew and Collins [1].

Computational Considerations

Computational considerations overwhelmingly favor a network formulation of the faculty/course scheduling problem given the current state-of-the-art in algorithmic development and computer technology (see Glover, Karney, and Klingman [5], and Mulvey [7], [9]). The costs of solving the network optimization model for GSM (with approximately 1000 nodes and 4500 arcs) using the recently developed program SUPERK (see Barr, Glover, and Klingman [2]) are in the range of 50.50 to 51.00 for the optimization, and 54.00 to 57.00 for a complete run including I / O charges.

Integer programming formulations of the faculty/course scheduling problem have been proposed by Shih and Sullivan [11] and by Mulvey [8] which include considera- tions that cannot be captured in this network model. We might wish to require that course B be offered only if course A is offered, or that course D be scheduled in the winter quarter if course C is offered in the fall, but in the spring quarter if C is taught

INTEGRATED OPTIMIZATION INFORMATION SYSTEM 1337

in the winter. Similarly, we might wish to require that each faculty member teach at least one undergraduate course. While these considerations cannot be explicitly included in the network formulation, we feel that the lower cost of solving it more than compensates for the omitted detail. This lower cost encourages the scheduler to make use of the model more frequently, and makes possible an iterative solution strategy which ensures that important considerations omitted from the network model are incorporated into the final schedule.

Information Requirements

The information requirements of the network formulation are similar to the information obtained when the schedule for GSM was determined manually. Eor each faculty member, it requires:

A list of the courses he is eligible to teach (from historical records and other inputs, including his requests) (index set 7,).

Preference weights for teaching each course on some numerical scale (e.g., —2 to + 2 ) ( « , ) .

Number of sections of each course that the individual is willing to teach per quarter

Teaching load per year (minimum, r,: maximum r,); per quarter (minimum 5,; maximum, 5,).

Plans for sabbaticals, leaves, retirement, research and administrative releases, and other nonclassroom duties that relieve the faculty from formal teaching responsibili- ties.

Identification by rank (e.g., assistant professor), area of specialization (e.g.. account- ing), and any other grouping of interest (e.g., salary level, tenured versus nontenured, etc.).

The preference weights are obtained from the faculty using a simple questionnaire. During the GSM implementation, each faculty member was provided with an initial menu of courses including each course he had taught in the previous three academic years. In addition, the introductory courses in each individual's area of specialization were included on the list even if he had not taught them in recent years. The determination of this list is an important task, since obviously a course cannot be assigned to an individual by the model if it is not on his list. The faculty members were invited to add any additional courses to the list that they might wish to teach. They were then instructed to assign a preference weight to each course from a five-point scale in which —2 is labeled "prefer not to teach," 0 is labeled "indifferent," and -1-2 is labeled "prefer to teach.^"

Even less information is required for each course. Specifically, we need: The number of sections of each course that should be offered per year (minimum,

g_ ; maximum aj)\ per quarter (minimum, bj\ maximum Z>). Identification by level (e.g., undergraduate), area of specialization (e.g., accounting),

and any other grouping of interest (e.g., lecture, seminar, or laboratory). Within GSM, a computer-based enrollment forecasting system using inputs from

student questionnaires aids in making these course-related judgments.

User Needs

User needs also influence the decisions regarding the appropriate level of detail in the model. The network formulation of the faculty/course scheduling problem is easy

2 In a field development study of this system at several colleges and departments of two other universities, department heads preferred a scale from 0 labeled "teach only if no one else will " to 5 labeled "want to teach by all means." We do not consider the choice of scale to be a critical factor in the actual use of the system.

1338 JAMES S. DYER AND JOHN M. MULVEY

to understand because it is easy to visualize pictorially, is inexpensive to solve, and requires minimal information beyond that normally gathered for the scheduling task. Nevertheless, this formulation is only an approximation to the ideal model that would solve the faculty/course scheduhng problem with finality in a single computer run. We adopt the view that the network model is only an aid to the decision-maker, and that the actual solution strategy for the faculty/course scheduhng problem will be iterative. The model will be used to provide a "good" initial solution for the decision-maker. It should then be sufficiently flexible to aid the scheduler m attempts to improve this solution. We shall now describe the information system features of the model thai were designed to assist the user in evaluating alternative schedules.

3. The Information System

The efficiency of an information system depends upon the flexibility of its report writer and its ability to assist the user in finding and recognizing a solution to his problem. Our design reflects these notions.

Report Writing Eeatures

The program accepts information regarding faculty and course categories. Overlap- ping subset groupings defined on these categories can be arbitrarily specified, and their only use within the scheduling system is in identifying subsets of the faculty a n d / o r the courses for the report writer. With this information, a series of linked list arrays are established and maintained. For further details, see Knuth [6] and Mulvey [9].

Obvious examples of subsets would be the accounting faculty and the operations research courses. The user can print the schedule for any selected subset of faculty a n d / o r courses that he might wish to see. This feature is especially important, since the pattern of course offerings within each area of specialization, such as operations research, is always of concern. The report writer can also provide the intersection of a subset of faculty and a subset of courses. For example, the user might wish to see a listing of the full professors who are teaching undergraduate courses.

The report writer provides the following four basic types of output: (1) a listing by faculty member showing his annual teaching schedule by quarter; (2) a listing by course showing the faculty members assigned to it by quarter; (3) for each quarter, a listing by faculty member showing his teaching schedule; and (4) for each quarter, a listing by course showing the faculty members assigned to it. Any of these four types of outputs can be obtained for any previously defined subset of the faculty and of the courses. Also available is an option which lists the differences between a current schedule and some previous schedule. With this option, the user can readily identify the discrepancies between two schedules. Another feature is used to answer the question, "Who can teach what?" Here, all the faculty that can teach a particular course a n d / o r all the courses that an individual faculty member is able to teach are listed. This option assists the scheduler in determining hand assignments.

"Superprof" and ''Supercourse"

A second feature of the information system originally introduced as a computa- tional convenience has proved to be of extreme importance in enhancing the value of the system to the user. We were concerned that, in some instances, the network model would have no feasible solution. That is, some instructors would not have sufficient courses to teach, while at the same time, other courses could not be staffed. This situation can easily arise given a relative oversupply of instructors in one area (e.g., accounting), but not enough instructors in another area. Therefore, we added a "superprof" to our list of faculty members with the ability to teach any course offered

INTEGRATED OPTIMIZATION INFORMATION SYSTEM 1339

within the department, but with a low preference weight ( — 9) for doing it. Similarly, we added a "supercourse" that every instructor could teach, although we assigned the low weight of - 9 to the course for each instructor. We elected to print the schedule for superprof and the instructors assigned to supercourse along with the normal assignments.

It quickly became evident that these two features were extremely important in assisting the user in isolating the problems that must be resolved before a schedule could be finalized. Superprof and supercourse highlight the planning needs of the department, and provide a reference point from which actions to meet these needs can be postulated. By studying the courses assigned to superprof, the decision-maker can determine immediately what teaching abilities are needed from additional lecturers, new faculty members, and visiting faculty members during the forthcoming academic year. The list of faculty members assigned to supercourse provides an indication of areas with excess teaching capacity.

In order to enhance this feature, we then defined a superprof and a supercourse for each curriculum area. The accounting superprof. for example, could teach any accounting course, but only these. The accounting supercourse could be offered only by the accounting faculty. Thus, if the teaching schedule could only be completed by assigning the superprof in an area several courses, then that area might receive a priority consideration for lecturers, visiting professors, and new faculty members. As an alternative, the proposed course offerings could be scrutinized to identify sections which could be dropped without serious harm to the academic programs.

4. Uses of the System

This departmental optimization/information system can be used for detailed sched- uling and maintenance and short-range planning.

Detailed Scheduling

The primary use of the system is in assisting the decision-maker in creating a complete faculty/course/quarter schedule. This task was accomplished within GSM during the winter of 1974. We considered it important to involve the faculty in this effort since they would be affected by its results, and to dispel any feelings that the schedule was determined solely by a computer. In order to generate the course data, a tentative course schedule (without faculty assignments) for 1974-75 prepared by departmental administrators was given to each faculty member. This tentative sched- ule used the concept of a minimum and a maximum number of offerings of a course for the year and for each quarter. The faculty members were asked to suggest changes in this tentative schedule, and it was modified based on this feedback. The remainder of the faculty data was obtained at the same time using a questionnaire.

Upon receipt of this data, a trial solution was generated. The imbalances in the schedule identified by the superprofs and supercourses were resolved over a period of several weeks, since in some instances it was necessary to hire visiting professors and lecturers for 1974-75 to provide the required teaching skills. Finally, a "first cut" schedule was developed in an iterative fashion by the departmental administrators. To accomplish this task, the network was modified and run several times, and some adjustments were made by hand.

The schedule was reviewed first by representatives of the curriculum areas, and then by the individual faculty members. Changes were made to accommodate any concerns that were expressed, and the schedule was finalized. As circumstances have created vacancies in this schedule, various listings provided by the report writer have been useful in resolving these difficulties through "hand assignments." The task of assigning the final faculty/course combinations to classrooms and times was accom- plished manually.

1340 JAMES S. DYER AND JOHN M. MULVEY

Of the 125 course sections actually scheduled for the fall quarter of 1974 for GSM, only one was cancelled, and no new sections were required after student enrollments. This contrasts with the more usual number of 6-10 cancellations per quarter ex- perienced prior to the use of the computer-based system.

Short-Range Planning

Short-range planning efforts consider a time horizon of one to five years into the future. This system can be used to study the effects of changes in programs, changes or shifts in enrollments, and changes in faculty resources. This short-range planning function is related to the use of the model to assist in the determination of recruiting priorities. This was actually accomplished at GSM during the fall quarter of 1973. A rough schedule of course offerings for the 1974-75 academic year was developed by departmental administrators, and the faculty preference questionnaires were distrib- uted. A schedule was generated and the superprofs and supercourses were analyzed. The areas with the most critical needs for additional manpower to staff their courses were identified. This information, along with other considerations, was used in determining the recruiting priorities for GSM for 1974-75. Similar analyses could be performed to evaluate the impacts of major changes in degree programs and course offerings.

5. Extensions and Further Research

The problem of assigning faculty resources to course sections is only one aspect of the departmental scheduling effort. Another important component involves the as- signment of faculty/course combinations to classrooms and times. Computationally, this problem is more difficult to solve since the traditional formulation requires several explicitly imposed network side constraints (e.g., see Swart [12]). Mulvey [9] has recently proposed a man-machine interactive strategy for solving this problem which we hope to implement. This strategy eliminates the need for the explicit formulation of these side constraints.

A second area of future research lies in designing the appropriate man-machine interactive environment. During the successful use of the existing system, one of the authors was the administrator of GSM responsible for scheduling and resource allocation. Although the logic and concept of this system has been enthusiastically endorsed by the other administrators, we are convinced that its continued use will depend on the development of an appropriate conversational time-sharing interface that presumes a user with little knowledge of mathematical models or computers. Eventually, secretaries and administrative assistants should be able to operate the system after a brief training session. In developing this system, we hope to gain a better understanding of man-machine interactive problem-solving in general.

Finally, we hope to generalize this system so that it can be made available to other colleges and universities. A copy of this system has been prepared for the National Center for Higher Education Management Systems of the Western Interstate Com- mission for Higher Education (WICHE). They have recently conducted a field development study of the system at several colleges and departments of two other universities. One difficulty they have encountered is that many departments use a variable workload concept. According to this concept, teaching two graduate courses may be considered equivalent to teaching three undergraduate courses, or teaching one section with a enrollment of 200 students may be considered the equivalent of teaching two sections of courses with smaller enrollments. Thus, defining the flow on the arcs of the network in "course section equivalents" may not be appropriate in every department. This issue needs to be reconciled to encourage wider use of the system. Additional details regarding this system and a "users manual" are provided by Mulvey [9].

iGKATXD"OPTIMIZATION INFORMATION SYSTEM 1341

References

1. ANDREW, G. M. AND COLLINS, R., "Matching Faculty to Courses," College and University, Vol. 46, No. 2 (Winter 1971), pp. 83-89.

2. BARR, R. S., GLOVER, F . AND KLINGMAN, D., "An Improved Version of the Out-of-Kilter Method and a Comparative Study of Computer Codes," Mathematical Programming, Vol. 7, No. 1 (August 1974), pp. 60-86.

3. DYER, J. S., "Academic Resource Allocation Models at UCLA," in A. C. Heinlein (ed.), Decision Models in Academic Administration, The Decision Science Institute of the Center for Business and Economics, Kent State University, Kent, Ohio. 1974.

4. GEOFFRION, A. M., DYER, J. S. AND FEINBERG, A., "An Interactive Approach for Multi-Criterion Optimization, with an Application to the Operation of an Academic Department," Management Science, Vol. 19, No. 4 (December 1972). pp. 357-368.

5. GLOVER, F., KARNEY, D . AND KLINGMAN, D., "Implementation and Computational Comparisons of Primal, Dual and Primal-Dual Computer Codes for Minimum Cost Network Flow Problems," Networks, Vol. 4 (1974), pp. 191-212.

6. KNUTH, D . E., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, New York, 1968.

7. MULVEY: J. M., "Column Weighting Factors and Other Enhancements to the Augmented Threaded Index Method for Network Optimization," Joint ORSA/TIMS Meeting, San Juan. Puerto Rico. October 1974.

8. , "Preliminary Application of a Resource Allocation Procedure for the Educational Sector," Discussion Paper No. 21. Operations Research Study Center, Graduate School of Management, UCLA (March 1972).

9. . "Special Structures in Network Models and Associated Applications," Ph.D. Dissertation, Graduate School of Management, University of California. Los Angeles. 1975.

10. SEN, A . K., Collective Choice and Social Welfare, Holden-Day. Inc.. San Francisco, 1970. 11. SHIH, W . AND SULLIVAN, J. A., "A Linear Programming Model for Faculty Teachmg Assignments (A

Preliminary Report)," College of Business Administration. Bowling Green State University, pre- sented at the ORSA/TIMS Meeting. Boston (April 1974).

12. SWART. W . K.. "A Course Scheduling Problem: Model Development. Analysis, and Solution Algorithms," West Virginia University. Kanawha Valley Graduate Center Institute, West Virginia, presented at the ORSA Meeting, New Orleans (April 1972).