Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors Online publication date: Tue, 01-Jun-2010
by Adel Manaa, Chengbin Chu
European J. of Industrial Engineering (EJIE), Vol. 4, No. 3, 2010
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]
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the European J. of Industrial Engineering (EJIE):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com