Tuning parameters to improve a heuristic method: more and better solutions to an NP-hard real-time problem

Author

Ferro, E. ; Santos, J. ; Orozce, J. ; Cayssials, R.

Author_Institution

Inst. de Ciencias e Ingenieria de Computacion, Univ. Nacional del Sur, Bahia Blanca, Argentina

fYear

1996

fDate

12-14 Jun 1996

Firstpage

47

Lastpage

51

Abstract

The paper presents a tuned heuristic method to solve the NP-hard problem of assigning a set of preemptible tasks with placement, resource, communication, time and precedence constraints to a set of heterogeneous processors. Depending on the tuning parameters, two versions are described. They produce more and better (e.g. with a less loaded communication network) solutions than the untuned version. Time to obtain the first solution and the number of solutions found for different known problems are given

Keywords

computational complexity; formal specification; heuristic programming; processor scheduling; real-time systems; NP-hard real-time problem; heterogeneous processors; heuristic method; preemptible tasks; tuned heuristic method; tuning parameters; Assembly; Communication networks; Delay effects; Fault tolerance; Local area networks; Multiprocessing systems; NP-hard problem; Round robin; Testing; Time factors;

fLanguage

English

Publisher

ieee

Conference_Titel

Real-Time Systems, 1996., Proceedings of the Eighth Euromicro Workshop on

Conference_Location

L´Aquila

ISSN

1068-3070

Print_ISBN

0-8186-7496-2

Type

conf

DOI

10.1109/EMWRTS.1996.557788

Filename

557788