  This paper focuses on the identical parallel machine scheduling problem with
sequence-dependent setup time, with special attention paid to the uncertainty
of processing time. In this paper, a mathematical model of the parallel machine
scheduling problem with stochastic processing time is constructed. Then a
branch and bound (B&B) algorithm is proposed, and three methods for generating
upper bounds and one heuristic for generating lower bound are developed to
evaluate the performance of the B&B. In addition, a new branch scheme and two
dominance rules are also devised to further improve the efficiency of the
algorithm. In the numerical experiment analysis, the performance of the new
branch scheme, the upper and lower bounds, and the dominance rule are tested,
and the robustness of the stochastic parallel machine scheduling problem is
verified by compared it with the deterministic version .
