This study focuses on the flexible job shop scheduling problem with sequence-dependent setup times (FJSP-SDST), and the goal is minimizing the makespan. To solve FJSP-SDST, first, we develop a constraint programming (CP) model to obtain optimal solutions. Due to the NP-hardness of FJSP-SDST, a CP assisted meta-heuristic algorithm (C-VNS-CP) is designed to make use of the advantages of both CP model and cooperative variable neighborhood search (C-VNS). The C-VNS-CP algorithm consists of two stages. The first stage involves C-VNS, for which eight neighborhood structures are defined. In the second stage, CP is used to further optimize the good solution obtained from C-VNS. In order to prove the efficiency of the C-VNS algorithm, CP model, and C-VNS-CP algorithm, experiments of 20 instances are conducted.