In this paper, we study a stochastic parallel machine scheduling problem denoted as \(Pm|r_j, p_j \thicksim stoch|\sum w_j E(C_j)\) , where the processing time of each job follows a general discrete distribution. To address this problem, we develop an exact solution approach by extending the set partitioning model. Unlike its deterministic counterpart, the computation of the expected completion time \(E(C_j)\) in this stochastic setting is highly complex and nonlinear, rendering traditional solution methods inapplicable. To overcome this challenge, we propose a branch-and-price algorithm to solve the problem efficiently. Specifically, we introduce a series of approximations for \(E(C_j)\) that can be computed significantly faster than the exact value. These approximations are employed to identify promising job sequences and to prune less profitable ones in the pricing subproblem of the column generation procedure. Computational experiments demonstrate that the proposed algorithm can solve large-scale instances of the stochastic parallel machine scheduling problem within a reasonable time. Furthermore, we show that our proposed method can be easily adapted to related problems such as \(Pm|r_j, d_j, p_j \thicksim stoch|\sum w_j E(T_j)\) and \(Pm|r_j, d_j, p_j \thicksim stoch|\sum w_j E(U_j)\) .
