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

• Current Assignee: Cegelec (VINCI SA)
• Original Assignee: Cegelec (VINCI SA)
• Inventors: Dworzecki, Jozef
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): PARK, ALICE
• Application Number:
  US08/510,343
• Time in Patent Office: 1,175 Days
• Field of Search: 395/672, 395/673
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A method of scheduling tasks subject to timing and succession constraints essentially comprises grouping the tasks in layers according to succession constraints and scheduling the tasks layer by layer in increasing layer order up to the last layer, if possible, and then deciding that the resulting scheduling succeeds. If the scheduling achieved in a layer other than the first layer does not satisfy one or more constraints applying to a task belonging to the current layer, the method reschedules a layer containing a predecessor task corresponding to an unsatisfied constraint, schedules or reschedules all the other layers higher than the layer of the predecessor task, up to the last layer, if possible, and then decides that the resulting scheduling succeeds. Applications include scheduling of transmission of information on an industrial data bus.

Claims

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.

2. Method according to claim 1 comprising the following steps in this order for scheduling each current layer:

calculating for each task of said current layer upper and lower limits of the time interval in which execution of that task must start;

constructing a first series in which all said tasks of the current layer are scheduled in increasing order of their lower limit, and are scheduled in increasing order of their upper limit when several tasks have a same lower limit;

constructing a second series in which all said tasks of the current layer are scheduled in increasing order for their upper limit, and are scheduled in decreasing order of their lower limits when several tasks have a same upper limit and have different lower limits;

constructing a current permutation, first by scheduling all said tasks of the current layer in the order of said first series;

verifying if said current permutation satisfies all said constraints applying to said tasks of the current layer, the tasks being considered one by one in the order corresponding to said current permutation, to check whether each task satisfies all the constraints applying to said task;

deciding that the scheduling of the current layer succeeds if all said constraints are satisfied;

otherwise, determining in the said current permutation the first so-called ill-placed task for which a constraint is not satisfied;

determining in said second series a so-called candidate task immediately following said ill-placed task in said second sequence and which also precedes said ill-placed task in said current permutation, said candidate being a task which has already been verified, all the tasks following said candidate task in said current permutation being not considered as satisfying all the constraints, any more;

verifying that, if said candidate task is shifted to be immediately after said ill-placed task, all said constraints applying to all said tasks shifted in this way are then satisfied; and

if at least one constraint is not satisfied, deciding that said candidate task is not suitable, then determining in said second sequence another candidate task and repeating the previous verification; and

, if this is not possible, deciding that the scheduling of the current layer fails;

if all said constraints are satisfied, deciding that the scheduling of the current layer succeeds.