Rejectable advance scheduling: A dimensionality reduction approach

In this work, we study an advance scheduling problem for customized products, integrating order acceptance and production timing decisions. We exploit a dynamic programming method to formulate the problem. At the beginning of each period, the decision maker determines the number of orders to accept/reject and the production timing for each accepted order. The objective is to minimize the total expected discounted cost to the future from manufacturing costs, rejection costs, and delay costs associated with unproduced orders in the system. To handle the curse of dimensionality, we focus on an allocation scheduling variant where the decision maker only determines order acceptance/rejection and the number of orders to produce in the current period. In this variant, we prove the multimodular properties of the value function of an alternative reformulated model. Based on this, some monotonic properties of the decision variables are established. We then use the solution of the variant model to construct an optimal solution for our primary problem. In this way, we reduce the original advance scheduling problem’s dimensionality of both state and decision spaces from T+1 to 2. We also extend our method to models that include urgent orders and non-zero initial backlog. Numerical analyses are conducted to verify the efficiency of the proposed method and to examine parameter sensitivities.