Multiprocessor task scheduling to minimize the maximum tardiness and the total completion time

We consider a scheduling problem with two parallel processors, where one ta sk may need the processing of more than one processor simultaneously. Alter natives are available to allocate processors to process a task. Under a giv en alternative, a task is assigned to some specific processor(s), and requi res correspondingly a specific processing time. Task preemption is allowed. The problem is to minimize the maximum tardiness of task completion times from their due dates, through determining the following: 1) the optimal ass ignment of each task to processor(s) and 2) the optimal schedule for each p rocessor to process the tasks assigned to it. We present a two-stage approa ch, which can generate an optimal solution in pseudopolynomial time. We als o apply/extend the two-stage approach to other problems where the number of processors required by each task is prespecified, preemption is prohibited , and the total completion time is to be minimized.