Minimizing setup costs for parallel multi-purpose machines under load-balancing constraint

This article focuses on the minimization of the setup costs of a workshop modeled with parallel multi-purpose machines. Any admissible workshop configuration has to ensure that a load-balanced production plan meeting a given demand exists. This problem is shown to be NP-hard in the strong sense, and is stated as a mixed integer linear program. It is shown that under some hypotheses, it can be stated as a transportation problem and solved in polynomial time. An upper bound and lower bound are proposed, as well as a performance ratio assessment that is reached only when degenerate optimal solutions to the transportation problem exist. (C) 2006 Elsevier B.V. All rights reserved.