Heuristics based on partial enumeration for the unrelated parallel processor scheduling problem (Q1861922)

In this paper three heuristics for the unrelated parallel machine problem \(R||C_{\max}\) are considered, where the makespan has to be minimized. All these heuristics are based on a mixed integer linear programming (MILP) formulation with binary variables \(x_{ij}\) (denoting when job \(i\) is assigned to machine \(j\)). After solving the linear programming relaxation of the MILP problem, restricted MILP subproblems are constructed from the optimal LP solution by eliminating several variables. Then these subproblems are solved by branch-and-bound techniques providing heuristic solutions for the whole problem. Finally, computational results are presented, comparing the proposed heuristics with results obtained by other heuristics from \textit{S. Martello, F. Soumis} and \textit{P. Toth} [Discrete Appl. Math. 75, 169-188 (1997; Zbl 0882.68016)] and \textit{S. L. van de Velde} [ORSA J. Comput. 5, 192-205 (1993; Zbl 0777.90019)].