Scheduling Multiprocessor Tasks to Minimize Schedule Length
- 1 May 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (5), 389-393
- https://doi.org/10.1109/tc.1986.1676781
Abstract
The problem considered in this paper is the deterministic scheduling of tasks on a set of identical processors. However, the model presented differs from the classical one by the requirement that certain tasks need more than one processor at a time for their processing. This assumption is especially justified in some microprocessor applications and its impact on the complexity of minimizing schedule length is studied. First we concentrate on the problem of nonpreemptive scheduling. In this case, polynomial-time algorithms exist only for unit processing times. We present two such algorithms of complexity O(n) for scheduling tasks requiring an arbitrary number of processors between 1 and k at a time where k is a fixed integer. The case for which k is not fixed is shown to be NP-complete. Next, the problem of preemptive scheduling of tasks of arbitrary length is studied. First an algorithm for scheduling tasks requiring one or k processors is presented. Its complexity depends linearly on the number of tasks. Then, the possibility of a linear programming formulation for the general case is analyzed.Keywords
This publication has 11 references indexed in Scilit:
- Scheduling independent 2-processor tasks to minimize schedule lengthInformation Processing Letters, 1984
- A linear time algorithm for restricted bin packing and scheduling problemsOperations Research Letters, 1983
- Scheduling subject to resource constraints: classification and complexityDiscrete Applied Mathematics, 1983
- Recent Developments in Deterministic Sequencing and Scheduling: A SurveyPublished by Springer Nature ,1982
- On the diagnosability of self-testing multi-microprocessor systemsMicroprocessing and Microprogramming, 1981
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a SurveyPublished by Elsevier ,1979
- Fault-tolerance: The survival attribute of digital systemsProceedings of the IEEE, 1978
- Algorithm 520: An Automatic Revised Simplex Method for Constrained Resource Network Scheduling [H]ACM Transactions on Mathematical Software, 1977
- Scheduling with Deadlines and Loss FunctionsManagement Science, 1959