×

The economic lot scheduling problem under power-of-two policy. (English) Zbl 0980.90030

Summary: We present further analysis on the Economic Lot Scheduling Problem (ELSP) without capacity constraints under Power-of-Two (PoT) policy. We explore its optimality structure and discover that the optimal objective value is piecewise convex. By making use of the junction points of this function, we derive an effective (polynomial time) search algorithm to secure a global optimal solution. The conclusions of this research lay the foundation for deriving an efficient heuristic, and also creates a benchmark for evaluating the quality of the heuristics for the conventional ELSP under PoT policy.

MSC:

90B35 Deterministic scheduling theory in operations research
90B05 Inventory, storage, reservoirs
90B40 Search theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Elmaghraby, S. E., The economic lot scheduling problem (ELSP): Review and extension, Mgmt. Sci., 24, 587-597 (1978) · Zbl 0376.90051
[2] Lopez, M. A.; Kingsmans, B. G., The economic lot scheduling problem: Theory and practice, Int. J. Prod. Econ., 23, 147-164 (1991)
[3] Yao, M. J., The economic lot scheduling problem with extension to multiple resource constraints, Unpublished Ph.D. Dissertation (1999), North Carolina State University: North Carolina State University Raleigh, NC
[4] Davis, S. G., Scheduling economic lot size production runs, Mgmt. Sci., 36, 985-998 (1990) · Zbl 0712.90030
[5] Haessler, R.; Hogue, S., A note on the single machine multi-product lot scheduling problem, Mgmt. Sci., 22, 909-912 (1976)
[6] Haessler, R., An improved extended basic period procedure for solving the economic lot scheduling problem, AIEE Trans., 11, 336-340 (1979)
[7] Bomberger, E., A dynamic programming approach to a lot size scheduling problem, Mgmt. Sci., 12, 778-784 (1966) · Zbl 0139.13606
[8] Axsäter, S., Alternative dynamic programming approaches to obtain upper bounds for the economic lot scheduling problem, Eng. Costs and Prod. Econ., 6, 17-23 (1982)
[9] Hsu, W. L., On the general feasibility of scheduling lot sizes of several products on one machine, Mgmt. Sci., 29, 93-105 (1983) · Zbl 0508.90050
[10] Madigan, J. C., Scheduling a multi-product single machine system for an infinite planning period, Mgmt. Sci., 14, 713-719 (1968)
[11] Goyal, S. K., Scheduling a multi-product single-machine system, Opnl. Res. Quart., 24, 261-266 (1973) · Zbl 0256.90024
[12] Boctor, F. F., The G-group heuristic for single machine lot scheduling, Int. J. Prod. Res., 25, 363-379 (1987) · Zbl 0618.90043
[13] Doll, C. L.; Whybark, D. C., An interactive procedure for the single-machine multi-product lot scheduling problem, Mgmt. Sci., 20, 50-55 (1973)
[14] Geng, P. C.; Vickson, R. G., Two heuristics for the economic lot scheduling problem: An experimental study, Naval Res. Logist, 35, 605-617 (1988) · Zbl 0642.90032
[15] Park, K. S.; Yun, D. K., A stepwise partial enumeration algorithm for the economic lot scheduling problem, IEE Trans., 16, 363-370 (1984)
[16] Elmaghraby, S. E., The economic lot scheduling problem (ELSP): Review and extension, Report 112, Graduate Program in Operations Research (1976), North Carolina State University
[17] Roundy, R., Rounding off to powers of two in continuous relaxations of capacitated lot sizing problems, Mgmt. Sci., 35, 1433-1442 (1984) · Zbl 0684.90029
[18] Jackson, P. L.; Maxwell, W. L.; Muckstadt, J. A., The joint replenishment problem with a power-of-two restriction, IIE Trans., 17, 25-32 (1985)
[19] Federgruen, A.; Zheng, Y. S., Optimal power-of-two replenishment strategies in capacitated general production/distribution networks, Mgmt. Sci., 39, 710-727 (1993) · Zbl 0796.90016
[20] Elmaghraby, S. E., An extended basic period approach to the ELSP, Report 115, Graduate Program in Operations Research (1977), North Carolina State University
[21] Fujita, S., The application of marginal analysis to the economic lot scheduling problem, AIIE Trans., 10, 354-361 (1978)
[22] Hanssman, F., (Operations Research in Production and Inventory (1962), John Wiley & Sons: John Wiley & Sons New York), 158-160
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.