一种基于神经网络的生产调度方法

提出解决具有开、完工期限制的约束Job-shop生产调度问题的一种神经网络方法. 该方法通过约束神经网络,描述各种加工约束条件,并对不满足约束的开工时间进行相应调 节,得到可行调度方案;然后由梯度搜索算法优化可行调度方案,直至得到最终优化可行调度 解.理论分析、仿真实验表明了方法的有效性.     

Min-degree constrained minimum spanning tree problem: New formulation via Miller–Tucker–Zemlin constraints

Given an undirected network with positive edge costs and a positive integer $d>2$, the minimum-degree constrained minimum spanning tree problem is the problem of finding a spanning tree with minimum total cost such that each non-leaf node in the tree has a degree of at least $d$. This problem is new to the literature while the related problem with upper bound constraints on degrees is well studied. Mixed-integer programs proposed for either type of problem is composed, in general, of a tree-defining part and a degree-enforcing part. In our formulation of the minimum-degree constrained minimum spanning tree problem, the tree-defining part is based on the Miller–Tucker–Zemlin constraints while the only earlier paper available in the literature on this problem uses single and multi-commodity flow-based formulations that are well studied for the case of upper degree constraints. We propose a new set of constraints for the degree-enforcing part that lead to significantly better solution times than earlier approaches when used in conjunction with Miller–Tucker–Zemlin constraints.     

Online constrained optimization based adaptive robust control of a class of MIMO nonlinear systems with matched uncertainties and input/state constraints

A performance oriented two-loop control approach is proposed for a class of multiple-input–multiple-output (MIMO) systems with input saturation, state constraints, matched parametric uncertainties and input disturbances. In the inner loop, a constrained adaptive robust control (ARC) law is synthesized to achieve the required robust tracking performances with respect to on-line replanned trajectory in the presence of input saturation and various types of matched uncertainties. In the outer loop, a replanned trajectory is generated by solving a constrained optimization algorithm online to minimize the converging time of the overall system response to the desired trajectory while not violating various constraints. Interaction of the two loops is explicitly characterized by a set of inequalities that the design variables of each loop have to satisfy. It is theoretically shown that the resulting closed-loop system can track feasible desired trajectories with a guaranteed converging time and steady-state tracking accuracy without violating the state constraints. Since the system in study is most appropriate to describe the dynamics of the robotic systems, the control of a two-axis planar robotic manipulator is used as an application example. Comparative simulation results demonstrate the advantage of the proposed approach over the traditional approaches in practical applications.     

Adaptive receding horizon control for constrained MIMO systems

An adaptive control algorithm for open-loop stable, constrained, linear, multiple input multiple output systems is presented. The proposed approach can deal with both input and output constraints, as well as measurement noise and output disturbances. The adaptive controller consists of an iterative set membership identification algorithm, that provides a set of candidate plant models at each time step, and a model predictive controller, that enforces input and output constraints for all the plants inside the model set. The algorithm relies only on the solution of standard convex optimization problems that are guaranteed to be recursively feasible. The experimental results obtained by applying the proposed controller to a quad-tank testbed are presented.     

Cellular automata approach for modelling climate change impact on water resources

ABSTRACT

In this work, we consider the cellular automata (CA) approach for modelling the climate change impact on water resources. This consists in: constructing a CA model that describes the water cycle dynamics taking into account physical terrain attributes and climatic constraints; coupling the CA model with climate projection scenarios for a considered region as input data; determining and analysing in output the variations of the underground, surface and evaporated water. We present these variations per time interval and per zone of influence. As an application, we consider simulation for a basin in northern Morocco using a simulation software we have designed in Java Object Oriented Programming.

We consider cellular automata (CA) approach for modelling climate change impact on water resources. This consists in, first constructing a CA model that describes the water cycle dynamics taking into account physical terrain attributes and climatic constraints, then coupling the CA model with climate projection scenarios for a considered region as input data, and we determine and analyze in output the variations of the water resources (groundwater and surface water). We present these variations per time interval and per zone of influence. The approach application is for a basin in northern Morocco for which we use simulation software that we have designed in Java Object Oriented Programming. Digital terrain model, geological map and satellites image are used for input data.     

A Systematic Approach for Designing Analytical Dynamics and Servo Control of Constrained Mechanical Systems

A systematic approach for designing analytical dynamics and servo control of constrained mechanical systems is proposed. Fundamental equation of constrained mechanical systems is first obtained according to Udwadia-Kalaba approach which is applicable to holonomic and nonholonomic constrained systems no matter whether they satisfy the D'Alember's principle. The performance specifications are modeled as servo constraints. Constraint-following servo control is used to realize the servo constraints. For this inverse dynamics control problem, the determination of control inputs is based on the Moore-Penrose generalized inverse to complete the specified motion. Secondorder constraints are used in the dynamics and servo control. Constraint violation suppression methods can be adopted to eliminate constraint drift in the numerical simulation. Furthermore, this proposed approach is applicable to not only fully actuated but also underactuated and redundantly actuated mechanical systems. Two-mass spring system and coordinated robot system are presented as examples for illustration.      

Timetabling through Constrained Heuristic Search and Genetic Algorithms

Hybrid genetic algorithms are presented that use constrained heuristic search and genetic techniques for the timetabling problem (TP). The TP is an NP-hard problem for which a general polynomial time deterministic algorithm is not known. The paper describes the classification of constraints and the constraint ordering to obtain the minimization of backtracking and the maximization of parallelism. The school timetabling problem is discussed in detail as a case study. The genetic algorithm approach is particularly well suited to this kind of problem, since there exists an easy way to assess a good timetable, but not a well structured automatic technique for constructing it. So, a population of timetables is created that evolves toward the best solution. The evaluation function and the genetic operators are well separated from the domain-specific parts, such as the knowledge of the problem and the heuristics, i.e. from the timetable builder. The present paper illustrates an approach based on the hybridization of constrained heuristic search with novel genetic algorithm techniques. It compares favourably with known programs to solve decision problems under logic constraints. The cost of the new algorithm and the quality of the solutions obtained in significant experiments are reported.     

Exhaustive and Efficient Constraint Propagation: A Graph-Based Learning Approach and Its Applications

This paper presents a novel pairwise constraint propagation approach by decomposing the challenging constraint propagation problem into a set of independent semi-supervised classification subproblems which can be solved in quadratic time using label propagation based on $k$ -nearest neighbor graphs. Considering that this time cost is proportional to the number of all possible pairwise constraints, our approach actually provides an efficient solution for exhaustively propagating pairwise constraints throughout the entire dataset. The resulting exhaustive set of propagated pairwise constraints are further used to adjust the similarity matrix for constrained spectral clustering. Other than the traditional constraint propagation on single-source data, our approach is also extended to more challenging constraint propagation on multi-source data where each pairwise constraint is defined over a pair of data points from different sources. This multi-source constraint propagation has an important application to cross-modal multimedia retrieval. Extensive results have shown the superior performance of our approach.     

Axis-coupled trajectory generation for chains of integrators through smoothing splines

Integrator based model is used to describe a wide range of systems in robotics. In this paper, we present an axis-coupled trajectory generation algorithm for chains of integrators with an arbitrary order. Special notice has been given to problems with pre-existing nominal plans, which are common in robotic applications. It also handles various type of constraints that can be satisfied on an entire time interval, including non-convex ones which can be transformed into a series of convex constraints through time segmentation. The proposed approach results in a linearly constrained quadratic programming problem, which can be solved effectively with off-the-shelf solvers. A closed-form solution is achievable with only the boundary constraints considered. Finally, the proposed method is tested in real experiments using quadrotors which represent high-order integrator systems.     

Constrained linear quadratic regulation

The paper is a contribution to the theory of the infinite-horizon linear quadratic regulator (LQR) problem subject to inequality constraints on the inputs and states, extending an approach first proposed by Sznaier and Damborg (1987). A solution algorithm is presented, which requires solving a finite number of finite-dimensional positive definite quadratic programs. The constrained LQR outlined does not feature the undesirable mismatch between open-loop and closed-loop nominal system trajectories, which is present in the other popular forms of model predictive control (MPC) that can be implemented with a finite quadratic programming algorithm. The constrained LQR is shown to be both optimal and stabilizing. The solution algorithm is guaranteed to terminate in finite time with a computational cost that has a reasonable upper bound compared to the minimal cost for computing the optimal solution. Inherent to the approach is the removal of a tuning parameter, the control horizon, which is present in other MPC approaches and for which no reliable tuning guidelines are available. Two examples are presented that compare constrained LQR and two other popular forms of MPC. The examples demonstrate that constrained LQR achieves significantly better performance than the other forms of MPC on some plants, and the computational cost is not prohibitive for online implementation     

Two-machine flowshop scheduling with bicriteria problem

This paper attempts to solve a two-machine flowshop bicriteria scheduling problem with release dates for the jobs, in which the objective function is to minimize a weighed sum of total flow time and makespan. To tackle this scheduling problem, an integer programming model with N²+3N variables and 5N constraints where N is the number of jobs, is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, a heuristic scheduling algorithm is presented. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. The average solution quality of the heuristic algorithm is above 99% and is much better than that of the SPT rule as a benchmark. A 15-job case requires only 0.018 s, on average, to obtain an ultimate or even optimal solution. The heuristic scheduling algorithm is a more practical approach to real world applications than the integer programming model.     

On constrained spectral clustering and its applications

Constrained clustering has been well-studied for algorithms such as K-means and hierarchical clustering. However, how to satisfy many constraints in these algorithmic settings has been shown to be intractable. One alternative to encode many constraints is to use spectral clustering, which remains a developing area. In this paper, we propose a flexible framework for constrained spectral clustering. In contrast to some previous efforts that implicitly encode Must-Link (ML) and Cannot-Link (CL) constraints by modifying the graph Laplacian or constraining the underlying eigenspace, we present a more natural and principled formulation, which explicitly encodes the constraints as part of a constrained optimization problem. Our method offers several practical advantages: it can encode the degree of belief in ML and CL constraints; it guarantees to lower-bound how well the given constraints are satisfied using a user-specified threshold; it can be solved deterministically in polynomial time through generalized eigendecomposition. Furthermore, by inheriting the objective function from spectral clustering and encoding the constraints explicitly, much of the existing analysis of unconstrained spectral clustering techniques remains valid for our formulation. We validate the effectiveness of our approach by empirical results on both artificial and real datasets. We also demonstrate an innovative use of encoding large number of constraints: transfer learning via constraints.     

A particle filter via constrained sampling for nonlinear dynamic systems

This article is concentrated on the particle filtering problem for nonlinear systems with nonlinear equality constraints. Considering the constraint information incorporated into filters can improve the state estimation accuracy, we propose an adaptive constrained particle filter via constrained sampling. First, in order to obtain particles drawn from the constrained important density function, we construct and solve a general optimization function theoretically fusing equality constraints and the importance density function. Furthermore, to reduce the computation time caused by the number of particles, the constrained Kullback‐Leiler distance sampling method is given to online adapt the number of particles needed for state estimation. A simulation study in the context of road‐confined vehicle tracking demonstrates that the proposed filter outperforms the typical constrained ones for equality constrained dynamic systems.     

Tight complexity analysis of the relocation problem with arbitrary release dates

The paper considers makespan minimization on a single machine subject to release dates in the relocation problem, originated from a resource-constrained redevelopment project in Boston. Any job consumes a certain amount of resource from a common pool at the start of its processing and returns to the pool another amount of resource at its completion. In this sense, the type of our resource constraints extends the well-known constraints on resumable resources, where the above two amounts of resource are equal for each job. In this paper, we undertake the first complexity analysis of this problem in the case of arbitrary release dates. We develop an algorithm, based on a multi-parametric dynamic programming technique (when the number of parameters that undergo enumeration of their values in the DP-procedure can be arbitrarily large). It is shown that the algorithm runs in pseudo-polynomial time when the number m of distinct release dates is bounded by a constant. This result is shown to be tight: (1) it cannot be extended to the case when m is part of the input, since in this case the problem becomes strongly NP-hard, and (2) it cannot be strengthened up to designing a polynomial time algorithm for any constant m>1, since the problem remains NP-hard for m=2. A polynomial-time algorithm is designed for the special case where the overall contribution of each job to the resource pool is nonnegative. As a counterpart of this result, the case where the contributions of all jobs are negative is shown to be strongly NP-hard.     

Parallel matheuristics for the discrete unit commitment problem with min‐stop ramping constraints

The discrete unit commitment problem with min‐stop ramping constraints optimizes the daily production of thermal power plants, subject to an operational reactivity of thermal units in a 30‐minute delay. Previously, mixed integer programming (MIP) formulations aimed at an exact optimization approach. This paper derives matheuristics to face the short time limit imposed by the operational constraints. Continuous relaxations guide the search for feasible solutions exploiting tailored variable fixing strategies. Parallel matheuristics are derived considering complementary strategies in parallel. Tests were performed on more than 600 real‐life instances. Our parallel matheuristic provides high‐quality solutions and outperforms the MIP approach in the time limits imposed by the industrial application. This paper illustrates a special interest for matheuristics in industrial highly constrained problems: many tailored neighborhood searches can be derived from an MIP formulation, and their combination in a parallel scheme improves the solution quality as well as the consistency of the heuristic.     

约束预测控制器设计的新方法

Using the framework of predictive control algorithms and the analysis results of unconstrained predictive control systems, the desired pole placement is achieved by the coefficient mapping between the characteristic polynomials of the closed-loop system and the open-loop plant. The designed control law can not only ensure the dynamical performance of the closed-loop system, but also provide plentiful degrees of freedom to satisfy input-output constraints. Based on the theory of invariant set, this paper derives some sufficient conditions for the satisfaction of constraints with these degrees of freedom and presents an approach to design corresponding constrained controller.The constrained controller with performance guarantee can be designed off-line. Furthermore, it has convenient on-line computation and satisfies all constraints. A simulation example is presented to illustrate the proposed approach.     

An integrated model for strategic supply chain design: Formulation and ABC-based solution approach

This study develops a mixed integer nonlinear programming (MINLP) model to design supply chains. In view of the limitations of many available strategic supply chain design models, this model involves three major supply chain stages, including procurement, production, and distribution, and their interactions; it takes into account bill of materials constraints for modeling complex supply chain inter-relationships. In addition, in accordance with the fact that companies nowadays develop product families, our model addresses multi-product supply chain design to respond to diverse customer requirements. Recognizing their importance, this study identifies and formulates constraints related to facility pairwise relationships and supplier priority along with the classical constraints from the available literature. To efficiently solve such a highly constrained, large scale MINLP model, we develop an approach based on an artificial bee colony (ABC) algorithm. Bicycle design and production is used to demonstrate the potential of the MINLP model for designing supply chains and the performance of the ABC-based solution approach in solving the model. The proposed model and solution approach can be considered as two fundamental components of an expert system in the broad sense. Thus, this study is expected to stimulate more future research on the development of practical expert systems for designing supply chains.     

Approximate optimization of systems with high-dimensional uncertainties and multiple reliability constraints

A novel approach is proposed to solve reliability-based optimization (RBO) problems where the uncertainty dimension can be large and where there may be many reliability constraints. The basic idea is to transform all reliability constraints in the target RBO problem into non-probabilistic ordinary ones by a pilot analysis. It will be shown that such a pilot analysis only requires a single run of the modified subset simulation (called the parallel subset simulation) regardless the number of the reliability constraints. Once the reliability constraints are approximated by the ordinary ones, the RBO problem can be solved as if it is an ordinary optimization problem. The resulting optimal solution should be approximately feasible, and the corresponding objective function value is minimized under the approximate constraints. Three numerical examples are investigated to verify the proposed novel approach. The results show that the approach may be capable of finding approximate solutions that are usually close to the actual solution of the target RBO problem.     

An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem

We present an optimal solution procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. In this problem, we assume the constrained renewable resources are limited to very expensive equipments and machines that are used in other projects and are not available in all periods of time of a project. In other words, for each resource, there is a dictated ready date as well as a due date such that no resource can be available before its ready date but the resources are permitted to be used after their due dates by paying penalty cost depending on the resource type. We also assume that only one unit of each resource type is available and no activity needs more than it for execution. The objective is to determine a schedule with minimal total weighted resource tardiness penalty costs. For this purpose, we present a branch-and-bound algorithm in which the branching scheme starts from a graph representing a set of conjunctions (the classical finish-start precedence constraints) and disjunctions (introduced by the resource constraints). In the search tree, each node is branched to two child nodes based on the two opposite directions of each undirected arc of disjunctions. Selection sequence of undirected arcs in the search tree affects the performance of the algorithm. Hence, we developed different rules for this issue and compare the performance of the algorithm under these rules using a randomly generated benchmark problem set.     

Evolutionary resource assignment for workload-based production scheduling

In this paper, we propose an evolutionary method with a simulation model for scheduling jobs including operations specified in terms of workload rather than processing time. It is suggested that processing times should be determined according to the number of assigned resources rather than the workload. The simulation model is used to estimate the result of resource allocation in a time horizon based on preselected rules. The evolutionary methods improve a production schedule in terms of compliance with due dates by selecting an alternative resource allocation rule and changing timing constraints. The results of computational experiments show that compliance with due dates improved by as much as 30 % under the modified production schedule over the initial schedule.