Global Constraints for the Mean Absolute Deviation and the Variance: Application to the Vertical Line Balancing

Schaus, Pierre [UCL] Deville, Yves [UCL]

Optimization with a balancing objective often appear in practical problems where humans are implied in the solution. For example, in tasks assignment problems it is a desirable property that the workload is fairly distributed among the workers. In general, a violation measure of the perfect balance can be defined as the Lp norm of the vector of variables minus their mean. Two global constraints are presented that can be used in constraint programming to optimize the criteria L1 (the mean absolute deviation) and L2 (the variance). These global constraints have been implemented in the Gecode and Ilog CP environments and experimented on the vertical assembly line balancing problem. To the best of our knowledge, this is the first exact method to minimize L1 or L2 on this problem.