The CPM (Critical Path Method) is a network-based approach for project management. This method identifies the longest path, which allows us to find the critical path that must be shortened so that the completion time of the whole project can be shortened. However, considering uncertainty in CPM is not straightforward. In this paper, we consider an optimization problem for stochastic CPM problems, where task durations are expressed as discrete histograms obtained from historical operation data, that maximizes the probability that all tasks are completed within a given completion time by improving the task durations on the critical path. We propose two reformulations of the problem as a mixed-integer linear programming problem: one based on tasks, and the other based on paths. In addition, we propose an iterative method to solve the problem efficiently by reducing the number of binary variables. Finally, we demonstrate efficiency of our proposed methods in some case studies. (C) 2019 Institution of Chemical Engineers. Published by Elsevier B.V. All rights reserved.