An Efficient Preprocessing Algorithm to Speed-Up Multistage Production Decision Optimization Problems

In this paper we focus on the problem of optimizing a Multistage Production Network (MPN), in which a number of products need to be manufactured. Each product can be produced by one or more assembly node processes, where each assembly is composed of several machines working in parallel. For the required demand of the output products, a decision must be made on how much should be produced by each MPN assembly node, which machines should be on and their output level as to minimize the total production cost. We previously proposed the online-decomposition algorithm (ODA) based on offline preprocessing of static assembly components in order to catalog optimal machine configurations and cost functions for possible assembly outputs. The online ODA uses the preprocessed catalog to decompose the original MPN problem into smaller problems and reduce the exponential search space of machine configurations into a small number of optimal or near optimal machine configurations. Thus, ODA significantly improves the online solution quality and time complexity at the expense of the offline preprocessing. In this paper we focus on preprocessing and propose an adaptive algorithm that considers only a small part of the discretized range of assembly output values, by iteratively classifying outputs based on their predicted machine configuration. We also conduct an initial experimental evaluation, that shows significant improvement in preprocessing time with no reduction in the quality of the online solution.