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.

This paper aims at improving effectiveness of previously proposed hybrid priority lists, {L*i=LdLsi}, that are applied in nonpreemptive 2-processor scheduling of general acyclic SWITCH-less program nets, where Ld and Lsi are dynamic and static priority lists respectively. Firstly, we investigate the effectiveness of Ld through experiments. According to the experimental results, we reconstruct Ld to propose its improved list L1d. Then analyzing the construction methodology of the static priority lists {Lsi}, we propose a substituted list L2d by taking into account of the factor: remaining firing numbers of nodes. Finally, we combine a part of L1d and L2d to propose a new priority list L**. Through scheduling simulation on 400 program nets, we find the new priority list L** can generate shorter schedules, close to ones of GA (Genetic Algorithm) scheduling that has been shown exceedingly effective but costing much computation time.

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 Ld and four static priority lists {Lsii=1,2,3,4}; and then combining Ld and Lsi (i=1,2,3,4) we propose four hybrid priority lists {L*ii=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.

This paper deals with two-processor scheduling for a class of program nets, that are acyclic and SWITCH-less, and of which each node has unity node firing time. Firstly, we introduce a hybrid priority list L* that generates optimal schedules for the nets whose AND-nodes possess at most single input edge. Then we extend L* to suit for general program nets to give a new priority list L**. Finally, we use genetic algorithm to do the performance evaluation for the schedules generated by L** and show these schedules are quite close to optimal ones.