Optimal resource allocation in new product development projects: a control-theoretic approach

Considers problems motivated by the dynamic allocation of limited heterogeneous resources in new product development (NPD) projects. The interchangeability of resources and simultaneous resource sharing are defining characteristics of NPD processes. A continuous flow model is introduced that incorporates these features. For problems without activity precedence constraints, a linear program is presented which yields the minimum completion time for all activities. A dynamic, rule-based algorithm is shown to be optimal for two resources processing a multiple-activity arrival stream. For problems with precedence constraints, some special cases are solved, and structural properties of the class of optimal controls for the general problem are discussed.     

基于关键路径法的软件过程控制模型

为了增强软件过程控制能力,保障软件产品质量,提出一种基于关键路径法的软件过程控制模型。该模型以过程活动间的网络拓扑结构为基础,在确保工期和关键路径上资源需求的条件下,控制其他活动的开始时间,使得过程中所需的总资源耗费较少,且在此耗费下各活动开始时间较早。在最优耗费的约束下,还给出了一个基于资源竞争链的浮动信息更新算法,以便更新各活动的浮动信息。最后,用实例验证了所提模型的有效性和可行性。     

Scheduling of a limited communication channel for optimal control

In this paper a method for optimal off-line scheduling of a limited resource used for control purposes is presented. For various reasons, real-time communication channels are prone to have limited bandwidth. To overcome this obstacle, the rate of actions must be chosen accordingly at design time, both with respect to the limitation of the resource and to control performance. A resulting off-line schedule implements the rate of actions as a repetitive sequence of communication instants. Periodic control theory is used to define a cost functional for LQ-control, that measures the performance of a sampled-data system in relation to a desired continuous time performance. In contrast to uniform sampling, the communication sequence is here allowed to be time-varying. This approach results in a complex combinatorial optimization problem, whose solution gives the optimal off-line schedule, i.e., the sequence in which the actions should take place. The optimization problem is solved by a neighborhood search method where a heuristic method is used to generate initial guesses close to the optimum. The optimal schedule is typically such that the sampling is non-uniform, but the resulting LQ-control law is time-varying and takes this non-uniform sampling into account.     

Iterative Learning Control for Discrete-time Stochastic Systems with Quantized Information

An iterative learning control (ILC) algorithm using quantized error information is given in this paper for both linear and nonlinear discrete-time systems with stochastic noises. A logarithmic quantizer is used to guarantee an adaptive improvement in tracking performance. A decreasing learning gain is introduced into the algorithm to suppress the effects of stochastic noises and quantization errors. The input sequence is proved to converge strictly to the optimal input under the given index. Illustrative simulations are given to verify the theoretical analysis.      

An efficient optimal algorithm for the quantity discount problem in material requirement planning

An optimal algorithm based on branch-and-bound approach is presented in this paper to determine lot sizes for a single item in material requirement planning environments with deterministic time-phased demand and constant ordering cost with zero lead time, where all-units discounts are available from vendors and backlog is not permitted. On the basis of the proven properties of optimal order policy, a tree-search procedure is presented to construct the sequence of optimal orders. Some useful fathom rules have been proven, which make the algorithm very efficient. To compare the performance of this algorithm with the other existing optimal algorithms, an experimental design with various environments has been developed. Experimental results show that the performance of our optimal algorithm is much better than the performance of other existing optimal algorithms. Considering computational time as the performance measure, this algorithm is considered the best among the existing optimal algorithms for real problems with large dimensions (i.e. large number of periods and discount levels).     

Perturbation analysis of stochastic fluid models with respect to the fluid arrival process

The deployment of network applications (e.g., multimedia and other real time applications) has put extra pressure on network scarce resources (bandwidth and buffers) thus generating a need for effective resource allocation and management. In this paper we adopt a stochastic fluid model (SFM) framework and derive sensitivity estimators for three performance measures of interest (workload, throughput and loss volume) with respect to the fluid inflow process parameters. The motivation is to use the sensitivity estimators for dynamic control and optimisation of the systems performance. Subsequently these estimators are evaluated based on data observed from a single sample path of the discrete-event system and are used to dynamically control the input process to the system allowing the network to work continuously at an optimal or near optimal point. The proposed analysis naturally leads to a distributed algorithm for evaluating the propagation of perturbations in a network (e.g., due to changes in the buffer size of upstream nodes).     

Optimal and asymptotically optimal linear regulators resulting from a one-stage performance index

An optimal control algorithm is derived which minimizes at each time instant the one-stage k-step-ahead performance index for the state-space representation of the CARMA model. Equivalence of the input-output representation in its asymptotic form and in the Clarke-Hastings-James algorithm is proved. Formulae for computing the output and control variances at any time instant for both optimal and asymptotic algorithms are given. The results are illustrated by a numerical example.     

A Decomposition Algorithm for Feedback Min–Max Model Predictive Control

An algorithm for solving feedback min–max model predictive control for discrete-time uncertain linear systems with constraints is presented in this note. The algorithm is based on applying recursively a decomposition technique to solve the min–max problem via a sequence of low complexity linear programs. It is proved that the algorithm converges to the optimal solution in finite time. Simulation results are provided to compare the proposed algorithm with other approaches.     

一种基于服务选取的SBS云资源优化分配方法

获取满足全局优化目标的资源分配策略,是影响云环境中基于服务的软件系统(service-based software system,简称SBS)运行时优化效果的关键.然而,由于SBS内部复杂的业务逻辑关系和云环境中的资源约束,现有分配方法无法得到最优资源分配量.以满足SLA约束和最小化资源成本为目标,根据不同资源状态对应不同组件服务性能的特点,将组件服务可能的资源分配量、相应性能及成本转换为备选逻辑服务集,进而提出了一种云环境中基于服务选取的SBS资源优化分配模型,并设计了一种求解模型的混合遗传算法.算法采用整数编码以提高求解效率,并在选择算子中引入了精英保留策略,从而保证收敛到全局最优解.为提高遗传算法的局部搜索能力、加快收敛速度,以局部搜索策略改进了标准变异算子.实验验证了所提出的资源优化分配模型和求解算法的有效性,并表明:与分支定界法及精英保留策略遗传算法相比,混合遗传算法能够在较大规模的问题上快速获得具有较低资源成本的资源分配策略.     

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.     

Model Predictive Control for Stochastic Resource Allocation

In this paper, we consider a class of stochastic resource allocation problems where resources assigned to a task may fail probabilistically to complete assigned tasks. Failures to complete a task are observed before new resource allocations are selected. The resulting temporal resource allocation problem is a stochastic control problem, with a discrete state space and control space that grow in cardinality exponentially with the number of tasks. We modify this optimal control problem by expanding the admissible control space, and show that the resulting control problem can be solved exactly by efficient algorithms in time that grows nearly linear with the number of tasks. The approximate control problem also provides a bound on the achievable performance for the original control problem. The approximation is used as part of a model predictive control (MPC) algorithm to generate resource allocations over time in response to information on task completion status. We show in computational experiments that, for single resource class problems, the resulting MPC algorithm achieves nearly the same performance as the optimal dynamic programming algorithm while reducing computation time by over four orders of magnitude. In multiple resource class experiments involving 1000 tasks, the model predictive control performance is within 4% of the performance bound obtained by the solution of the expanded control space problem.     

A computational technique for the design of a specific optimal controller

For a linear plant, the optimization of a performance index of integral type, which is quadratic in states and control, results in a control law. This ideal controller, however, must often be replaced by an approximate controller; e.g., due to inaccessible state variables. The input-output relation of such a controller may be specified within some parameters in advance. A specific optimal controller (SOC) is obtained when the parameters are chosen in an optimal manner so as to minimize a performance criterion; for example, the degradation of a performance index. Since these parameters depend on the initial state, the SOC is designed in regard to the worst initial state resulting in the maximum deterioration, which is then minimized by the best parameters. A computational procedure for this design is proposed. An algorithm is constructed and applied to this min-max problem.     

Fixed-structure synthesis of induced-norm controllers

This paper proposes a fixed-structure technique for synthesizing controllers that are optimal with respect to various operator norms. An optimal control problem is developed for each of these operator norms, and necessary conditions for sub-optimal performance are derived. Mixed-norm optimal control problems are also formulated. A continuation algorithm using quasi-Newton corrections is used to compute approximate solutions of the necessary conditions for a sequence of problems whose solutions approach an optimal controller. Optimal controllers with respect to each of the operator norms are synthesized for a 4th-order mass-spring-dashpot system.     

Maintenance policies in markovian deterioration models of parallel unit systems

Markovian deterioration models of parallel unit systems are dealt with. Units of a system are supposed to be of different types, and a state of the system is represented by a vector whose component corresponds to the state of each unit. Therefore all the states of the system are only partially ordered, while they are totally ordered in ordinary markovian deterioration models. It is proved under some conditions that the optimal maintenance policy is a partial control limit policy, which is a generalization of the well-known control limit policy in the ordinary case. An algorithm improving the successive approximation method is proposed for obtaining the optimal policy. A typical case of the model is also discussed.     

Sufficient optimality conditions for discrete automaton-type systems

A discrete system that models the operation of a dynamic automaton with memory is considered. In distinction from the ordinary models of discrete systems, in which the states are changed (switched) at prescribed instants of time, automaton-type systems may change their states at arbitrary instants. Furthermore, the choice of the instants when the automaton “fires” is a control resource and it is subject to optimization. Sufficient optimality conditions for such systems under a limited or unlimited number of switchings are proved. Equations for the synthesis of the optimal closed-loop control are derived. Application of the optimality conditions is illustrated by examples.     

Superposition in efficient robust constrained predictive control

A stabilizing control method, which does not require on-line optimizations, is developed for linear systems with polytopic model uncertainties and hard input constraints. This work is motivated by the constrained robust MPC (CRMPC) approach (IEEE Trans. Automat. Control 45 (2000a) 1765) which adopts the dual mode prediction strategy (i.e. free control moves and invariant set) and minimizes a worst case performance criterion. Based on the observation that, a feasible control sequence for a particular state can be found as a linear combination of feasible sequences for other states, we suggest a stabilizing control algorithm providing sub-optimal and feasible control sequences using pre-computed optimal sequences for some canonical states. The on-line computation of the proposed method reduces to simple matrix multiplication.     

An intelligent search method for project scheduling problems

We develop an approach for implementing a real time admissible heuristic search algorithm for solving project scheduling problems with resource constraints. This algorithm is characterized by the complete heuristic learning process: state selection, heuristic learning, and search path review. The implementation approach is based on the network structure and the activity status of a project; which consists of definition of states, state transition operator, heuristic estimation, and state transition cost. The performance analysis with a benchmark problem shows that, the accumulation of heuristic learning during the search process leads to the re-scheduling of more promising activities, and finds an optimal schedule efficiently.     

A regularization algorithm for singular controls of parabolic systems

A practically convenient method of regularization is proposed to solve an optimal control problem for a parabolic equation with a delta function on its right-hand side. The corresponding regularized analogue is proved to converge to a delta function in a negative space. The differential characteristics of the performance criterion are analyzed. An algorithm for finding the optimal control is developed for a regularized problem. Results from a numerical testing of the algorithm are presented. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 86–94, January–February 2006.     

An optimal line following algorithm

An algorithm is described for optimal following of the lines in digitized TV pictures. Initially, the picture is subjected to an edge detection operation resulting in short edge-line pieces (strokes). The bifurcation points of the lines in the picture are detected on the basis of variances in stroke angles. A mathematical model using graph theoretical concepts is set up on the arrays of strokes (streaks) to be found among the bifurcation points. The model assumes that the streaks will follow the lines of the picture in an optimal way. An algorithm is given which finds the streaks. The correctness of the algorithm is proved in a pure mathematical way. Experiments with on-line TV pictures show the performance of the algorithm.     

桥式吊车系统的伪谱最优控制设计

对于桥式吊车系统的最优控制问题,根据实际的工况要求,性能指标有时不一定是标准的二次形式.同时,在实际的控制问题中,状态和控制输入往往会受到一些边界条件和路径过程中的约束.针对这一问题,本文应用Chebyshev伪谱优化算法来处理,它可以处理状态和控制约束的非线性最优化问题以及一个非标准的目标函数.首先对桥式吊车系统模型进行一系列的坐标变换,将其转变为上三角系统形式的误差模型.然后将桥式吊车最优控制问题转化成具有一系列代数约束的参数优化问题,即非线性规划问题.通过求解离散化后的参数优化问题,得到桥式吊车的最优控制律.本文还给出了Chebyshev伪谱最优解的可行性和一致性分析.最后,在仿真研究中验证该控制器的有效性.