×

Method of scheduling successive tasks

  • US 5,826,080 A
  • Filed: 08/02/1995
  • Issued: 10/20/1998
  • Est. Priority Date: 08/11/1994
  • Status: Expired due to Fees
First Claim
Patent Images

1. Method of scheduling successive and repetitive tasks, using a computer, where each task has a respective start time interval and some tasks must satisfy constraints requiring the task'"'"'s respective execution start time to be within a predetermined time interval relative either to the execution start time of a predecessor task, execution of which precedes that of the task in question, or to an absolute reference time, said method comprising the steps of:

  • determining a macrocycle time interval, the duration of which is equal to the lowest common multiple of all said task start time intervals;

    reducing the macrocycle time interval to a microcycle, or layer, the duration of which is equal to the highest common denominator of all the task repeat periods;

    grouping each of said tasks into a respective layer in accordance with time sequences imposed by said constraints;

    and scheduling the tasks of a macrocycle layer by layer, beginning with the first layer in time of the macrocycle, where said scheduling comprises repeating the following steps;

    scheduling all tasks in a current layer, where said current layer is a layer immediately following a last scheduled layer;

    determining if task scheduling for said current layer is possible given said constraints of said tasks in said current layer;

    if said task scheduling is not possible for said current layer, determining if said current layer is said first layer in time;

    if no scheduling of the first layer in time satisfies all said constraints applying to the tasks of the first layer, stopping scheduling and providing notification of scheduling failure and;

    if the scheduling effected in said current layer, that is not said first layer in time, does not satisfy one or more constraints applying to a task of the current layer;

    rescheduling the last layer in time of those layers containing the respective predecessor tasks corresponding to the unsatisfied constraints of said tasks within said current layer by shifting the execution time of the predecessor task contained in that last layer in a direction and by an amount such that the unsatisfied constraint can be satisfied on subsequent rescheduling of said current layer; and

    rescheduling said last layer in time and all other layers following it in time and then deciding whether the resulting rescheduling succeeds.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×