A Hybrid Genetic Algorithm to Minimize Total Tardiness for Unrelated Parallel Machine Scheduling with Precedence Constraints

摘要

The paper presents a novel hybrid genetic algorithm (HGA) for a deterministic scheduling problemwhere multiple jobs with arbitrary precedence constraints are processed on multiple unrelatedparallel machines. The objective is to minimize total tardiness, since delays of the jobs may leadto punishment cost or cancellation of orders by the clients in many situations. A priority rule-basedheuristic algorithm, which schedules a prior job on a prior machine according to the priorityrule at each iteration, is suggested and embedded to the HGA for initial feasible schedules thatcan be improved in further stages. Computational experiments are conducted to show that theproposed HGA performs well with respect to accuracy and efficiency of solution for small-sizedproblems and gets better results than the conventional genetic algorithm within the same runtimefor large-sized problems.