A greedy algorithm for computing finite-makespan controllable sublanguages

Abstract

The Ramadge-Wonham supervisory control paradigm has been shown effective in dealing with logic control. Nevertheless, time-related performance is always one of the major concerns in industry. Recently, a new time optimal control framework has been proposed, and an algorithm for synthesizing a minimum-makespan controllable sublanguage has been provided. But it has been shown that computing such a minimum-makespan controllable sublanguage is NP-hard. To avoid this complexity issue, we present a polynomial-time algorithm that computes a finite-makespan controllable sublanguage. To evaluate the potential difference between the attained finite makespan and the actual minimum makespan, we provide a polynomial-time algorithm to compute a strictly lower bound of the minimum makespan so that explicitly computing such a minimum makespan can be avoided. Experimental results are provided to show the effectiveness of our algorithms.