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

Authors: Alexandros S. Xanthopoulos; Dimitrios E. Koulouriotis

Addresses: Department of Production and Management Engineering, Democritus University of Thrace, School of Engineering, Vasilisis Sofias 12, 67100 Xanthi, Greece. ' Department of Production and Management Engineering, Democritus University of Thrace, School of Engineering, Vasilisis Sofias 12, 67100 Xanthi, Greece

Abstract: 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.

Keywords: single machine scheduling; heuristics; tardy jobs; multi-objective evolutionary algorithms; maximum earliness; random keys encoding.

DOI: 10.1504/IJMCDM.2012.046942

International Journal of Multicriteria Decision Making, 2012 Vol.2 No.2, pp.178 - 188

Published online: 22 May 2012 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article