DOI:10.32604/csse.2022.017793
| Computer Systems Science & Engineering DOI:10.32604/csse.2022.017793 | |
| Article |
Stochastic Programming For Order Allocation And Production Planning
International University-Vietnam National University, Vietnam National University, HoChiMinh City, 70000, Vietnam
*Corresponding Author: Phan Nguyen Ky Phuc. Email: pnkphuc@hcmiu.edu.vn
Received: 11 February 2021; Accepted: 16 April 2021
Abstract: Stochastic demand is an important factor that heavily affects production planning. It influences activities such as purchasing, manufacturing, and selling, and quick adaption is required. In production planning, for reasons such as reducing costs and obtaining supplier discounts, many decisions must be made in the initial stage when demand has not been realized. The effects of non-optimal decisions will propagate to later stages, which can lead to losses due to overstocks or out-of-stocks. To find the optimal solutions for the initial and later stage regarding demand realization, this study proposes a stochastic two-stage linear programming model for a multi-supplier, multi-material, and multi-product purchasing and production planning process. The objective function is the expected total cost after two stages, and the results include detailed plans for purchasing and production in each demand scenario. Small-scale problems are solved through a deterministic equivalent transformation technique. To solve the problems in the large scale, an algorithm combining metaheuristic and sample average approximation is suggested. This algorithm can be implemented in parallel to utilize the power of the solver. The algorithm based on the observation that if the remaining quantity of materials and number of units of products at the end of the initial stage are given, then the problems of the first and second stages can be decomposed.
Keywords: Mixed integer programming; two-stage stochastic programming; production planning; order allocation
To satisfy customers and improve supply chain performance are among the most important objectives of firms. Supply chain performance is influenced by activities such as purchasing, manufacturing, transport, and sales. We focus on problems encountered in purchasing and production planning, such as utilization of discount policies and making decisions before demand has been realized. It has been pointed out that discounts may have an impact on purchase prices [1], and it can be a win-win situation when both supplier and purchaser benefit from discounts. Similar to production, planning can help to efficiently allocate resources while maintaining a minimum cost. In reality, order allocation is not easy, as it heavily relies on the transparency and accuracy of information in the whole supply chain, and it is often accomplished in several stages. Market demand is the uncertain factor that attracts the attention of researchers, as material procurement and production planning depend on it. However, perfect demand forecasting is impossible and impractical in real life, since demand depends on factors such as the market, environment, and season. Stochastic programming can be used to deal with this uncertainty.
Stochastic programming is an optimization framework that considers uncertain parameters to define optimal solutions. It has been applied in fields such as financial and planning control and manufacturing and capacity planning. With this model, uncertainty can be overcome, and firms can reduce supply chain expense to gain a competitive advantage.
The main contribution of this study is to construct a two-stage stochastic linear programming model for multiple materials and products, while considering discount policies from different suppliers and their effects on production planning. The model strives to answer the question of the quantity of material to be ordered from a specific supplier. Production planning at all stages provides basic information such as required labor, operational hours, and production lines. At a small scale, the problem can be solved directly through a deterministic equivalent. In a larger scenario, random search combined with sample average approximation is applied.
The remainder of this paper is organized as follows. The next section reviews the related literature. Section 3 presents the proposed two-stage stochastic mixed-integer programming mathematical models, and Section 4 describes the framework for applying random search and sample average approximation to solve the large-scale problem. Conclusions are drawn in Section 5.
Material procurement is the initial activity in production planning. In this phase, orders are allocated based on supplier price quotations to minimize total expenditures. Suppliers use quantity discounts to increase order sizes. Various methods for order allocation based on quantity discounts have been proposed, including mixed integer programming and stochastic programming optimization models. Stochastic programming can effectively account for uncertainty in modeling. Moheb-Alizadeh et al. [2] proposed a multi-objective mixed-integer nonlinear programming model for efficient and sustainable supplier selection and order allocation with stochastic demand. Their methods relied on a bi-objective data envelopment analysis and fuzzy multi-objective programming approach. Zhou et al. [3] proposed a system with two levels between retailers and their potential suppliers. At the beginning of each period, the retailer uses its inventory to satisfy customer stochastic demand and place orders for the next period. The objective is to minimize the total expected cost, using stochastic programming to identify the optimal order quantity based on the current inventory, and identifying the best supplier for the period based on that. Hadayani and Setayama et al. [4] applied supply chain operations reference approach, which was supported by supported by the Analytical Hierarchy Process (AHP) method to evaluate and improve the supply chain performance. Meena et al. [5] considered a two-stage supply chain with a selected group of suppliers based on multiple factors and criteria, where the purchaser places orders based on stochastic customer demand with a known probability distribution. Jolai et al. [6] proposed a mixed integer nonlinear programming model to solve the supplier order allocation problem with multiple periods and products and a linear discount. They considered discount price schemes, capacity limitations, and other factors to effectively allocate orders among a set of qualified suppliers. Shi et al. [7] developed a multi-stage stochastic programming model considering market demand variability and price fluctuations to make replenishment decisions at various stages over time, so as to minimize the procurement risk measured as the conditional value at-risk. Tarray et al. [8] suggested a sampling strategy for estimation of population variance on two occasion successive sampling. This sampling strategy has high potential in analyzing the market demand.
Production planning is another process whose role is important in order to minimize the total cost and control the leverage of the manufacturing phase. Many scholars have used stochastic programming to construct aggregate planning for production from many aspects, especially when the demand is unstable and cannot be predicted accurately. Mahdavi et al. [9] proposed mixed integer linear programming to aggregate multiple products in multiple periods along with constraints on machine capacity, material balances, and shortages, whose objective is to minimize the total production cost with various cost components. Altendorfer et al. [10] developed aggregate production planning under stochastic customer demand using mixed integer linear programming, and discovered the effects of forecast error on the optimal plan and total cost. Leung et al. [11] proposed two-stage stochastic programming using market demand variability to determine optimal medium-term production plans, with the main objective to minimize the total expected production cost. Zanjani et al. [12] used multi-stage stochastic programming to plan production given uncertain demand and material quality. The demand was considered as dynamic stochastic data with stationary behavior. The uncertain yield was constructed with a stationary probability distribution during the planning horizon. Their goal was to minimize the total inventory and backorder costs for all products and materials. Leung et al. [13] used stochastic programming and developed a two-stage model for perishable products considering stochastic parameters of market demand, production, and inventory holding cost to minimize the cost and shortage of products under constraints on the warehouse, labor working time, and machine operation time. Aouam et al. [14] sought the most promising among three formulations of production planning problems, consisting of a chance constrained model, two-stage stochastic programming model, and robust optimization model, using workload-dependent lead time, capacity, and uncertain demand. Zanjani et al. [15] studied production planning with uncertainty in the quality of raw materials in the sawmill industry. The solution methodology was based on a sample average approximation (SAA) scheme, and the result was validated through Monte Carlo simulation. Fang et al. [16] considered a hybrid manufacturing and remanufacturing system that used remanufacturable parts in end-of-use products, and investigated a production planning problem integrating resource capacity planning shared by both manufacturing and remanufacturing. Demand was assumed to be stochastic, and the problem was solved using Lagrangian relaxation and problem decomposition. Zhang et al. [17] proposed a stochastic production planning model for an international enclosure manufacturing company with seasonal demand and market growth uncertainty. The company forecast demand and informed suppliers to reduce risks for both parties. A two-stage stochastic production planning model was developed to minimize the total costs under all scenarios. Marteo et al. [18] studied a two-stage stochastic model for selecting grocery shop brands to ensure high-quality products and minimal farm-to-table time under seasonal contracts, with the aim to minimize overall procurement costs and meet future demand. This problem is common in the fresh vegetable industry. The problem was solved by Lagrangian relaxation and parallel computing algorithms using the CPLEX solver.
Several approaches have been developed to solve stochastic programming problems. Some of the most common are random search methods, stochastic approximation, stochastic quasi-gradient methods, and sample average approximation. Random search (stochastic) algorithms use randomness or probabilities to modify the solution process, and can be useful for ill-structured global optimization problems, whose objective function may be nonconvex or in a mixed continuous-discrete domain. Such algorithms include simulated annealing, tabu search, genetic algorithms, evolutionary programming, particle swarm optimization, and ant colony optimization [19–22]. Introduced by Robbins and Monro [23], stochastic approximation (SA) has become one of the most widely applicable and useful stochastic programming methods. The gradient is estimated by iterative sampling, and is used to update the current solution and project it back to the feasible region. Constraints are handled by Lagrange multipliers or penalty costs. Extensions of the SA approach include simultaneous perturbation stochastic approximation [24], scaled-and-shifted Kiefer-Wolfowitz [25], and accelerated stochastic approximation [26]. Stochastic quasi-gradient methods [27,28] are random search techniques that use asymptotically consistent estimates, rather than precise values, for the values of the functions and their derivatives. They are often applied to stochastic optimization problems with complex objective functions and constraints. These methods also require projection of solutions back to the feasible region. Stochastic approximation and stochastic quasi-gradient methods are hindered by the difficulty of the projection process to ensure the feasibility of the updated solution. Sample average approximation (SAA) solves the stochastic problem just once through sampling and optimization methods for deterministic problems. There is no update process, and gradient estimation is unnecessary [29–31].
Inspired by stochastic programming in order allocation and aggregate planning in a real production environment, this paper aims to optimize purchasing at two stages and form two aggregate plans for the production stages after receiving material from the procurement phase. The proposed model simultaneously considers the effect of decisions on the expected total cost at both stages and solves them together. The result is globally optimal for all scenarios, since the first stage considers impacts on all scenarios in the second stage. The results include essential information such as the number of hires, total production lines needed, and total overtime hours in each scenario of customer demand under some resource limitations and constraints.
Our two-stage stochastic linear programming model is constructed.
m: index of materials,
p: index of products,
s: index of suppliers,
r: index of price ranges,
e: index of scenarios,
Parameters
Decision variables
Mathematical model
Our objective is to minimize the expected total cost of stages 1 and 2. The main cost components of stage 1 are for purchasing and manufacturing. Costs in stage 2 are more complex and include purchasing and manufacturing costs, balanced by income from selling products, salvage products, and salvage materials.
The expected total cost for both stages can be presented as
where
and
Subject to:
where Eqs. (4) and (5) force materials purchased from each supplier to be zero or to be in only one price range
Eqs. (6)–(8) state that if
Eqs. (9)–(11) ensure that if
Eq. (12) expresses that the total purchased materials in both stages must be less than their maximum in all scenarios.
Eqs. (13) and (14) represent the constraints in purchasing material quantities due to supplier capacities at each stage.
Eqs. (15) and (16) express that the number of units of product type p produced at each stage must be less than the total available of material type m at that stage.
Eqs. (17) and (18) force the total hours for manufacturing a product type p to be less than the total hours of allrelated lines. Eqs. (19) and (20) ensure that the number of lines for each product is less than its maximum.
Eqs. (21) and (22) constrain the number of workers in each stage to be greater than the minimum required for line operation.
Eqs. (23) and (24) show how the salvage benefit is calculated when the company has manufactured or purchased more than demand in each scenario. To linearize the maximum constraints in Eqs. (23) and (24), variables
Eq. (25) can be rewritten in linear form as
With Eqs. (27) and (28), the constraint of Eq. (23) can be expressed as
Eq. (24) can similarly be linearized by Eqs. (32)–(36):
Eq. (35) shows that if demand quantity is less than the manufacturing or purchase quantity in each scenario, all products can be sold at price
Several instances of the problem were created to validate the model, from which it can be seen that materials with a high difference in cost between the first and second stages take more priority in purchasing activity in the first stage. As a result, they are often purchased to cover usage over the whole planning horizon. These decisions are in contrast to remaining materials with a low difference in cost between the two stages. For these materials, the decision-maker will apply a delay strategy, purchasing only a fraction of the materials in the first stage, and deciding on subsequent purchases after demand has been realized.
If the cost is high to manufacture one product or to open one line, a manufacturer often accepts a lost sale. However, products with high selling prices are often manufactured in large quantities, which can create overage products in some scenarios.
The above example is a small-scale problem solved through a deterministic equivalent transformation to validate the model. If the number of scenarios is large, then a random search combined with sample average approximation is suggested, which can be solved by parallel computing.
Let
Figure 1: Random search and SAA combination
Stochastic linear programming of optimization problems is popular due to its effectiveness in describing real phenomena. In this study, a two-stage stochastic linear programming approach is proposed for the procurement and manufacturing process, considering material all-unit discounts to order optimal quantities for production. In the first stage, managers must make decisions without demand realization, and available information consists only of suppliers’ quotations and the manufacturer’s capacities and facilities. The decisions in the first stage propagate their effects to the second stage. However, in the second stage, based on first-stage outcomes and stochastic market demand realization, correct actions can be taken to determine the optimal order allocation and production planning. To solve the problem in the large scale, an algorithm combining metaheuristic and sample average approximation is suggested. This can be implemented in parallel to utilize the power of the solver.
Acknowledgement: The authors thank Vietnam National University Ho Chi Minh City (VNU-HCM), who kindly sponsored this research.
Funding Statement: This research is funded by Vietnam National University Ho Chi Minh City (VNU-HCM) under Grant No. C2020-28-10.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
1. A. Sen, H. Yaman, K. Güler and E. Körpeoğlu, “Multi-period supplier selection under price uncertainty,” Journal of the Operation Reserach Society, vol. 65, no. 11, pp. 1636–1648, 2017. [Google Scholar]
2. H. Moheb-Alizadeh and R. Handfield, “An integrated chance-constrained stochastic model of efficient and sustainable supplier selection and order allocation,” International Journal of Production Research, vol. 56, no. 21, pp. 1–27, 2017. [Google Scholar]
3. Y. Zhou, L. Zhao, X. Zhao and J. Jiang, “A supplier selection and order allocation with stochastic demands,” International Journal of Systems Science, vol. 42, no. 8, pp. 1323–1338, 2011. [Google Scholar]
4. A. Handayani and C. Y. Setyatama, “Analysis of supply chain management performance using SCOR and AHP methods in green avenue apartments of East Bekasi,” Journal of Applied Science, Engineering, Technology, and Education, vol. 1, no. 2, pp. 141–148, 2019. [Google Scholar]
5. P. L. Meena and S. P. Sarmah, “Miligating the risks of supply disruption under stochastic demand,” International Journal of Management Science and Engineering, vol. 9, no. 13, pp. 157–168, 2014. [Google Scholar]
6. F. Jolai, M. S. Neyestani and H. Golmakani, “Multi-objective model for multi-period, multi-products, supplier order allocation under linear discount,” International Journal of Management Science and Engineering, vol. 8, no. 1, pp. 24–31, 2014. [Google Scholar]
7. Y. Shi, F. Wu, L. K. Chu, D. Sculli and Y. H. Xu, “A portfolio approach to managing procurement risk using multi-stage stochastic programming,” Journal of the Operational Research Society, vol. 62, no. 11, pp. 1958–1970, 2017. [Google Scholar]
8. T. A. Tarray, Z. A. Ganie and B. Youssuf, “An improved mathematical model applying practicable algorithms,” Journal of Applied Science, Engineering, Technology, and Education, vol. 1, no. 2, pp. 114–118, 2019. [Google Scholar]
9. I. Mahdavi, K. Taghizadeh, M. Bagherpour and M. Solimanpur, “Modelling of multi-period multi- product production planning considering production routes,” International Journal of Production Research, vol. 50, no. 6, pp. 1749–1766, 2012. [Google Scholar]
10. K. Altendorfer, T. Ferberbauer and H. Jodlbauer, “Effects of forecast errors on optimal utilisation in aggregate production planning with stochastic customer demand,” International Journal of Production Research, vol. 54, no. 12, pp. 3718–3735, 2016. [Google Scholar]
11. S. C. H. Leung, Y. Wu and K. K. Lai, “A stochastic programming approach for multi-site aggregate production planning,” Journal of the Operation Reserach Society, vol. 57, no. 2, pp. 123–132, 2017. [Google Scholar]
12. M. K. Zanjani, M. Nourelfath and D. Ait-Kadi, “A multi-stage stochastic programming approach for production planning with uncertainty in the quality of raw materials and demand,” International Journal of Production Research, vol. 48, no. 16, pp. 4701–4723, 2010. [Google Scholar]
13. S. C. H. Leung and W. L. Ng, “A stochastic programming model for production planning of perishable products with postponement,” Production Planning & Control, vol. 18, no. 3, pp. 190–202, 2007. [Google Scholar]
14. T. Aouam and R. Uzsoy, “Zero-order production planning models with stochastic demand and workload- dependent lead times,” International Journal of Production Research, vol. 56, no. 6, pp. 1661–1679, 2014. [Google Scholar]
15. M. K. Zanjani, M. Nourelfath and D. Ait-Kadi, “A stochastic programming approach for production planning with uncertainty in the quality of raw materials: A case in sawmills,” Journal of the Operation Reserach Society, vol. 62, no. 7, pp. 1334–1343, 2017. [Google Scholar]
16. C. Fang, X. Liu, P. M. Pardalos, J. Long, J. Bei et al., “A stochastic production planning problem in hybrid manufacturing and remanufacturing systems with resource capacity planning,” Journal of Global Optimization, vol. 68, no. 4, pp. 851–878, 2017. [Google Scholar]
17. X. Zhang, M. Prajapati and E. Peden, “A stochastic production planning model under uncertain seasonal demand and market growth,” International Journal of Production Research, vol. 49, no. 7, pp. 1957–1975, 2011. [Google Scholar]
18. J. Mateo, L. M. Pla, F. Solsona and A. Pages, “A production planning model considering uncertain demand using two-stage stochastic programming in a fresh vegetable supply chain context,” SpringerPlus, vol. 5, no. 1, pp. 339, 2016. [Google Scholar]
19. C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Overview and conceptual comparison,” ACM Computing Surveys, vol. 35, no. 3, pp. 268–308, 2003. [Google Scholar]
20. R. Horst and P. M. Pardalos, “Stochastic methods,” in Handbook of Global Optimization, 1st ed., vol. 2. Springer US: Springer, pp. 829–869,1995. [Google Scholar]
21. J. C. Spall, “Evolutionary computation I: Genetic algorithms,” In Introduction to Stochastic Search and Optimization: Estimation, Simulation and Control, 1st ed., vol. 1. John Wiley & Sons, pp. 231–258,2003. [Google Scholar]
22. Z. B. Zabinsky, “Pure random search and pure adaptive search,” in Stochastic Adaptive Search for Global Optimization, 1st ed., vol. 1. Springer US: Springer, pp. 25–54,2003. [Google Scholar]
23. J. H. Goodfriend, “Discrete event systems: Sensitivity analysis and stochastic optimization by the score function method,” Technometrics, vol. 37, no. 1, pp. 124–125, 1995. [Google Scholar]
24. J. C. Spall, “Multivariate stochastic approximation using a simultaneous perturbation gradient approximation,” IEEE Transactions on Automatic Control, vol. 37, no. 3, pp. 332–341, 1992. [Google Scholar]
25. M. Broadie, D. Cicek and A. Zeevi, “General bounds and finite-time improvement for the Kiefer-Wolfowitz stochastic approximation algorithm,” Operations Research, vol. 59, no. 5, pp. 1211–1224, 2011. [Google Scholar]
26. S. Ghadimi and G. Lan, “Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization II: Shrinking procedures and optimal algorithms,” SIAM Journal on Optimization, vol. 23, no. 4, pp. 2061–2089, 2013. [Google Scholar]
27. Y. M. Ermoliev and A. A. Gaivoronski, “Stochastic quasigradient methods for optimization of discrete event systems,” Annals of Operations Research, vol. 39, no. 1, pp. 1–39, 1992. [Google Scholar]
28. S. T. Wallace and W. T. Ziemba, “SQG: Software for solving stochastic programming problems with stochastic quasi-gradient methods,” Applications of Stochastic Programming, 1st ed., vol. 1. Society for Industrial and Applied Mathematics,pp. 37–60, 2005. [Google Scholar]
29. A. J. Kleywegt, A. Shapiro and T. Homem-de-Mello, “The sample average approximation method for stochastic discrete optimization,” SIAM Journal on Optimization, vol. 12, no. 2, pp. 479–502, 2002. [Google Scholar]
30. R. Y. Rubinstein and A. Shapiro, “Optimization of static simulation models by the score function method,” Mathematics and Computers in Simulation, vol. 32, no. 4, pp. 373–392, 1990. [Google Scholar]
31. S. M. Robinson, “Analysis of sample-path optimization,” Mathematics of Operations Research, vol. 21, no. 3, pp. 513–528, 1996. [Google Scholar]
 | This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |