Parallel machine scheduling with earliness and tardiness penalties

In the parallel machine scheduling problem with earliness and tardiness penalties (PMSP_E/T) considered here, a set of independent jobs with sequence-dependent setups is given to be scheduled on a set of parallel machines (processors) in a non-preemptive fashion such that the sum of the weighted earliness and tardiness values of all jobs is minimized. The due dates of the jobs are distinct which complicates the problem. In addition, each job has its own arrival time which brings the model closer to reality but complicates it further. The weights for earliness and tardiness are common to all jobs and are unequal in general. Two genetic algorithm approaches are employed to attack this problem; one with a crossover operator which is developed to solve multi-component combinatorial optimization problems of which PMSP_E/T is an instance, and the other with no crossover operator. Results of tests on 960 randomly generated problems indicate that genetic algorithms provide an efficient algorithm for PMSP_E/T; that neighborhood exchange type of search can yield relatively better results in small and easy instances of the problem but the genetic algorithm with the crossover operator outperforms such search in large-sized, more difficult problems; and that the recombinative power of the genetic algorithm with the crossover operator improves with increasing problem size and difficulty, making it ever more attractive for applications of larger sizes.