Heuristic search is a core area of Artificial Intelligence and the employment of an efficient search algorithm is critical to the performance of an intelligent system. This paper addresses a production scheduling problem with complex precedence constraints in an identical parallel machines environment. Although, this particular problem can be found to several production and other scheduling applications; it is considered to be NP-hard due to its high computational complexity. The solution approach we adapt is based on a comparison among several dispatching rules combined with a diagram analysis methodology. Computational results on large instances provide relatively high quality practical solutions in very short computational times, indicating the applicability of the methodology in real life production scheduling applications. http://www.informatik.uni-trier.de/~ley/db/journals/cai/cai24.html