Scheduling UET task systems with concurrency on two parallel identical processors

Problems with unit execution time tasks and two identical parallel processo rs have received a great deal of attention in scheduling theory. In contras t to the conventional models, where each task requires only one processor, we consider a situation when a task may require both processors simultaneou sly. For problems without precedence constraints we present several polynom ial time algorithms which complement recent results of Lee and Cai. We also show that the introduction of precedence constraints leads to NP-hardness results for maximum lateness and mean flow time objective functions. For th e maximum lateness problem, a family of algorithms, based upon the idea of modified due dates, is considered. The worst case behaviour of these algori thms is analysed, and it is shown that the same upper bound is tight for ea ch algorithm of this family.