Scheduling of unrelated parallel machines: An application to PWB manufacturing

Llan Yu, Heloisa M. Shih, Michele Pfund, W. Matthew Carlyle, John Fowler

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)921-931
Number of pages11
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number11
StatePublished - Nov 2002

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Scheduling of unrelated parallel machines: An application to PWB manufacturing'. Together they form a unique fingerprint.

Cite this