Method of scheduling successive tasks subject only to timing constraints

• US 5,606,695 A
• Filed: 08/02/1995
• Issued: 02/25/1997
• 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): TOPLU, LUCIEN
• Application Number:
  US08/510,533
• Time in Patent Office: 573 Days
• Field of Search: 395/650, 364/281.8, 364/281.6, 364/281.7, 364/281.3
• US Class Current: 705/7.12
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations

Abstract

A method of scheduling successive tasks subject only to timing constraints calculates for each task upper and lower limits of the interval in which execution of that task must start. It then constructs a first series in which all the tasks are scheduled in increasing order of their lower limit and a second series in which all the asks are scheduled in increasing order of their upper limit, before constructing an initial permutation by scheduling all the tasks in the order of the first series and verifying if the initial permutation satisfies all the constraints. If not all the constraints are satisfied, the method determines in the initial permutation the first ill-placed task for which a constraint is not satisfied and a candidate task in the second series immediately preceding the ill-placed task in the second series in the current permutation. It then verifies that if the candidate task is shifted in the current permutation to a position immediately after the ill-placed task all the constraints applying to all the tasks shifted in this way are then satisfied.

Claims

1. Method for scheduling successive tasks by means of a computer, said tasks being subject only to timing constraints, a timing constraint requiring that the execution start time be in at least one predetermined time interval relative to an absolute reference time;

said method comprising the following successive steps in this order;

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

constructing a first series in which all said tasks 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 are scheduled in increasing order of 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 in the order of said first series;

verifying if said current permutation satisfies all said constraints supplying to said tasks, 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;

concluding that the scheduling succeeds if all said constraints are satisfied;

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

determining in said second series a candidate task immediately following said ill-placed task in said second series that 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 a position 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, concluding that said candidate task is not suitable and then determining in said second series another candidate task and repeating the previous verification; and

, if this is not possible, concluding that the scheduling fails;

if all said constraints are satisfied, concluding that the scheduling succeeds.