This open-shop schedule has no restriction on the processing order of the jobs. The problem for minimizing the total tardy cost in an m-machine nonpreemptive open-shop is NP-hard. A network structure• based on the spanning tree is constructed in this work to simplify the mathematical model of a nonpreemptive open-shop problem whose objective is to minimize total tardy cost. The idle time rule developed in this work serves as the decision criterion to test the performance. The proposed Heuristic A is compared with SPT, EDD, SLACK, and MWSTR/EST (Minimum Weighted , Slack Time Remaining rule and Early ,Starting Time rule) methods using 7,200 cases, which are constructed by different features. Experimental results indicate that Heuristic A performs much better than the other four methods under the total tardy cost criterion and even better for complex problems. The results also reveal that the tardiness factor has significant influence on Heuristic A, and the due-date range has minor influence.