Data processing: financial – business practice – management – or co – Automated electrical financial or business practice or... – Health care management
Reexamination Certificate
1998-04-07
2001-08-21
Hafiz, Tariq R. (Department: 2165)
Data processing: financial, business practice, management, or co
Automated electrical financial or business practice or...
Health care management
Reexamination Certificate
active
06278978
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer systems and computer-implemented methods for generating and optimizing schedules for a collection of agents. In particular, the invention relates to methods for optimizing agent schedules to satisfy variable staffing requirements and shift constraints.
BACKGROUND OF THE INVENTION
The task of creating an efficient schedule for a collection of agents is known to be a very complex constraint satisfaction problem. The problem becomes even more complex when the number of agents is large, or when there are variable constraints upon the shifts such as the number of breaks within an agent's shift, the scheduling of the breaks within a shift, and the lengths of the breaks.
Traditionally, scheduling is performed manually. Because the manual preparation of schedules is very laborious, however, computerized scheduling methods have been devised to perform the task of scheduling. Although computerized scheduling is far faster than manual scheduling, it often does not produce schedules that make the most efficient use of agents. One major reason for the difficulty in producing efficient schedules is that the scheduling problem is a computational problem of type NP-complete, i.e. the only known algorithms to solve the problem require an amount of time that grows exponentially with the size of the problem. There are no known algorithms, therefore, which can perfectly solve the scheduling problem in less than exponential time. The problem of generating a good schedule, therefore, requires computational techniques for maximizing the schedulers efficiency while minimizing the amount of computational time, and inherently involves trade-offs that are peculiar to each specific application.
U.S. Pat. No. 5,195,172 issued Mar. 16, 1993 to Elad et al. discloses a method for solving a broad class of problems, which includes scheduling problems. The method makes use of techniques from operations research and artificial intelligence. Because the method is a general-purpose problem-solving algorithm, however, it does not provide techniques to address the problems specifically associated with optimizing agent schedules. In other words, while the techniques disclosed by Elad may provide a small improvement to conventional scheduling techniques, they are too general to provide a fast and effective method for efficient agent scheduling.
U.S. Pat. No. 5,369,570 issued Nov. 29, 1994 to Parad discloses adjusting a resource schedule to adapt it to changing conditions, needs, and requirements. The method is directed to the scheduling of general resources, and the concept of schedule repair is accordingly limited to a very general context. The problem of agent scheduling, on the other hand, brings with it special constraints and associated complexities. While the disclosed method may solve certain problems of a general nature related to efficient scheduling, specific problems associated with optimizing agent scheduling are not addressed.
U.S. Pat. No. 5,111,391 issued May 5, 1992 to Fields et al. discloses a skill-based staff scheduling system, which is largely concerned with agent placement within existing or fixed schedules. As a result of this lack of flexibility, it is not able to produce a well-optimized schedule which allows for the variation of other parameters.
U.S. Pat. No. 5,325,292 issued Jun. 28, 1994 to Crockett discloses a method for agent scheduling which includes a post-processing step for optimization. The post-processing step allows for changes in break times, swapping shifts for preferences, and eliminating unnecessary tours. Because it does not allow for many other possible schedule changes, however, the disclosed method is less than ideal. By unnecessarily fixing many attributes of the schedule, it can not always find a more optimal schedule. For example, the post-processing step does not allow a single agent to exchange shifts and does not allow the day that an agent works to be changed. The post-processing also does not allow more than one agent to be simultaneously rescheduled. These limitations, as well as others, contribute to the production of a less than optimal agent schedule. Moreover, the post-processing step is blindly iterated a fixed number of times. As a result, computational time is spent in an attempt to optimize the schedule regardless of whether or not the schedule is likely to benefit from another iteration.
OBJECTS AND ADVANTAGES OF THE INVENTION
Accordingly, it is a primary object of the present invention to overcome the limitations of the prior art agent scheduling methods. More specifically, it is an object of the invention to provide a fast, efficient and flexible computer-implemented method for optimizing an agent schedule.
SUMMARY OF THE INVENTION
These objects and advantages are attained by a novel computer-implemented method for improving an agent schedule. The method is distinguished from the prior art by numerous advantageous features. For example, the method includes swapping shift patterns and not just shift start times, completely unscheduling an agent and not just modifying an agent schedule, using a unique and very simple score for evaluating the desirability of a schedule, and scoring schedules that have unscheduled, or indeterminate, break times. The method is also characterized by the use of an asymmetric scoring function having a stochastic factor. In contrast with prior art methods, the present invention is able to find the locally best schedule.
The method for improving an agent schedule comprises the following steps: unscheduling an agent from a shift in the schedule; evaluating a score function for each of a plurality of possible schedules which have the agent scheduled for different possible shifts; and selecting an improved schedule from among the plurality of possible schedules. The improved schedule is characterized by an improved value of the score function. The above steps are repeated until a locally optimal schedule is obtained. The break times in the possible shifts are not necessarily scheduled in the above procedure.
In another aspect of the invention, a method is provided for locally optimal break scheduling. The method includes the steps of unscheduling a break; evaluating a score function for a plurality of possible break times for the break; and selecting an improved break time from the possible break times. The improved break time is characterized by an improved score.
In the above procedures, the evaluation of the score function for a possible schedule includes selecting, for each interval in the possible schedule, one of a plurality of predetermined values corresponding to distinct staffing levels. In an preferred embodiment, the plurality of predetermined values comprises four values corresponding to whether the interval in the possible schedule is very understaffed, slightly understaffed, slightly overstaffed, or very overstaffed.
REFERENCES:
patent: 4700295 (1987-10-01), Katsof et al.
patent: 5111391 (1992-05-01), Fields et al.
patent: 5195172 (1993-03-01), Elad et al.
patent: 5233533 (1993-08-01), Edstrom et al.
patent: 5319781 (1994-06-01), Syswerda
patent: 5325292 (1994-06-01), Crockett
patent: 5329444 (1994-07-01), Takahashi et al.
patent: 5369570 (1994-11-01), Parad
patent: 5826236 (1998-10-01), Narimatsu et al.
patent: 5848403 (1998-12-01), Gabriner et al.
patent: 5890134 (1999-03-01), Fox
patent: 5897629 (1999-04-01), Shinagawa et al.
patent: 5943652 (1999-08-01), Sisley et al.
patent: 5963913 (1999-10-01), Henneuse et al.
patent: 6038539 (2000-03-01), Maruyama et al.
patent: 6216109 (2001-04-01), Zweben et al.
patent: 0514122 A (1992-11-01), None
Sprout, Alison L., “Scheduling Your Forces with a PC,” Fortune, vol. 129, No. 11, p. 131, May, 1994.*
Heck, Mike, “High-End Project Managers,” InfoWorld, vol. 15, No. 5, pp. 59-70, Feb. 1993.*
“Harlequin: Harlequin Announces Visionary Adaptive Workflow Strategy for Digital Printing and Publishing,” M2 Presswire, p. N/A, Oct. 1996.*
Dobson, Ricardo, “PeopleScheduler Plus Adds Graphics to Schedules,” PC Magazine, vol. 1
Andre David
Nourbakhsh Illah
Blue Pumpkin Software, Inc.
Hafiz Tariq R.
Lumen Intellectual Property Services Inc.
Meinecke-Diaz Susanna
LandOfFree
Agent scheduling system and method having improved... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Agent scheduling system and method having improved..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Agent scheduling system and method having improved... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2521368