Job shop scheduling with unit time operations under resource constraints and release dates

Abstract

We consider the problem of job shop scheduling with m machinesand n jobs J i, each consisting of ei unit time operations. There are s distinct resources R h and a quantity q h avaiable of each one. The execution of the j-th operation of Ji requires the presence of u ijh units of R h, 1≤i≤n, 1≤j≤ei and 1≤h≤s. I addition, ach Ji has a release date r i, that is J i cannot start before time r i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let e=max{e i} and u=| {u ijh}|. If m., s, u and e are fixed then both algorithms terminate within polynomial time.