A Virus Evolution Genetic Algorithm for Scheduling Problem with Penalties of Independent Tasks on a Single Machine

Scheduling problem with penalties of independent tasks on a single machine is a NP-hard problem. In this paper, a scheduling problem of n tasks which have different ready times and due dates is given. With respect to this problem, a virus evolution genetic algorithm called SMSP-VEGA is developed. SMSP-VEGA is used to obtain the optimal scheduling sequences for the tasks so that the total tardy penalty costs are minimized. Different from GA, SMSP-VEGA has two types of operator: genetic operator and virus_infection operator. As the genetic operators can transfer evolutionary genes from parent to child generation and the virus_infection operators can spread evolutionary genes in the same generation, respectively, It can perform global search and local search in the same time. The schema theory is adopted to analyze the performance of SMSP-VEGA and the experimental results are also given. The theoretical analysis and experimental results show that the SMSP-VEGA outperforms the GA.