On Process Capacity
The concept of the capacity of a process and the associated managerial insights on the investment and management of capacity are of fundamental importance in Operations Management. Most OM textbooks use the following simple approximation to determine process capacity: the capacity of each resource is first calculated by examining that resource in isolation; process capacity is then defined as the smallest (bottleneck) among the capacities of the resources. In a recent paper, Gurvich and Van Mieghem (2015) show that this “bottleneck formula” can be significantly inaccurate, and obtain a necessary and sufficient condition under which it correctly determines process capacity. We provide further clarity on the intractability of process capacity by showing that it is hard to calculate process capacity exactly and, furthermore, also hard to efficiently approximate it to within a reasonable factor; e.g., within any constant factor. These results are based on a novel characterization, which we establish, of process capacity that relates it to the fractional chromatic number of an associated graph. An important implication is that it is unlikely that we can replace the bottleneck formula with a simple but close approximation of process capacity. From a practical viewpoint, our analysis results in a natural hierarchy of sub-classes of policies that require an increasing amount of sophistication in implementation and management: While process capacity is the maximum long-term process rate achievable over all feasible policies, we provide a precise expression for the maximum process rate over policies in each subclass in this hierarchy, thus highlighting the trade-off between operational difficulty and the achievable process rate.