Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs

摘要

Today’s importance of on time deliveries according to JIT concept makes managers to consider a desired set of extra ‘due date related’ criteria in the workshop scheduling. These criteria can be stated as tardiness, number of tardy jobs, and earliness. In this paper we focus on the bi-criteria scheduling problem of minimizing the number of tardy jobs and maximum earliness for single machine, in which the idle time is not allowed. The problem is known to be NP-hard. For this problem we developed a genetic algorithm by exploiting its general structure that further improves the initial population, utilizing a heuristic algorithm on the initial population. We present a computational experiment that shows the performance of the developed GA.