Method, apparatus, and program for scheduling resources in a penalty-based environment
US7480913B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 9, 2003 |
| Grant date | Jan 20, 2009 |
| Priority date | — |
| Expiry date | Feb 14, 2026 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q10/06
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention relates to the problem of scheduling work for employees and/or other resources in a help desk or similar environment. The employees have different levels of training and availabilities. The jobs, which occur as a result of dynamically occurring events, consist of multiple tasks ordered by chain precedence. Each job and/or task carries with it a penalty which is a step function of the time taken to complete it, the deadlines and penalties having been negotiated as part of one or more service level agreement contracts. The goal is to minimize the total amount of penalties paid. The invention consists of a pair of heuristic schemes for this difficult scheduling problem, one greedy and one randomized. The greedy scheme is used to provide a quick initial solution, while the greedy and randomized schemes are combined in order to think more deeply about particular problem instances. The invention also includes a scheme for determining how much time to allocate to thinking about each of several potential problem instance variants.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.