Method for calendaring future events in real-time

• US 5,260,868 A
• Filed: 10/15/1991
• Issued: 11/09/1993
• Est. Priority Date: 08/11/1986
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Gupta, Subhash, Sidhu, Sanjiv S., Vlach, Frank
• Primary Examiner(s): Envall, Jr., Roy N.
• Assistant Examiner(s): CHUNG TRANS, XUONG MY
• Application Number:
  US07/776,713
• Time in Patent Office: 756 Days
• Field of Search: 364/478, 364/468, 364/156, 364/152, 364/402, 364/153, 364/401
• US Class Current: 700/100
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/34418 Scheduler for sequential control, task planning, control sequence
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G07C 3/00 Registering or indicating the condition or the working of machines or other apparatus, other than vehicles
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

A mechanism and method for calendaring a plurality of events such as scheduling the operation of interrelated machines which perform a process flow. Future time is divided into segments, called buckets, of increasing length. The first two buckets are of the same size and each of the following buckets twice as large as its preceding bucket. The first bucket slides so as to always cover a specified length of time following the current time. Events scheduled in the calendar is added to the appropriate bucket, depending on how far in the future it is to take place. When the current time equals the scheduled time for an event, then that event is removed from the bucket where it resides. When a bucket has become empty because all events have been removed from it, the events in the following bucket are distributed over the two buckets preceding it.

Claims

1. A method to be performed by a machine for calendaring a plurality of events which are to occur on a plurality of machines at various times to thereby control operation of and improve scheduling of said plurality of machines, comprising the steps of:

(a) dividing future time spans into a plurality of segments of unequal length, wherein later segments are predetermined multiples of the length of the first segment;

(b) placing events to occur on any of the said plurality of machines in appropriate buckets representative of the time segments;

(c) incrementing a clock, wherein each of said events are removed from the first bucket when the clock reaches their calendared time; and

(d) dividing the events contained in larger buckets among appropriate smaller buckets when previous buckets have been emptied, and resetting the time represented by the first bucket to the current time.

2. The method for calendaring a plurality of events of claim 1, wherein said first bucket is a sliding bucket.

3. The method for calendaring a plurality of events of claim 1, wherein only said first bucket is sorted.

4. The method for calendaring a plurality of events of claim 1, wherein said events in all buckets other than said first bucket are linked lists of events.

5. The method for calendaring a plurality of events of claim 4, wherein each of said events has a description identifying what is to occur, a time, and a pointer to the next event in the list.

6. The method for calendaring a plurality of events of claim 4, wherein said linked lists are simple single linked lists.

7. The method for calendaring a plurality of events of claim 1, wherein said second bucket covers a segment of future time span equal to said first bucket, and each other said bucket covers a segment of future time spans which is twice that of an immediately preceding bucket, so that said segment covered by any particular bucket will always exactly span the sum of the segments of all preceding buckets.

8. A calendar mechanism for a scheduler system controlling the operation of a plurality of machines, comprising:

a timing means which is adapted to be incremented by the system;

a means for dividing future time spans into a plurality of segments of unequal length, assigning each of a plurality of buckets to correspond to each of the plurality of segments, wherein later segments are predetermined multiples of the length of the first segment;

a means for receiving inputted events from the system and placing said inputted events in appropriate buckets representative of the time segments received from said segmenter;

a means for removing events from a first bucket when the incremented clock reaches their calendared time and outputting such event to the system for appropriate response by the machine; and

a controlling means for dividing the events contained in later buckets among appropriate earlier buckets when previous buckets have been emptied, and resetting the time represented by the first bucket to the current time.

9. The calendar mechanism for a scheduler system of claim 8, wherein said first bucket is a sliding bucket.

10. The calendar mechanism for a scheduler system of claim 8, wherein only said first bucket is sorted.

11. The calendar mechanism for a scheduler system of claim 8, wherein said events in all buckets other than said first bucket are linked lists of events.

12. The calendar mechanism for a scheduler system of claim 11, wherein each of said events has a description identifying what is to occur, a time, and a pointer to the next event in the list.

13. The calendar mechanism for a scheduler system of claim 11, wherein said linked lists are simple single linked lists.

14. The calendar mechanism for a scheduler system of claim 8, wherein a second bucket covers a segment of future time span equal to said first bucket, and each other of said plurality of buckets cover a segment of future time spans which is twice that of an immediately preceding bucket, so that said segment covered by an particular bucket will always exactly span the sum of the segments of all preceding buckets.