Capacity-driven acceptance of customer orders for a multi-stage batch manufacturing system: models and algorithms

An automotive parts manufacturer produces a wide variety of parts in a job shop environment. Many of the manufacturing operations have substantial setups. When a client phones in an order, the manufacturer must decide quickly whether or not it has the capacity required to accept the order. We develop a simplified formulation of the order acceptance problem. We formulate the discrete-time version as an integer program. The problem is NP-hard, but in 51 out of 51 test problems the LP relaxation is tight. For larger problems we test several heuristics. Three of the heuristics look promising: simulated annealing, a genetic algorithm, and a linear-programming-based heuristic.