Considering the uncertainty of cutting dynamics, the optimization of heavy-duty milling parameters was presented to obtain the maximum material removal rate under the constraints of cutting stability and machine tool working capacity. The three-dimensional dynamic model was set up according to the property of the face milling cutter in heavy-duty milling, in which the natural frequency, damping ratio, machine tool stiffness, and cutting force coefficients were regarded as the uncertain factors. The zero-excluding theory and edge theory were used to analyze the uncertainty of obtaining a robust cutting stability lobes diagraph. Then, the cutting tool that could achieve maximum cutting depth was selected according to the relation of cutting depth, tool diameter, and number of teeth. Finally, the optimal model of process parameters selection was set up, and the optimal parameters of axial cutting depth, radial cutting depth, and spindle speed were selected. The results were verified with rough machining for a cylinder surface on a CNC machining center.