Minimizing Total Tardiness in the mMachine FlowShop Problem by Heuristic Algorithms
Abstract
In this work the mmachine permutation flowshop problem has been considered. The permutation flowshop scheduling problem where a set of jobs have to be scheduled on a set of machines in the same order. We propose heuristic algorithms for the flowshop problem to minimizing the total tardiness. A new genetic and Tabu search algorithm which initialized by the solution of EDD, NEH and EN algorithm. Computational experiments are performed on benchmark instances and the results show the good performances of these methods. Finally, some future research directions are given.
Keywords
Full Text:
PDFReferences
M. L. Pinedo, Scheduling: Theory, algorithms, and systems. Springer 2008.
J. Du and J. Y. T. Leung, “Minimizing total tardiness on one machine is NPhard,” Mathematics of Operations Research, vol. 19, pp. 483–495, 1990.
J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of Discrete Mathematics, vol. 1, pp. 343–362, 1977.
Y. D. Kim, “A new branch and bound algorithm for minimizing mean tardiness in twomachine flowshops,” Computers & Operations Research, vol. 20(4), pp. 391–401, 1993.
J. C.H. Pan and E.T. Fan, “Twomachine flowshop scheduling to minimize total tardiness,” International Journal of Systems Science, vol. 28, no. 4, pp. 405–414, 1997.
T. Sen, P. Dileepan, and J. N. D. Gupta, “The twomachine flowshop scheduling problem with total tardiness,” Computers & Operations Research, vol. 16(4), pp. 333–340, 1989.
J. C. H. Pan, J. S. Chen, and C. M. Chao, “Minimizing tardiness in a twomachine flowshop,” Computers & Operations Research, vol. 29, pp. 869–885, 2002.
M. Nawaz, E. Enscore, and I. Ham, “A heuristic algorithm for the mmachine njob flow shop sequencing problem,” Omega, vol. 11, pp. 91–95, 1983.
C. Koulamas, “A guaranteed accuracy shifting bottleneck algorithm for the twomachine flowshop total tardiness problem,” Computers & Operations Research, vol. 25, pp. 83–89, 1998.
I. Osman and C. Potts, “Simulated annealing for permutation flowshop scheduling,” Omega, vol. 17, no. 6, pp. 551–557, 1989.
J. Grabowski and M. Wodecki, “A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion,” Computers & Operations Research, vol. 31, pp. 1891–1909, 2004.
E. Nowicki and C. Smutnicki, “A fast tabu search algorithm for the permutation flowshop problem,” European Journal of Operational Research, vol. 91, pp. 160–175, 1996.
V. A. Armentano and D. P. Ronconi, “Tabu search for total tardiness minimization in flowshop scheduling problems,” Computers & Operations Research, vol. 26, pp. 219–235, 1999.
M. BenDaya and M. AlFawzan, “A tabu search approach for the flow shop scheduling problem,” European Journal of Operational Research, vol. 109, pp. 88–95, 1998.
J. Brandão and A. Mercer, “A tabu search algorithm for the multitrip vehicle routing and scheduling problem,” European Journal of Operational Research, vol. 100, pp. 180–191, 1997.
G. C. Onwubolu and M. Mutingi, “Genetic algorithm for minimizing tardiness in flowshop scheduling,” Production Planning and Control, vol. 10, pp. 462–471, 1999.
C.J. Liao, ChaoTang Tseng, and P. Luarn, “A discrete version of particle swarm optimization for flowshop scheduling problems,” Computers & Operations Research, vol. 34, no. 10, pp. 3099–3111, 2007.
M. F. Tasgetiren, Y. C. Liang, M. Sevkli, and G. Gencyilmaz, “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem,” European Journal of Operational Research, vol. 177, no. 3, pp. 1930–1947, 2007.
F. Della Croce, A. Grosso, and F. Salassa, “A matheuristic approach for the total completion time twomachines permutation flow shop problem,” Lecture Notes in Computer Science, 6622 LNCS, pp. 38–47, 2011.
Q. C. Ta, J. C. Billaut, and J. L. Bouquard, “Recovering beam search and Matheuristic algorithms for the F2 ∑Tj scheduling problem,” 11th Workshop on Models and Algorithms for Planning and Scheduling Problems, 2013, pp. 218–220.
E. Vallada, R. Ruiz, and G. Minella, “Minimising total tardiness in the mmachine flowshop problem: A review and evaluation of heuristics and metaheuristics,” Computers & Operations Research, vol. 35, pp. 1350–1373, 2008.
E. Vallada and R. Ruiz, “Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem,” European Journal of Operational Research, vol. 38, pp. 57–67, 2010.
V. FernandezViagas and J. M. Framinan, “NEHbased heuristics for the permutation flowshop scheduling problem to minimise total tardiness,” Computers & Operations Research, vol. 60, pp. 2736, 2015.
V. FernandezViagas, R. Ruiz, and J. M. Framinan, “A new vision of approximate methods for the permutation flowshop to minimise makespan: Stateoftheart and computational evaluation,” European Journal of Operational Research. vol. 257, pp. 707721, 2017.
J. A. Holland, Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975.
D. E. Goldberg, Genetic algorithms in Search, Optimization and Machine Learning. AddisonWelsey, Reading Mass, 1989.
M. C. Portmann and A. Vignier. "Chapter 4: Genetic algorithm and scheduling". In Production Scheduling, P. Lopez and F. Roubellat Eds, WileyISTE, 2008.
R. T. F. Della Croce, M. Ghirardi, “Recovering Beam Search: en hancing the beam search approach for combinatorial optimization problems,” J. Heuristics, vol. 10, pp. 89–104, 2004.
R. Ruiz, C. Maroto, and J. Alcaraz, “Two newrobust genetic algorithms for the flowshop scheduling problem,” Omega, vol. 34, pp. 461–476, 2006.
F. Della Croce, M. Ghirardi, and R. Tadei, “Recovering Beam Search : Enhancing the Beam Search Approach for Combinatorial,” Journal of Heuristics, vol. 10, pp. 89–104, 2004.
C. C. Wu, W. C. Lee, and T. Chen, “Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations,” Computers & Industrial Engineering, vol. 52, pp. 124–132, 2007.
F. Glover, “Tabu Search  Part I,” ORSA Journal on Computing, vol. 1, pp. 190–206, 1989.
F. Glover, “Tabu Search  Part II,” ORSA Journal on Computing, vol. 2, pp. 4–32, 1990.
E. Vallada, R. Ruiz, and G. Minella, “Minimising total tardiness in the mmachine flowshop problem : A review and evaluation of heuristics and metaheuristics,” Computers & Operations Research, vol. 35, pp. 1350–1373, 2008.
C. N. Potts and L. N. Van Wassenhove, “A decomposition algorithm for the single machine total tardiness problem,” Operations Research Letters, vol. 1, pp. 177–181, 1982.
Refbacks
