Abstract: The problems of scheduling jobs with different ready time on parallel machines to minimize the total completion time are addressed. A new iterated local search (ILS) is proposed based on a new neighborhood structure named variable-depth cycle exchange. First, we define the variable-depth cycle exchange neighborhood structure. Based on the variable-depth cycle exchange neighborhood and the traditional Swap neighborhood, a new ILS algorithm with two kick strategies is then proposed. Scatter search (SS) is embedded into ILS to enhance its power of getting away from the local optima, in which the algorithm continues work after combining the best and the second best solutions found so far. Computational experiments on 10 problems with up to 50 jobs and 20 machines for unrelated parallel machines and identical machines respectively are carried out to test the performance of the algorithm. For the identical parallel-machine scheduling problem, the average deviation of the ILS with SS to the lower bound obtained by Lagrangian Relaxation is 0.99%, but 1.06% for the ILS without SS. For the unrelated parallel-machine scheduling problem, the average performance of the ILS with SS make an improvement 6.06% over that of the ILS without SS, and also is better than that of multi-start descent algorithm.