Bicriteria single machine scheduling to minimize total tardiness and waiting time variance by genetic algorithms

Actual scheduling problems may necessitate the decision maker to consider a variety of criteria prior to make any decision. This research considers a single machine scheduling problem, with the objective of minimizing a combination of total tardiness and waiting time variance criteria in which the idle time is not allowed. Minimizing total tardiness is always regarded as one of the most important performance criteria in practical systems to avoid penalty costs of tardiness and waiting time variance is an important criterion in establishing Quality of Service (QoS) in many systems. Each of these criteria is known to be NP-hard and therefore the linear combination of them will be NP-hard as well. For this problem, we developed a genetic algorithm by utilizing its general structure. Two types of heuristic and random initial population and two distinct fitness functions are applied to genetic algorithms. The GA is shown experimentally to perform well by testing on various instances.