Result: Workload balancing in multi-stage production processes

We consider a variant on the general workload balancing problem, which arises naturally in automated manufacturing and throughput optimization of assembly-lines. The problem is to distribute the tasks over compatible machines and phases of the process simultaneously. The total duration of all phases is to be minimized. We have proved that this variant is NP-hard (even for uniform task lengths), and we propose a novel algorithmic approach. Our approach includes an exact solver for the case of uniform task lengths, which is based on network-flow techniques and runs in polynomial time for a fixed number of phases (the number of phases is indeed very small in practice). To solve the general case with arbitrary real task lengths, we combine our solver for uniform task lengths with a shortest-path based multi-exchange local search. We present results of an extensive computational study on real-world examples from printed circuit board manufacturing. This study demonstrates that our approach is very promising. The solution quality obtained by our approach is compared with lower bounds from an integer linear programming model. It turns out that our approach is faster than CPLEX by orders of magnitude, and the optimality gap is quite small.