Related Experiment Video
Updated: Oct 27, 2025
10:09
Operation of the Collaborative Composite Manufacturing CCM System
Published on: October 1, 2019
6.8K
Model abstraction for discrete-event systems by binary linear programming with applications to manufacturing systems
Lihong Cheng1,2, Lei Feng2, Zhiwu Li1
1School of Electro-Mechanical Engineering, Xidian University, Xi'an, China.
Science Progress
|July 22, 2021
Summary
This study introduces a novel method to simplify complex discrete-event systems by reformulating state space reduction as a binary linear programming problem. This approach enhances computational efficiency and understanding for verification and control synthesis.
Area of Science:
- Control Theory
- Computer Science
- Operations Research
Background:
- Model abstraction simplifies discrete-event systems (DES) for verification and control synthesis.
- Supremal quasi-congruence equivalence is a known method for state space reduction in DES.
- Existing algorithms for supremal quasi-congruence are graph-theory based.
Purpose of the Study:
- To propose a new method for computing supremal quasi-congruence.
- To convert the supremal quasi-congruence problem into a binary linear programming (BLP) problem.
- To optimize the state-to-coset allocation for coarsest quasi-congruence.
Main Methods:
- Formulating supremal quasi-congruence computation as a binary linear programming problem.
- Solving the optimal partitioning problem as an optimal state-to-coset allocation problem.
- Implementing solutions using mixed integer linear programming (MILP) in MATLAB and BLP in CPLEX.
Main Results:
- The proposed method successfully converts supremal quasi-congruence computation into a solvable optimization problem.
- Optimized translation process reduces computation time by simplifying variables and constraints.
- Computational efficiency and correctness verified using two distinct solvers.
- Applied to simplify a large-scale manufacturing system model.
Conclusions:
- The novel approach provides an effective alternative for computing the coarsest quasi-congruence.
- This method offers a more intuitive understanding of quasi-congruence relations in supervisory control.
- Future work includes exploring more efficient solvers for optimal state-to-coset allocation.
Related Concept Videos
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
135
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
135
01:26Classification of Systems-I
371
Linearity is a system property characterized by a direct input-output relationship, combining homogeneity and additivity.
Homogeneity dictates that if an input x(t) is multiplied by a constant c, the output y(t) is multiplied by the same constant. Mathematically, this is expressed as:
Homogeneity dictates that if an input x(t) is multiplied by a constant c, the output y(t) is multiplied by the same constant. Mathematically, this is expressed as:
371
01:21Linear Approximation in Time Domain
171
Nonlinear systems often require sophisticated approaches for accurate modeling and analysis, with state-space representation being particularly effective. This method is especially useful for systems where variables and parameters vary with time or operating conditions, such as in a simple pendulum or a translational mechanical system with nonlinear springs.
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
For a simple pendulum with a mass evenly distributed along its length and the center of mass located at half the pendulum's length,...
171
01:30Gaussian Elimination: Problem Solving
24
Systems of linear equations in several variables are pivotal in modeling complex scenarios involving multiple unknowns and constraints. Such systems are widely used in various fields to represent relationships where several conditions must be simultaneously satisfied. Each variable in the system corresponds to an unknown quantity, while each equation imposes a linear constraint, leading to a structured approach for analyzing and solving real-world problems.A system of three equations with three...
24
01:21Mechanistic Models: Overview of Compartment Models
210
Mechanistic models, a category encompassing both physiological and compartmental modeling, differ from empirical models' approaches to incorporating known factors about the systems being modeled. Empirical models describe data with minimal assumptions, while mechanistic models aim to provide a robust description of available data by specifying assumptions and integrating known factors about the system. Compartmental analysis is a key example of a mechanistic model in pharmacokinetics and...
210
01:24BIBO stability of continuous and discrete -time systems
610
System stability is a fundamental concept in signal processing, often assessed using convolution. For a system to be considered bounded-input bounded-output (BIBO) stable, any bounded input signal must produce a bounded output signal. A bounded input signal is one where the modulus does not exceed a certain constant at any point in time.
To determine the BIBO stability, the convolution integral is utilized when a bounded continuous-time input is applied to a Linear Time-Invariant (LTI) system....
To determine the BIBO stability, the convolution integral is utilized when a bounded continuous-time input is applied to a Linear Time-Invariant (LTI) system....
610