Heuristic for scheduling grouped jobs with set-ups on parallel machines

A model of scheduling grouped N jobs on M identical machines in parallel was addressed. The model assumes that a set-up time is incurred when a machine changes from processing one type of parts to a different type of parts. And the scheduling objective is to minimize the total sum of flow time. Based on the necessary conditions of optimal solution, jobs can be combined into fundamental runs. By studying the combinatorial rules of these fundamental runs, a heuristic algorithm was developed. The efficiency of this heuristic was tested on several groups of random problems. As the number of fundamental runs is usually far less than the number of jobs, the heuristic has potential for practical application in larger scale production systems.