Printer Friendly

Scheduling personnel with an artificial intelligence program.

Donna Hefley is hematology supervisor at South Suburban Hospital, Hazel Crest, Ill, Her coauthor is assistant professor in the de padment of pharmacology at Northwestern University, Chicago.

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:

works (Person,evenings)


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,days) nomatch

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

works(tech#1,days) matches

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#1,evenings) discarded

works(tech#2,days) nomatch

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.
COPYRIGHT 1989 Nelson Publishing
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 1989 Gale, Cengage Learning. All rights reserved.

Article Details
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.

Related Articles
New technologies emerge in medical AI.
PRODIGY speeds computer learning.
AI at work: from prisons to autos to space.
Replacing humans with machines: the insurance industry has begun to leverage artificial intelligence to cut costs and improve efficiency. But...
Artificial Intelligence for Computer Games.
Artificial intelligence; proceedings.
Robots Unlimited.
STAIRS 2006; proceedings.
Artificial intelligence research and development.

Terms of use | Copyright © 2016 Farlex, Inc. | Feedback | For webmasters