TWO PARETO OPTIMUM-BASED HEURISTIC ALGORITHMSFOR MINIMIZING TARDINESS AND LATE JOBS IN THESINGLE MACHINE FLOWSHOP PROBLEM

Abstract

Flowshop problems play a prominent role in operations research, and have considerable practical significance. The single-machine flowshop
problem is of particular theoretical interest. Until now the problem of minimizing late jobs or job tardiness can only be solved exactly by computationally intensive methods such as dynamic programming or linear programming. In this paper we introduce, test, and optimize two new heuristic algorithms for mixed tardiness and late job minimization in single-machine flowshops. The two algorithms both build partial schedules iteratively. Both also retain Pareto optimal solutions at intermediate stages, to take into account both tardiness and late jobs within the partial schedule, as well as the effect of partial completion time on not-yet scheduled jobs. Both algorithms can potentially be applied to scenarios with hundreds of jobs, with execution times running from
less than a second to a few minutes. Although they are slower than dispatch rule-based heuristics, the solutions obtained are far better. We also attempted a neural-network solution which performs poorly, and propose reasons why neural networks may not be a suitable approach.