A capacity allocation problem with integer side constraints

We address a capacity allocation problem arising as a subproblem of an artificial intelligence-based scheduling system for a semiconductor wafer fabrication facility. Tooling constraints, setup considerations and differences in machine capabilities are taken into account. Focusing on the objectives of maximizing throughput and minimizing deviation from predetermined production goals, we formulate the problem as a maximum flow problem on a bipartite network with integer side constraints and develop efficient heuristics which obtain near-optimal solutions in negligible computation time. The type of network flow problem we study has not been addressed in the literature to date and is of considerable theoretical interest. From a practical point of view, the network flow model of the problem and the algorithms developed for its solution are applicable to a wide range of production settings. (C) 1998 Elsevier Science B.V.