Filtering Rules for Flow Time Minimization in a Parallel Machine
  Scheduling Problem
  This paper studies the scheduling of jobs of different families on parallel
machines with qualification constraints. Originating from semiconductor
manufacturing, this constraint imposes a time threshold between the execution
of two jobs of the same family. Otherwise, the machine becomes disqualified for
this family. The goal is to minimize both the flow time and the number of
disqualifications. Recently, an efficient constraint programming model has been
proposed. However, when priority is given to the flow time objective, the
efficiency of the model can be improved. This paper uses a polynomial-time
algorithm which minimize the flow time for a single machine relaxation where
disqualifications are not considered. Using this algorithm one can derived
filtering rules on different variables of the model. Experimental results are
presented showing the effectiveness of these rules. They improve the
competitiveness with the mixed integer linear program of the literature.
