Combination of Genetic Algorithm and LP-metric to Solve Single Machine Bi-criteria Scheduling Problem

This paper addresses single machine bi-criteria scheduling problem with the aim of minimizing total weighted tardiness and weighted number of tardy jobs. While weighted number of tardy jobs measures the service quality provided to customers, total weighted tardiness quantify the magnitude of lateness of each job. Therefore, considering both objectives, simultaneously, will provide the highest customers satisfaction. Both objectives are known to be NP-hard, thus, Genetic Algorithm is hired to solve the problem. Since LP-metric method is a rigorous multi-objective technique for making a combined dimensionless objective, it is used to navigate the search direction of Genetic algorithm. In this way, we can reach to some of solutions that are compatible to decision maker's opinion while overcoming the issue of problem complexity. Finally for testing the efficiency of the proposed approach, some test problems are solved.