The steelmaking process consists of two phases: primary steelmaking and finishing lines. The scheduling of the continuous galvanizing lines (CGL) is regarded as the most difficult process among the finishing lines due to its multi-objective and highly-constrained nature. In this paper, we present a multi-population parallel genetic algorithm (MPGA) with a new genetic representation called k(th) nearest neighbor representation, and with a new communication operator for performing better communication between subpopulations in the scheduling of CGL. The developed MPGA consists of two phases. Phase one generates schedules from a primary work in process (WIP) inventory filtered according to the production campaign, campaign tonnage, priorities of planning department, and the due date information of each steel coil. If the final schedule includes the violations of some constraints, phase two repairs these violations by using a secondary WIP inventory of steel coils. The developed scheduling system is currently being used in a steel making company with encouraging preliminary results.