Two-Processor Scheduling of General Acyclic SWITCH-less Program Nets via Hybrid Priority Lists (Special Section of Selected Papers from the 12th Workshop on Circuit and Systems in Karuizawa)

概要

論文の詳細を見る
This paper deals with two-processor scheduling for general acyclic SWITCH-less program nets with random node firing times. First, we introduce a hybrid priority list L^* that has been shown to generate optimal schedules for the acyclic SWITCH-less program nets with unity node firing times, of which AND-nodes possess at most single input edge. Then considering the factors of existence of the AND-nodes with two input edges as well as random node firing times, we extend L^* to design a new dynamic priority list L_d and four static priority lists {L_<si>|i=1, 2, 3, 4}; and then combining L_d and L_<si>(i=1, 2, 3, 4) we propose four hybrid priority lists {L^*_i|i=1, 2, 3, 4}. Finally, we apply genetic algorithm to evaluate the schedules generated by the four lists through simulations on 400 program nets. Our simulation results show two of the four lists can generate reasonably good schedules.
社団法人電子情報通信学会の論文
2000-03-25