Deadline scheduling of multiprocessor tasks. (English) Zbl 0854.68005
Summary: In the classical scheduling theory it is widely assumed that any task requires for its processing only one processor at a time. Nowadays with the technological progress this assumption has become not so obvious. In the paper, two algorithms for solving the problem of scheduling tasks requiring more than one processor at a time in the real-time environment, will be given. The first is based on a generation of all feasible layouts of tasks and on an application of linear programming. The second – heuristic one – is based on the descent search in solution space and the tabu search metaheuristic combined with linear programming. Results of a computational comparison of the two methods, are also reported.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
Keywords:
scheduling theoryReferences:
| [1] | Avizienis, A., Fault tolerance: The survival attribute of digital systems, (Proc. IEEE, 66 (1978)), 1109-1125 |
| [2] | Blazewicz, J.; Drabowski, M.; Weglarz, J., Scheduling multiprocessor tasks to minimize schedule length, IEEE Trans. Comput., 35, 389-393 (1986) · Zbl 0604.68040 |
| [3] | Blazewicz, J.; Drozdowski, M.; Schmidt, G.; de Werra, D., Scheduling independent two processor tasks on a uniform duo-processor system, Discrete Appl. Math., 28, 11-20 (1990) · Zbl 0715.90069 |
| [4] | Cin, M. D.; Dilger, E., On the diagnosibility of self-testing multiprocessor systems, (Microprocessing Microprogramming (1981)), 177-184 |
| [5] | Du, J.; Leung, J. Y-T., Complexity of scheduling parallel task systems, SIAM J. Discrete Math., 2, 473-487 (1989) · Zbl 0676.90029 |
| [6] | Glover, F., Future paths for integer programming and links to artificial intelligence, (CAAI Report 85-8 (1985), University of Colorado: University of Colorado Boulder, CO) · Zbl 0615.90083 |
| [7] | Glover, F., Tabu-search — Part I, ORSA J. Comput., 1/3, 190-206 (1989) · Zbl 0753.90054 |
| [8] | Hertz, A.; de Werra, D., The Tabu search metaheuristic: how we used it, Ann. Math. Artificial Intelligence, 111-121 (1990) · Zbl 0878.68053 |
| [9] | Krawczyk, H.; Kubale, M., An approximation algorithm for scheduling diagnostic tests in multicomputer systems, IEEE Trans. Comput., 34, 869-872 (1985) |
| [10] | Kubale, M., The complexity of scheduling independent two-processor tasks on dedicated processors, Inform. Process. Lett., 24, 141-147 (1987) · Zbl 0653.68015 |
| [11] | Plehn, J., Preemptive scheduling of independent jobs with release times and deadlines on a hypercube, Inform. Process. Lett., 34, 161-166 (1990) · Zbl 0695.68030 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
