The paper is concerned with scheduling problems with multiprocessor tasks and presets conditions under which such problems can be solved inpolynomial time. The application of these conditions is illutrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem witha UET task system, two parallel processors, the criterion of total completion time, and precednece constraints in the form of out-trees
Oguz, C, Zinder, Y, Do, V, Janiak, A & Lichtenstein, M 2004, 'Hybrid flow-shop scheduling problems with multiprocessor task systems', European Journal of Operational Research, vol. 152, pp. 115-131.View/Download from: Publisher's site
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 algorithms efficiency and sensitivity to variation in the input data.
Zinder, Y & Do, V 2005, 'Scheduling UET tasks on two parallel machines with the criteria of makespan and total completion time' in Kendall, G, Burke, E, Petrocic, S & Gendreau, M (eds), Multidisciplinary Scheduling: Theory and applications, Springer, USA, pp. 83-109.
Two extensions of the classical scheduling model with two parallel identical machines and a partially ordered set of unit execution time tasks are considered. It is well known that the Coffman-Graham algorithm constructs for this model a so-called ideal schedule: that is, a schedule which is optimal for both makespan and total completion time criteria simultaneously. The question of the existence of such a schedule for the extension of this model, where each task has a release time, has remained open over seneral decades. The paper gives a positive answer to this question and presents the corresponding polynormal-time algorithm.Another straightforward generalisation of the considered classcial model is obtained by the introduction of multiprocessor tasks. It is shown that, despite the fact tha a slightly modified Coffman-Graham algorithm solves the makespan problem with multiprocessor tasks for arbirtary precedence constraints, generally an ideal schedule does not exist and the problem with the criterion of total completion time turns out to be NP-hard ithe strong sense even for in-trees.