A Multi-stage Stochastic Programming Approach in Lot-sizing and Scheduling under Uncertain Environments

Based on the time ranges, production planning is considered in a three-level decision making procedure: long-term, medium-term and short-term, which corresponds to the facility location and resource allocation, production quantity decision or lot-sizing over a planning horizon, and daily operations including job scheduling, respectively [1]. The medium-term planning usually spans about half of the year when the market and manufacturing condition might change. Therefore, addressing lot-sizing and scheduling problems under uncertainty instead of traditional deterministic version is valuable. In the context of the general lot-sizing and scheduling under uncertainty, Alem et al [2] proposed a budget-uncertainty set robust optimization model considering uncertain demand. An overview of the work in planning and scheduling under uncertainty can be found in Verderame et al [3], in which they also summarized the general commonalities in the uncertainty approaches within various fields. In order to address the uncertainty in lot-sizing and scheduling problems, two-stage stochastic programming is utilized where the decision maker determines the regular production quantity and production sequence in the first stage, then a recourse action corresponding to the extra production plan is taken in the second stage after a random event occurs. Considering the computational complexity of the two-stage stochastic programming model, some efforts were devoted to improve the solving efficiency. For example, Hu and Hu [4] applied scenario generation and forward selection to create scenario and identify the most respective scenario sets for the two-stage stochastic programming model in lot-sizing and scheduling levels. Keller and Bayraksan [5] formulated an exact solution methodology which combined the Benders decomposition and a sampling-based solution to handle the proposed two-stage integer program model for jobs scheduling. In real world application, the lot-sizing and scheduling decisions need to be made sequentially over an entire planning horizon including several production decision-making periods. The absence of the sequential decision making in the two-stage stochastic programming technique was avoided by the multi-stage stochastic programming technique which updates decisions as new data becomes available. Based on the multi-stage stochastic programming approach, Hu and Hu [6] investigated the capacitated lot-sizing and scheduling problem with sequence dependent setups. Körpeoğlu, Yaman and Aktürk [7] addressed the master production schedules with finite capacity, controllable processing times and uncertain demand. Curcio et al. [8] proposed an approximate heuristic strategy to tackle the multi-stage stochastic programming model for the lot-sizing and scheduling problem. The two-stage and multi-stage stochastic programming approaches aforementioned in [3-8] provide guidelines for lot-sizing and scheduling problems under uncertainty, but some factors are not well considered. Firstly, the lot-sizing and scheduling problems involve various uncertain factors, e.g., demand, capacity and processing time, which significantly affects the efficiency of operations, however most existing research only focus on one of them, such as [2,4,6,8]. Secondly, assuming demand to be period independent is invalid in practice and new models can be formulated based on lot-sizing and scheduling settings [6]. Thirdly, although multi-stage stochastic programming models may yield better results than the two-stage programming models which usually perform better than the deterministic model under uncertain environments, the trade-off is the intractability. Note that multi-stage stochastic programs are challenging optimization problems as their size increases exponentially with the number of stages. Decomposition algorithms are commonly used to solve these large-scale problems. Based on various decomposition approaches, this research also aims to develop effective approaches for multi-stage stochastic programming. To summarize, in the context of lot-sizing and scheduling problems under uncertain environments, this research can focus on the following parts: (1) Study multiple uncertain factors (e.g., demand, processing time, due date, etc.) instead of only considering demand uncertainty. (2) Investigate the problem in other lot-sizing settings, such as multi-level lot-sizing and lot-sizing with parallel machine. (3) Introduce other risk criteria into practical lot-sizing and scheduling settings, such as value-at-risk (VaR) and conditional value-at-risk (CVaR) criteria, which have been utilized in project scheduling problems [9] and no-wait flow shop scheduling problems [10], respectively. (4) Combine different decomposition approaches as well as strong formulations to extend the capability of solving mixed integer multi-stage stochastic programs.