Open shop scheduling with delays

Abstract

The concept of interprocessor delay is introduced to the open shop modeL Delays are uniform if they are always the same for any job and between any pair of machines. Scheduling an open shop with uniform delays is shown to be NP-complete even for two machines. However, if ail tasks are unit excution time and the delays are uniform then a polynomial algorithm to solve the dcision problem is exhibited. If the delays are nonuniform, the problem remains NP-complete.