The Economic Lot Scheduling Problem in Flow Lines with Sequence-Dependent Setups

Authors: M. Heydari, S. A. Torabi

Abstract:

The problem of lot sizing, sequencing and scheduling multiple products in flow line production systems has been studied by several authors. Almost all of the researches in this area assumed that setup times and costs are sequence –independent even though sequence dependent setups are common in practice. In this paper we present a new mixed integer non linear program (MINLP) and a heuristic method to solve the problem in sequence dependent case. Furthermore, a genetic algorithm has been developed which applies this constructive heuristic to generate initial population. These two proposed solution methods are compared on randomly generated problems. Computational results show a clear superiority of our proposed GA for majority of the test problems.

Keywords: Economic lot scheduling problem, finite horizon, genetic algorithm, mixed zero-one nonlinear programming, sequence-dependent.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1083025

References:

[1] T. Batch, Selective Pressure in Evolutionary Algorithms. IEEE press1, NJ, 57-62(1994).
[2] E.A. Bomberger, Dynamic programming approach to a lot size scheduling problem. Management science. 12:778-784 (1996).
[3] G. Dobson, The ELSP: Achieving feasibility using time-varing lot sizes. Operations research. 35:764-771 (1987).
[4] W.C. Driscoel, H. Emmoss, Scheduling production on the one machine with change over costs. AIIE Transactions. 9:388-395 (1977)
[5] S. Fujita, The application of marginal analysis to the ELSP. AIIETransactrion. 10:354-361 (1978).
[6] G. Gallego, D.X. Show, Complexity of the ELSP with general cyclic schedules. IEEE Transactions. 29:109-113 (1997).
[7] A.M. Geoffrion, G.W. Graves, Scheduling parallel production lines with change over costs. Operations Research. 24:595-610 (1976).
[8] O.H. Hong-Choon, I.A. Karimi, Planning production on a single processor with sequence dependent setups: part1, computer and chemical enginnering. 5:1021-1030 (2001).
[9] O.H. Hong-Choon, I. Karimi, A planning production on a single processor with sequence dependent setups: part2, Computer and chemical enginnering. 25:1031-1043 (2001).
[10] S.A. Irani, U. Gunasena, Single machine setup dependent sequencing using a setup complexity ranking scheme. Journal of manufacturing systems. 7:11-23 (1988)
[11] B. Karimi, S.M.T. Fatemi Ghomi, J.M. Wilson, The capacitated lot sizing problem: a review of models and algorithms. Omega. 31:365-378 (2003)
[12] W.L. Maxwell, The scheduling of economic lot sizes. Navel Research logistics Quartery.11:89-124 (1964).
[13] J. Ouenniche, The impact of sequencing decisions on multi-item lot sizing and scheduling in flowshops. International Journal of operational research. 37: 2253-2270 (1999).
[14] P.W. Poon, J.N. Carter, Genetic algorithm crossover operators for ordering applications. Computers and Operations Research. 22:135-147 (1995).
[15] J. Roger, A computational approach to the economic lot scheduling problem. Journal of Management Science. 4: 264-291 (1958).
[16] R. Ruis, C. Maroto, Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristic. European Journal of Operational Research. Article in press (2004).
[17] H. Singh, J.B. Foster, Production scheduling with sequence dependent setup costs. IEE Transaction. 19:43-49 (1987).
[18] G. Taylor, M. Taha, A heuristic model for the sequence-dependent lot scheduling problem. Production planning and control. Vol8. 3: 213- 225(1997).
[19] S.A. Torabi, S.M.T. Fatemi Ghomi, B. Karimi, A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chain. European journal of operational research. Article in press (2005).
[20] S.A. Torabi, B. Karimi, S.M.T. Fatemi Ghomi, The common cycle economic lot scheduling in flexible job shops: the finite horizon case. International Journal of Production Economics. 97: 52-65 (2004).
[21] J. Wagner, J. Davis, A search heuristic for the sequence-dependent economic lot scheduling problem. European Journal of Operational Research. 141:133-146 (2001).