Situational Operational Planning in Real-time Systems

The scheduling problem is considered for the case when requests for the execution of job complexes with known characteristics receive at given times. Interrupts and switching from one executive mechanism to another are allowed. The composition of all complexes and the characteristics of jobs become known only at the time of each request. It is required to determine whether there is an admissible schedule for the total set of jobs and build it in case of a positive answer. We have developed a polynomial algorithm for solving the problem. The algorithm is based on constructing a network flow model and searching for the maximum flow. The problem of constructing an admissible schedule for jobs with non-fixed durations is studied. We have developed a method for preliminary (before the experiment in real-time) calculation of schedules, the computational complexity of which is significantly less than the computational complexity of a complete enumeration of all possible duration vectors.