This paper proposes an effective hybrid discrete differential evolution (DDE) algorithm for solving a scheduling problem of flexible manufacturing systems (FMSs), where sequence-dependent setup times are considered. The objective is to find a deadlock-free schedule that minimizes the makespan. Based on the timed Petri net models of FMSs, a possible solution of the scheduling problem is represented as an individual that is a permutation with repetition of jobs. For the existence of deadlocks, most of the individuals cannot be directly decoded into feasible (live) schedules. Therefore, a deadlock controller is applied in the decoding scheme, and infeasible individuals are amended into feasible ones. Moreover, in order to overcome the premature convergence of DDE algorithm and improve solution quality, a variable neighbourhood search algorithm, which performs a systematic change of neighbourhood in solution searching, is adopted. Then a hybrid scheduling algorithm that combines a DDE with a variable neighbourhood search is presented. Computational results and comparison based on a variety of instances show the feasibility and superiority of the proposed algorithm.