Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors

Adel Manaa and Chengbin Chu

European Journal of Industrial Engineering, 2010, vol. 4, issue 3, 265-279

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. (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.inderscience.com/link.php?id=33331 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:4:y:2010:i:3:p:265-279

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().