This paper presents a genetic algorithm (GA) based on heuristic rules for high-constrained large-size single-stage multi-product scheduling problem (SMSP) with parallel units. SMSP has been widely studied, very often solved by using mixed-integer linear programming (MILP methods). When the problem size increases linearly, the computational time of MILP will increase exponentially. Therefore, it is very difficult for MILP to obtain acceptable solutions to the large-size problems within reasonable time. To solve the large-size scheduling problems, the preferred method in industry is the use of scheduling rules. However, due to the constraints in SMSP, the simple rule-based method may not guarantee the feasibility and quality of the solutions. In this study, random search based on heuristic rules is proposed first. Through exploring a set of random solutions, better feasible solutions are obtained. To improve the quality of solutions, GA based on heuristic rules is then proposed to evolve the random solutions. The heuristic rules play a very important role in the algorithm. However, the computational time of the GA increases dramatically due to some constraints that may create infeasibility. To overcome this, a penalty method is adopted. Through comparison of computational results of MILP, random search and GA, GA has demonstrated its effectiveness and reliability in solving the highly constrained large-size scheduling problems. (c) 2007 Elsevier B.V. All rights reserved.