  Quality control lead times are one of most significant causes of loss of time
in the pharmaceutical and cosmetics industries. This is partly due to the
organization of laboratories that feature parallel multipurpose machines for
chromatographic analyses. The testing process requires long setup times and
operators are needed to launch the process. The various controls are
non-preemptive and are characterized by a release date, a due date and
available routings. These quality processes lead to significant delays, and we
therefore evaluate the total tardiness criterion. Previous heuristics were
defined for the total tardiness criterion, parallel machines, and setup such as
ATC (Apparent Tardiness Cost) and ATCS (ATC with setups). We propose new rules
and a simulated annealing procedure in order to minimize total tardiness.
