A MIXED-INTEGER LINEAR-PROGRAMMING MODEL FOR SHORT-TERM SCHEDULING OFSINGLE-STAGE MULTIPRODUCT BATCH PLANTS WITH PARALLEL LINES

An important industrial problem is the short-term scheduling of batch multiproduct facilities where a wide range of products are manufacture d in small amounts that must be satisfied at certain due dates during the given time horizon. This paper presents a new MILP mathematical fo rmulation for the batch scheduling problem involving a single processi ng stage for every product to be delivered. Based on a continuous repr esentation of the time domain and the concept of job predecessor and s uccessor to effectively handle changeovers, the proposed model is able to determine the optimal allocation of jobs to lines/units, the seque nce of jobs on every line/unit, and their starting and completion time s so sis to minimize one of the following problem objectives: the over all tardiness, the schedule makespan, or the number of tardy orders. F acilities having nonidentical parallel units/lines, sequence-dependent changeovers, finite release times for units and orders, and restricti ons 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 t hat relies on the use of heuristics is also reported. These heuristics allow one to partially prune the set of feasible predecessors for eac h customer order, reducing the size of the MILP problem representation . Examples involving up to 20 orders and 4 units were successfully sol ved with an advanced branch-and-bound code requiring reasonable CPU ti me.