  In this paper, we proposed an effective approach for scheduling of
multiprocessor unit time tasks with chain precedence on to large multiprocessor
system. The proposed longest chain maximum processor scheduling algorithm is
proved to be optimal for uniform chains and monotone
(non-increasing/non-decreasing) chains for both splitable and non-splitable
multiprocessor unit time tasks chain. Scheduling arbitrary chains of
non-splitable multiprocessor unit time tasks is proved to be NP-complete
problem. But scheduling arbitrary chains of splitable multiprocessor unit time
tasks is still an open problem to be proved whether it is NP-complete or can be
solved in polynomial time. We have used three heuristics (a) maximum
criticality first, (b) longest chain maximum criticality first and (c) longest
chain maximum processor first for scheduling of arbitrary chains. Also compared
performance of all three scheduling heuristics and found out that the proposed
longest chain maximum processor first performs better in most of the cases.
