Scheduling personnel with an artificial intelligence program.
After many long afternoons with pencil and paper, struggling to schedule a limited hematology staff every six weeks, we concluded there must be a better way.
Trying to map out two shifts per day, seven days a week, while taking into account vacations, holidays, and requests for days off, without incurring any overtime, was too time-consuming. Putting a microcomputer to work on this task appeared to be an obvious solution.
The most commonly used programming languages, such as Basic and Fortran, could not help because they were unsuited to logicoriented problems. Fortunately, artificial intelligence language programs employed to develop expert systems had made their way into the microcomputer market. We purchased Turbo Prolog (Borland International, 4585 Scotts Valley Drive, Scotts Valley, Calif. 95066) for less than $100 to tackle scheduling of the hematology staff.
Prolog has an easy-to-use editor for writing programs and a very fast compiler that converts the written program to the machine language of the computer. It also supports screen graphics and text windows, which we found useful in development of the scheduling program.
The minimum computer configuration for Prolog is an IBM PC, 384K RAM internal memory, and an MS-DOS operating system (version 2.0 or later). Although one of us had computer programming experience in other languages, this was our first endeavor with artificial intelligence.
Prolog uses a set of facts (a database) and a set of rules and relationships (clauses and predicates) to arrive at a specified goal. A Basic program will perform calculations and operations in a rigid order. Prolog, on the other hand, will find an intermediate solution to a subgoal and attempt to satisfy the next subgoal. If the attempt fails, the program backtracks to the intermediate solution of the first subgoal, discards it, and searches for another intermediate solution.
Scheduling will illustrate this process. The hematology section's staff consists of a supervisor, three full-time technologists on the day shift, and one full-time technologist on the evening shift. The day technologists also rotate to cover the later shift when the evening technologist is away. This information forms the beginnings of the database:
supervisor works days
tech#1 works days and tech#1 works evenings
tech#2 works days and tech#2 works evenings
tech#3 works days and tech#3 works evenings
tech#4 works evenings
In Prolog, this relationship between person and shift could be
written in the following manner:
The individual facts in the database would then be written as:
works (tech #1, days)
works(tech # 1, evenings)
Any information that is not explicitly written into the database is considered by Prolog to be false.
To start, we would like the program to select an employee designated for only the evening shift as our first choice to fill the position one evening. That choice is clear and could be made instantly without computer assistance, but the steps taken will show how Prolog works.
The first rule for selecting an employee to work an evening shift would be: Select a person who works evenings but does not work days. In the language of Prolog, this rule would be written as two subgoals:
Since Person is capitalized, Prolog treats it as a free variable to be matched by a search through the database. Think of the database as a stack of cards examined one at a time.
Subgoal 1: works(Person,evenings) Prolog result
works(supervisor,days) no match
works(tech#1,evenings) matches, Person =
tech#1 equal to tech#1. With the solution to subgoal I established, Prolog now tries to meet the conditions of subgoal 2.
That formulation now will contain tech#l as Person. If the search through the database does not find tech#l working days, subgoal 2 will be satisfied.
Subgoal 2: not(works(tech#1,days)) Prolog result
works(supervisor,days) no match
So subgoal 2 is not met. Prolog frees the variable Person from being equal to tech#l and renews its search for a solution to the first subgoal, beginning where it left off:
Subgoal 1: works(Person,evenings) Prolog result
works(tech#2,evenings) matches, Person =
This intermediate solution to the first subgoal will fail the test of the second subgoal, as will Person = tech#3, because technologists 2 and 3 work days as well as occasional evenings. The intermediate solution Person = tech#4 does succeed, however, since the database does not contain "works(tech#4,days)."
Prolog has the capability of changing facts within its database or changing the order in which the facts are stored. A simple example of these features demonstrates how we were able to rotate our staff throughout the work schedule.
Suppose Prolog has selected tech#1 to work one daytime shift in the schedule. The program will then automatically remove the fact "works(tech#1,days)" from the database, using the command "retract," and reinsert the fact at the end of the database with the command "assertz." In other words, once used, the fact goes to the bottom of the stack of cards. The next time Prolog searches for a person to work the day shift, the first match it encounters will be "works(tech#2,days)."
Not all the rules we use for scheduling personnel were immediately apparent to us when we first wrote the scheduling program. At times, the program had to be restructured to accommodate an additional rule. The following are scheduling rules we have used:
1. Schedule a minimum of three employees per day, two on the day shift and one on the evening shift.
2. As a first option, select the staff member designated as full time for the evening shift to work an evening shift.
3. The section supervisor
works the day shift only.
4. No one works double shifts.
5. An employee who works an evening shift will not work the day shift the following day.
6. An employee will not work either shift when scheduled for a vacation or a holiday.
7. An employee should not work more than five days per week.
8. If overtime is unavoidable on a particular day, schedule only two employees to work.
Much of the program is devoted to making it as easy as possible to enter scheduled days off and scheduled shifts. We have taken full advantage of Prolog's features in creating windows and editing data on screen.
When the program is run for the first time, it reads start-up information concerning staffing from a disk file and displays six blank weekly calendars (or windows) side by side on the screen for each of the six weeks to be scheduled. The days of the week run across the top of each window; down the left side of the screen is the list of available staff. Each window can be edited separately. A single character is entered on a particular day of a week to specify that an employee is assigned to the day shift (the letter X) or the p. m . shift (P), or that the employee has the day off (0), is on vacation (V), or is out because of a holiday (H).
Days off, vacations, and holidays are entered by the operator. Other spaces on the calendar are filled in by the computer. If the computer is unable to assign someone to a shift because of our scheduling rules, that day's space is left blank.
Each week's completed schedule is presented in an overlaid window for the operator to review (see Figure 1). The number of days to be worked by each staff member is also listed. Once the review is done, the program prints a copy of the full six-week schedule displayed on the screen (see Figure 11).
The program searches only for the minimum required staffing. If an individual has not been assigned enough days for the pay period, the operator must provide the additional scheduling. And if overtime is required, that selection too is left to the operator.
In case the final schedule is unsuitable, or the operator just wants to see what happens when a certain change is made, the calendar of assigned days can be recalled and edited. If the program is rerun, it reads the last calendar from disk; after the re-editing, a new schedule can be generated.
We have found that it is best to input a minimum of scheduling at the outset and leave most of the decisions to the computer. Its solutions can be quite creative. On occasion, the program has overridden initial scheduling decisions we made that resulted in overtime, in favor of a schedule without any overtime. In addition, the staff has complained less about scheduling since the function became computerized.
With a small investment of time, this program can be easily adapted to meet the needs of other laboratories. Readers can obtain a hard copy of the program and the source code by sending $2 and a self-addressed envelope without postage to the authors at 17109 Elm Drive, Hazel Crest, Ill. 60429. Alternatively, we can send a 5-1/4-inch floppy disk containing an executable program and source code for a $10 fee, which will cover the cost of the disk and handling.
|Printer friendly Cite/link Email Feedback|
|Author:||Hefley, Donna; Hefley, Thomas|
|Publication:||Medical Laboratory Observer|
|Date:||Feb 1, 1989|
|Previous Article:||Selecting laboratory instrumentation.|
|Next Article:||Four tested ways to avoid labor strife.|