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.
