For a process with parallel production lines, a scheduling algorithm possessing the function of allocating each job to a desirable production line is proposed. The proposed algorithm is based on the repetitive simulated annealing (SA) method, in which the scheduling is executed several times for a problem, and the best schedule is selected in the final stage of repetition. In the proposed algorithm, the feature of the repetitive SA method described above is successfully incorporated. First, desirable production lines for treating each job are derived from the scheduling results obtained through several rounds of scheduling. Then, scheduling of the remaining rounds is executed under the condition that the probabilities of allocating a job to desirable production lines are higher than those to the other lines. The proposed algorithm is applied to the scheduling problem of a heat treatment process consisting, of nine production lines. The effectiveness of the proposed algorithm is demonstrated through a comparison between scheduling results obtained with the proposed method and those obtained with the conventional repetitive SA method.