TABU SEARCH FOR MULTIPROCESSOR SCHEDULING: APPLICATION TO HIGH LEVEL SYNTHESIS

Marc Sevaux (), Alok Singh () and André Rossi ()
Additional contact information
Marc Sevaux: Université de Bretagne-Sud, UEB – Lab-STICC – CNRS, Centre de recherche, BP 92116, 56321 Lorient Cedex, France
Alok Singh: Department of Computer and Information Sciences, University of Hyderabad, Hyderabad - 500046, Andhra Pradesh, India
André Rossi: Université de Bretagne-Sud, UEB – Lab-STICC – CNRS, Centre de recherche, BP 92116, 56321 Lorient Cedex, France

Asia-Pacific Journal of Operational Research (APJOR), 2011, vol. 28, issue 02, 201-212

Abstract: This paper describes a tabu search approach for a multiprocessor scheduling problem, where a list of jobs has to be scheduled on identical parallel processors. Each job in the list has a release date, a due date, a processing time and a set of predecessors. The objective is to minimize the number of processors used while respecting the constraints imposed by release dates, due dates and precedences. Two versions of this problem are considered here, in the first one precedence constraints are relaxed, they are taken into account in the second one. The proposed method is used to solve High Level Synthesis problem instances. The results show the effectiveness of our approach for both versions of the problem. A comparison with an exact method is also conducted.

Keywords: Combinatorial optimization; multiprocessor scheduling; heuristics; tabu search; high level synthesis (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595911003132
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:wsi:apjorx:v:28:y:2011:i:02:n:s0217595911003132

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595911003132

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().