Academic
Publications
Scheduling Precedence Graphs in Systems with Interprocessor Communication Times

Scheduling Precedence Graphs in Systems with Interprocessor Communication Times,10.1137/0218016,Siam Journal on Computing,Jing-jang Hwang,Yuan-chieh C

Scheduling Precedence Graphs in Systems with Interprocessor Communication Times   (Citations: 290)
BibTex | RIS | RefWorks Download
Journal: Siam Journal on Computing - SIAMCOMP , vol. 18, no. 2, pp. 244-257, 1989
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...The scheduling algorithms typically address a particular task and processor model, e.g., arbitrary communication/computation execution cost [2], [3], conditional nodes [4], probabilistic execution cost [5], heterogeneous [6], and arbitrarily connected processor models [7]...

    Pravanjan Choudhuryet al. Online Scheduling of Dynamic Task Graphs with Communication and Conten...

    • ...ETF (Earliest Task First) [6] and CP/DT/MISF (Critical Path / Data Transfer / Most Immediate Successors First) [7] are proposed as the scheduling algorithms that consider the communication time between processors...

    Masahiko Utsunomiyaet al. Heuristic search based on branch and bound method for task scheduling ...

    • ...The ETF implementation is based on the description from [6]...

    Eryk Laskowskiet al. Extremal Optimization Applied to Task Scheduling of Distributed Java P...

    • ...Hwang et al. (1989) studied approximation list algorithms for scheduling problems where communication times depend on contention and a distance function on the involved tasks, as well as on the processors that execute the tasks...

    Rodolphe Giroudeauet al. Scheduling

    • ...In particular, the NP-hardness of MSP [22] has been a powerful driving force to develop efficient heuristic and/or approximating algorithms for solving the problem; e.g., Highest Level First with Estimated Times (HLFET) [12], Coffmann-Graham Algorithm [7], CP/MISF [15], Extended List Scheduling (ELS) [13], Mapping Heuristic (MH) [8], Modified Critical Path (MCP) scheduling [23], Dynamic Level Scheduling (DLS) [19], Mobility-Directed ...
    • ...Next, we consider the case in which each instance is with a uniform communication cost, where in the experiment, we fix the communication cost of each arc to either c ¼ 1 ,2 , or 3. ETF (earliest task first) [13], which is known as a typical list scheduling scheme to generate a quasi-optimal solution for those instances with communication costs [17], outputs a solution within one second...

    Satoshi Fujita. A Branch-and-Bound Algorithm for Solving the Multiprocessor Scheduling...

Sort by: