Minimization of the Makespan with a Discrete-Time State-Task Network Formulation

A novel algorithm is proposed for the minimization of the makespan of multipurpose batch plants using the state-task network (STN) formulation. The algorithm involves the solution of successive feasibility problems, where the time horizon is extended until a feasible schedule for the given demand is found. To exploit the tight LP relaxation of the STN formulation, a production maximization problem (subject to the given demand) is solved at each iteration, and the algorithm terminates when the first feasible solution is found. The algorithm is guaranteed to find an optimal solution, and if integer cuts are used, it can provide many alternative solutions. The algorithm appears to be computationally efficient for many classes of problems and process networks of medium complexity.