This paper addresses the m-machine flowshop problem with the objective of minimizing a weighted sum of makespan and maximum tardiness. Two types of the problem are addressed. The first type is to minimize the objective function subject to the constraint that the maximum tardiness should be less than a given value. The second type is to minimize the objective without the constraint. A new heuristic is proposed and compared to two existing heuristics. Computational experiments indicate that the proposed heuristic is much better than the existing ones. Moreover, a dominance relation and a lower bound are developed for a three-machine problem. The dominance relation is shown to be quite efficient.
