Hybrid Mathematical Programming Discrete-Event Simulation Approach for Large-Scale Scheduling Problems

Abstract

This article presents a new algorithm for industrially sized problems that, because of the large number of tasks to schedule, are either intractable or result in poor solutions when solved with full-space mathematical programming approaches. Focus is set on a special type of multistage batch plant featuring a single unit per stage, zero-wait storage policies, and a single transportation device for moving lots between stages. The algorithm incorporates a mixed-integer linear programming (MILP) continuous-time formulation and a discrete-event simulation model to generate a detailed schedule. More precisely, three stages are involved: (i) finding the best processing sequence, assuming that the transportation device is always available; (ii) generating a feasible schedule, taking into account the shared transportation resource; (iii) improving the schedule through a neighborhood search procedure. Relaxed and constrained versions of the full-space MILP are involved in stages (i) and (iii) with the simulation model taking care of stage (ii). Several examples are solved to illustrate the capabilities of the proposed method with the results showing better performance when compared to other published approaches. The balance between solution quality and total computational effort can easily be shifted by changing the number of lots rescheduled per iteration.