Równoległa meta2heurystyka dla problemu gniazdowego z równoległymi maszynami

• Autorzy: Bożejko W. , Uchroński M. , Wodecki M.

Warianty tytułu

EN

Parallel meta2heuristics for the flexible job shop problem

• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrywany jest ogólny problem kolejnościowy z równoległymi maszynami (flexible job shop problem), w którym dany jest zbiór zadań oraz zbiór maszyn. Maszyny tego samego typu (rodzaju), tj. o tych samych własnościach funkcjonalnych (które jednak mogą mieć różne parametry techniczne, takie jak na przykład wydajność) tworzą gniazdo. Do rozwiązania problemu proponujemy podejście dwupoziomowe - meta2heurystykę. Algorytm równoległy testowany jest na 128-procesorowej karcie GPU.

EN

We consider a double-level metaheuristic optimization algorithm in this paper. The algorithm proposed here includes two major modules: the machine selection module, which is executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, so we call this method meta2heuristics. We carry out computational experiment using 128-processors Graphics Processing Unit (GPU).

Słowa kluczowe

PL

problem gniazdowy; algorytm równoległy; GPU

EN

job shop problem; parallel algorithm; GPU

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2009
• Tom: T. 13, z. 2
• Strony: 207--213
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Bożejko W.

• Instytut Informatyki, Automatyki i Robotyki, Politechnika Wrocławska

autor

Uchroński M.

• Instytut Informatyki, Automatyki i Robotyki, Politechnika Wrocławska

autor

Wodecki M.

• Instytut Informatyki, Uniwersytet Wrocławski

Bibliografia

• [1] Adrabiński A., Wodecki M., An algorithm for solving the machine sequencing problem with parallel machines. Zastosowania Matematyki, XVI, 3, 1979, 513-541.
• [2] Alba E., Parallel Metaheuristics. A New Class of Algorithms. Wiley & Sons Inc., 2005.
• [3] Brandimarte P., Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41, 1993, 157-183.
• [4] Dauzcre-Percs S., Pauli J., An integrated approach for modeling and solving the general multiprocessor job shop scheduling problem using tabu search. Annals of Operations Research, 70, 3, 1997, 281-306.
• [5] Gao J., Sun L., Gen M., A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, 35, 2008, 2892-2907.
• [6] Ho N.B., Тау J.C., GENACE: an efficient cultural algorithm for solving the Flexible Job-Shop Problem. IEEE International Conference on Robotics and Automation, 2004, 1759-1766.
• [7] Hurink E., Jurisch В., Thole M., Tabu search for the job shop scheduling problem with multipurpose machine. Operations Research Spektrum, 15, 1994, 205-215.
• [8] Jia H.Z., Nee A.Y.C., Fuh J.Y.H., Zhang Y.F., A modified genetic algorithm for distributed scheduling problems. International Journal of Intelligent Manufacturing, 14, 2003, 351-362.
• [9] Kacem I., Hammadi S., Borne P., Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part С 32(1), 2002, 1-13.
• [10] Mastrolilli M., Gambardella L.M., Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling, 3(1), 2000, 3-20.
• [11] Nowicki E., Smutnicki C, A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 91, 1996, 160-175.
• [12] Pauli J., A hierarchical approach for the FMS scheduling problem. European Journal of Operational Research, 86(1), 1995, 32-42.
• [13] Pezzella F., Morganti G., Ciaschetti G., A genetic algorithm for the Flexible Jobschop Scheduling Problem. Computers & Operations Research 35, 2008, 3202-3212.
• [14] Pinedo M., Scheduling: theory, algorithms and systems. Englewood Cliffs, NJ: Prentice-Hall, 2002.