A stochastic production planning problem with nonlinear cost. (English) Zbl 1251.90111
Summary: Most production planning models are deterministic and often assume a linear relation between production volume and production cost. In this paper, we investigate a production planning problem in a steel production process considering the energy consumption cost which is a nonlinear function of the production quantity. Due to the uncertain environment, the production demands are stochastic. Taking a scenario-based approach to express the stochastic demands according to the knowledge of planners on the demand distributions, we formulate the stochastic production planning problem as a mixed integer nonlinear programming (MINLP) model.
Approximated with the piecewise linear functions, the MINLP model is transformed into a mixed integer linear programming model. The approximation error can be improved by adjusting the linearization ranges repeatedly. Based on the piecewise linearization, a stepwise Lagrangian relaxation (SLR) heuristic for the problem is proposed where variable splitting is introduced during Lagrangian relaxation (LR). After decomposition, one subproblem is solved by linear programming and the other is solved by an effective polynomial time algorithm. The SLR heuristic is tested on a large set of problem instances and the results show that the algorithm generates solutions very close to optimums in an acceptable time. The impact of demand uncertainty on the solution is studied by a computational discussion on scenario generation.
Approximated with the piecewise linear functions, the MINLP model is transformed into a mixed integer linear programming model. The approximation error can be improved by adjusting the linearization ranges repeatedly. Based on the piecewise linearization, a stepwise Lagrangian relaxation (SLR) heuristic for the problem is proposed where variable splitting is introduced during Lagrangian relaxation (LR). After decomposition, one subproblem is solved by linear programming and the other is solved by an effective polynomial time algorithm. The SLR heuristic is tested on a large set of problem instances and the results show that the algorithm generates solutions very close to optimums in an acceptable time. The impact of demand uncertainty on the solution is studied by a computational discussion on scenario generation.
Keywords:
stochastic production planning; inventory; scenario-based approach; stepwise Lagrangian relaxation; variable splitting; MINLPReferences:
| [1] | Azaron, A.; Tang, O.; Tavakkoli-Moghaddam, R., Dynamic lot sizing problem with continuous-time Markovian production cost, International Journal of Production Economics, 120, 607-612 (2009) |
| [2] | Bahl, H. C.; Ritzman, L. P.; Gupta, JND, Determining lot sizes and resource requirements: a review, Operations Research, 35, 329-345 (1987) |
| [3] | Bakir, M. A.; Byrne, M. D., Stochastic linear optimization of an MPMP production planning model, International Journal of Production Economics, 55, 87-96 (1998) |
| [4] | Barcia, P.; Jörnsten, K., Improved Lagrangean decomposition: an application to the generalized assignment problem, European Journal of Operational Research, 46, 84-92 (1990) · Zbl 0711.90055 |
| [5] | Brandimarte, P., Multi-item capacitated lot-sizing with demand uncertainty, International Journal of Production Research, 44, 2997-3022 (2006) · Zbl 1161.90381 |
| [6] | Carøe, C. C.; Schultz, R., Dual decomposition in stochastic integer programming, Operations Research Letters, 24, 37-45 (1999) · Zbl 1063.90037 |
| [7] | Chazal, M.; Jouini, E.; Tahraoui, R., Production planning and inventories optimization: a backward approach in the convex storage cost case, Journal of Mathematical Economics, 44, 997-1023 (2008) · Zbl 1142.90302 |
| [8] | Chen, Z.; Li, S.; Tirupati, D., A scenario based stochastic programming approach for technology and capacity planning, Computers and Operations Research, 29, 781-806 (2002) · Zbl 0995.90053 |
| [9] | Gutiérrez, J.; Puerto, J.; Sicilia, J., The multiscenario lot size problem with concave costs, European Journal of Operational Research, 156, 162-182 (2004) · Zbl 1043.90004 |
| [10] | Haugen, K. K.; Løkketangen, A.; Woodruff, D. L., Progressive hedging as a meta-heuristic applied to stochastic lot-sizing, European Journal of Operational Research, 132, 116-122 (2001) · Zbl 0990.90087 |
| [11] | Jans, R.; Degraeve, Z., Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches, European Journal of Operational Research, 177, 1855-1875 (2007) · Zbl 1102.90002 |
| [12] | Jörnsten, K.; Näsberg, M., A new Lagrangian relaxation approach to the generalized assignment problem, European Journal of Operational Research, 27, 313-323 (1986) · Zbl 0617.90068 |
| [13] | Karimi, B.; Fatemi Ghomi, S. M.T.; Wilson, J. M., The capacitated lot sizing problem: a review of models and algorithms, Omega, 31, 365-378 (2003) |
| [14] | Minner, S., A comparison of simple heuristics for multi-product dynamic demand lot-sizing with limited warehouse capacity, International Journal of Production Economics, 118, 305-310 (2009) |
| [15] | Mula, J.; Poler, R.; García-Sabater, J. P.; Lario, F. C., Models for production planning under uncertainty: a review, International Journal of Production Economics, 103, 271-285 (2006) |
| [16] | Oh, H. C.; Karimi, I. A., Planning production on a single processor with sequence-dependent setups part 1: determination of campaigns, Computers and Chemical Engineering, 25, 1021-1030 (2001) |
| [17] | Rizk, N.; Martel, A.; Ramudhin, A., A Lagrangean relaxation algorithm for multi-item lot-sizing problems with joint piecewise linear resource costs, International Journal of Production Economics, 102, 344-357 (2006) |
| [18] | Rockafellar, R. T.; Wets, R. J.B., Scenarios and policy aggregation in optimization under uncertainty, Mathematics of Operations Research, 16, 119-147 (1991) · Zbl 0729.90067 |
| [19] | Sox, C. R., Dynamic lot sizing with random demand and non-stationary costs, Operations Research Letters, 20, 155-164 (1997) · Zbl 0879.90075 |
| [20] | Takriti, S.; Birge, J. R., Lagrangian solution techniques and bounds for loosely coupled mixed-integer stochastic programs, Operations Research, 48, 91-98 (2000) · Zbl 1106.90363 |
| [21] | Tang, L.; Liu, J.; Rong, A.; Yang, Z., A review of planning and scheduling systems and methods for integrated steel production, European Journal of Operational Research, 133, 1-20 (2001) · Zbl 0988.90503 |
| [22] | Tempelmeier, H.; Derstroff, M., A Lagrangean-based heuristic for dynamic multilevel multiitem constrained lotsizing with setup times, Management Science, 42, 5, 738-756 (1996) · Zbl 0881.90045 |
| [23] | Wagner, H. M.; Whitin, T. M., Dynamic version of the economic lot size model, Management Science, 5, 89-96 (1958) · Zbl 0977.90500 |
| [24] | Xie, J.; Dong, J., Heuristic genetic algorithms for general capacitated lot-sizing problems, Computers and Mathematics with Applications, 44, 263-276 (2002) · Zbl 1007.90021 |
| [25] | Yu, S.; Du, T.; Nan, M.; Han, C.; Ai, M., A discussion of energy saving direction for rolling heating furnace, Industrial Furnace, 4, 39-43 (1997) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
