Performance properties of list scheduling algorithms under various dynamic assumptions are analyzed. The focus is on bounds for scheduling directed acyclic graphs with arbitrary precedence constrains and arbitrary task processing times subject to minimizing the makespan. New performance bounds are derived and compared with known results.

The complexities of many previous scheduling algorithms for IRIS tasks are too high to apply them to practical systems handling many tasks. The high complexities stem from the fact that the algorithms perform scheduling on all tasks in a system, producing an optimal solution. As a way to reduce the complexity of scheduling, we propose a heuristic on-line scheduling algorithm that schedules the IRIS tasks only in a scheduling window, producing a sub-optimal solution. A scheduling window contains W important tasks determined by a selection policy. The performance of the proposed algorithm is verified by simulation.

Among several multiprocessor topologies, two-dimensional (2D) mesh topology has become popular due to its simplicity and efficiency. Even though a number of scheduling and processor allocation schemes for 2D meshes have been proposed in the literature, little study has been done aimed for real-time environment. In this paper, we propose an on-line scheduling and allocation scheme for real-time tasks that require the exclusive use of submeshes in 2D mesh system. By effectively manipulating the information on allocated or reserved submeshes, the proposed scheme can quickly identify the earliest available time of a free submesh for a newly arrived task. We employ a limited preemption approach to reduce the complexity of the search for a feasible schedule. Computer simulation reveals that the proposed scheme allows high throughput by decreasing the number of tasks rejected.