PREEMPTIVE SCHEDULING IN REAL-TIME-SYSTEM
BY MULTIPRODUCT NETWORK FLOW TECHNIQUES

Fourougian M.G. (Computing Centre of Russian Academy of Science)

     The problem of scheduling n jobs with specific processing
requirement, release time and due date in real-time-system consisting
of m parallel processors is considered. The processors are asumed to
be uniform in the sense that they merely differ in processing speed.
Processors can work on only one job at a time and each job can be
processed by at most one processor at a time. Interruptions and
preemptions are allowed and corresponding expenditures are took into
consideration. A restriction of number of interruptions and
preemptions in the system at a time is given. Furthermore, a
restrictions of the processors communications which can be
time-variable are took into consideration. The feasibility problem
consisting of determining a feasible schedule (if one exists) is
solved. This problem is NP-complete. The algorithm of solving this
problem was elaborated. This algorithm is based on reduction of
initial problem to integer multiproduct network flow problem.
Necessary and sufficient conditions of existance of a fiasible
schedule are received.