Solving a large-scale industrial scheduling problem using MILP combined with a heuristic procedure

In this paper, a large-scale industrial production scheduling problem is considered. The problem includes the allocation of a number of production runs with release and due dates into a processing unit. The environment is further complicated with sequence-dependent setup times. A mixed integer linear programming (MILP) model is used to describe the scheduling task. However, due to the complex nature of the problem, the MILP model cannot directly be used to solve large-scale systems with industrial relevance, Therefore, an iterative heuristic procedure is used to address the notorious combinatorial complexity. Different properties of the algorithm are discussed and an illustrative example based on industrial data is presented. (C) 2002 Elsevier Science B.V. All rights reserved.