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.
-
Taming state-space explosion in the makespan optimization of Flexible Manufacturing Systems
J. Bastos, J. Voeten, S. Stuijk, R. Schiffelers and H. Corporaal.
In ACM Transactions on Cyber Physical Systems (TCPS), 5, 2, Article 15 (January 2021), 26 pages. ACM, USA, 2020. (abstract, pdf, doi).