Abstract:
Hybrid flow-shop problems and problems with multiprocessor task systems have remained subject of intensive
research over several years. Hybrid flow-shop problems overcome one of the limitations of the classical flow-shop
model by allowing parallel processors at each stage of task processing. Problems with multiprocessor task systems relax
the limitation of the classical parallel processor model by permitting tasks that require more than one processor simultaneously.
The great deal of interest for both types of problem, besides their obvious theoretical significance, was
inspired by needs of various manufacturing and computing systems. In this paper we consider a model which amalgamates
both above-mentioned generalizations, We show that, without precedence constraints and under the assumption
that all processing times are bounded above, the makespan minimization problem is solvable in polynomial
time, whereas the introduction of precedence constraints makes even the simplest version of this problem NP-hard. For
the arbitrary processing time task systems, we present an approximation algorithm based on the idea of tabu search and
discuss the results of computational experiments, which were performed to analyze the algorithm's efficiency and
sensitivity to variation in the input data.
