Integrated Flow Shop and Vehicle Routing Problem Based on Tabu Search Algorithm

Authors

  • Quang Chieu Ta Department of Artificial Intelligence, Thuyloi University, 175 Tay Son, Dong Da, Hanoi. Vietnam
  • Phuong Mai Pham Department of Artificial Intelligence, Thuyloi University, 175 Tay Son, Dong Da, Hanoi. Vietnam

Keywords:

flow shop problem, vehicle routing problem, metaheuristic algorithm, Tabu search

Abstract

We consider in this paper a m-machine permutation flow shop scheduling problem and vehicle routing problem (VRP) integrated [1]. The manufacturing workshop is a flow shop and there is only one vehicle available. We are interested in the minimization of the total tardiness. related to the delivery completion times. Therefore, we are faced to three interdependent problems: scheduling the jobs in the flow shop environment, batching the completed jobs, and routing the batches. Then, we present the resolution method based on Tabu search and the results that have been obtained. Computational experiments are performed on random data sets and show the efficiency of the methods. Finally, a conclusion and some future research directions are proposed.

References

[1] Q. C. Ta, J. C. Billaut, J. L. Bouquard and P-E. Morin. “Minimisation de la somme des retards pour un problème d’ordonnancement de type flow-shop à deux machines et un problème de livraison intégrés.” 15ème congrès de la Société de la Société Française de Recherche Opérationnelle et d'Aide à la Décision Roadef’, 2014. Bordeaux, France.
[2] J. K. Lenstra and A. H. G. Rinnooy Kan. “Complexity of vehicle routing and scheduling problems”. Networks, vol 11, pp. 221-227, 1981.
[3] Q. C. Ta, J. C. Billaut and J. L. Bouquard. “An hybrid metaheuristic. a hybrid lower bound and a tabu search for the two-machine flowshop total tardiness problem.” Proceedings of the 10th IEEE RIVF International Conference on Computing and Communication Technologies (RIVF’13), 2013, Hanoi, Vietnam.
[4] Q. C. Ta, J. C. Billaut and J. L. Bouquard. “Minimizing total tardiness in the m-machine flow-shop by genetic and matheuristic algorithms”. Journal of Intelligent Manufacturing, vol 29, pp. 617- 628, 2015.
[5] 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.

Downloads

Published

2022-04-25

How to Cite

Ta, Q. C., & Phuong Mai Pham. (2022). Integrated Flow Shop and Vehicle Routing Problem Based on Tabu Search Algorithm. International Journal of Computer (IJC), 43(1), 24–35. Retrieved from https://ijcjournal.org/index.php/InternationalJournalOfComputer/article/view/1927

Issue

Vol. 43 No. 1 (2022)

Section

Articles

License

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