TY - JOUR

T1 - Application of df/ihs to minimum total weighted flow time multiprocessor scheduling problems

AU - Kasahara, Hironori

AU - Kai, Munenori

AU - Narita, Seinosuke

AU - Wada, Hidehiko

PY - 1988/6

Y1 - 1988/6

N2 - In most cases, the scheduling problem for the multiprocessor system is NP‐ or strong NP‐hard. For this problem, we have already proposed a practical optimization algorithm DF/IHS (Depth First/Implicit Heuristic Search), which combines the list‐scheduling algorithm and the depth‐first search, for the minimum parallel processing time multiprocessors scheduling problem. This paper presents a result of application of DF/IHS to the minimum total weighted flow time problem, which is used in the optimization of memory utilization. The problem of allocating tasks to m processors is considered with or without precedence constraints among the tasks. It was verified that the DF/IHS can be applied to this kind of problem very effectively, where the optimal or highly accurate approximate solution is obtained for the large‐scale problem with several hundreds of tasks.

AB - In most cases, the scheduling problem for the multiprocessor system is NP‐ or strong NP‐hard. For this problem, we have already proposed a practical optimization algorithm DF/IHS (Depth First/Implicit Heuristic Search), which combines the list‐scheduling algorithm and the depth‐first search, for the minimum parallel processing time multiprocessors scheduling problem. This paper presents a result of application of DF/IHS to the minimum total weighted flow time problem, which is used in the optimization of memory utilization. The problem of allocating tasks to m processors is considered with or without precedence constraints among the tasks. It was verified that the DF/IHS can be applied to this kind of problem very effectively, where the optimal or highly accurate approximate solution is obtained for the large‐scale problem with several hundreds of tasks.

UR - http://www.scopus.com/inward/record.url?scp=0024030438&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024030438&partnerID=8YFLogxK

U2 - 10.1002/scj.4690190603

DO - 10.1002/scj.4690190603

M3 - Article

AN - SCOPUS:0024030438

SN - 0882-1666

VL - 19

SP - 25

EP - 34

JO - Systems and Computers in Japan

JF - Systems and Computers in Japan

IS - 6

ER -