Multiple-machine lower bounds for shop-scheduling problems

In order to compute lower bounds for shop scheduling problems, a lot of att ention has been paid to adjustment techniques based on one-machine relaxati ons. We present such a new technique but, following the observation that ma chines are connected to each other through precedence constraints, we also study techniques that are based on the combination of precedence constraint s and disjunctive constraints between operations that are processed on diff erent machines. A computational study of the effectiveness of these new tec hniques is performed on job shop and flow-shop instances.