Preemptive Scheduling for Two-Processor Systems

Article type: Research Article

Authors: Rowicki, Andrzej

Affiliations: Institute of Computing Machines, Warsaw

Abstract: The purpose of the paper is to consider an algorithm for preemptive scheduling for two-processor systems with identical processors. Computations submitted to the systems are composed of dependent tasks with arbitrary execution times and contain no loops and have only one output. We assume that preemptions times are completely unconstrained, and preemptions consume no time. Moreover, the algorithm determines the total execution time of the computation. It has been proved that this algorithm is optimal, that is, the total execution time of the computation (schedule length) is minimized.

Keywords: execution time, network, nonpreemptive scheduling, preemptive scheduling, reduct, reduction

DOI: 10.3233/FI-1988-11102

Journal: Fundamenta Informaticae, vol. 11, no. 1, pp. 1-19, 1988