Microcomputer-based workforce scheduling

Abstract

The feasibility of using a modestly priced microcomputer to solve weekly labor tour-scheduling problems is investigated, using a new solution approach. The results from a previous experimental analysis using a mainframe computer showed that the implementation of this new approach has the potential to provide substantial improvement in labor utilization. The applicability of the approach to small service organizations that currently do not have the capability to schedule their workers using large mainframe computers is demonstrated. The results clearly support the feasibility of using microcomputers to solve workforce scheduling problems of a size that might well be expected in a typical service organization. They are particularly encouraging for labor-intensive service firms that do not have access to mainframe computers. Optimal or near optimal integer solutions to all 128 tour-scheduling problems were obtained using implicit modeling and a modestly priced microcomputer system. Fully 96% of the test problems were solved within a one-hour CPU time limit.

INTRODUCTION

Productivity improvement is a major concern for operations managers in today's economy. Shaw 1! recently reported that managers worldwide are actively seeking to enhance the productivity of their organizations and called for increased emphasis on productivity in the teaching of, and research directed towards, operations management. The need to enhance productivity is particularly crucial in service firms, for the service sector of the economy has consistently lagged behind the manufacturing sector in productivity growth since the end of the Second World War.

For service organizations, which are typically more labour-intensive than the goods producers, the key to better productivity is often sought through improvements in labour productivity. Service operations managers often attempt to improve labour-scheduling efficiency through the use of one or more types of scheduling flexibility. These scheduling flexibility types include, but are not limited to: staggered shift starting-times and overlapped shifts; shifts containing fewer than the usual eight hours of work; meal breaks and/or rest breaks which may occur within a "window" of time periods within a shift; weekly schedules which allow employees to begin work at dierent hours each day; weekly schedules which allow employees to work shifts of varying lengths each day; weekly schedules which contain fewer than the usual five days of work; and weekly schedules which provide for days-o which are not consecutive. The main advantage of scheduling flexibility is that it allows a closer match between the forecast labour requirements and the amount of labour which is actually scheduled As a simple example, onsider a small sesvice establishment which is open for business from 8.00 a.m. to 4.00 p.m. each day, five days a week. Assume that, in order to accommodate customer demand, one employee is required between the hours of 8.00 a.m. and noon; and two employees are required between noon and 4.00 p.m. each day. If no scheduling flexibility were permitted, two full-time employees would be scheduled. This establishment would thus incur four hours of excess labour each day. However, one full-time employee, and one part- time employee who works from noon until 4.00 p.m., would exactly meet the projected labour requirements without having any excess labour.

Segal 2! was one of the first researchers to note that, even with the inclusion of part-time employees in the workforce a rather large amount of excess labour could occur in those situations where all the requirements for labour had to be covered. Typically, in his research, excess labour amounted to about 9 per cent of total labour at the point where his scheduling procedure satisfied customer demand. More recent research by Showalter and Mabert 3!, Bechtold and Jacobs 4,5! Mabert and Showalter 6! and Bailey and Field 7! demonstrates that substantial improvements in labour utilization can be obtained by using a combination of labour-scheduling flexibility types.

Mathematical models of workforce-scheduling problems which incorporate scheduling flexibility are notoriously difficult to solve. This is due, in part, to the inherent complexity of these problems and is also related to the very large number of scheduling alternatives which are possible in many applications. A number of large organizations have, nonetheless, reported on the successful use of mainframe computers to schedule their operating personnel. See for example 8-12! for mainframe applications in workforce scheduling in transport; and 2,13,14! for such applications in telecommunications. Unforhnately, the potential utility of such models for perhaps the majority of service organizations has been severely restricted owing to a lack of access to mainframe computers.

This article examines the feasibility of using a modestly priced microcomputer to solve weekly labour tour-scheduling problems, using a new solution approach.The results from an earlier experimental analysis using a mainframe computer 15! showed that the implementation of this new approach has the potential to provide substantial improvement in labour utilization. The present study demonstrates the applicability of this approach to small service organizations such as restaurants, groceries, beauty shops, pharmacies, department stores and other firms which nwently do not have the capability to schedule their workers using large mainframe computers.

BACKGROUND IN LABOUR PRODUCTIVITY AND MATHEMATICAL WORKFORCE-SCHEDULING MODELS

Service industries have grown to dominate the economies of many developed nations of the world. It is widely believed that the trend in the growth of services in these economies will continue to outstrip that of the goods product sector 16,17,18!.

Growth in productivity in the service segment of the US economy, however, has been much slower than that of the goods-producing sector. In recent years there has been very little, if any, productivity improvement in the service sector. This weakness in productivity growth in the service sector has not been limited to the USA. The National Institute Economic Review of Great Britain recently reported similar results in the UK 19!.

Significant productivity gains achieved with the increased use of labour-scheduling flexibility have been reported recently in the literature. In 1985, United Airlines reported annual labour savings of approximately $6 million as a result of scheduling improvements made by using a system which provided for wider flexibility in labour schedules 9!. A new scheduling system developed for the San Francisco Police Department increased the department's ability to meet calls for service by around 25 per cent. The equivalent increase in staff which would have been required to provide this higher level of service under the old system would have increased payroll costs by $11 million annually 20!. OR/MS Today 21! recently reported that Delta Air Lines and Northwest Airlines each signed contracts for software enhancements to AT&T's Advanced Decision Support Systems' KORBX crew allocation system. With this enhanced scheduling system, Delta expects to realize annual cost reduction of $12 million, and Northwest estimates annual cost savings in the order of $10 million. Clearly, there is enormous potential for productivity improvement through efficient labour scheduling in services.

The task of developing efficient labour schedules in a service environment for tht tour-scheduling problem, particularly where scheduling flexibility is permitted, is extremely difficult. The labour-scheduling activity in services differs from that undertaken in goods production primarily as a result of the restricted ability ol services to build inventory. Inventory serves to decouple the productive unit from consumer demand, so that relatively invariant labour schedules can be constructed. In services, production activities are frequently performed at the time of occurrence of customer demand, often in the presen of the customer. Thus the labour-scheduling task in seice firms is focused primarily on matching the number of employees to an uncertain and highly variable customer demand. Research in this area has addressed three principal functions: (1) demand forecasting; (2) service level and labour requirement determination; and (3) workforce scheduling.

Demand forecasting provides information which may be used in scheduling the appropriate labour capacity to meet variable demand. Demand forecasts generated for the purpose of workforce scheduling usually express the variation in service intensity between periods of the day and between days of the week. A number of models have been successfully developed to forecast patterns of customer demand. Buffa et al. 22!, for example, described a forecasting system used by General Telephone of California which employed Box-Jenkins ARIMA modelling to generate demand forecasts. The manpower-planning system used by United Airlines 9! in its reservations personnel workforce-scheduling function is also based on ARIMA modelling.

Service level and labour requirement determination involves the conversion of customer demand forecasts into labour requirements for each forecast-planning period. This process is accomplished within the context of a prescribed service level. Determining a service level which is appropriate for a specific service organization is extremely difficult, often involving a wide range of issues in marketing, advertising, location, operating hours, and service facility layout and design. Service level may also involve customer perceptions of the courtesy, knowledgeability, and helpfulness of the service employee.

Service level, as it pertains to the establishment of labour requirements, is often prescribed by management policy as the average duration of time which customers may be expected to wait for service. A service level policy for a telephone company may,as in Segal 2! be stated, "no more than a fraction a of the nstomers will be delayed more than P units of time". Queuing models which incorporate the policy variables alpha and beta, the forecast distribution of customer arrivals each time-period, and the expected distribution of customer service times, are frequently used to determine the required number of employees each period. Edie 23!, Segal 2! and Buffa et al 22! describe such models.

Workforce scheduling involves the specification of exact schedules for employees to work. Since 1954, when George Dantzig 24! first expressed workforce scheduling as a mathematical programming problem, researchers have devised numerous solution approaches which seek to produce optimal solutions. Solution methodologies have been devised from a diverse set of approaches including linear programming, integer programming, goal programming, network flow, non-linear programming, and dynamic programming.

Mathematical models in workforce scheduling are often classified within the context of three problem categories, originally defined by Baker 25!. These problem categories are shift scheduling, day-off scheduling, and tour scheduling. We provide a brief description of the literature in each of these categories.

Segal 2! used heuristic procedures in an application in shift scheduling dealin with meal-and rest-break windows. Henderson and Berry 26!, in a study dealing with telephone operators, used a "working sub-set" of the "master set" of all possible shift schedules in order to reduce problem sizes enough to allow a heuristic solutior to be obtained. It has been noted that applications of this type often contain as many as 15,000 variables in the master set 27!. Henderson and Berry 28! presented ar optimal method using a branch and bound algorithm for solving the proble described in 26!. Bailey and Field 7! shdied the labour utilization impact of flexibk shift lengths of six, eight and ten hours. A rounding procedure developed b Bartholdi 29! was used to produce integer results. Bechtold and Jacobs 5! developed an implicit modelling approach to obtain integer optimal solutions to shift problems containing multiple shift lengths and meal-break windows.

A number of solution approaches for day-off scheduling for single and multiple shifts each day have been reported in the literahre. These studies have, for the most part, assumed that the amount of labour required for each day's shifts has beer previously determined. Tibrewala et al. 30! developed a three-step scheduling procedun which guarantees an optimal solution. Baker 31! introduced a two-phase non-iterative algorithm which was reported always to find the optimal solution, but no proof that it was optimal was produced. Bartholdi and Ratliff 32! described an efficient solution approach based on network analysis. Burns and Koop 33! presented a manpower minimizing algorithm for scheduling three shifts with constraints involving day-off requirements, k of n consecutive weekends-off requirements, and maximum work requirements. Bechtold 34! developed an implicit optimal integer-programming formulation approach for modelling employee scheduling across multiple locations. In this research, a heuristic procedure was also developed which provided near optimal solutions with very little computational effort.

The feasibility study on which we report was based on the tour-scheduling problem. The need for research in this context first was noted in Bodin 35,36!. At the time of the Bodin study, little, if any, work had been undertaken in this area. Bodin suggested, since no computer codes existed which could solve this problem, that a sequential approach might provide an appropriate solution methodology. Baker 25! also posed this as an important research direction. Baker noted that most prior research had proceeded by solving the shift model first and taking those allocations as requirements for the day-off problem, an approach similar to Bodin's earlier suggestion. Baker, however, stated, "the next step would appear to be the development of an integrative model for both the shift-scheduling and day-off allocation problems". Much of the subsequent research in tour-scheduling has attempted such an integration.

McGinnis et al 37! developed procedures for simultaneously solving the tour-schedule problem which "constructed" schedules without reourse to linear programming. These construction heuristics were shown to outperform an approach based on the sequential solution of the shift and day-off problems. This finding supported Baker's thesis that integrated solution approaches should be developed. More recently, however, in an evaluation of a number of the most widely used workforce-scheduling heuristics, Bechtold et al 38! reported that a two-stage procedure developed by Bechtold and Showalter 39! outperformed all other construction procedures.

Mabert and Watts 40! investigated the impact on labour utilization of a set of six different policies with respect to working subset selection in a tour-scheduling environment. Morris and Showalter 41! developed a heuristic procedure based on a linear programming solution to the tour-scheduling problem. Their results demonstrated that solutions of very good quality could be obtained for tour-scheduling environments which operate 24 hours a day, seven days a week. Bailey 42! developed an integer programming formulation for tour-scheduling problems. With the exception of the Bechtold 34! models, this formulation diers from previous tour-scheduling models discussed. In particular, the Bailey and Bechtold models generate an implicit assignment vector of tour-schedules, whereas explicit schedules are generated by the previously noted heuristics and LP models. An allocation procedure must be used to convert output from the Bailey and Bechtold models to explicit employees schedules.

Mabert and Showalter 6! used the solution approach described in Morris and Showalter in conducting a study in scheduling flexibility in the tour-scheduling environment. The results showed very strong labour utilization effects owing to the use of part-time workers. Recently, Easton and Rossin 43! proposed a working-set approach using a column generation heuristic in a computational study conducted in a mainframe computer environment.

In fact, most of the research studies cited above have focused on the development and use of scheduling models in mainframe computing environments. Unfortunately, the vast majority of service organizations which could make use of mathematical workforce-scheduling models are not likely to have ready access to mainframe computers. Of a total of 2.66 million service segment firms in the USA (including transportation, retail trade, and sewice industries sectors) surveyed in 44!, 2. 63 million (or about 98.8 per cent of the total number of such establishments) employed fewer than 100 employees each. Clearly most seice organizations are relatively small and are unlikely to have access to mainframe computers for use in scheduling their employees. Thus relatively small service establishments, such as groceries, restaurants, liquor stores, and pharmacies have not generally profited from the existence of the diverse set of scheduling methodology available today.

SCHEDULING APPLICATION

To test the feasibility of solving practical workforce-scheduling problems on a microcomputer within the context of an appropriate environment, we used the tour-scheduling application from a previous mainframe study which was conducted with the purpose of determining the impact of labour-scheduling flexibility on efficient labour utilization 15!. We assume that demand forecasts have been made and that appropriate labour requirements have been determined. The labour requirements have been designated on an hourly basis over a seven-day scheduling horizon and occur in fewer than 24 hours per day on each of the seven days of the horizon. The workforce-scheduling problem contained the following flexibility types:

(1) employees who work fewer than eight hours per day (shift length flexibility);

(2) employees who work fewer than five days per week (tour length flexibility);

(3) employees who receive a meal break during any one of a number of defined periods within their shift (meal-break flexibility);

(4) employees who may begin work in any period of the day, so long as their shifts do not extend beyond the end of the day (shift-start flexibility);

(5) individual employees who may begin work in different periods on different days of the week (start-time float flexibility);

(6) employees who may receive their recreation days on non-consecutive days of the week (non-consecutive days off;

and the following attributes of labour requirement variability:

(1) length of service day;

(2) mean of labour requirements;

(3) amplitude of labour requirement.

For the microcomputer feasibility study, we tested one basic pattern of labour requirement demand. That pattern was unimodal across the day and week, with maximum demand for labour occurring in the centre period of the day (week). The pattern was synthetically generated to obtain a set of hypothetical hourly labour requirements.

The three attributes of labour requirement variability were included in the microcomputer feasibility study primarily to determine how well the solution approach would perform across a wide variety of environmental conditions. In the prior mainframe study 15!, none of the three attributes of labour requirement variability was associated with any significant degradation in solution performance. The results had, however, indicated that longer execution times could be expected for problems having longer day lengths.

The scheduling flexibility types are generally representative of the nature of the scheduling problem faced by many service establishments, including those which typically do not have access to mainframe computers for workforce scheduling. In the prior mainframe study, certain of these scheduling flexibility types were found to be associated with important improvements in labour utilization. These findings are widely applicable to managers of both large and small service firms, where the ability exists to schedule their operating personnel using computers. Specifically, meal-break flexibility, shift-start flexibility, and shift-length flexibility were fowld to be extremely eective in improving labour utilization. Similarly, tour-length flexibility resulted in substantial improvement in labour utilization. Details of these findings and their implications are discussed in 15!.

MODELLING APPROACH

The mathematical programming representation of the tour-scheduling problem has traditionally been expressed as Dantzig 24! set-covering formulation for workforce scheduling. This formulation requires a unique variable for every allowed schedule. Using the Dantzig set-covering formulation to model the flexibility types included in the cuwent study would have resulted in an extremely large number of variables. A total of 128 problems, comprising various combinations of flexibility types and labour requirement variability attributes noted above,were included in this study. The average number of set-covering variables in this problem set exceeded 64 million, and the largest problem required over 3.8 billion variables. Regardless of the availability of commercial hardware and software, modelling these test problems according to the traditional set-covering formulation would result in problem sizes so large that optimal or near-optimal solutions could not be obtained with mathematical programming methods.

The formulation used in this feasibility study was based on modelling methods published in Bailey 421, and Bechtold andJacobs 4,5!. The extension of this methodology to the weekly tour-scheduling environment is described in detail in Jacobs 15!. This new approach yielded a much more compact formulation, which was accomplished through the use of implicit representation of the allowed work schedules.

This new implicit modelling approach was based on the realization that it was likely that substantial reductions in model size could be achieved only by reducing the information requirements of the model. A large reduction in the information requirements was achieved in the new modelling approach through implicit representation of break assignments for all shifts and shift assignments for all weekly tours. Specifically, this was accomplished by associating break variables with planning periods as opposed to shifts, and by associating shifts with day-long planning periods as opposed to weekly tours. A particular break variable represents the total number of employees starting a break in its associated planning period; individual shift variables represent the number of employees working a specific shift on a specific day.

The variables in the implicit model do not provide information concerning the timing of the breaks and shifts.Therefore actual schedules are determined by assigning the breaks represented by the optimal values of the break variables to the appropriate shift types and by assigning the shifts represented by the optimal values of the shift variables to the appropriate day-on types. Efficient procedures were developed to make these assignments 5,15!.

A Fortran computer program was written to generate the input matrices. Summary input matrix characteristics of the 128 test problems used in this study are reported in Table I.

*T

INPUT MATRIX CHARACTERISTICS FOR THE IMPLICIT MODEL

VARIABLES CONSTRAINTS

Minimum 35 106

Maximum 469 398

Average 155 208

-0

It is evident from Table I that the use of the implicit formulation resulted in an immense reduction in the number of decision variables required for mathematical modelling. Nevertheless, the implicitly represented problems were still quite large for input to integer-programming software. Therefore the 128 test problems represented a significant challenge for the hardware and software configuration which could be expected in a typical small services application.

COMPUTER INFORMATION

The microcomputer used in the study was a Zenith PC equipped with a 15MHz 80386 CPU supported by an 80287 maths co-processor running under DOS 3.30, a 40 megabyte hard disk, and one megabyte of extended memory. An experimental pre-release version of SAS/OR PC was used to solve the study problems. This software product has since been released and is now commercially available 45!. The microcomputer hardware/software package used in this study currently retails for less than $3,000.

To assess the feasibility of solving integer problems of this size, we tested the 128 scheduling problems on the microcomputer system described above and on SAS/OR installed on an Amdahl mainframe computer. A preliminary study had indicated the Amdahl to be approximately 60 times faster than the microcomputer. The SAS/OR time-limits were, therefore, set a 60 to 1 ratio: 3,600 CPU seconds for the microcomputer and 60 CPU seconds for the mainframe. The preliminary study also indicated that the microcomputer version of SASIOR required a substantial amount of free disk space to store temporary work files; therefore 15 megabytes of free space were maintained on the microcomputer system'S hard disk. This proved to be an adequate work space for all the problems executed in this study.

RESULTS

Given the size of the labour tour-scheduling problems included in this study, it was unrealistic to expect that optimal solutions would be obtained for all test problems within the prescribed time-limits. Indeed, Table II indicates that optimal solutions were not achieved for all problems. (Table II omitted) However, the microcomputer achieed optimal integer solutions for 75 per cent (96 of 128) of the test problems. Surprisingly, the microcomputer produced more integer optimal solutions than the mainframe.

The mainframe was able to achieve at least the fractional (relaxed) optimal linear programming solution for all test problems. Unfortunately, a relaxed solution to a workforce-scheduling problem presents less information of immediate value since the solution must be subjected to some type of rounding heuristic prior to assingment of employees. The microcomputer was unable to find the relaxed solution for only two of the 128 problems within the one-hour time-limit.

Table III summarizes the CPU times recorded in the study. In general, the mainframe appears to be about 40 times faster than the microcomputer. However, owing to the difference in solution quality, a meaningful comparison of execution times is not possible.

*T

Computer Minimum CPU Maximum CPU Average CPU system seconds seconds seconds

Mainframe 1.03 60 21.84

Microcomputer 50.00 3,600 852.42

-0

As shown in Table II, the microcomputer did not produce integer solutions for five of the test problems (including the two problems for which no solution was found). To determine how much time might be required to produce usable schedules for these five problems, they were rerun using first a two-hour time-limit, then a four-hour time-limit.

Table IV shows the time required to produce relaxed and integer solutions for each of these problems. As Table IV shows, extension of the CPU time-limit for the microcomputer produced integer solutions for the five workforce-scheduling problems for which an integer solution was not achieved with a one-hour time-limit. Three of the five problems were solved to an integer solution within two hours with the remaining two problems reaching an integer solution within four hours.

*T

One-hour Two-hour Four-hour Problem time-limit time-limit time-limit number solution solution solution

92 relaxed integer -

116 relaxed integer optimal -

122 no solution relaxed integer

123 no solution relaxed integer

124 relaxed integer -

-0

The microcomputer did not produce optimal solutions for all test problems. To determine how far the solutions might be from optimal, the maximum potential divergence from optimal was computed for each problem. This value was obtained in a two-step procedure. First, the relaxed solution was obtained for each problem and the smallest feasible integer schedule value greater than the relaxed solution was computed. Second, the percentage dierence between the value so obtained and the integer solution was computed for each problem. The results of this analysis could not be directly compared with the mainframe study, since a total of 16 problems did not yield integer solutions on the mainframe. Therefore solutions from a prior mainframe study 15! of the 128 test problems were used as a benchmark for comparing the quality of the solutions obtained using the microcomputer. This prior study had used a three-stage solution approach to obtain high quality integer solutions to this problem set. Table V shows the results of this comparison.

*T

Computer Optimal Average potential system solutions divergence from (% of total) optimal (%)

Mainframe (three-stage) 79.69 0.33

Microcomputer 75.78 0.52

-0

Table V shows very little difference in solution quality between the microcomputer results and the three-stage mainframe results. Specifically, the three-stage mainframe solution approach was able to identify only an additional five optimal solutions, and improved the average potential divergence from optimal by only 0.19 per cent.

CONCLUSION

The results of this study clearly support the feasibility of using microcomputers to solve workforce-scheduling problems of a size which might well be expected in a typical service organization. These results are particularly encouraging for small labour-intensive sewice firms which do not have ready access to mainframe computers.

Optimal or near optimal integer solutions to all 128 tour-scheduling problems were obtained using implicit modelling and a modestly priced microcomputer system. Ninety-six per cent of these test problems were solved within a one-hour CPU time-limit, and the worst-case CPU solution time was only four hours. The relatively brief solution times observed in this study suggest that service firms probably would not need to purchase a microcomputer dedicated specifically to the workforce-scheduling task. A manager could submit the firm's scheduling problem for solution at a time when the microcomputer would not otherwise be engaged. Many service organizations which currently use microcomputers would probably be able to allocate, from existing equipment, an additional four hours of microcomputer CPU time per week for workforce scheduling.

The quality of the solutions obtained in this study was very encouraging and compared quite favourably with results obtained using a mainframe computer. Optimal solutions were generated for more than 75 per cent of the problems using the microcomputer system and the potential divergence from optimal averaged less than 0.6 per cent. The best result we could obtain using a mainframe computer on this problem set yielded only a very slight improvement. The environmental conditions, length of service day, mean of labour requirements, and amplitude of service requirement, were not associated with any differences from the results obtained in the mainframe study. Clearly, optimal, or very near optimal, solutions to realistically sized workforce-scheduling problems are obtainable using implicit modelling and a currently available microcomputer system.

Our results show that the computational power for worldorce scheduling, previously available only to mainframe computer users, is attainable by users of small microcomputer systems. This encouraging finding strongly suggests that labour utilization improvements of the kind regularly reported by large service organizations using mainframe computers may become available to smaller organizations through the use of microcomputers.

Finally, it is not uncommon for managers of small service operations to spend a substantial amount of their time in the preparation of labour schedules for their workers. The use of microcomputer-based scheduling systems should provide the opportunity to reduce the amount of managerial time and effort associated with the development of labour schedules manually. This would enable the managers, as well as the workers, to use their time more productively.

The scheduling flexibility types and labour requirement variability attributes included in this study were representative of the numerous flexibility options available to many service operations managers. Therefore future research should investigatethe impact of other kinds of flexibility, such as split shifts, rest-break (as well as meal-break) flexibility, employees who work dierent shift lengths on subsequent days of their tours, and simultaneous usage of multiple kinds of flexibility. In addition, such studies could consider other attributes of labour requirement variability, such as multiple peaks and troughs of labour requirement demand across the planning day and week (the underlying shape of the distribution of labour requirements), labour requirements which must be satisfied across different geographical locations, and stochastic demand for labour.

This report is a feasibility study and represents a first step towards bringing the power of today's workforce-scheduling models to the microcomputer environment. A great deal of work remains to be done before that goal can be accomplished. For example, while the experimental release of SAS/OR PC produced good results, a number of other packages are now available which may be capable of finding good solutions with less computer time. Faster solvers would be particularly valuable in cases where managers wished to investigate "what-if?" scenarios involving adjustments to an optimal schedule.

Additionally, other problem types need to be addressed. For example, many retail service firms, such as some convenience stores, groceries, and restaurants, remain open to the public 24 hours each day. Models which address such continuously operating organizations need to be developed. Also the problem set studied assumed that the firm's employees could work any feasible schedule produced. While this assumption is valid in some organizations (for example, retail groceries, hotels, pharmacies, auto repair establishments, some banking operations), new research needs to consider the case where organizations must schedule an existing pool of employees who are restricted in their availability for work.

Finally, we suggest that the next logical step is the development of actual workforce-scheduling systems, capable of representing a substantial degree of scheduling flexibility, to be installed on microcomputer. Firms which have the ability to make use of large-scale workforce-schedulmg systems installed on mainframe computers, such as AT&T's KORBX crew-scheduling system, have the opportunity for significant cost savings. We have demonstrated that it is possible, with currently available knowledge and computer techniques, to develop powerful workforce-scheduling systems for users of microcomputers.

REFERENCES

1. Shaw, W.N., "Productivity Improvement: An Important Issue for Private and Public Sector Organizations", International Journal of Operations & Production Management, Vol. 8 No. 7, 1988, pp. 42-53.

2. Segal, M., "The Operator-scheduling Problem: A Network-flow Approach", Operations Research, Vol. 22, 1974, pp. 808-23.

3. Showalter, M.J. and Mabert, V.A., "An Evaluation of a Full/Part-time tour-scheduling Methodology", International Journal of Operations & Production Management, Vol. 8 No. 7, 1988, pp. 54-71.

4. Bechtold, S.E. and Jacobs, L.W., "Improvement of Labour Utilization in Shift Scheduling for Services with Implicit Optimal Modelling", International Journal of Operations and Production Management Vol. 11 No. 2, 1991, pp. 54-69.

5. Bechtold, S.E. and Jacobs, L.W., "Implicit Modeling of Flexible Break Assignments in Optimal Shift Scheduling", Management Science, Vol. 36 No. 11, November 1990, pp. 1339-51.

6. Mabert, V.A. and Showalter, M.J., "Measuring the Impact of Part-time Workers in Service Organizations", Journal of Operations Management, Vol. 9 No. 2, 1990, pp. 209-29.

7. Bailey, J. and Field, J., "Personnel Scheduling with Flexshift Models", Journal of Operations Management, Vol. 5 No. 1, 1985, pp. 327-38.

8. Gabella, A. and Pearce, W., "Telephone Sales Manpower Planning at QANTAS", Interfaces, Vol. 9 No. 3, May 1979, pp. 1-9.

9. Holloran, T.J. and Byrn, J.E., "United Airlines Station Manpower.planning System", Interfaces, Vol. 16 No. 1, January.February 1986, pp. 39-50.

10. Lavoie, S., Minoux, M. and Odier, E., "A New Approach for Crew-pairing Problems by Column Generation with an Application to Air Transportation", European Journal of Operational Research, Vol. 35, 1988, pp. 45-58.

11, Paixao, J. and Pato, M., "A Structural Lagrangean Relaxation for Two-duty Bus Driver Scheduling Problems", European Journal of Operational Research, Vol. 9, 1989, pp. 13-22.

12. Smith, B.M., "IMPACS--A Bus Crew Scheduling System Using Integer Programming", Mathematical Programming, Vol. 42, 1988, pp. 181-7.

13. Henderson, W.B. and Berry, W.L., "Determining Optimal Shift Schedules for Telephone Traffic Exchange Operators", Decision Sciences, Vol. 8, 1977, pp. 239-55.

14. van Oudheusden, D.L. and Wen-Jenq, W., "Telephone Operator Scheduling with a Fixed Number of Operators", European Journal of Operational Research, Vol. 11, 1982, pp. 55-9.

15. Jacobs, L.W., "A Compact Integer-programming Approach to Workforce Scheduling: A Study in Flexibility", Doctoral Dissertation, College of Business, The Florida State University, Tallahassee, FL, University Microfilms publication number 9002926, UMI, Ann Arbor, MI, 1989.

16. Kendrick, J.A., "Service Sector Productivity", Business Economics, Vol. 22 No. 1, April 1987, pp. 18-24.

17. Monthly Labor Review, "Deindustrialization and the Shift to Services", June 1986.

18. Haugen, S.E., "The Employment Expansion in Retail Trade, 1973-1985", Monthly Labor Review, US Department of Labor, Bureau of Labor Statistics, Washington, August 1986.

19. "Productivity in Services", Naonal Institute Economic Review, No. 115. February 1986.

20. Taylor, E. and Huxley, SJ., "A Break from Tradition for the San Francisco Police: Patrol Officer Scheduling Using an Optimization-based Decision Support System", Interfaces, Vol. 19 No. 1, January.February 1989, pp 4.24.

21. OR/MS Today, June 1991, pp, 16-7.

22. Buffa, E.S., Cosgrove, MJ. and Luce, B,T., "An Integrated Work Shift-scheduling System", Decision Sciences, Vol. 7 No. 4, 1976, pp. 620-30.

23. Edie, L.C., "Traffic Delays at Toll Booths", Journal of Operations Research Society of America, Vol. 2 No. 2, 1954, pp. 107-38.

24. Dantzig, G.B., "A Comment on Edie's Traffic Delay at Toll Booths", Operations Research, Vol. 2 No. 3, 1954, pp. 339-41.

25. Baker, K.R., "Workforce Allocation in Cyclical Scheduling Problems: A Survey", Operational Research Quarterly, Vol. 27 No. 1, 1976, pp. 155-67.

26. Henderson, W. and Berry, W., "Heuristic Methods for Telephone Operator Shift Scheduling: An Experimental Analysis", Management Science, Vol. 22 No. 12, 1976.

27. Klasskin, P.M., "Operating to Schedule Operators", TelePhony, 30 July 1973, pp. 29-31.

28. Henderson, W. and Berry, W., "Determining Optimal Shift Schedules for Telephone Traffic Exchange Operators", Decision Sciences, Vol. 8 No. 2, 1977.

29. Bartholdi, JJ., "A Guaranteed-accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering", Operations Science, Vol. 29 No. 3, 1981.

30. Tibrewala, K., Philippe, D. and Browne, J., "Optimal Scheduling of Two Consecutive Idle Periods", Management Science, Vol. 19 No. 1, 1972, pp. 71-5.

31. Baker, K.R., "Scheduling a Full-time Workforce to Meet Cyclic Staffing Requirements", Management Science, Vol. 20 No. 12, 1974, pp. 1561-8.

32. Bartholdi, JJ. and Ratliff, H.D., "Unnetworks, with Applications to Idle Time Scheduling", Management Science, Vol. 24 No. 8, 1978, pp. 850-8.

33. Burns, R.N. and Koop G.J., "A Modular Approach to Optimal Multiple-shift Manpower Scheduling", Operations Research, Vol. 35 No. 1, 1987, pp. 100-10.

34. Bechtold, S.E., "Implicit Optimal and Heuristic Labor Staffing in a Multiple-Objective, Multilocation Environment", Decision Sciences, Vol. 19 No. 2, 1988, pp. 353-73.

35. Bodin, L.D., "Towards a General Model for Manpower Scheduling--Part 1", Urban Analysis, Vol. 1, 1973, pp. 191-207.

36. Bodin, L.D., "Towards a General Model for Manpower Scheduling--Part 2", Urban Analysis, Vol. 1, 1973, pp. 223-45.

37. McCinnis, L.E, Culver, W.D. and Dean, R.H., "One-and Two-phase Heuristics for Workforce Scheduling", Computers and Industrial Engineering, Vol. 2 No. 1, 1978.

38. Bechtold, S.E., Brusco, MJ. and Showalter, M.J., "A Comparative Evaluation of Labour Tour-scheduling Methods", Decision Sciences, Vol. 22 No. 4, 1991, pp. 683-99.

39. Bechtold, S.E. and Showalter, M.J., "A Methodology for Labor Scheduling in a Service Organization", Decision Sciences, Vol. 18 No. 1, Winter 1987.

40. Mabert, V.A. and Watts, C.A., "A Simulation Analysis of Tour-shift Construction Procedures", Management Science, Vol. 28 No. 5, 1982, pp. 520-32.

41. Morris, J.G. and Showalter, M.J., "Simple Approaches to Shift, Days-off and Tour-scheduling Problems", Management Science, Vol. 29 No. 8, 1983, pp 942-50.

42. Bailey, J., "Integrated Days-off and Shift Personnel Scheduling" Computers and Industrial Engineering, Vol. 9 No. 4, 1985, pp. 395-404.

43. Easton, F.F. and Rossin, D.E, "Sufficient Working Subsets for the Tour-scheduling Problem", Management Science, Vol. 7 No. 11, 1991, pp. 1441-51.

44. 1987 Enterprise Statistics, Company Surveys, ES87-3, US Department of Commerce, Economics and Statistics Administration, Bureau of the Census, June 1991.

45. SAS/OR User's Guide, Version 6, 1st ed., SAS Institute Inc., Cary, NC, 1989.