On structural minimality of optimal supervisors for flexible manufacturing systems

This paper develops a place invariant based deadlock prevention method to obtain an optimal, i.e., maximally permissive, liveness-enforcing Petri net supervisor with a minimal supervisory structure that means the minimal number of control places. Maximal permissiveness can be achieved by designing place invariants that make all legal markings reachable while all first-met bad markings unreachable. An integer linear programming problem is formulated to compute all place invariants and its objective function minimizes the number of place invariants, aiming to yield a minimal supervisory structure. Importantly, we develop a technique to greatly improve the efficiency of the proposed method by reducing the number of constraints and variables in the integer linear programming problem under consideration. A number of examples from the literature are used to illustrate the proposed approaches.     

Grid automata and supervisory control of dense real-time discrete event systems

We present a generalization of the classical supervisory control theory for discrete event systems to a setting of dense real-time systems modeled by Alur and Dill timed automata. The main problem involved is that in general the state space of a timed automaton is (uncountably) infinite. The solution is to reduce the dense time transition system to an appropriate finite discrete subautomaton, the grid automaton, which contains enough information to deal with the timed supervisory control problem (TSCP). The plant and the specifications region graphs are sampled for a granularity defined in a way that each state has an outgoing transition labeled with the same time amount. We redefine the controllability concept in the context of grid automata, and we provide necessary and sufficient solvability conditions under which the optimal solution to centralized supervisory control problems in timed discrete event systems under full observation can be obtained. The enhanced setting admits subsystem composition and the concept of forcible event. A simple example illustrates how the new method can be used to solve the TSCP.     

An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem

We consider a resource‐constrained project scheduling problem originating in particle therapy for cancer treatment, in which the scheduling has to be done in high resolution. Traditional mixed integer linear programming techniques such as time‐indexed formulations or discrete‐event formulations are known to have severe limitations in such cases, that is, growing too fast or having weak linear programming relaxations. We suggest a relaxation based on partitioning time into so‐called time‐buckets. This relaxation is iteratively solved and serves as basis for deriving feasible solutions using heuristics. Based on these primal and dual solutions and bounds, the time‐buckets are successively refined. Combining these parts, we obtain an algorithm that provides good approximate solutions soon and eventually converges to an optimal solution. Diverse strategies for performing the time‐bucket refinement are investigated. The approach shows excellent performance in comparison to the traditional formulations and a metaheuristic.     

Feedback Control Logic for Backward Conflict Free Choice Nets

This paper discusses the forbidden state problem, as specified by generalized mutual exclusion constraints, in the context of supervisory control of discrete event systems modelled by Petri nets. The case of backward-conflict-free and free-choice uncontrollable subnets is considered and it is shown how to transform such subnets in well-formed free-choice nets. Then, the well-formed free-choice nets are decomposed in marked graph components by recurring to minimal T-invariants. The forbidden state problem is so reformulated for the obtained marked graph components into an equivalent one which is shown to be a linear programming problem. Thus, improving existing results in literature, a polynomial complexity solution, suitable for on-line control, is achieved. Free-choice relationship and cycle modelling, that frequently occur in real-life situations, are so allowed in the uncontrollable subnet     

Petri net modeling and scheduling for cyclic job shops with blocking

Cyclic scheduling is an effective scheduling method in the repetitive discrete manufacturing environment. We investigate the scheduling problem for general cyclic job shops with blocking where each machine has an input buffer of finite capacity. We develop Petri net models for the shops. We propose a sequential buffer control policy that restricts the jobs to enter the input buffer of the next machine in a specified sequence. We show that the scheduling model of a cyclic shop with finite buffers under such a buffer control policy can be transformed into a scheduling model of a cyclic shop with no buffer that can be modeled as a timed marked graph. In addition, we characterize the structural properties for deadlock detection. Finally, we present a mixed integer programming model to find an optimal deadlock-free schedule that minimizes the cycle time.     

Optimal Nonblocking Directed Control of Discrete Event Systems

For the control of discrete event systems, the notion of directed control refines that of supervisory control. A directed controller is one that selects at most one controllable event to be enabled at any state (without disabling any uncontrollable event), which is in fact how a discrete event control is implemented. In contrast, a supervisory controller computes a maximal allowable set of controllable events at each state, leaving undecided exactly which controllable event should be enabled. In previous works, we developed a framework for the computation of optimal directed controllers and a polynomial synthesis algorithm for acyclic plants. In this paper, we present a novel synthesis approach for general plants, i.e., plants with or without cycles, thus providing a complete solution to the optimal directed control problem. The complexity of the approach remains polynomial in the size of plant.      

Supervision Based on Place Invariants: A Survey

The supervision based on place invariants (SBPI) is an efficient technique for the supervisory control of Petri nets. This paper reveals the significance of the SBPI based on a literature survey, applications, and an analysis of problems and supervisory settings that can be addressed using SBPI. Special attention is given to the various settings within which the problem can be formulated. Such settings can be distinguished based on the concurrency type, the type of controllability and observability, and the centralized or decentralized type of supervision. As we show, it is possible to approach the most general settings in a purely structural way, without resorting to reachability analysis. We begin by describing the SBPI problem and the literature methods that address this problem or are related to it. Then, we proceed to show classes of problems that can be reduced to the SBPI problem. In the SBPI, the specification is described as a system of inequalities that the Petri net marking must satisfy at any time. However, as we show, problems involving more general specifications can be approached in the SBPI setting, sometimes under additional assumptions, by performing net and/or specification transformations. Four of the specifications we will consider are logic constraints, language specifications, disjunctions of linear constraints, and liveness. We conclude with a presentation of possible applications of the SBPI approach to programming with semaphores, fault tolerance, and synchronic-distance based designs.     

Optimal sizing,scheduling and shift policy of the grinding section of a ceramic tile plant

This paper addresses the optimal design of the grinding section of a ceramic tile plant operating in a cyclic mode with the units (mills) following a batch sequence. The optimal design problem of this single product plant is formulated with a fixed time horizon of one week, corresponding to one cycle of production, and using a discrete-time resource task network (RTN) process representation. The size of the individual units is restricted to discrete values, and the plant operates with a set of limited resources (workforce and equipment). The goal is to determine the optimal number and size of the mills to install in the grinding section, the corresponding production schedule, and shift policy. This problem involves labor/semi-labor intensive (LI/SLI) units with a depreciation cost of the same order as that of the operation cost. The optimal design of the grinding section comprises the trade-off between these two costs. The resulting optimization formulation is of the form of a mixed integer linear programming (MILP) problem, solved using a branch and bound solver (CPLEX 9.0.2). The optimal solution is analyzed for various ceramic tile productions and different shift policies.     

A Probabilistic approach for model following of Markovian jump linear systems subject to actuator saturation

This paper is concerned with the model following problem of Markovian jump linear systems (MJLSs), which suffer from stochastic uncertainties and actuator saturation. By applying a probabilistic approach based on particles, a sequence of control inputs is designed to guarantee that the model following error remains within a desired region in a certain probability, as well as the control cost is optimal. Motivated by this, the stochastic control problem is represented by chance constrained programming, and approximated as a determinate optimization one, which is solved by mixed integer linear programming (MILP). Furthermore, an improved particle control approach is proposed to reduce the computation complexity. The effectiveness of this improved approach is demonstrated by an example along with complexity comparison.     

A Linear Programming Model for Distribution of Electrical Energy in a Steel Plant

The energy crisis is one of the deterrents of economic growth in a developing country like India. Rapid industrialization and poor capacity utilization of power plants make the operations of energy consuming industries like integrated steel plants extremely difficult. This case study discusses the development and implementation of a mixed integer linear programming model for optimal distribution of electrical energy in an integrated steel plant. The model considers the balance equations of capacity, material, thermal and electrical energy, oxygen. It also considers the constraints of yields, product routes, net realizations, variable costs, market demands and commitments to decide not only the hierarchy of shutdowns in the event of a power crisis but also the optimal product mix in each level of power availability. The round-the-clock implementation of the model increased the net profit per ton of saleable steel by 58% in 1986. Since then, the model, which is generic in nature, has been successfully integrated into the decision-making process. The cumulative benefit from this work will be at least 73 million US dollars.     

A Survey of Petri Net Methods for Controlled Discrete Event Systems

This paper surveys recent research on the application of Petri net models to the analysis and synthesis of controllers for discrete event systems. Petri nets have been used extensively in applications such as automated manufacturing, and there exists a large body of tools for qualitative and quantitative analysis of Petri nets. The goal of Petri net research in discrete event systems is to exploit the structural properties of Petri net models in computationally efficient algorithms for computing controls. We present an overview of the various models and problems formulated in the literature focusing on two particular models, the controlled Petri nets and the labeled nets. We describe two basic approaches for controller synthesis, based on state feedback and event feedback. We also discuss two efficient techniques for the on-line computation of the control law, namely the linear integer programming approach which takes advantage of the linear structure of the Petri net state transition equation, and path-based algorithms which take advantage of the graphical structure of Petri net models. Extensions to timed models are briefly described. The paper concludes with a discussion of directions for future research.     

Materialization of fragmented views in multidimensional databases

The most effective technique to enhance performances of multidimensional databases consists in materializing redundant aggregates called views. In the classical approach to materialization, each view includes all and only the measures of the cube it aggregates. In this paper we investigate the benefits of materializing views in vertical fragments, aimed at minimizing the workload response time. We formalize the fragmentation problem as a 0–1 integer linear programming problem, which is then solved by means of a standard integer programming solver to determine the optimal fragmentation for a given workload. Finally, we demonstrate the usefulness of fragmentation by presenting a large set of experimental results based on the TPC-H benchmark.     

Operation planning of district heating and cooling plants using genetic algorithms for mixed integer programming

In recent years, an operation planning of a district heating and cooling (DHC) plant has been arousing interest as a result of development of cooling load or heat demand prediction methods for district heating and cooling systems. In this paper, we formulate an operation planning of a district heating and cooling plant as a mixed integer linear programming problem. Since the formulated problem involves hundreds of variables, we anticipate that it is difficult to strictly solve it by enumeration-based methods. Thereby, we propose an approximate solution method based on genetic algorithms for mixed integer programming problems. Furthermore, we show the feasibility and effectiveness of the proposed method by comparison with the branch-and-bound method through numerical experiments using actual plant data.     

A resource allocation problem on timed marked graphs: a decomposition approach

In complex man-made environments discrete event dynamic systems are frequently encountered, and a timed marked graph is widely accepted as a convenient tool to describe systems of this kind. We consider trade-offs of cost and performance on such a system. First we formulate an optimization problem and transform it into a mixed integer linear programming problem. To improve computational efficiency, we decompose the problem into two phases. In phase one we determine the optimal number of each resource to be adopted in the system, and in phase two we optimize the distribution of these resources over the system. Phase one is solved very quickly and approximately by the dominance relaxation through a binary search procedure. This also gives the estimate of error bounds. An illustrative example shows an application to a jobshop optimization problem, and numerical experiments are carried out for some sample problems.     

Fast algorithm for a constrained infinite horizon LQ problem

This paper presents an efficient algorithmic solution to the infinite horizon linear quadratic optimal control problem for a discrete-time SISO plant subject to bound constraints on a scalar variable. The solution to the corresponding quadratic programming problem is based on the active set method and on dynamic programming. It is shown that the optimal solution can be updated after inclusion or removal of an active constraint by a simple procedure requiring in the order of kn operations, n being the system order and k the time at which the constraint is included or removed.     

A parametric analysis of linear integer programming problems

Parametric programming may be utilized to obtain restrictions to linear programming relaxations to linear integer programming problems. The purpose of such approaches is to reduce the size of the subproblems that appear subsequent to solving the relaxed linear programming problem. The optimal dual variables to the linear programming problem provide information regarding the difference between the continuous linear programming optimal objective function value and that of the integer linear programming objective function value.     

Net structure and control logic synthesis of controlled Petri nets

Control logic synthesis of discrete-event systems is considered in the setting of controlled Petri nets. The problem is to find a control policy that restricts the behavior of a controlled Petri net so that a collection of forbidden state conditions is satisfied. S-decreases are introduced as a tool for the control synthesis. The S-decreases are weight vectors defined on the places of a net such that the weighted sum of tokens in the net never increases with any transition firing. On the basis of S-decreases, the authors propose an efficient method for the synthesis of the maximally permissive state feedback control polity for a class of controlled Petri nets whose uncontrolled subnets are forward and backward conflict-free nets. This method upgrades all integer linear programming-based methods for which one only requires to solve the much simpler linear programming problems to determine maximally permissive controls     

适于估计OD矩阵的交通检测点的最优分布

讨论了适于估计起迄点出行分布矩阵(OD矩阵)的交通检测点的合理分布问题.根 据检测点应当满足的规则,建立了关于检测点分布的非线性规划模型.在已知极点问转移概 率的前提下,将检测点的分布问题描述成一个平均报酬Markov决策过程,并通过转化为一 个等价的整数线性规划问题来求解.最后实例结果表明该模型是有效的、合理的.     

Evolutionary algorithms for orthogonal frequency division multiplexing-based dynamic spectrum access systems

This paper proposes two evolutionary algorithms (EAs) to perform dynamic spectrum assignment in distributed OFDM-based cognitive radio access networks. To achieve better radio resource utilization, the central spectrum manager (CSM) jointly considers the type of modulation level which can be used by each radio pair when deciding the number of subcarriers to be assigned. Using the piecewise convex transformations, we reformulate the nonlinear integer programming problem to an integer linear programming so that it is possible to obtain the optimal solution. While the solution to the integer linear programming problem is NP-hard, the proposed EAs provide useful suboptimal solutions especially when the number of radios and subcarriers are large. Our first proposed EA adopts the genetic algorithm. Although the reproduction process generates chromosomes which do not fulfill the constraints, our algorithm integrates the invisible walls technique used in particle swam optimization to retain the diversity while constructing chromosomes for the next generation. The second EA adopts the ant colony optimization approach using a directed multigraph. The vertices are used to represent the subcarriers and each edge corresponds to a possible chosen modulation index of a specific radio. We further obtain the performance of the two EAs through simulations and benchmark them against the optimal solution. Our studies show that ant colony algorithm gives better solutions most of the time, however, its computation time increases much faster compared to generic algorithm when the numbers of users and subcarriers increase.     

Design of Optimal Petri Net Supervisors for Flexible Manufacturing Systems via Weighted Inhibitor Arcs

This paper develops an approach to the design of an optimal Petri net supervisor that enforces liveness to flexible manufacturing systems. The supervisor contains a set of observer places with weighted inhibitor arcs. An observer place with a weighted inhibitor arc is used to forbid a net from yielding an illegal marking by inhibiting the firing of a transition at a marking while ensuring that all legal markings are preserved. A marking reduction technique is presented to decrease the number of considered markings, which can dramatically lower the computational burden of the proposed approach. An integer linear program is presented to simplify the supervisory structure by minimizing the number of observer places. Finally, several examples are used to shed light on the proposed approach which can lead to an optimal supervisor for the net models that cannot be optimally controlled via pure Petri net supervisors.