A Hybrid Bounding Procedure for the Workload Allocation Problem on Parallel Unrelated Machines with Setups

Abstract

A nonpreemptive single stage manufacturing process with parallel, unrelated machines and multiple job types with setups (PUMS) is considered. We propose a hybrid approximation procedure where a Lagrangean relaxation dual and a Lagrangean decomposition dual are solved one after the other to generate a good lower bound on the optimal makespan value. Computational results are reported.

Keywords:

• scheduling
• Lagrangean decomposition
• Lagrangean relaxation

View correction statement:

Erratum