Scheduling grouped jobs on single machine with genetic algorithm

Production scheduling of grouped jobs has been an active research area since Group Technology was widely applied in practical manufacturing systems. To minimize the total flowtime of grouped jobs on a single machine, we combine jobs into fundamental runs based upon the necessary condition of the optimal solution. It is proved that the optimal solution is a combination of fundamental runs. A genetic algorithm is designed based on studies on the combinatorial rules of fundamental runs. The numerical results show that the computational performance of the algorithm depends on the number of ‘fundamental’ runs, not on the number of jobs. In general, the number of fundamental runs is far less than the number of jobs. Therefore, the algorithm has potential for practical application in large scale production systems.