Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria

The authors consider the problem of scheduling sequence-dependent jobs on identical parallel machines. Each job has to be processed without interruption on one of the machines. A machine changeover time must be respected between job processing on each machine. This changeover time is dependent on the job sequence. The present objective is to minimize the maximum completion time of the jobs or the mean completion time of the jobs. This problem is a vehicle routeing problem and is NP hard. The authors propose an assignment algorithm to solve it. The present heuristic is an extension of the Hungarian method to the multiple use of resources and has been developed during past years to solve routeing problems. This paper models the scheduling problem, presents the solution tool, and shows the heuristic result quality for 24 problem sizes.