An approach based on simulated annealing algorithm and heuristic method is presented as an efficient means of scheduling the manufacturing operations of virtual cellular manufacturing systems in the automotive industry. The objectives are to minimise the total weighted tardiness of the production schedule and to minimise the total materials travelling distance. A two-stage approach is employed for scheduling the manufacturing operations. In the first stage, the simulated annealing algorithm is applied to get the optimal schedule. In the second stage, a heuristic approach that was presented by Mak et al. (2007) is employed with some adjustments to minimise the total materials travelling distance. Examples are introduced to evaluate the performance of the present approach and to illustrate how the approach is employed to tackle scheduling problems. The results show that the approach is quite successful and can be used for scheduling the virtual manufacturing cells for the production of parts in case of frequently changing demands.