Mixed-Integer Linear Programming Model for Short-Term Batch Scheduling in Parallel Lines

CERDÁ, JAIME; HENNING, GABRIELA; GROSSMANN, IGNACIO

INDUSTRIAL & ENGINEERING CHEMICAL RESEARCH

ACS Publications

Año: 1997 vol. 36 p. 1695 - 1707

0888-5885

An important industrial problem is the short-term scheduling of batch multiproduct facilities where a wide range of products are manufactured in small amounts that must be satisfied at certain due dates during the given time horizon. This paper presents a new MILP mathematical formulation for the batch scheduling problem involving a single processing stage for every product to be delivered. Based on a continuous representation of the time domain and the concept of job predecessor and successor to effectively handle changeovers, the proposed model is able to determine the optimal allocation of jobs to lines/units, the sequence of jobs on every line/unit, and their starting and completion times so as to minimize one of the following problem objectives: the overall tardiness, the schedule makespan, or the number of tardy orders. Facilities having nonidentical parallel units/lines, sequence-dependent changeovers, finite release times for units and orders, and restrictions on the types of orders that can be manufactured in each equipment can easily be handled. To deal with real world single-stage scheduling problems, a successful strategy for expediting the problem solution that relies on the use of heuristics is also reported. These heuristics allow one to partially prune the set of feasible predecessors for each customer order, reducing the size of the MILP problem representation. Examples involving up to 20 orders and 4 units were successfully solved with an advanced branch-and-bound code requiring reasonable CPU time.