Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems

References

• Aho A. V., Hopcroft J. E., Ullman J. D.Data Structures and Algorithms (1983) (Addison-Wesley Publishing Company, Reading, Ma) 53–60Google Scholar
• Baker K. R., Dixon P., Magazine M. J., Silver E. A. An algorithm for the dynamic lot-size problem with time-varying production capacity constraints. Management Sci. (1978) 24:1710–1720Link, Google Scholar
• Bitran G. R., Matsuo H. Approximation formulations for the single-product capacitated lot size problem. Oper. Res. (1986) 34:63–74Link, Google Scholar
• Bitran G. R., Yanasse H. H. Computational complexity of the capacitated lot size problem. Management Sci. (1982) 28:1174–1186Link, Google Scholar
• Chan L. M. A., Muriel A., Shen Z. J., Simchi-Levi D. On the effectiveness of zero-inventory ordering policies for economic lot-sizing models with piece-wise linear cost structures. (1999) . Technical report, Northwestern University, Evanston, ILGoogle Scholar
• Chen H.-D., Hearn D., Lee C.-Y. A new dynamic programming algorithm for the single item capacitated dynamic lot size model. J. Global Optim. (1994a) 4:285–300Crossref, Google Scholar
• Chen H.-D., Hearn D., Lee C.-Y. A dynamic programming algorithm for dynamic lot size models with piecewise linear costs. J. Global Optim. (1994b) 4:397–413Crossref, Google Scholar
• Chen W.-H., Thizy J.-M. Analysis of relaxations for the multi-item capacitated lot-sizing problem. Ann. Oper. Res. (1990) 26:29–72Crossref, Google Scholar
• Chung C.-S., Lin C.-H. M. An 𝒪(T2) algorithm for the NI/G/NI/ND capacitated lot size problem. Management Sci. (1988) 34:420–426Link, Google Scholar
• Chung C.-S., Flynn J., Lin C.-H. M. An effective algorithm for the capacitated single item lot size problem. Eur. J. Oper. Res. (1994) 75:427–440Crossref, Google Scholar
• Constantino M. Lower bounds in lot-sizing models: A polyhedral study. Math. Oper. Res. (1998) 23:101–118Link, Google Scholar
• Erenguc S. S., Aksoy Y. A branch and bound algorithm for a single item nonconvex dynamic lot sizing problem with capacity constraints. Comput. Oper. Res. (1990) 17:199–210Crossref, Google Scholar
• Federgruen A., Tzur M. Capacitated dynamic lot-sizing models. (1995) . Working paper, Graduate School of Business, Columbia University, New York, NYGoogle Scholar
• Flippo O. E., Kolen A. W. J., Koster A. M. C. A., Van de Leensel R. L. M. J. A dynamic programming algorithm for the local access telecommunication network expansion problemon problem. Eur. J. Oper. Res. (2000) 127:189–202Crossref, Google Scholar
• Florian M., Klein M. Deterministic production planning with concave costs and capacity constraints. Management Sci. (1971) 18:12–20Link, Google Scholar
• Florian M., Lenstra J. K., Rinnooy Kan A. H. G. Deterministic production planning: Algorithms and complexity. Management Sci. (1980) 26:669–679Link, Google Scholar
• Gavish B., Johnson R. E. A fully polynomial approximation scheme for single-product scheduling in a finite capacity facility. Oper. Res. (1990) 38:70–83Link, Google Scholar
• Karmarkar U. S., Kekre S., Kekre S. The dynamic lot-sizing problem with startup and reservation costs. Oper. Res. (1987) 35:389–398Link, Google Scholar
• Kirca Ö. An efficient algorithm for the capacitated single item dynamic lot size problem. Eur. J. Oper. Res. (1990) 45:15–24Crossref, Google Scholar
• Kovalyov M. Y. Improving the complexities of approximation algorithms for optimization problems. Oper. Res. Lett. (1995) 17:85–87Crossref, Google Scholar
• Lambrecht M., Vander Eecken J. A capacity constrained single-facility dynamic lot-size model. Eur. J. Oper. Res. (1978) 2:132–136Crossref, Google Scholar
• Leung J. M. Y., Magnanti T. L., Vachani R. Facets and algorithms for capacitated lot sizing. Math. Programming (1989) 45:331–359Crossref, Google Scholar
• Lofti V., Yoon Y.-S. An algorithm for the single item capacitated lot-sizing problem with concave production and holding costs. J. Oper. Res. Soc. (1994) 45:934–941Crossref, Google Scholar
• Love S. F. Bounded production and inventory models with piecewise concave costs. Management Sci. (1973) 20:313–318Link, Google Scholar
• Pochet Y. Valid inequalities and separation for capacitated economic lot sizing. Oper. Res. Lett. (1988) 7:109–116Crossref, Google Scholar
• Pochet Y., Wolsey L. A. Lot-sizing with constant batches: Formulations and valid inequalities. Math. Oper. Res. (1993) 18:767–785Link, Google Scholar
• Pochet Y., Wolsey L. A. Algorithms and reformulations for lot-sizing problems. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. (1995) 20:245–293Crossref, Google Scholar
• Rosling K. A capacitated single-item lot-size model. Internat. J. Production Econom. (1993) 30-31:213–219Crossref, Google Scholar
• Salomon M., Kroon L. G., Kuik R., Van Wassenhove L. N. Some extensions of the discrete lotsizing and scheduling problem. Management Sci. (1991) 37:801–812Link, Google Scholar
• Shaw D. X., Wagelmans A. P. M. An algorithm for single-item capacitated economic lot-sizing with piecewise linear production costs and general holding costs. Management Sci. (1998) 44:831–838Link, Google Scholar
• Swoveland C. A deterministic multi-period production planning model with piecewise concave production and holding-backorder costs. Management Sci. (1975) 21:1007–1013Link, Google Scholar
• Veinott A. F. Production planning with convex costs: A parametric study. Management Sci. (1964) 10:441–460Link, Google Scholar
• van Hoesel C. P. M., Wagelmans A. P. M. An 𝒪(T3) algorithm for the economic lot-sizing problem with constant capacities. Management Sci. (1996) 42:142–150Link, Google Scholar
• Woeginger G. J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?. INFORMS J. Comput. (2000) 12:57–74Link, Google Scholar