New bounds on time and number of processors for multiprocessor optimal schedules

Two problems for task schedules in a multiprocessor parallel system are discussed in this paper:

1. Given a partially ordered set of tasks represented by the vertices of an acyclic directed graph with their corresponding processing times, derive the lower bound on the minimum time(LBMT) needed to process the task graph for a given number of processors.
2. Determine the lower bound on minimum number of processors(LBMP) needed to complete those tasks in minimum time. It is shown that the proposed LBMT is sharper than previously known values and the computational aspects of these bounds are also discussed.