A heuristic for parallel machine scheduling with due dates and ready times

In this paper, we consider an n-job, non-preemptive and identical parallel machine scheduling problem of minimizing the sum of earliness and tardiness with different release times and due dates. In the real world, this problem is more realistic than the problems that release times equal to zero or due dates are common. The problem is proved to be NP-complete. Thus, a heuristic is developed to solve this problem. To illustrate its suitability, the proposed heuristic is compared with a genetic algorithm for a large number of randomly generated test problems. Computational results show the effectiveness and efficiency of proposed heuristic. In summary, the proposed heuristic provides better solutions than genetic algorithm when the problem size is large.