The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] combined OR-node(1hit)

1-1hit
  • An Optimal Two-Processor Scheduling for a Class of SWITCH-less Program Nets with Combined OR-nodes

    Qi-Wei GE  

     
    PAPER

      Vol:
    E85-A No:6
      Page(s):
    1274-1280

    This paper deals with two-processor nonpreemptive scheduling problem for acyclic SWITCH-less program nets including two types of nodes: AND-node and OR-node. Compared with task graphs that are a special case of acyclic SWITCH-less program nets and include only AND-nodes, the multiprocessor scheduling problem of general acyclic SWITCH-less program nets is more complicated. Since multiprocessor scheduling problem for general task graphs is NP-hard, so is for acyclic SWITCH-less program nets generally. In this paper, we suppose the acyclic SWITCH-less program nets satisfy: (i) each AND-node and OR-node have 1 and 0 node firing time, respectively; (ii) each AND-node possesses single input edge. For such a class of acyclic SWITCH-less program nets, we first propose a hybrid priority list L that consists of both dynamic and static sub-lists. Then we prove that, for a given acyclic SWITCH-less program net to be executed by two identical processors, the schedule generated by L is optimal.