An Adaptive Genetic Algorithm for the single-machine sequencing problem with early/tardy penalties
Abstract
This paper treats the total tardiness single machine scheduling problem with earliness and tardiness penalties, considering due dates and sequence-dependent setup time. According to its complexity, an auto adaptive genetic algorithm is proposed to solve it. Many search operators are used to explore the solutions space where the choice probability for each operator depends to the success in a previous search. The initial population is generated by the combination between construct methods based on greedy, random and GRASP techniques. For each individual (job sequence) generated, a polynomial time algorithm are used to determine the processing initial optimal date to each job. Computational results show the effectiveness of the proposed algorithm.
References
Du, J. and Leung, J. Y. T. (1990). “Minimizing total tardiness on one machine is np-hard”. Mathematics of Operations Research, 15:483–495.
Feo, T. A. and Resende, M. G. C. (1995). “Greedy randomized adaptive search procedures”. Journal of Global Optimization, 6:109–133.
Glover, F. (1996). “Tabu search and adaptive memory programming - advances, applications and challenges”. In Barr, R. S., Helgason, R. V., and Kennington, J. L., editors, Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, pages 1–75. Kluwer Academic Publishers.
Gomes Jr., A. C., Carvalho, C. R. V., Munhoz, P. L. A., and Souza, M. J. F. (2007). “A hybrid heuristic method for solving the single machine scheduling problem with earliness and tardiness penalties (in portuguese)”. In Proceedings of the XXXIX Brazilian Symposium of Operational Research (XXXIX SBPO), pages 1649–1660, Fortaleza, Brazil.
Hino, C. M., Ronconi, D. P., and Mendes, A. B. (2005). “Minimizing earliness and tardiness penalties in a single-machine problem with a common due date”. European Journal of Operational Research, 160:190–201.
Lee, C. Y. and Choi, J. Y. (1995). “A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights”. Computers and Operations Research, 22:857–869.
Matias, P. T. (2008). “Avaliação comparativa de algoritmos evolutivos com operadores adaptativos”. Dissertação de mestrado, Programa de Engenharia Civil, UFRJ, Rio de Janeiro.
Prais, M. and Ribeiro, C. C. (2000). “An application to a matrix decomposition problem in tdma traffic assignment”. INFORMS - Journal on Computing, 12:164–176.
Rossetti, I. C. M. (2003). “Estratégias sequenciais e paralelas de GRASP com reconexão por caminhos para o problema de síntese de redes a 2 caminhos”. Tese de doutorado, Programa de Pós-Graduação em Informática, PUC-RJ, Rio de Janeiro, Brasil.
Wan, G. and Yen, B. P. C. (2002). “Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties”. European Journal of Operational Research, 142:271–281.
