Parallel machine scheduling with earliness and tardiness penalties

In the parallel machine scheduling problem with earliness and tardiness pen alties (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 (pr ocessors) in a non-preemptive fashion such that the sum of the weighted ear liness 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 complicat es it further. The weights for earliness and tardiness are common;to all jo bs and are unequal in general. Two genetic algorithm approaches are employe d 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 te sts on 960 randomly generated problems indicate that genetic algorithms pro vide an efficient algorithm for PMSP-E/T; that neighborhood exchange type o f search can yield relatively better results in small and easy instances of the problem but the genetic algorithm with the crossover operator outperfo rms such search in larger-sized, more difficult problems; and that the reco mbinative power of the genetic algorithm with the crossover operator improv es with increasing problem size and difficulty making it ever more attracti ve for applications of larger sizes. (C) 1999 Elsevier Science Ltd. All rig hts reserved.