This work proposes a parallel memetic algorithm applied to the total tardiness single machine scheduling problem. Classical models of parallel evolutionary algorithms and the general structure of memetic algorithms are discussed. The classical model of global parallel genetic algorithm was used to model the global parallel memetic analogue where the parallelization is only applied to the individual optimization phase of the algorithm. Computational tests show the efficiency of the parallel approach when compared to the sequential version. A set of eight instances, with sizes ranging from 56 up to 323 jobs and with known optimal solutions, is used for the comparisons. © 2006 IEEE.2006 Buriol, L., França, P., Moscato, P., A new memetic algorithm for the asymmetric traveling salesman problem (2004) Journal of Heuristics, 10 (5), pp. 483-506Cantú-Paz, E., Designing efficient master-slave parallel genetic algorithms (1997), Technical Report 97004, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-ChampaignCantú-Paz, E., A survey of parallel genetic algorithms (1997), Technical Report 97003, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-ChampaignCantú-Paz, E., Goldberg, D., Efficient parallel genetic algorithms: Theory and practice (2000) Computer methods in applied mechanics and enginneering, 186, pp. 221-238Du, J., Leung, J., Minimizing total tardiness on one machine is NP-hard (1990) Mathematics of Operations Research, 15, pp. 483-495França, P., Gupta, J., Mendes, A., Moscato, P., Veltink, K., Metaheuristic approaches for the pure flowshop manufacturing cell problem (2005) Computers & Industrial Engineering, 48 (3), pp. 491-506França, P., Mendes, A., Moscato, P., A memetic algorithm for the total tardiness single machine scheduling problem (2000) European Journal of Operational Research, 132 -1, pp. 224-242Gorges-Schleuter, M., Asparagos: An asynchronous parallel genetic optimization strategy (1989) Third International Conference of Genetic Algorithms, p. 422Graham, R., Lawler, E., Lenstra, J., Rinooy Kan, A., Optimization and approximation in deterministic sequencing and scheduling: A survey (1979) Annals of Discrete Mathematics, 5, pp. 287-326Graves, S., A review of production scheduling (1981) Operations Research, 29, pp. 646-675Lee, Y., Bhaskaran, K., Pinedo, M., A heuristic to minimize the total weighted tardiness with sequence-dependent setups (1997) IIE Transactions, 29, pp. 45-52Mendes, A., França, P., Moscato, P., Fitness landscape for the total tardiness single machine scheduling problem (2002) Neural Network World, 2 (2), pp. 165-180Mendes, A., Müller, F., França, P., Moscato, P., Comparing meta-heuristic approaches for parallel machine scheduling problems with sequence-dependent setup times (2002) Production Planning & Control, 13 (2), pp. 143-154Moscato, P., On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms (1989), Technical Report C3P 826, Caltech Concurrent Computation ProgramRaman, N., Rachamadugu, R., Talbot, F., Real time scheduling of an automated manufacturing center (1989) European Journal of Operations Research, 40, pp. 222-242Rubin, P., Ragatz, G., Scheduling in sequence dependent setup enviroment with genetic search (1995) Computers and Operations Research, 22 -1, pp. 85-99Tan, K., Narasimhan, R., Minimizing tardiness on a single processor with a sequence-dependent setup times: A simulated annealing approach (1997) OMEGA - International Journal of Management Science, 25 -6, pp. 619-634