A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems

详细信息    查看全文

• 作者：Claudio Fabiano Motta Toledo ; Márcio da Silva Arantes…
• 关键词：Lot ; sizing ; Heuristics ; Relax ; and ; fix ; Fix ; and ; optimize ; Backlogging ; 90C11
• 刊名：Journal of Heuristics
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：21
• 期：5
• 页码：687-717
• 全文大小：2,455 KB
• 参考文献：Absi, N., Detienne, B., Dauzère-Pérès, S.: Heuristics for the multi-item capacitated lot-sizing problem with lost sales. Comput. Oper. Res. 40(1), 264-72 (2013)MathSciNet CrossRef
  Akartunal?, K., Miller, A.J.: A heuristic approach for big bucket multi-level production planning problems. Eur. J. Oper. Res. 193(2), 396-11 (2009)CrossRef
  Akartunal?, K., Miller, A.J.: A computational analysis of lower bounds for big bucket production planning problems. Comput. Optim. Appl. 53(3), 729-53 (2012)MathSciNet CrossRef
  Almada-Lobo, B., Klabjan, D., Carravilla, M.A., Oliveira, J.F.: Multiple machine continuous setup lotsizing with sequence-dependent setups. Comput. Optim. Appl. 47(3), 529-52 (2010)MathSciNet CrossRef
  Almeder, C.: A hybrid optimization approach for multi-level capacitated lot-sizing problems. Eur. J. Oper. Res. 200, 599-06 (2010)CrossRef
  Baki, M.F., Chaouch, B.A., Abdul-Kader, W.: A heuristic solution procedure for the dynamic lot sizing problem with remanufacturing and product recovery. Comput. Oper. Res. 43, 225-36 (2014)MathSciNet CrossRef
  Ball, M.O.: Heuristics based on mathematical programming. Surv. Oper. Res. Manage. Sci. 16(1), 21-8 (2011)
  Barany, I., van Roy, T.J., Wolsey, L.A.: Uncapacitated lot sizing: the convex hull of solutions. Math. Program Study 22, 32-3 (1984)CrossRef
  Belvaux, G., Wolsey, L.A.: bc-prod: a specialized branch-and-cut system for lot-sizing problems. Manage. Sci. 46(5), 724-38 (2000)CrossRef
  Billington, P.J., McClain, J.O., Thomas, L.J.: Heuristics for multilevel lot-sizing with a bottleneck. Manage. Sci. 32, 989-006 (1986)CrossRef
  Degraeve, Z., Jans, R.: A new Dantzig-Wolfe reformulation and branch-and-price algorithm for the capacitated lot-sizing problem with setup times. Oper. Res. 55(5), 909-20 (2007)MathSciNet CrossRef
  Eppen, G.D., Martin, R.K.: Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper. Res. 35(6), 832-48 (1987)CrossRef
  Federgruen, A., Meissner, J., Tzur, M.: Progressive interval heuristics for multi-item capacitated lot sizing problem. Oper. Res. 55(3), 490-02 (2007)MathSciNet CrossRef
  Florian, M., Lenstra, J.K., Rinnooy Kan, H.G.: Deterministic production planning: algorithms and complexity. Manage. Sci. 26(7), 669-79 (1980)MathSciNet CrossRef
  Helber, S., Sahling, F.: A fix-and-optimize approach for the multi-level capacitated lot sizing problem. Int. J. Prod. Econ. 123, 247-56 (2010)CrossRef
  Kébé, S., Sbihi, N., Penz, B.: A lagrangean heuristic for a two-echelon storage capacitated lot-sizing problem. J. Intell. Manuf. 23(6), 2477-483 (2012)CrossRef
  Krarup, J., Bilde, O.: Plant location, set covering and economic lotsizes: an O(\(mn\) ) algorithm for structured problems. Optimierung bel Graphentheoretischen und Ganzzahligen Probleme, pp. 155-80. Birkhauser (1997)
  Kü?ükyavuz, S., Pochet, Y.: Uncapacitated lot-sizing with backlogging: The convex hull. Math. Program. 118(1), 151-75 (2009)MathSciNet CrossRef
  Miller, A.J., Nemhauser, G.L., Savelsbergh, M.W.P.: On the polyhedral structure of a multi-item production planning model with setup times. Math. Program. 94(2-), 375-05 (2003)MathSciNet CrossRef
  MIPLIB. A library of pure and mixed integer problems (2010). http://?miplib.?zib.?de/-/span> . Accessed on 29 Dec 2014
  Multi-LSB. Multi-item lot-sizing problems with backlogging: a library of test instances (2014). http://?dx.?doi.?org/-0.-5129/-52b7827-b62b-4af4-8869-64b12b1c69a1 . Accessed 29 Dec 2014
  Pochet, Y., Wolsey, L.A.: Production Planning by Mixed Integer Programming. Springer, Berlin (2006)
  Ramezanian, R., Saidi-Mehrabad, M.: Hybrid simulated annealing and mip-based heuristics for stochastic lot-sizing and scheduling problem in capacitated multi-stage production system. Appl Math Modell 37(7), 5134-147 (2013)MathSciNet CrossRef
  Rardin, R.L., Wolsey, L.A.: Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems. Eur. J. Oper. Res. 71(1), 95-09 (1993)CrossRef
  Seeanner, F., Almada-Lobo, B., Meyr, H.: Combining the principles of variable neighborhood decomposition search and the fix & optimize heuristic to solve multi-level lot-sizing and scheduling problems. Comput. Oper. Res. 40(1), 303-17 (2013)MathSciNet CrossRef
  Stadtler, H.: Multilevel lot sizing with setup times and multiple constrained resources: internally rolling schedules with lot-sizing windows. Oper. Res. 51, 487-02 (2003)CrossRef
  Toledo, C.F.M., da Silva Arantes, M., de Oliveira, R.R.R., Almada-Lobo, B.: Glass container production scheduling through hybrid multi-population based evolutionary algorithm. Appl. Soft Comput. 13(3), 1352-364 (2013)CrossRef
  Toledo, C.F.M., de Oliveira, R.R.R., Fran?a, P.M.: A hybrid multi-population genetic algorithm applied to solve the multi-level capacitated lot sizing problem with backlogging. Comput. Oper. Res. 40(4), 910-19
• 作者单位：Claudio Fabiano Motta Toledo (1)
  Márcio da Silva Arantes (1)
  Marcelo Yukio Bressan Hossomi (1)
  Paulo Morelato Fran?a (2)
  Kerem Akartunal? (3)
  
  1. Institute of Mathematics and Computer Science, University of S?o Paulo, Avenida trabalhador s?o-carlense, 400, Centro, S?o Carlos, SP, 13566-590, Brazil
  2. Department of Mathematics and Computer Science, UNESP, R. Roberto Simonsen, 305, CP 266, Presidente Prudente, SP, 19060-080, Brazil
  3. Department of Management Science, University of Strathclyde, 40 George Street, Glasgow, G1 1QE, UK
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Artificial Intelligence and Robotics
  Calculus of Variations and Optimal Control
  
• 出版者：Springer Netherlands
• ISSN：1572-9397

文摘

In this paper, we propose a simple but efficient heuristic that combines construction and improvement heuristic ideas to solve multi-level lot-sizing problems. A relax-and-fix heuristic is firstly used to build an initial solution, and this is further improved by applying a fix-and-optimize heuristic. We also introduce a novel way to define the mixed-integer subproblems solved by both heuristics. The efficiency of the approach is evaluated solving two different classes of multi-level lot-sizing problems: the multi-level capacitated lot-sizing problem with backlogging and the two-stage glass container production scheduling problem (TGCPSP). We present extensive computational results including four test sets of the Multi-item Lot-Sizing with Backlogging library, and real-world test problems defined for the TGCPSP, where we benchmark against state-of-the-art methods from the recent literature. The computational results show that our combined heuristic approach is very efficient and competitive, outperforming benchmark methods for most of the test problems. Keywords Lot-sizing Heuristics Relax-and-fix Fix-and-optimize Backlogging