Flexible Manufacturing Systems (FMS) have transfigured into a complex system because of its need to accommodate fluctuation in demands and fulfilling customers’ requirements with immediate effects. FMS scheduling problem is strongly non-deterministic polynomial-time (NP)-hard problem and is usually difficult to find its optimal solution. The performance of a scheduling system, in practice, is not evaluated to satisfy a single objective, but to obtain a trade-off schedule regarding multiple objectives. Therefore, in this research, we make use of one of the multiple objective decision-making methods, a global criterion approach, to develop a multi-objective model for solving FMS scheduling problems with consideration of three performance measures, namely minimizing mean job tardiness and mean job earliness and also mean machine idle time, simultaneously Due to the complexity of the multi-objective model, a Variable Neighbourhood Search (VNS) approach is developed for solving the addressed FMS scheduling problem. Moreover, Taguchi method is utilized to tune the parameters of the algorithm and analyze the parameters of the studying problem. The feasibility and adaptability of the proposed heuristic is investigated through a test problem in small and large sizes. Finally, the results clearly indicate the superior performance of the proposed VNS approach for the problem.