Toward a Global Constraint for Minimizing the Flowtime

This work is a study toward a global constraint minimizing the flowtime of a single machine scheduling problem. Classical methods for filtering algorithms use a lower bound coming from the solution of a relaxation. Notably, there are several polynomial relaxations to minimize the flowtime on a single machine. A general scheme for the global constraint is proposed that allows the use of a subset of polynomial relaxations that lays the ground for more complex filtering algorithms. The filtering algorithm has a complexity of O(n ·M· R), where n is the number of tasks, M is an upper bound on the time windows of these tasks, and R is the complexity of the algorithm used for solving the relaxation. The constraint has been tested on both single machine and flowshop problems. Experimental results show that the performance improvement depends on the type of problem. The number of branches reduction is promising for designing new filtering rules.