Finding technique for a scheduling system

• US 20010047287A1
• Filed: 04/02/2001
• Published: 11/29/2001
• Est. Priority Date: 03/31/2000
• Status: Abandoned Application

• Current Assignee: Ventyx Software SRL (ABB Limited)
• Original Assignee: Ventyx Software SRL (ABB Limited)
• Inventors: Druce, Guy, Jacobs, Simon
• Application Number:
  US09/824,850
• Publication Number:
  US 20010047287A1
• Time in Patent Office: Days
• US Class Current: 705/9
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/063112 Skill-based matching of a person or a group to a task
• CPC Class Codes: G06Q 10/063114 Status monitoring or status determination for a person or group
• CPC Class Codes: G06Q 10/063116 Schedule adjustment for a person or group
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource
• CPC Class Codes: G06Q 10/06315 Needs-based resource requirements planning or analysis
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 10/109 Time management, e.g. calendars, reminders, meetings or time accounting
• CPC Class Codes: G06Q 10/1095 Meeting or appointment
• CPC Class Codes: G06Q 10/1097 Task assignment
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y02P 90/80 Management or planning

Abstract

An aspect of the present invention includes a method for finding an opening in which to fit an order in a schedule. The method includes computing an amount of time required in a shift to fit the order, and creating a schedulable time block from a virtual free time block. The schedulable time block includes a primary block. The method further includes examining the primary block. The primary block is a candidate for fitting the order if the duration of the primary block, excluding at least one break, is greater than or equal to the amount of free time required in the shift to fit the order. The method further includes creating at least one opening in the shift from the schedulable time block so as to present to a customer at least one option of fitting the order in the schedule to perform a desired service.

Claims

1. A method for scheduling, comprising:

forming a list of shifts in a schedule;

determining a shift in which an order can be scheduled; and

assigning the order to the shift determined by the act of determining, wherein the acts of forming, determining, and assigning are contemporaneously executed while a customer is on a phone attempting to schedule the order.

2. The method of

claim 1

, wherein forming includes forming a window over a schedule of a worker, wherein the schedule of the worker includes a number of shifts, wherein the window encompasses a portion of the number of shifts in the schedule of the worker, and wherein forming a list of shifts includes selecting at least one shift from the portion of the number of lists encompassed by the window.

3. The method of

claim 1

, wherein assigning includes assigning to an earlier time period of the shift before assigning to a later time period of the shift.

4. A method for finding an opening in which to fit an order in a schedule, comprising:

computing an amount of free time required in a shift to fit the order;

creating a schedulable time block from a virtual free time block, wherein the schedulable time free block includes a primary block, zero or more expansion blocks, and zero or more load blocks;

examining the primary block, wherein the primary block is a candidate to fit the order if a duration of the primary block, excluding at least one break is greater than or equal to the amount of free time required in the shift to fit the order; and

creating at least one opening in the shift from the schedulable time block so as to present to a customer at least one option of fitting the order in the schedule to perform a desired service.

5. The method of

claim 4

, further comprising generating a list of shifts from a window defined over a set of shifts of a worker.

6. The method of

claim 5

, further comprising generating a list of virtual free time blocks from a shift of a worker.

7. The method of

claim 6

, further comprising calculating a travel time between a first activity and a second activity.

8. The method of

claim 7

, wherein calculating a travel time includes calculating a difference travel time when the order is inserted into a virtual free time block of the shift of the worker, wherein the different travel time is defined as a result of a subtraction of the travel time between the first activity and the second activity and the travel time of the order and the second activity, and wherein the virtual free time block that the order is inserted into is between the first activity and the second activity.

9. The method of

claim 8

, further comprising calculating a job time, wherein the job time is defined as the time that the order will take to be performed in the shift.

10. The method of

claim 9

, wherein computing an amount of free time required in the shift to fit the order includes summing the travel time, the difference travel time, and the job time.

11. The method of

claim 10

, further comprising computing an extra time by relocating a portion of the shift to fit the order.

12. The method of

claim 11

, wherein computing an extra time by relocating a portion of the shift includes computing an amount of time that the portion of the shift must be shifted to fit the order, wherein the amount of time that the portion of the shift must be shifted is defined as a result of a subtraction of the amount of free time required in the shift to accommodate the order and a time available in the virtual free time block.

13. The method of

claim 11

, wherein computing an extra time by relocating a portion of the shift includes computing an amount of time that the portion of the shift can be shifted, wherein computing an amount of time that the portion of the shift can be relocated includes aggregating a number of virtual free time blocks in the portion of the shift.

14. The method of

claim 11

, further comprising executing the act of computing the extra time by relocating a portion of the shift to later in time in the shift if the act of examining the primary block determines that the primary block is not a candidate, wherein the primary block is a candidate to fit the order if the extra time plus the duration of the primary block is greater than or equal to the amount of free time required in the shift to fit the order, and updating the at least one expansion block if the primary block is a candidate.

15. The method of

claim 14

, further comprising executing the act of computing the extra time by relocating a portion of the shift to earlier in time in the shift if the act of executing the act of computing the extra time by relocating a portion of the shift to later in time and the act of examining the primary block determine that the primary block is not a candidate, executing the act of examining the primary block, wherein the primary block is a candidate to fit the order if the extra time plus the duration of the primary block is greater than or equal to the amount of free time required in the shift to fit the order, and updating the at least one expansion block if the primary block is a candidate.

16. The method of

claim 15

, further comprising eliminating the virtual free time block from further consideration if the act of executing the act of computing the extra time by relocating a portion of the shift to earlier in time in the shift and the act of examining the primary block determine that the primary block is not a candidate.

17. The method of

claim 16

, further comprising checking a load limit of the shift if the primary block is being expanded by the extra time to fit the order, wherein checking includes adding the amount of free time required in the shift to fit the order to a current load of the shift to define a new load, and wherein checking includes comparing the new load against the load limit.

18. The method of

claim 17

, further comprising reducing a total load of the shift by finding at least one virtual free time blocks to be removed, wherein if the act of finding finds at least one virtual free time block to be removed, the act of reducing executes an act of adding the at least one virtual free time block to be removed, and updating the at least one load block if the act of finding finds at least one virtual free time block to be removed.

19. The method of

claim 18

, further comprising eliminating the virtual free time block if the act of reducing fails to reduce the total load of the shift to fit the order.

20. The method of

claim 19

, further comprising iterating a set of the above acts for each virtual free time block in the list of virtual free time blocks, wherein the set excludes some of the above acts.

21. The method of

claim 20

, further comprising iterating the act of

claim 20

for each shift in the list of shifts.

39. The method of

claim 38

, further comprising iterating the act of

claim 17

for each shift in the list of shifts.

22. A computer-readable medium having instructions stored thereon for causing a computer to perform a method for finding an opening to fit an order in a schedule, the method comprising:

computing an amount of free time required in a shift to fit the order;

creating a schedulable time block from a virtual free time block, wherein the schedulable time block includes a primary block, at least one expansion block, and at least one load block;

examining the primary block, wherein the primary block is a candidate to fit the order if a duration of the primary block, excluding at least one break is greater than or equal to the amount of free time required in the shift to fit the order; and

creating at least one opening in the shift from the schedulable time block so as to present a customer with at least one option of fitting the order in the schedule to perform a desired service.

23. The method of

claim 22

, further comprising generating a list of shifts from a window defined over a set of shifts of a worker.

24. The method of

claim 23

, further comprising generating a list of virtual free time blocks from a shift of a worker.

25. The method of

claim 24

, further comprising calculating a travel time between a first activity and a second activity.

26. The method of

claim 25

, wherein calculating a travel time includes calculating a difference travel time when the order is inserted into a virtual free time block of the shift of the worker, wherein the different travel time is defined as a result of a subtraction of the travel time between the first activity and the second activity and the travel time of the order and the second activity, and wherein the virtual free time block that the order is inserted into is between the first activity and the second activity.

27. The method of

claim 26

, further comprising calculating a job time, wherein the job time is defined as the time that the order will take to be performed in the shift.

28. The method of

claim 27

, wherein computing an amount of free time required in the shift to fit the order includes summing the travel time, the difference travel time, and the job time.

29. The method of

claim 28

, further comprising computing an extra time by relocating a portion of the shift to fit the order.

30. The method of

claim 29

, wherein computing an extra time by relocating a portion of the shift includes computing an amount of time that the portion of the shift must be shifted to fit the order, wherein the amount of time that the portion of the shift must be relocated is defined as a result of a subtraction of the amount of free time required in the shift to accommodate the order and a time available in the virtual free time block.

31. The method of

claim 29

, wherein computing an extra time by relocating a portion of the shift includes computing an amount of time that the portion of the shift can be shifted, wherein computing an amount of time that the portion of the shift can be shifted includes aggregating a number of virtual free time blocks in the portion of the shift.

32. The method of

claim 29

, further comprising executing the act of computing the extra time by relocating a portion of the shift to later in time in the shift if the act of examining the primary block determines that the primary block is not a candidate, wherein the primary block is a candidate to fit the order if the extra time plus the duration of the primary block is greater than or equal to the amount of free time required in the shift to fit the order, and updating the at least one expansion block if the primary block is a candidate.

33. The method of

claim 32

, further comprising executing the act of computing the extra time by relocating a portion of the shift to earlier in time in the shift if the act of executing the act of computing the extra time by relocating a portion of the shift to later in time and the act of examining the primary block determine that the primary block is not a candidate, executing the act of examining the primary block, wherein the primary block is a candidate to fit the order if the extra time plus the duration of the primary block is greater than or equal to the amount of free time required in the shift to fit the order, and updating the at least one expansion block if the primary block is a candidate.

34. The method of

claim 33

, further comprising eliminating the virtual free time block from further consideration if the act of executing the act of computing the extra time by relocating a portion of the shift to earlier in time in the shift and the act of examining the primary block determine that the primary block is not a candidate.

35. The method of

claim 34

, further comprising checking a load limit of the shift if the primary block is being expanded by the extra time to fit the order, wherein checking includes adding the amount of free time required in the shift to fit the order to a current load of the shift to define a new load, and wherein checking includes comparing the new load against the load limit.

36. The method of

claim 35

, further comprising reducing a total load of the shift by finding at least one virtual free time blocks to be removed, wherein if the act of finding finds at least one virtual free time block to be removed, the act of reducing executes an act of adding the at least one virtual free time block to be removed, and updating the at least one load block if the act of finding finds at least one virtual free time block to be removed.

37. The method of

claim 36

, further comprising eliminating the virtual free time block if the act of reducing fails to reduce the total load of the shift to fit the order.

38. The method of

claim 37

, further comprising iterating a set of the above acts for each virtual free time block in the list of virtual free time blocks, wherein the set excludes some of the above acts.