Scheduling of unrelated parallel machines: an application to PWB manufacturing

In this paper, we tackle scheduling the bottleneck operation of a Printed Wiring Board (PWB) manufacturing line. The problem may be characterized as unrelated parallel machines and we are interested in several performance measures including: makespan, the average finish time, mean flow time, utilization, the number of lots and the total amount of overtime beyond the release interval. Due to setup reduction techniques employed by the company, setups are negligible, and we construct an Integer Programming (IP) model with a special structure unimodularity. Thus, the corresponding linear programming optimal solution always satisfies the integrality constraints. In order to account for multiple objectives of the scheduling system, we introduce preference constraints and bring them into the objective function by Lagrangian Relaxation (LR). We give a heuristic procedure to select constraints to be relaxed, and formulations to determine the Lagrange multipliers. To verify the validity of the proposed method, we compare it with a network model and with a modified FIFO method. The proposed method presents very promising results in terms of our measures of interest.