Due to the interrelationship between statistical process control (SPC) and equipment maintenance, a great deal of attention has been paid to the joint optimization of them. However, most of the existing models are developed based on the assumption of constant maintenance time. This assumption is appropriate in some situations but may be too restrictive in other situations. Intuitively, the maintenance time is influenced by various factors in reality, such as experience of maintenance workers and failure severity. Therefore, it is more flexible to assume random maintenance time but not constant maintenance time. Motived by this, this paper develops the graphical evaluation and review technique (GERT) based on the semi-Markovian principle for the proposed problem. By using the GERT network model, both the expected preventive maintenance cycle and the expected cycle cost can be predicted. A solution procedure is proposed to get near optimal solutions of the resulting nonlinear programming problem. A numerical example is provided to illustrate the whole procedure. The results indicate the potential cost reduction of the proposed method.