Scheduling with arranged multi-purpose machines (Q614212)

Summary: 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 \(J_i(1\leq i\leq n)\), a ``first permissible'' machine \(h_i (1\leq h(i)\leq m)\) is given on which it can be processed. Thus, machines \(M_{h_i},\ldots , M_m\) are capable of processing job \(J_i\) while machines \(M_1,\ldots , M_{h_i - 1}\) cannot process job \(J_i\). Each job \(J_i\) requires a time \(p_i\) 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.