Multiprocessor (parallel machine) flow shop scheduling problem with makespan criterion: a tabu search approach

Abstract

Effective schcduling iu manufactnring systems leads to reduction in manufacturing costs (inventory costs, labor costs etc.) and improves operational efficieucy of the management. The multiprocessor flow shop scheduling problem with makespan criterion is relatively simply formulated, but it is unfortunately a hard combinatorial problem, typically leads to NP-hardness. For this reason many heuristic algorithms have been proposed and tested to solve the problem in a short time. This research aimed at customizing a fast Tabu Search (TS) algorithm for multiprocessor flow shop scheduling problem with makcspan criterion, origmally proposed by Grabowski and Wodecki (2004, 2005) for permutation flow shop and job shop scheduling problems based on the ncw block properties. The blocks of jobs have built-in elimination properties during the search of the solUllon space which facilitates in keeping the nelghborhood size at moderate level. In order to decrease the computational effort for the search in TS, calculation of the lo\,er bounds has been presented on the makespans lllstead of computing makespans eXplicitlyfor use in selecting jhe best solution. Also, a tabu list with dynamic length has been presented which changes cyclically as the current iteration number of IS increases, using a ''pick'' in order to carry the search to another area of tile solution space. Finally, some penurbations associated with block properties arc periodically applied. A computer program has been coded and the perfonnance of the developed algoritlun has been analyzed by running it for different iterations using the data of RahimAfrooz Batteries Ltd (RBL). RBL is a well-respected business house in Bangladesh and one of the largest lead-acid battery manufactUrers in the SAARC rcgion, which produces almost all kinds of automotive and industrial batteries.