PARALLEL MACHINE EARLINESS-TARDINESS SCHEDULING Comparison of Two Metaheuristic Approaches

摘要

This paper considers the problem of parallel machine scheduling with the earliness and tardiness penalties (PMSP E/T) in which a set of sequence-independent jobs is to be scheduled on a set of given machines to minimize a sum of the weighted earliness and tardiness values. The weights and due dates of the jobs are distinct positive numbers. The machines are diverse - each has a different execution speed of the respective jobs, thus the problem becomes more complex. To handle this, it two heuristics are employed, namely: the genetic algorithm with the MCUOX crossover operator and the tabu search. The performances of the both approaches are evaluated and their dependency on the shape of the investigated instances examined. The results indicate the significant predominance of the genetic approach for the larger-sized instances.