Flexible job shop problem - parallel tabu search algorithm for multi-GPU

• Autorzy: Bożejko W. , Uchroński M. , Wodecki M.
• Języki publikacji: EN

Abstrakty

EN

In the paper we propose a new framework for the distributed tabu search algorithm designed to be executed with the use of a multi-GPU cluster, in which cluster of nodes are equipped with multicore GPU computing units. The proposed methodology is designed specially to solve difficult discrete optimization problems, such as a flexible job shop scheduling problem, which we introduce as a case study used to analyze the efficiency of the designed synchronous algorithm.

Słowa kluczowe

EN

jobs scheduling; flexible manufacturing; parallel algorithm; discrete optimization

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2012
• Tom: Vol. 22, no. 4
• Strony: 389--397
• Opis fizyczny: Bibliogr. 10 poz., rys., tab., wzory

Twórcy

autor

Bożejko W.

autor

Uchroński M.

autor

Wodecki M.

• Institute of Computer Engineering, Control and Robotics, Wroclaw University of Technology, Poland

Bibliografia

• [1] E. Alba: Parallel Metaheuristics. A New Class of Algorithms.Wiley & Sons Inc., 2005.
• [2] W. Bożejko A new class of parallel scheduling algorithms. Wrocław University of Technology Publishing House, 2010.
• [3] P. Brandimarte: Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41 (1993), 157-183.
• [4] S. Dauzère-Pérès and J. Pauli: An integrated approach for modeling and solving the general multiprocessor job shop scheduling problem using tabu search. Annalsof Operations Research, 70(3), (1997), 281-306.
• [5] M. J. Flynn: Very highspeed computing systems. Proceedings of the IEEE, 54 (1966), 1901-1909.
• [6] J. Gao, L. Sun and M. Gen: A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, 35 (2008), 2892-2907.
• [7] M. Mastrolilli and L.M. Gambardella: Effective neighborhood functions for the flexible job shop problem. J. of Scheduling, 3(1), (2000), 3-20.
• [8] E. Nowicki and C. Smutnicki: An advanced tabu search algorithm for the job shop problem. J. of Scheduling, 8(2) (2005), 145-159.
• [9] M. Pinedo: Scheduling: theory, algorithms and systems, Englewood Cliffs, NJ, Prentice-Hall, 2002.
• [10] S. Voß: Tabu search: Applications and prospects. In: D.Z. Du and P.M. Pardalos (Eds.), Network Optimization Problems, World Scientific Publishing Co., Singapore 1993, 333-353.