Fitness Landscapes For The Total Tardiness Single Machine Scheduling Problem

This paper addresses several issues related to the approximate solution of the Single Machine Scheduling problem with sequence-dependent setup times using metaheuristic methods. Instances with known optimal solution are solved using a memetic algorithm and a multiple start approach. A fitness landscape analysis is also conducted on a subset of instances to understand the behavior of the two approaches during the optimization process. We also present a novel way to create instances with known optimal solutions from the optimally solved asymmetric travelling salesman problem (ATSP) instances. Finally we argue for the test set of instances to be used in future works as a convenient performance benchmark.122165180Boese, K., (1995) Cost versus Distance in the Traveling Salesman Problem, , Tech. Report. TR-950018, CS Department, University of California at Los AngelesBurke, E.K., Newall, J.P., Weare, R.F., A memetic algorithm for University exam timetabling (1996) Lecture Notes in Computer Science, 1153, pp. 241-250Corne, D., Glover, F., Dorigo, M., (1999) New Ideas in Optimisation, , McGraw-HillFranca, P.M., Mendes, A., Moscato, P., A memetic algorithm for the total tardineas single machine scheduling problem (2001) EJOR - European Journal of Operational Research, 132 (1), pp. 224-242Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey (1979) Annals of Discrete Mathematics, 5, pp. 287-326Graves, S.C., A review of production scheduling (1981) Operations Research, 29, pp. 646-675Merz, P., Freisleben, B., Memetic algorithms and the fitness landscape of the graph bipartitioning problem (1998) Proceedings of the 5th International Conference on Parallel Problem Solving from Nature - PPSN V, pp. 765-774. , SpringerMoscato, P., On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms (1989) C3P Report, 826. , Caltech Concurrent Computation ProgramMoscato, P., An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search (1993) Annals of Operations Research, 41 (1-4), pp. 85-121Reeves, C.R., Landscapes, operators and heuristic search (1999) Annals of Operations Research, 86, pp. 473-490TSPLIB web page, , http://www.crpc.rice.edu/softlib/tsplib/Wright, S., The roles of mutation, inbreeding, crossbreeding and selection in evolution (1932) Proceedings of the 6th International Congress on Genetics, 1, pp. 356-36