1,720,978 research outputs found
Supervisory Control of Timed Discrete Event Systems with Logical and Timed Specifications
Full text linkA novel framework is introduced for the supervisory control (SC) of timed discrete event systems, based on Time Petri nets. The method encompasses both logical (markings to reach or avoid) and temporal specifications (arrival and departure times in specific markings). It relies on the construction of a partial forward reachability graph, of the Modified State Class Graph type, and the formulation of integer linear programming problems to establish suitable firing time intervals (FTIs) for the controllable transitions. The SC algorithm provides for each enabled controllable transition the largest FTI that guarantees that the specifications are met, irrespectively of the firing times of the uncontrollable transitions
Computation of K-reachable paths in Petri nets
Full text linkThe enumeration of legal transition paths leading to a target state (or set of states) is of paramount importance in the control of discrete event systems, but is hindered by the state explosion problem. A method is proposed in this paper, in the context of Petri nets, to calculate and enumerate firing count vectors for which there exists at least an admissible transition sequence leading to a given target marking. The method is based on the concept of singular complementary transition invariants proposed by Kostin and combines an integer linear programming formulation that finds the shortest minimal solution and a branching procedure that effects a partition of the solution set. The enumeration can be restricted to minimal solutions or extended to non-minimal ones. Some analytical examples are discussed in detail to show the effectiveness of the proposed approach
Optimization-based computation of bounded sequences to reach target states in DESs
No full textThe enumeration of legal transition paths leading to a target state (or set of states) is of paramount importance in the control of discrete event systems, but is hindered by the state explosion problem. A method is proposed in this paper, in the context of Petri nets, to calculate and enumerate firing count vectors for which there exists at least an admissible transition sequence leading to a given target marking. The method is shown to improve the approach based on singular complementary transition invariants proposed by Kostin and combines an integer linear programming formulation that finds the shortest minimal solution and a branching procedure that realizes a partition of the solution set. The enumeration can be restricted to minimal solutions or extended to non-minimal ones. Moreover, the approach is extended by adding a further constraint that the target transition sequences should pass by intermediate markings (in a specific order or not). Finally, source, target and via markings can be replaced by sets of markings. Some analytical examples are discussed in detail to show the effectiveness of the proposed approach
Metaheuristics for the Minimum Gap Graph Partitioning Problem
Full text linkThe Minimum Gap Graph Partitioning Problem (MGGPP) consists in partitioning a vertex-weighted undirected graph into a given number of connected subgraphs with the minimum difference between the largest and the smallest weight in each subgraph. We propose a two-level Tabu Search algorithm and an Adaptive Large Neighborhood Search algorithm to solve the MGGPP in reasonable time on instances with up to about 23 000 vertices. The quality of the heuristic solutions is assessed comparing them with the solutions of a polynomially solvable combinatorial relaxation
An efficient heuristic approach to solve the unate covering problem
No full textThe paper presents a new approach to solve the unate covering problem based on exploitation of information provided by Lagrangean relaxation. In particular, main advantages of the proposed heuristic algorithm are the effective choice of elements to be included in the solution, cost-related reductions of the problem, and a good lower bound on the optimum. The results support the effectiveness of this approach: on a wide set of benchmark problems, the algorithm nearly always hits the optimum and in most cases proves it to be such. On the problems whose optimum is actually unknown, the best known result is strongly improved
A Heuristic for the Vehicle Routing Problem with Time Windows
No full textIn this paper we propose a heuristic algorithm to solve the Vehicle Routing Problem with Time Windows. Its framework is a smart combination of three simple procedures: the classical k-opt exchanges improve the solution, an ad hoc procedure reduces the number of vehicles and a second objective function drives the search out of local optima. No parameter tuning is required and no random choice is made: these are the distinguishing features with respect to the recent literature. The algorithm has been tested on benchmark problems which prove it to be more effective than comparable algorithms
Toward smart building design automation: Extensible CAD framework for indoor localization systems deployment
Full text linkOver the last years, many smart buildings applications, such as indoor localization or safety systems, have been subject of intense research. Smart environments usually rely on several hardware nodes equipped with sensors, actuators, and communication functionalities. The high level of heterogeneity and the lack of standardization across technologies make design of such environments a very challenging task, as each installation has to be designed manually and performed ad-hoc for the specific building. On the other hand, many different systems show common characteristics, like the strict dependency with the building floor plan, also sharing similar requirements such as a nodes allocation that provides sensing coverage and nodes connectivity. This paper provides a computer-aided design application for the design of smart building systems based on the installation of hardware nodes across the indoor space. The tool provides a site-specific algorithm for cost-effective deployment of wireless localization systems, with the aim to maximize the localization accuracy. Experimental results from real-world environment show that the proposed site-specific model can improve the positioning accuracy of general models from the state-of-the-art. The tool, available open-source, is modular and extensible through plug-ins allowing to model building systems with different requirements
A heuristic approach to the overnight security service problem
No full textThis paper introduces the overnight security service problem. The model obtained is a single-objective mixed integer programming problem. It is NP-hard in the strong sense, and exact approaches are not practicable when solving real-life instances. Thus, the model is solved heuristically, through a decomposition in two subproblem. The former is a capacitated clustering problem, the latter is a multiple travelling salesman problem with time windows. Both have a radius constraint which is unusual. The computational results prove the robustness of the approach used. Moreover, a detailed discussion of the results shows that the management objectives are satisfied, providing lower costs, a strong guarantee on the level of service and several different solutions
- …
