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

Abstract

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 meta$^2$heuristics. We carry out computational experiment using 128-processors Graphics Processing Unit (GPU). 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 - meta$^2$heurystykę. Algorytm równoległy testowany jest na 128-procesorowej karcie GPU.