Complexity of Buffer Capacity Allocation Problems for Production Lines with Unreliable Machines

Abstract : Buffer capacity allocation problems for flow-line manufacturing systems with unreliable machines are studied. These problems arise in a wide range of manufacturing systems and concern determining buffer capacities with respect to a given optimality criterion which can depend on the average production rate of the line, buffer cost, inventory cost, etc. Here, this problem is proven to be NP-hard for a tandem production line and oracle representation of the revenue and cost functions, and NP-hard for a series-parallel line and stepwise revenue function.