A logic-based approach to scheduling problems with resource constraints

This paper addresses the problem of modeling discrete resource constraints (e.g., number of operators, fixed amount of electricity) in continuous time MILP scheduling models that handle fixed lot sizes. It is shown that these resource constraints can be expressed in terms of 0-1 variables that gives rise to a very large problem which is too difficult to solve simultaneously as an MILP. To circumvent this difficulty a novel relaxation method is proposed that combines LP-based branch and bound and disjunctive programming. The basic idea is to formulate the underlying continuous time scheduling model as an MILP while formulating all resource constraints as disjunctions. Furthermore, instead of considering them explicitly for the solution, only the violated set is generated within the branch and bound enumeration at nodes with feasible scheduling assignments. At these nodes a new disjunctive tree enumeration is created that switches from a el representation to a disjunctive program for the resource constraints. Results show that the solution of problems with this approach reduces the number of enumerated nodes by orders of magnitude when compared with the mixed 0-1 representation. (C) 1997 Elsevier Science Ltd.