Title: Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors

Authors: Adel Manaa, Chengbin Chu

Addresses: OSI, Institute Charles Delaunay, University of Technology of Troyes, 12 rue Marie Curie, B.P. 2060, Troyes 10010, France. ' Laboratoire Genie Industriel, Ecole Centrale Paris, Grande Voie des Vignes, 92295, Chatenay-Malabry Cedex, France

Abstract: In this paper, we consider the problem of scheduling tasks on two dedicated processors where some tasks need to be processed only by the first processor and some others by the second processor; the remaining tasks, however, need both processors simultaneously. Tasks have release dates and have to be scheduled without preemption. The objective is to minimise its makespan. For this problem, which is known to be NP-hard in the strong sense, we propose a lower bound based on processor relaxation and show that it is equal to the optimal solution for a preemptive case. We propose two heuristics with a worst-case analysis and its generalisation to any semi-active schedule. A set of dominance properties are established and a branch-and-bound algorithm is developed and tested on a set of randomly generated instances. [Received 29 September 2008; Revised 01 March 2009; Accepted 13 April 2009]

Keywords: multiprocessor scheduling; branch-and-bound; dedicated processors; makespan; task scheduling.

DOI: 10.1504/EJIE.2010.033331

European Journal of Industrial Engineering, 2010 Vol.4 No.3, pp.265 - 279

Published online: 01 Jun 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article