Majorization and Stochastic Comparison Techniques for Scheduling of Parallel Systems

Parallel programs are usually modeled by task graphs which are directed acyclic graphs. Their vertices represent tasks and arcs represent precedence relations between tasks. These tasks are to be executed on parallel processors subject to precedence constraints: a task can start execution only when all its predecessor tasks have completed execution. A parallel program, or simply a job, is said to finish its execution if all its tasks complete executions. This completion time is referred to the job completion time. In a monoprogrammed system, at any time instant only tasks belong to the same job can run simultaneously on different processors, whereas in a multiprogrammed system, a sequence of jobs arrive in the system and tasks belong to different jobs can run simultaneously. For any given set of tasks, the scheduling problem consists in assigning tasks to..