A Heuristic Scheduling Algorithm for Reducing the Total Error of an Imprecise Multiprocessor System with 0/1 Constraint
Kihyun Song, Kyunghee Choi, Seung-Kyu Park, Dugkyoo Choi, Kyongok Yun · Journal of Electrical Engineering and Information Science · 1997
The scheduling problem of satisfying both 0/1 constraint and the timing constraint while minimizing the total error is NP-complete when the optional parts have arbitrary processing times. In this paper. we present a heuristic scheduling algorithm for 0/1 constraint imprecise systems which consist of communicating tasks running on multiple processors. The algorithm is based on the program graph which is similar to the one presented in[4]. To check the schedulability, we apply Lawler and Moore's theorem. To analyze the performance, of the proposed algorithm, intensive simulation is done. The results of the simulation shows that the longest processing first selection strategy outperforms random or minimal laxity policies.