Scheduling with arranged multi-purpose machines

In the present study, we consider a special case of multi-purpose machines (MPMs) in which there is a linear order given for the machines. In addition, for each job Ji(1≤i≤n), a 'first permissible' machine hi (1≤h(i)≤m) is given on which it can be processed. Thus, machines Mhi,…, Mm are capable of processing job Ji while machines M1,…, Mhi−1 cannot process job Ji. Each job Ji requires a time pi and the goal is to minimise the makespan. We prove the NP-hardness of the general problem and present some polynomial sub-problems. Heuristics with an exact algorithm of branch and bound type are also presented with numerical experimentations.