A heuristic master planning algorithm for supply chains that consider substitutions and commonalities

This study focuses on solving the master planning problem for supply chains by considering substitutions and common components. Such problems address the difficulties involved in synchronizing manufacturing processes and transporting of materials, semi-finished products, and final products along a supply chain and facilitate decision-making related to the effective and efficient use of production and transportation capacities over periods ranging from one month to one year. This study considers product structures with multiple final products, given substitutions and common components. For situations in which the capacity of the supply chain network partners is limited, the model constructed in this study is able to plan all demands and minimize delay costs, substitutions, and the costs of production, transportation, substitution, and inventory holding. Mixed integer programming is a popular way to solve supply chain master planning problems. However, as such problems increase in complexity, the MIP model becomes insolvable due to the time and computer resources it requires. Therefore, this study proposes a heuristic algorithm, called the Dynamic Search BOM Substitution Algorithm (DSBSA), to solve the supply chain master planning problem efficiently and effectively. DSBSA sorts demands according to the necessary final products, due dates, shared capacities, and substitution conditions, to name several possible criteria. Then, DSBSA plans the demands individually, using a minimum cost production tree. If the demand cannot be filled completely using the original BOMs (Bill of Materials), DSBSA substitutes another BOM to fill the demands. This study develops two algorithms to search the substitute BOM: one searches for substitutions in the BOM’s materials levels, this maintaining most of the materials in the original BOM; the other searches for substitutions and uses them to fill bottlenecks, allowing insufficient levels of materials to be detected and supplemented. To show the effectiveness and efficiency of DSBSA, a prototype was constructed and tested to demonstrate the power of DSBSA using complexity and computational analysis.