In this paper, a variable-fidelity constrained lower confidence bound (VF-CLCB) criterion is presented for computationally expensive constrained optimization problems (COPs) with two levels of fidelity. In VF-CLCB, the hierarchical Kriging model is adopted to model the objective and inequality constraints. Two infill sampling functions are developed based on the objective and the constraints, respectively, and an adaptive selection strategy is set to select the elite sample points. Moreover, based on the VF-CLCB criterion, a parallel optimization method noted as PVF-CLCB is subsequently developed to accelerate the optimization process. In PVF-CLCB, a VF influence function is defined to approximately evaluate the estimation error of the hierarchical Kriging models, based on which multiple promising points can be determined at each iteration. In addition, an allocation strategy is proposed to distribute the computation resources between the objective- and constraint-oriented functions properly. Lastly, the proposed VF-CLCB and PVF-CLCB approaches are compared with the alternative methods on 12 benchmark numerical cases, and their significant superiority in solving computationally expensive COPs is verified. Furthermore, the proposed methods are employed to optimize the global stability of the stiffened cylindrical shell, and the optimum structure is yielded.