HEURISTIC ALGORITHM FOR SCHEDULING BATCH AND SEMICONTINUOUS PLANTS WITH PRODUCTION DEADLINES, INTERMEDIATE STORAGE LIMITATIONS AND EQUIPMENT CHANGEOVER COSTS

We describe a heuristic algorithm for scheduling a multiproduct, batch or semicontinuous plant. In particular, we address a problem involvin g intermediate product draw-offs, raw-material feeds to any stage, fin ite intermediate storage inserted between all stages, and order-deadli nes. The strategy is characterized by discretization of the scheduling horizon, generalized way of handling storage and a flexible method of objective function evaluation. Each order is assigned a priority taki ng into account the due dates, product importance and scheduling prefe rence. Orders are scheduled sequentially according to priority. The al gorithm maintains the status of all units and inventories of all mater ials throughout the planning horizon. To satisfy an order, a productio n run for the material is initiated as close to the deadline as unit a nd tank availability constraints permit. Then orders for feeds to the scheduled task are generated, and requirements for each feed are met b y scheduling their respective tasks. This procedure is carried out rec ursively until the feeds are externally supplied raw-materials. Differ ent schedules are generated by changing the order priorities. For each trial, an objective function comprising inventory costs, changeover c osts and deadline violation penalties is calculated. This objective fu nction is used as a criterion for choosing the best schedule. The algo rithm has been successfully tested on data from an existing multiprodu ct plant and was found to give significantly better schedules than tho se manually generated by plant staff. The heuristic solutions are foun d to be within 23% of an exact lower bound by relaxing the integrality constraints to the scheduling problem posed as an MILP. The goodness of the heuristic was further statistically analyzed by evaluating poin t and interval estimates for the optimal solution value and calculatin g the performance measure of the heuristic. This measure was always le ss than 8% indicating a powerful heuristic.