A hybrid method for a parallel-machine scheduling problem

The scheduling problem considered consists of determining a feasible schedule when each job is defined with a ready date, a processing time different on each machine and a deadline. They are setup time sequence dependent. The parallel machines are composed of 2 types. The first one is characterized with “cheap” machines, and the second one with “expensive” machines. The objective function is to first find a feasible schedule and then to minimize the cost due to assignment and setup time costs. The method presented in this paper is based on a three-phase heuristic. The first phase is based on an iterative heuristic, the second one on a genetic algorithm and the third one on a branch and bound for post optimization