View Item 

Show simple item record

Computational complexity of finding Pareto efficient outcomes for biobjective lot‐sizing models
dc.contributor.authorRomeijn, H. Edwinen_US
dc.contributor.authorMorales, Dolores Romeroen_US
dc.contributor.authorHeuvel, Wilcoen_US
dc.date.accessioned2014-08-06T16:49:49Z
dc.date.availableWITHHELD_13_MONTHSen_US
dc.date.available2014-08-06T16:49:49Z
dc.date.issued2014-08en_US
dc.identifier.citationRomeijn, H. Edwin; Morales, Dolores Romero; Heuvel, Wilco (2014). "Computational complexity of finding Pareto efficient outcomes for biobjective lot‐sizing models." Naval Research Logistics (NRL) 61(5): 386-402.en_US
dc.identifier.issn0894-069Xen_US
dc.identifier.issn1520-6750en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/108049
dc.description.abstractIn this article, we study a biobjective economic lot‐sizing problem with applications, among others, in green logistics. The first objective aims to minimize the total lot‐sizing costs including production and inventory holding costs, whereas the second one minimizes the maximum production and inventory block expenditure. We derive (almost) tight complexity results for the Pareto efficient outcome problem under nonspeculative lot‐sizing costs. First, we identify nontrivial problem classes for which this problem is polynomially solvable. Second, if we relax any of the parameter assumptions, we show that (except for one case) finding a single Pareto efficient outcome is an N P ‐hard task in general. Finally, we shed some light on the task of describing the Pareto frontier. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 386–402, 2014en_US
dc.publisherWiley Periodicals, Inc.en_US
dc.publisherFreeman and Companyen_US
dc.subject.otherBiobjectiveen_US
dc.subject.otherExpenditureen_US
dc.subject.otherPareto Efficient Outcomesen_US
dc.subject.otherComplexity Analysisen_US
dc.subject.otherLot‐Sizingen_US
dc.titleComputational complexity of finding Pareto efficient outcomes for biobjective lot‐sizing modelsen_US
dc.typeArticleen_US
dc.rights.robotsIndexNoFollowen_US
dc.subject.hlbsecondlevelStatistics (Mathematical)en_US
dc.subject.hlbtoplevelScienceen_US
dc.description.peerreviewedPeer Revieweden_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/108049/1/nav21590.pdf
dc.identifier.doi10.1002/nav.21590en_US
dc.identifier.sourceNaval Research Logistics (NRL)en_US
dc.identifier.citedreferenceM.J. Retel Helmrich, R. Jans, W. van den Heuvel, and A.P.M. Wagelmans, The economic lot‐sizing problem with an emission constraint, Forthcoming in Eur J Oper Res, ( 2014 ).en_US
dc.identifier.citedreferenceC. S. Chung and C. H. M. Lin, An O( T 2 ) algorithm for the NI/G/NI/ND capacitated lot size problem, Manag Sci 34 ( 1988 ), 420 – 426.en_US
dc.identifier.citedreferenceM. Ehrgott and X. Gandibleux, A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spektrum 22 ( 2000 ), 425 – 460.en_US
dc.identifier.citedreferenceM. Ehrgott and X. Gandibleux, Approximative solution methods for multiobjective combinatorial optimization, TOP, 12 ( 1 ) ( 2004 ), 1 – 89.en_US
dc.identifier.citedreferenceA. Federgruen and J. Meissner, Competition under time‐varying demands and dynamic lot‐sizing costs, Nav Res Log 56 ( 1 ) ( 2009 ), 57 – 73.en_US
dc.identifier.citedreferenceA. Federgruen and M. Tzur, A simple forward algorithm to solve general dynamic lot sizing models with n periods in O ( n log ⁡ n ) or O ( n ) time, Manag Sci 37 ( 1991 ), 909 – 925.en_US
dc.identifier.citedreferenceM. Florian and M. Klein, Deterministic procurement planning with concave costs and capacity constraints, Manag Sci 18 ( 1971 ), 12 – 20.en_US
dc.identifier.citedreferenceM. Florian, J.K. Lenstra, and A.H.G. Rinnooy Kan, Deterministic production planning: algorithms and complexity, Manag Sci 26 ( 1980 ), 669 – 679.en_US
dc.identifier.citedreferenceM.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP‐completeness, W.H. Freeman and Company, New York, 1979.en_US
dc.identifier.citedreferenceS. M. Gilbert, Coordination of pricing and multiple‐period production for constant priced goods, Eur J Oper Res 114 ( 1999 ), 330 – 337.en_US
dc.identifier.citedreferenceF. Love, Bounded production and inventory models with piecewise concave costs, Manag Sci 20 ( 1973 ), 313 – 318.en_US
dc.identifier.citedreferenceS. Mittal and A.S. Schulz, A general framework for designing approximation schemes for combinatorial optimization problems with many objectives combined into one, Oper Res 61 ( 2 ) ( 2013 ), 386 – 397.en_US
dc.identifier.citedreferenceC.H. Papadimitriou and M. Yannakakis, “On the approximability of trade‐offs and optimal access of web sources,” In: Proceedings of 41st Annual Symposium on Foundations of Computer Science, Los Alamitos, California, 2000, pp. 86–92.en_US
dc.identifier.citedreferenceT. Stidsen, K.A. Andersen, and B. Dammann, A branch and bound algorithm for a class of biobjective mixed integer programs, Manag Sci 60 ( 4 ) ( 2014 ), 1009 – 1032.en_US
dc.identifier.citedreferenceE. Toczylowski, “An O ( T 2 ) algorithm for the lot‐sizing problem with limited inventory levels,” in: IEEE Symposium on Emerging Technologies & Factory Automation, Vol. 3, Los Alamitos, California, 1995, pp. 78–85.en_US
dc.identifier.citedreferenceE.L. Ulungu and J. Teghem, Multi‐objective combinatorial optimization problems: a survey, J Multi‐Criteria Decis Anal 3 ( 1994 ), 83 – 104.en_US
dc.identifier.citedreferenceC.P.M. van Hoesel and A.P.M. Wagelmans, An O ( T 3 ) algorithm for the economic lot‐sizing problem with constant capacities, Manag Sci 42 ( 1996 ), 142 – 150.en_US
dc.identifier.citedreferenceC.P.M. van Hoesel and A.P.M. Wagelmans, Parametric analysis of setup cost in the economic lot‐sizing model without speculative motives, Int J Prod Econ 66 ( 2000 ), 13 – 22.en_US
dc.identifier.citedreferenceJ.C. Velázquez‐Martínez, J.C. Fransoo, E.E. Blanco, and J. Mora‐Vargas, The impact of carbon footprinting aggregation on realizing emission reduction targets, Flex Serv Manuf J 26 ( 1–2 ) ( 2014 ), 196 – 220.en_US
dc.identifier.citedreferenceA.P.M. Wagelmans, C.P.M. van Hoesel, and A. Kolen, Economic lot sizing: An O ( n log ⁡ n ) algorithm that runs in linear time in the Wagner‐Whitin case, Oper Res 40 ( 1992 ), S145 – S156.en_US
dc.identifier.citedreferenceH.M. Wagner and T.M. Whitin, Dynamic version of the economic lot size model, Manag Sci 5 ( 1958 ), 89 – 96.en_US
dc.identifier.citedreferenceL.A. Wolsey, Lot‐sizing with production and delivery time windows, Math Program Ser A 107 ( 2006 ), 471 – 489.en_US
dc.identifier.citedreferenceW.I. Zangwill, Minimum concave cost flows in certain networks, Manag Sci 14 ( 1968 ), 249 – 265.en_US
dc.identifier.citedreferenceN. Absi, S. Dauzère‐Pérès, S. Kedad‐Sidhoum, B. Penz, and C. Rapine, Lot‐sizing with carbon emission constraints, Eur J Oper Res 227 ( 1 ) ( 2013 ), 55 – 61.en_US
dc.identifier.citedreferenceA. Aggarwal and J. K. Park, Improved algorithms for economic lot‐size problems, Oper Res 14 ( 1993 ), 549 – 571.en_US
dc.identifier.citedreferenceS. Benjaafar, Y. Li, and M. Daskin, Carbon footprint and the management of supply chains: Insights from simple models, IEEE Trans Autom Sci Eng 10 ( 1 ) ( 2013 ), 99 – 116.en_US
dc.identifier.citedreferenceG. R. Bitran and H. H. Yanasse, Computational complexity of the capacitated lot size problem, Manag Sci 28 ( 1982 ), 1174 – 1186.en_US
dc.identifier.citedreferenceR. Blanquero and E. Carrizosa, A D.C. biobjective location model, J Global Optim 23 ( 2002 ), 139 – 154.en_US
dc.identifier.citedreferenceY. Bouchery, A. Ghaffari, Z. Jemai, and Y. Dallery, Including sustainability criteria into inventory models, Eur J Oper Res 222 ( 2 ) ( 2012 ), 229 – 240.en_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Name:
nav21590.pdf
Size:
260.8KB
Format:
PDF
View/Open

Show simple item record

Remediation of Harmful Language

The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.

Accessibility

If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.