05829537

j

05829537 Boudhar, Mourad Tchikou, Hamza Scheduling with arranged multi-purpose machines. Int. J. Oper. Res. 8, No. 3, 379-397 (2010). 2010 Inderscience Enterprises, Gen\`eve EN makespan complexity branch and bound scheduling theory MPMs multi-purpose machines heuristics

doi:10.1504/IJOR.2010.033545

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.