Improving the efficiency of discrete time scheduling formulation

The problem of production scheduling in multipurpose plants can be formulated as a mixed integer linear programming (MILP) problem based on a discrete representation of time. The mathematical difficulties associated with solving integer programs are well established and combining this factor with the increasing complexity and size of scheduling problems, there exists a strong requirement for efficient solution algorithms. This paper attempts to address this requirement by looking at two ways to reduce the gap between the optimal solution and the solution of its relaxed LP counterpart. The first;method involves generating cut constraints in problems where the presence of changeover activities tends to widen the relaxation gap. The second method uses an established reformulation technique based on variable disaggregation which exploits the lot sizing problem found embedded in many scheduling instances. The reformulation is applied to a general scheduling framework and its performance evaluated. Test examples are described for both methods, along with their numerical results. (C) 1998 Elsevier Science Ltd. All rights reserved.