# Minimizing Total Tardiness in the m-Machine Flow-Shop Problem by Heuristic Algorithms

### Abstract

In this work the m-machine permutation flow-shop problem has been considered. The permutation flow-shop 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 flow-shop 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.### References

M. L. Pinedo, Scheduling: Theory, algorithms, and systems. Springer 2008.

J. Du and J. Y. T. Leung, “Minimizing total tardiness on one machine is NP-hard,” 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 two-machine flowshops,” Computers & Operations Research, vol. 20(4), pp. 391–401, 1993.

J. C.-H. Pan and E.-T. Fan, “Two-machine 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 two-machine 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 two-machine flow-shop,” Computers & Operations Research, vol. 29, pp. 869–885, 2002.

M. Nawaz, E. Enscore, and I. Ham, “A heuristic algorithm for the m-machine n-job flow shop sequencing problem,” Omega, vol. 11, pp. 91–95, 1983.

C. Koulamas, “A guaranteed accuracy shifting bottleneck algorithm for the two-machine flowshop total tardiness problem,” Computers & Operations Research, vol. 25, pp. 83–89, 1998.

I. Osman and C. Potts, “Simulated annealing for permutation flow-shop 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. Ben-Daya and M. Al-Fawzan, “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 multi-trip 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 flow-shop scheduling,” Production Planning and Control, vol. 10, pp. 462–471, 1999.

C.-J. Liao, Chao-Tang 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 two-machines 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 m-machine 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. Fernandez-Viagas and J. M. Framinan, “NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness,” Computers & Operations Research, vol. 60, pp. 27-36, 2015.

V. Fernandez-Viagas, R. Ruiz, and J. M. Framinan, “A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation,” European Journal of Operational Research. vol. 257, pp. 707-721, 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. Addison-Welsey, Reading Mass, 1989.

M. C. Portmann and A. Vignier. "Chapter 4: Genetic algorithm and scheduling". In Production Scheduling, P. Lopez and F. Roubellat Eds, Wiley-ISTE, 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 m-machine 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.

Authors who submit papers with this journal agree to the following terms:

- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
- By submitting the processing fee, it is understood that the author has agreed to our terms and conditions which may change from time to time without any notice.
- It should be clear for authors that the Editor In Chief is responsible for the final decision about the submitted papers; have the right to accept\reject any paper. The Editor In Chief will choose any option from the following to review the submitted papers:A. send the paper to two reviewers, if the results were negative by one reviewer and positive by the other one; then the editor may send the paper for third reviewer or he take immediately the final decision by accepting\rejecting the paper. The Editor In Chief will ask the selected reviewers to present the results within 7 working days, if they were unable to complete the review within the agreed period then the editor have the right to resend the papers for new reviewers using the same procedure. If the Editor In Chief was not able to find suitable reviewers for certain papers then he have the right to accept\reject the paper.B. sends the paper to a selected editorial board member(s). C. the Editor In Chief himself evaluates the paper.
- Author will take the responsibility what so ever if any copyright infringement or any other violation of any law is done by publishing the research work by the author
- Before publishing, author must check whether this journal is accepted by his employer, or any authority he intends to submit his research work. we will not be responsible in this matter.
- If at any time, due to any legal reason, if the journal stops accepting manuscripts or could not publish already accepted manuscripts, we will have the right to cancel all or any one of the manuscripts without any compensation or returning back any kind of processing cost.
- The cost covered in the publication fees is only for online publication of a single manuscript.