Abstract | ||
---|---|---|
The emergence of multicore processors makes multicore task scheduling a focus of researchers. Since the multicore task scheduling problem is NP-hard, in most cases only approximate algorithms can be adopted to resolve it. This paper provides a detail analysis of the four aspects of applying variable neighborhood search algorithm (VNSA) to the multicore task scheduling problem. We further give a solution: (1) we propose a general solution model named task assignment matrix (TAM) (2) and define relevant element swap operations between the TAM instances; (3) then we present a construction method of the neighborhood and the neighborhood set; (4) finally we introduce a local search strategy for the neighborhood set. We have proved the effectiveness of this scheme through experiments. The results show that the scheduled tasks with different communication to computation ratio have a 1.079-4.258 times performance improvement. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-642-41635-4_13 | Communications in Computer and Information Science |
Keywords | Field | DocType |
VNSA,multicore processor,task scheduling | Job shop scheduling,Fair-share scheduling,Variable neighborhood search,Computer science,Scheduling (computing),Parallel computing,Algorithm,Local search (optimization),Dynamic priority scheduling,Multi-core processor,Performance improvement | Conference |
Volume | ISSN | Citations |
396 | 1865-0929 | 0 |
PageRank | References | Authors |
0.34 | 8 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
chang wang | 1 | 33 | 12.55 |
Jiang Jiang | 2 | 50 | 5.43 |
xianbin xu | 3 | 0 | 0.34 |
xing han | 4 | 1 | 0.83 |
Qiang Cao | 5 | 593 | 57.50 |