Bloki w problemie przepływowym z minimalizacją sumy kosztów opóźnień

Abstract

Blocks are applied in the best metaheuristic algorithms of solving flow shop problem with the makespan ($C_{max}$) criterion. It makes possible to eliminate moves which generates worse elements of a neighborhood. In this paper we present generalization of the classic block formulation, which we are applying in the tabu search algorithm to solving total tardiness flow shop problem $(F||\Sigma w_{i}T_{i})$. W najlepszych algorytmach metaheurystycznych rozwiązywania problemu przepływowego z kryterium $C_{max}$ są stosowane bloki z drogi krytycznej. Pozwalają one na eliminację ruchów generujących »gorsze« elementy otoczenia. W pracy przedstawiamy uogólnienie klasycznego bloku, które stosujemy w algorytmie poszukiwania z zabronieniami dla problemu przepływowego z minimalizacją sum kosztów opóźnień $(F||\Sigma w_{i}T_{i})$.