From manufacturing scheduling to supply chain coordination: the control of complexity and uncertainty

With time-based competition and rapid advancements in technology, effective manufacturing scheduling and supply chain coordination are critical to quickly respond to changing market conditions. These problems, however, are difficult in view of inherent complexity and various uncertainties involved. In this paper, decomposition and coordination based on Lagrangian relaxation are identified as an effective way to control complexity and uncertainties. A manufacturing scheduling problem is first formulated within the job shop context with uncertain order arrivals, processing times, due dates, and part priorities. A solution methodology that combines Lagrangian relaxation, stochastic dynamic programming, and heuristics is developed. Method improvements to effectively solve large problems are highlighted. A decentralized supply chain model is then established. By relaxing cross-member constraints, the model is decomposed into member-wise subproblems, and a nested optimization structure is established. Coordination is performed through the iterative updating of cross-member prices without accessing other member´s private information or intruding their decision-making authorities, either with or without a coordinator. Two examples are presented to demonstrate the effectiveness of the method. Finally, future prospects are discussed.