A greedy algorithm for computing finite-makespan controllable sublanguages

• Main Author: Su, Rong.
• Other Authors: School of Electrical and Electronic Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/84659; http://hdl.handle.net/10220/12502
• Institution: Nanyang Technological University

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.