Schedule Synthesis for Halide Pipelines

In this paper we focus on the makespan optimization of industrial-sized flexible manufacturing systems. This optimization problem is NP-Hard and finding optimal solutions often results in state-space explosion. To get a grip on state-space sizes we extend an existing specification and design exploration framework with a novel algebra that allows us to systematically relate state-space and optimization-space sizes and makespan-optimal solutions. Further, this algebra allows non-essential (over-specification) requirements to be exploited to prune the state-space and optimization-space. These non-essential requirements are formalized in terms of constraints for which we establish the conditions under which their application results in a reduction of the optimization-space. We demonstrate the applicability of the algebra and reduction approach to minimize the makespan of batches manufactured in an industrial-sized wafer handling controller.