Short‐term capacity allocation problem with tool and setup constraints |
| |
Authors: | Elif Akal Alper Üngr Reha Uzsoy |
| |
Institution: | Elif Akçal?,Alper Üngör,Reha Uzsoy |
| |
Abstract: | We consider a short‐term capacity allocation problem with tool and setup constraints that arises in the context of operational planning in a semiconductor wafer fabrication facility. The problem is that of allocating the available capacity of parallel nonidentical machines to available work‐in‐process (WIP) inventory of operations. Each machine can process a subset of the operations and a tool setup is required on a machine to change processing from one operation to another. Both the number of tools available for an operation and the number of setups that can be performed on a machine during a specified time horizon are limited. We formulate this problem as a degree‐constrained network flow problem on a bipartite graph, show that the problem is NP‐hard, and propose constant factor approximation algorithms. We also develop constructive heuristics and a greedy randomized adaptive search procedure for the problem. Our computational experiments demonstrate that our solution procedures solve the problem efficiently, rendering the use of our algorithms in real environment feasible. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005 |
| |
Keywords: | network flows degree constraints approximation algorithms heuristics capacity allocation semiconductor manufacturing |
|
|