Comparing heuristic and evolutionary approaches for minimising the number of tardy jobs and maximum earliness on a single machine

摘要

The bi-criterion problem of minimising the number of tardy jobs and maximum earliness on a single machine is investigated experimentally. Two approximate solution approaches are tested. The first one is based on transforming the bi-criterion problem into a series of single-objective sub-problems and then applying a deterministic, heuristic procedure to solve them iteratively. The second approach is based on a multi-objective evolutionary algorithm with random keys encoding scheme. A dataset of 180 problem instances with 50, 100, and 150 jobs was generated randomly in order to evaluate the performance of the two approaches. The Pareto optimal sets computed by the evolutionary approach were consistently under-populated when compared to those of the heuristic however; more than 60% of the solutions found by the heuristic in all instances were dominated by solutions generated by the evolutionary algorithm.