  This work proposes a unified heuristic algorithm for a large class of
earliness-tardiness (E-T) scheduling problems. We consider single/parallel
machine E-T problems that may or may not consider some additional features such
as idle time, setup times and release dates. In addition, we also consider
those problems whose objective is to minimize either the total (average)
weighted completion time or the total (average) weighted flow time, which arise
as particular cases when the due dates of all jobs are either set to zero or to
their associated release dates, respectively. The developed local search based
metaheuristic framework is quite simple, but at the same time relies on
sophisticated procedures for efficiently performing local search according to
the characteristics of the problem. We present efficient move evaluation
approaches for some parallel machine problems that generalize the existing ones
for single machine problems. The algorithm was tested in hundreds of instances
of several E-T problems and particular cases. The results obtained show that
our unified heuristic is capable of producing high quality solutions when
compared to the best ones available in the literature that were obtained by
specific methods. Moreover, we provide an extensive annotated bibliography on
the problems related to those considered in this work, where we not only
indicate the approach(es) used in each publication, but we also point out the
characteristics of the problem(s) considered. Beyond that, we classify the
existing methods in different categories so as to have a better idea of the
popularity of each type of solution procedure.

Artificial Intelligence