A boundle of on-line algorithms for scheduling computational tasks - Dariusz Dorota; Czeslaw Smutnicki (International Journal of Electronics and Telecommunications)
We deal with the problem of scheduling the set of computational tasks on parallel identical processors. Each task needs a predefined number of processors to perform. The problem is known in scheduling theory and has been considered up to now by a few authors. Starting from the formal original description of the problem, we provide a mathematical model and then propose, at first, the solution method in the deterministic case. In fact, the paper focuses chiefly on the nondeterministic variant of the problem. We have proposed several online algorithms for this case. These algorithms are evaluated through competitive analysis and experiments. The practical application of the problem can be found in embedded systems with increased dependability obtained through hardware and software redundancy.