Method of scheduling successive tasks subject only to timing constraints
US5606695A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Aug 2, 1995 |
| Grant date | Feb 25, 1997 |
| Priority date | — |
| Expiry date | Aug 2, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q10/0631
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.