Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions.

*(English)*Zbl 0948.90009Summary: The Capacitated Lot Sizing and Loading Problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the Capacitated Lot Sizing Problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search and genetic algorithms to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.

##### MSC:

90B05 | Inventory, storage, reservoirs |

90B30 | Production models |

90B35 | Deterministic scheduling theory in operations research |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

capacitated lot sizing and loading problem; parallel processors; scheduling problem; heuristics; simulated annealing; tabu search; genetic algorithms
PDF
BibTeX
XML
Cite

\textit{L. Özdamar} and \textit{Ş. İ. Birbil}, Eur. J. Oper. Res. 110, No. 3, 525--547 (1998; Zbl 0948.90009)

Full Text:
DOI

##### References:

[1] | Billington, P.J.; McClain, J.O.; Thomas, L.J., Heuristics for multilevel lot-sizing with a bottleneck, Management science, 32, 989-1006, (1986) · Zbl 0596.90038 |

[2] | Billington, P.; Blackburn, J.; Maes, J.; Millen, R.; Van Wasssenhove, L.N., Multi item lot sizing in capacitated multi-stage serial systems, IIE transactions, 26, 12-18, (1994) |

[3] | Bitran, G.R.; Yanasse, H.H., Computational complexity of the capacitated lot size problem, Management science, 28, 1174-1186, (1982) · Zbl 0502.90046 |

[4] | Bozyel, M.A.; Özdamar, L., A heuristic approach to the capacitated lot sizing and scheduling problem (with parallel facilities), Yeditepe university, department of systems engineering (working paper), (1996) · Zbl 0929.90025 |

[5] | Cattrysse, D.; Maes, J.; Van Wassenhove, L.N., Set partitioning and column generation heuristics for capacitated lotsizing, European journal of operational research, 46, 38-47, (1990) · Zbl 0711.90019 |

[6] | Cattrysse, D.; Salomon, M.; Kuik, R.; Van Wassenhove, L.N., A dual ascent and column generation heuristic for the discrete lot sizing and scheduling problem with setup times, Management science, 39, 477-486, (1993) · Zbl 0774.90059 |

[7] | Cheng, T.C.E.; Sin, C.C.S., A state of the art review of parallel machine scheduling research, European journal of operational research, 47, 271-292, (1990) · Zbl 0707.90053 |

[8] | Dauzerre-Peres, S.; Laserre, J.B., Integration of lot sizing and scheduling decisions in a job-shop, European journal of operational research, 75, 413-426, (1994) |

[9] | De Jong, K.A., Adaptive system design: a genetic approach, IEEE transactions on systems, man and cybernetics, SMC-10, 566-574, (1980) |

[10] | De Matta, R.; Guignard, M., Dynamic production scheduling for a process industry, Operations research, 42, 492-503, (1994) · Zbl 0809.90066 |

[11] | Diaby, M.; Bahl, H.C.; Karwan, M.H.; Zionts, S., A Lagrangiean relaxation approach for very large scale capacitated lot sizing, Management science, 38, 1329-1340, (1992) · Zbl 0758.90020 |

[12] | Dixon, P.S.; Elder, M.D.; Rand, G.K.; Silver, E.A., A heuristic algorithm for determining lot sizes of an item subject to regular and overtime production capacities, Journal of operations management, 3, 121-130, (1983) |

[13] | Dixon, P.S.; Silver, E.A., A heuristic solution procedure for the multi-item single level limited capacity lot sizing problem, Journal of operations management, 2, 23-39, (1981) |

[14] | Dowsland, K.A., Some experiments with simulated annealing techniques for packing problems, European journal of operational research, 68, 389-399, (1993) · Zbl 0800.90729 |

[15] | Duplaga, E.A.; Hahn, C.K.; Watts, C.A., Evaluating capacity change and setup time reduction in a capacity constrained joint lot sizing situation, International journal of production research, 34, 1859-1873, (1996) · Zbl 0928.90003 |

[16] | Fleischmann, B., The discrete lot sizing and scheduling problem, European journal of operational research, 44, 337-348, (1990) · Zbl 0689.90043 |

[17] | Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039 |

[18] | Glover, F., Tabu search — part I, ORSA journal of computing, 1, 190-206, (1989) · Zbl 0753.90054 |

[19] | Glover, F., Tabu search — part II, ORSA journal of computing, 2, 4-32, (1990) · Zbl 0771.90084 |

[20] | Glover, F.; Kelly, J.P.; Laguna, M., Genetic algorithms and tabu search:hybrids for optimization, Computers and operations research, 22, 111-134, (1995) · Zbl 0813.90093 |

[21] | Goldberg, D., Genetic algorithms in search, optimization and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056 |

[22] | Grefenstette, J., Optimization of control parameters for genetic algorithms, IEEE transactions on systems, man and cybernetics, SMC-16, (1986) |

[23] | Günther, H.O., Planning lot sizes and capacity requirements in a single stage production system, European journal of operational research, 31, 223-231, (1987) · Zbl 0615.90057 |

[24] | Hax, A.C.; Candea, D., Production and inventory management, (1984), Prentice-Hall Englewood Cliffs, NJ |

[25] | Holland, J.H., Adaptation in natural and artificial systems, (1975), University of Michigan Press Ann Arbor, MI |

[26] | Huntley, C.L.; Brown, D.E., Parallel genetic algorithms with local search, Computers and operations research, 23, 559-571, (1996) · Zbl 0847.90116 |

[27] | Johnson, D.S., Fast algorithms for bin packing, Journal of computer and system sciences, 8, 272-314, (1974) · Zbl 0284.68023 |

[28] | Jordan, C.; Drexl, A., Discrete lot sizing and scheduling by batch sequencing, University of Kiel, Kiel (working paper), (1996) |

[29] | Kim, D.; Mabert, V.A., Integrative versus separate cycle scheduling heuristics for capacitated discrete lot sizing and sequencing problems, International journal of production research, 33, 2007-2021, (1995) · Zbl 0913.90172 |

[30] | Kirkpatrick, A.; Gelatt, C.D.; Vechi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162 |

[31] | Kirca, Ö.; Kökten, M., A new heuristic approach for the multi-item dynamic lot sizing problem, European journal of operational research, 75, 332-341, (1994) · Zbl 0806.90031 |

[32] | Kolen, A.W.J.; Kroon, L.G., On the computational complexity of the (maximum) class scheduling, European journal of operational research, 54, 23-38, (1991) · Zbl 0741.90035 |

[33] | Kuik, R.; Salomon, M.; van Wassenhove, L.N.; Maes, J., Linear programming, simulated annealing and tabu search heuristics for lot sizing in bottleneck assembly systems, IIE transactions, 25, 62-72, (1993) |

[34] | Lambrecht, M.R.; Vanderveken, H., Heuristic procedure for the single operation multi-item loading problem, IIE transactions, 11, 319-326, (1979) |

[35] | Maes, J.; McClain, J.O.; Van Wassenhove, L.N., Multilevel capacitated lot sizing complexity and LP-based heuristics, European journal of operational research, 53, 131-148, (1991) · Zbl 0734.90036 |

[36] | Maes, J.; Van Wassenhove, L.N., A simple heuristic for the multi-item single level capacitated lot sizing problem, Operations research letters, 4, 265-273, (1986) · Zbl 0596.90029 |

[37] | Michalewicz, Z., Genetic algorithms +data structures=evolution programs, (1994), Springer Berlin · Zbl 0818.68017 |

[38] | Mühlenbein, H., Evolutionary algorithms: theory and applications, () · Zbl 0722.92010 |

[39] | Özdamar, L., A genetic algorithm approach for the multimode resource-constrained project scheduling problem under general resource categories, () |

[40] | Özdamar, L.; Atli, A.Ö.; Bozyel, M.A., Heuristic family disaggregation techniques in hierarchical production planning systems, International journal of production research, 34, 2613-2628, (1996) · Zbl 0929.90025 |

[41] | Özdamar, L.; Birbil, I.; Portmann, M.C., New results for the capacitated lot sizing problem with overtime decisions and setup times, (1997), Yeditepe University, Department of Systems Engineering Istanbul, Turkey, (working paper) |

[42] | Özdamar, L.; Bozyel, M.A., The capacitated lot sizing problem with overtime decisions and setup times, (1996), Yeditepe University, Department of Systems Engineering Istanbul, Turkey, (working paper) |

[43] | Özdamar, L.; Bozyel, M.A., Simultaneous lot sizing and loading of product families on parallel facilities of different classes, International journal of production research, (1997), (to appear) · Zbl 0946.90549 |

[44] | Portmann, M.C., Genetic algorithms and scheduling: A state of the art and some propositions, () |

[45] | Portmann, M.C., Scheduling methodology: optimization and compu-search approaches I, () |

[46] | Potts, J.C.; Giddens, T.D.; Yadav, S.B., The development and evaluation of an improved genetic algorithm based on migration and artificial selection, IEEE transactions on systems, man and cybernetics, 24, 73-86, (1994) |

[47] | Salomon, M.; Kroon, L.G.; Kuik, R.; Van Wassenhove, L.N., Some extensions of the discrete lot sizing and scheduling problem, Management science, 37, 801-811, (1991) |

[48] | Srinivas, M.; Patnaik, L.M., Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE transactions on systems, man and cybernetics, 24, 656-667, (1994) |

[49] | Tempelmeier, H.; Derstroff, M., A Lagrangean based heuristic for dynamic multi item multi level constrained lot sizing with setup times, Management science, 42, 738-757, (1996) · Zbl 0881.90045 |

[50] | Tempelmeier, H.; Helber, S., A heuristic for dynamic multi item multi level capacitated lot sizing for general product structures, European journal of operational research, 75, 296-311, (1994) · Zbl 0809.90070 |

[51] | Thizy, J.M.; Van Wassenhove, L.N., Lagrangian relaxation the multi-item capacitated lotsizing problem: A heuristic implementation, IIE transactions, 17, 308-313, (1985) |

[52] | Trigeiro, W.W.; Thomas, L.J.; McLain, J.O., Capacitated lot sizing with setup times, Management science, 35, 353-366, (1989) |

[53] | Uckun, S.; Bagchi, J.C.; Proust, C., Managing genetic search in job shop scheduling, IEEE expert, 8, 15-24, (1993) |

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.