The paper considers open shop problems with unit processing times. n jobs have to be processed on m machines. The order in which a given job is processed on the machines is not fixed. For each job a release time or a due date may be given. In addition, the paper consider the restriction that every machine must perform all corresponding operations without any delay time. Unit time open shop problems with release times to minimize total completion time were unsolved up to now for both allowed and forbidden delay times. It will solve these problems in the case of two and three machines. Furthermore the paper will give polynomial algorithms for several no-delay-problems with due dates.
