New Computational Results with a Dynamic Programming Approach for Product Selection and Supermarket Shelf-Space Allocation

This study reports on new computational results relating to a dynamic programming approach that optimally selects among a given set of products and allocates integer shelf-space units to the products in supermarkets. The computational results are reported for large problems that have been solved on an IBM-PC AT microcomputer.     

A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints

Knapsack constraints are a key modeling structure in constraint programming. These constraints are normally handled with simple bounding arguments. We propose a dynamic programming structure to represent these constraints. With this structure, we are able to achieve hyper-arc consistency, to determine infeasibility before all variables are set, to generate all solutions quickly, and to provide incrementality by updating the structure after domain reduction. Testing on a difficult set of multiple knapsack instances shows significant reduction in branching.     

投资组合模型的分式规划解法

以E-SV风险测度为基础提出了组合证券投资决策的效用函数,并建立了基于分式规划的投资组合选择模型,利用变换,把求解分式规划的问题转化为求解非分式规划问题。     

A Dynamic Programming Approach for Approximate Optimal Control for Cancer Therapy

In the last 15 years, tumor anti-angiogenesis became an active area of research in medicine and also in mathematical biology, and several models of dynamics and optimal controls of angiogenesis have been described. We use the Hamilton–Jacobi approach to study the numerical analysis of approximate optimal solutions to some of those models earlier analysed from the point of necessary optimality conditions in the series of papers by Ledzewicz and Schaettler.     

A Dynamic Programming Approach to the Three-machine Scheduling Problem

The three-machine scheduling problem, in which a number of jobsare to be sequenced for processing in the same order on eachof three machines so that the total elapsed time to completethe work is minimized, is formulated as a dynamic program. Aprocedure is developed which reduces the problem to one of evaluatinga subset of the total possible sequences. Some illustrativeexamples are given and the efficiency of the procedure discussedover a number of problems.     

Dynamic Programming Formulation of the Redundancy Allocation Problem

Dynamic programming formulation for obtaining the optimum number of redundancies at each stage in a system is explained in detail. It is also emphasized and illustrated by examples, that the ‘summation’ form of functional equations, as suggested in the paper, provide a faster solution to an otherwise computationally voluminous method.     

多维多目标模糊优选动态规划及其在资源分配中的应用

将目前所研究的一维模糊优选动态规划扩展为多维模糊优选动态规划。在求解多维多阶段问题时,采用遗传算法与模糊动态规划法相结合进行求解,保证了优化变量的全局最优性。在其中权系数的处理中,本文采用了主客观综合评定的方法,保证了数据的合理性及准确性。并且文中用此方法解决了多维多阶段多目标的资源分配问题。     

An Optimum Solution for One-Dimensional Slitting Problems: A Dynamic Programming Approach

One-dimensional slitting problems are often encountered in textile, paper or sheet-metal industries where a roll of this product needs to be divided into various narrower-width rolls. The rolls are slit into pieces such that the total value of the sale is maximized depending on the width and the number of defects in the sheet. As the width of a piece increases, the value of the piece increases also, but on the other hand, the number of defects in the piece increases as well, causing reduction in its value. Based on these constraints, a dynamic programming formulation is framed so as to maximize the total value of the sale. Computational complexity with a numerical example is discussed to demonstrate how the procedure works.     

警力分配问题中的模糊优选动态规划法

根据市区公安分局基层警力的分配问题的特点,将模糊优选理论与动态规划法相结合建立了多维多目标模糊优选动态规划模型,用此模型对警力进行合理分配,以得到最优警力分配方案,为公安决策者在警力分配问题中提供科学的理论依据.     

A Dynamic Programming Approach to Determine Optimal Manpower Recruitment Policies

The manpower planning models available in the literature have dealt with how changes take place in a manpower planning system, under various operating and policy constraints. However, none of these models has identified the manpower system costs. In this paper we have identified various manpower system costs. Further, we have developed a manpower planning model with the objective of minimizing the manpower system costs. The model has been found to be analogous to the Wagner-Whitin model in production/inventory management. A numerical example has been given to illustrate the model.     

Integer Fuzzy Programming Approach in Bi-objective Selective Maintenance Allocation Problem

An attempt has been made to obtain a compromise allocation based on maximization of individual reliabilities of repairable and replaceable components with in the subsystems, using the information of failed and operational components and a non linear cost function with fixed budget. A solution algorithm of fuzzy programming technique is used to solve the Bi-Objective Selective Maintenance Allocation Problem (BSMAP). Also, the problem has been solved by two other suggested methods; “Weighted Criterion Technique” and “Desirability Function Technique”. A numerical example is also presented to illustrate the computational details.     

适应编程需要的一种动态规划模型解法

由计算机软件编程需要出发,对库存管理中的一种动态规划方法进行了讨论,推导出了统一规范表达的允许状态集合和允许决策集合,并由此给出了计算程序框图,为计算机处理类似问题提供了依据。     

A Dynamic Programming Model for Pig Production

The feeding policy of a pig production unit affects both the cost of production and the weight and carcase composition of the pigs produced. Since the market value of the pigs produced is determined by the weight and composition of the carcase, feeding policy has a major influence on the economic performance of the unit. In order to evaluate possible feeding policies, the effect of feed intake on both the weight and the body composition of the growing pig must be known, and since an optimal policy will involve using least cost rations, it must be possible to determine the least cost rations to produce liveweight gains of specified body composition. A dynamic programming model to determine the optimal feeding policy to produce pigs of specified weight and carcase composition is developed using a published pig growth model which allows the formulation of the required least cost rations, and the use of this dynamic programming model is illustrated.     

求解多层线性规划的模糊规划法

本文用模糊集理论中的隶属函数描述多层线性规划的各层目标,在第一层给定最小满意水平下,通过求解相应层次的模糊规划来确定各层的最小满意度,从而最终得到问题的一个满意解。提出的方法只需求解一系列线性规划问题,具有较好的计算复杂性和可行性,最后的算例进一步验证了方法的有效性。     

一种可用于资金分配的线性规划模型

本运用DEA方法,给出了一种能够用来进行资金分配决策的线性规划模型,并证明了其最优解的存在性。     

带时间窗口的超市物流配送不确定规划模型

主要研究了不确定环境下带时间窗口的超市物流配送问题。假设超市的日需求量是不确定变量,在配送过程中车辆的行驶时间也为不确定变量。为了最小化配送过程中车辆行驶时间,建立了不确定机会约束模型。然后应用不确定变量的运算法则对模型进行等价转化,并为求解模型设计了算法。最后给出了一个数值算例来说明模型的实际应用。     

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach

This paper addresses the problem of virtual circuit switching in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our solutions are based on the rapidly mixing properties of random walks on expander graphs. In the static version of the problem an algorithm is required to route a path between each of K pairs of vertices so that no edge is used by more than g paths. A natural approach to this problem is through a multicommodity flow reduction. However, we show that the random walk approach leads to significantly stronger‐results than those recently obtained by Leighton and Rao [Proc. of 9th International Parallel Processing Symposium, 1995] using the multicommodity flow setup. In the dynamic version of the problem connection requests are continuously injected into the network. Once a connection is established it utilizes a path (a virtual circuit) for a certain time until the communication terminates and the path is deleted. Again each edge in the network should not be used by more than g paths at once. The dynamic version is a better model for the practical use of communication networks. Our random walk approach gives a simple and fully distributed solution for this problem. We show that if the injection to the network and the duration of connection are both controlled by Poisson processes then our algorithm achieves a steady state utilization of the network which is similar to the utilization achieved in the static case situation. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 87–109, 1999     

An Approach to Optimal Recruitment and Transition Strategies for Manpower Systems using Dynamic Programming

In this paper, concepts of dynamic programming are used within a discrete time Markovian model for the development of a graded population. Optimal recruitment and transition patterns are determined by minimizing expected discrepancies between actual states and preferred goals.     

Time Optimal Path Planning for Industrial Robots: A Dynamic Programming Approach Considering Torque Derivative and Jerk Constraints

This paper presents a dynamic programming approach for calculating time optimal trajectories for industrial robots, subject to various physical constraints. In addition to path velocity, motor torque, joint velocity and acceleration constraints, the present contribution also shows how to deal with torque derivative and joint jerk limitations. First a Cartesian path for the endeffector is defined by splines using Bernstein polynomials as basis functions and is parameterized via a scalar path parameter. In order to compute the belonging quantities in configuration space, inverse kinematics is solved numerically. Using this and in combination with the dynamical model, joint torques as well as their derivatives can be constrained. For that purpose the equations of motion are calculated with the help of the Projection Equation. As a consequence of the used optimization problem formulation, the dynamical model as well as the restrictions have to be transformed to path parameter space. Due to the additional consideration of jerk and torque derivative constraints, the phase plane is expanded to a phase space. The parameterized restrictions lead to feasible regions in this space, in which the optimal solution is sought. Result of the optimization is the time behavior of the path parameter and subsequently the feed forward torques for the optimal motion on the spatial path defined by previously mentioned splines. Simulation results as well as experimental results for a three axes industrial robot are presented. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

采购量分配决策模糊规划模型

供应商对形成企业的竞争力起着关键性的作用。采购决策中,采购商需要决策两方面的问题:应该选择哪些供应商以及在每一供应商应该采购多少。本文考虑了多目标性和目标的模糊性,同时为供应商选择和采购量分配提出了一个集成的决策模型。最后,通过一个算例阐释了该模型。