A job-splitting heuristic for lot-size scheduling in multi-stage, multi- product production processes. (English) Zbl 0809.90078

Summary: This paper focuses primarily on cyclic scheduling in multi-stage, multi- product production. Cyclic schedules are generalizations of common cycle schedules (CCSP) in which the cycle time for each product is required to be an integer multiple (not necessarily one as in the CCSP) of the base cycle time. Solution procedures which have been reported in literature for this problem ignore in-process inventory and are limited to single- stage and/or single-product production processes. After reviewing the literature, this paper presents an efficient heuristic procedure which generates near-optimal cyclic schedules for the multi-product, multi- stage flow shop production environment under deterministic and stationary conditions. This procedure accounts for all inventory costs including in- process inventory and idle time. The proposed solution is then compared to the optimal CCSP solution developed by El-Najdawi and Kleindorfer and, as expected, performed significantly better than the traditional CCSP approach. Compared to other heuristics studied in the literature, this procedure appears to be more useful as a computable and cost-efficient approach for practical size applications.


90B35 Deterministic scheduling theory in operations research
90B30 Production models
90B05 Inventory, storage, reservoirs


Full Text: DOI


[1] Boctor, F. F., The product, single-machine, static demand, infinite horizon lot scheduling problem, Management Science, 28, 298-807 (1982) · Zbl 0482.90022
[2] Buffa, E. S., Modern Production and Operations Management (1987), Wiley: Wiley New York
[3] Claver, J. F.; Jackson, P. L., Lot sizing in cyclic Scheduling, (Technical Report No. 736 (1987), School of OR&IE, Cornell University: School of OR&IE, Cornell University Ithaca, NY)
[4] Crowston, N. B.; Wagner, M.; Williams, J. F., Economic lot size determination in multi-stage assembly systems, Management Science, 19/5, 517-527 (1973) · Zbl 0251.90013
[5] Delporte, C. M.; Thomas, L. J., Lot sizing and sequencing for \(n\) products on one facility, Management Science, 23, 1070-1079 (1977) · Zbl 0354.90042
[6] Dobson, G., The economic lot scheduling problem: Achieving feasibility using time-varying lot sizes, Operations Research, 35/5, 764-771 (1987) · Zbl 0636.90038
[7] Dobson, G.; Yano, C. A., Cyclic scheduling to minimize inventory in a batch flow line, (Working Paper Series QM-9013 (1990), University of Rochester) · Zbl 0806.90063
[8] Doll, C. L.; Whybark, D. C., An interactive procedure for the single-machine, multi-product lot scheduling problem, Management Science, 20, 50-55 (1973)
[9] Eilon, S., Elements of Production Planning and Control, ((1962), Macmillan: Macmillan New York), 227-263
[10] Elmaghraby, S. E., The Economic Lot Scheduling Problem: Review and extensions, Management Science, 24, 287-598 (1978) · Zbl 0376.90051
[11] El-Najdawi, M. K., Common cycle scheduling approach to lot-size scheduling for multi-stage, multi-product production processes (1989), The Wharton School, University of Pennsylvania, Unpublished Dissertation · Zbl 0809.90078
[12] El-Najdawi, M. K., A compact heuristic for lot-size scheduling in multi-stage, multi-product production processes, International Journal of Production Economics, 27, 29-41 (1992)
[13] El-Najdawi, M. K.; Kleindorfer, P. R., Common cycle lot-size scheduling for multi-stage, multi-product production, Management Science, 39/7, 872-885 (1993) · Zbl 0785.90042
[14] Galego, G., The extended Economic Lot Scheduling Problem, (Technical Report #692 (1988), School of OR&IE, Cornell University: School of OR&IE, Cornell University Ithaca, NY)
[15] Galvin, T. M., Economic Lot Scheduling Problem with sequence-dependent setup costs, Production and Inventory Management, 28/1, 96-105 (1987)
[16] Galvin, T. M.; Van Deusen, D. L., Interactive economic lot scheduling: A successful implementation, Production and Inventory Management (1988), Second Quarter
[17] Geng, P. C.; Vickson, R. G., Two heuristics for the Economic Lot Scheduling Problem: An experimental study, Naval Research Logistics, 35, 605-617 (1988) · Zbl 0642.90032
[18] Goyal, S. K., Scheduling a multi-product single machine system, Operational Research Quarterly, 24 (1973) · Zbl 0256.90024
[19] Graves, S., The multi-product production cycling problem, AIIE Transactions, 12, 233-240 (1980)
[20] Hanssmann, F., Operations Research in Production and Inventory Control (1962), Wiley: Wiley New York · Zbl 0115.38203
[21] Hax, A.; Candea, D., Production and Inventory Management (1984), Prentice-Hall: Prentice-Hall Englewood Cliff, NJ
[22] Hsu, J. I.S., Economic production quantity determination in the multistage production process, Production and Inventory Management, 25/4, 61-70 (1984)
[23] Jensen, P.; Kahn, H. A., Scheduling in a multi-stage production system with set-up and inventory costs, AIIE Transactions, 4/2, 126-133 (1972)
[24] Matsuo, H., Cyclic scheduling problems in the two-machine flow shop: Complexity, worst-case and average case analysis, (Working Paper #87-12-4 (1987), Graduate School of Business, University of Texas at Austin: Graduate School of Business, University of Texas at Austin Austin, TX) · Zbl 0731.90041
[25] Maxwell, W. L., The scheduling of economic lot sizes, Naval Research Logistics Quarterly, 11, 89-124 (1964)
[26] Maxwell, W. L.; Muckstadt, J. A., A model for planning in an \(N\) stage system, ((1981), School of OR&IE, Cornell University: School of OR&IE, Cornell University Ithaca, NY), Technical Report
[27] McCormick, S. T.; Pinedo, M. L.; Shenker, S.; Wolf, B., Sequencing in an assembly line with blocking to minimize cycle time, ((1986), School of OR&IE, Cornell University: School of OR&IE, Cornell University Ithaca, NY), Technical Report · Zbl 0689.90048
[28] Miltenberg, J., Level schedules for mixed-model assembly lines in Just-In-Time production systems, Management Science, 35/2, 192-208 (1989)
[29] Peterson, R.; Silver, E. A., Decision Systems for Inventory Management and Production Planning (1985), Wiley: Wiley New York
[30] Roundy, R., Cyclic schedules for job shops with identical jobs, (Technical Report #766 (1988), School of OR&IE, Cornell University: School of OR&IE, Cornell University Ithaca, NY) · Zbl 0770.90036
[31] Szendrovits, A. Z., Manufacturing cycle time determination for a multistage economic production quantity model, Management Science, 22/3, 298-308 (1975) · Zbl 0313.90017
[32] Spence, A. M.; Porteus, E. L., Setup production and increased effective capacity, Management Science, 33/10, 1291-1301 (1989)
[33] Suzaki, K., The New Manufacturing Challenge (1987), Collier Macmillan: Collier Macmillan London
[34] Taha, H. A.; Skeith, R. W., The economic lot sizes in multi-stage production systems, AIIE Transactions, 2/2, 157-162 (1970)
[35] Ware, N.; Keown, B., Common cycle scheduling: A useful application, Production and Inventory Management, 28/1, 16-22 (1987)
[36] Wittrock, R. J., Scheduling algorithms for flexible flow lines, IBM Journal of Research and Development, 29, 401-412 (1985)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.