带有分批费用的容量有界的单机平行分批排序问题

考虑的问题是在添加工资费用或包装费用等附加的分批费用下,如何使单机平行分批中总完工时间和分批费用之和达到最小.首先我们假定工件和批处理机都在零时刻到达,工件被成批地进行加工,一旦开始加工就不允许中断,每批的加工时间等于该批中最大的加工时间,而且假设每分一批都产生一个分批费用.然后对具有m个不同的加工时间,批容量有界且为固定值b的情形下目标函数为∑C_j与分批费用之和这一排序问题,利用动态规划的方法给出了多项式时间算法,时间界为O(b²m2m²222^m).     

Optimizing cost flows by edge cost and capacity upgrade

We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost.

The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ,>0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+δ and 1+, respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/(δ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities.     

基于遗传算法的多因素证券组合投资决策模型

基于 APT理论 ,在不允许卖空、并考虑交易成本的情况下 ,本文建立了多因素证券组合投资决策模型 ,然后利用遗传算法研究了模型的求解     

Prophet inequalities for cost of observation stopping problems

Comparisons are made between the expected gain of a prophet (an observer with complete foresight) and the maximal expected gain of a gambler (using only non-anticipating stopping times) observing a sequence of independent, uniformly bounded random variables where a non-negative fixed cost is charged for each observation. Sharp universal bounds are obtained under various restrictions on the cost and the length of the sequence. For example, it is shown for X₁, X₂, … independent, [0, 1]-valued random variables that for all c ≥ 0 and all n ≥ 1 that E(max_{1 ≤ j ≤ n}(X_j − jc)) − sup_{t Tn} E(X_t − tc) ≤ 1/e, where T_n is the collection of all stopping times t which are less than or equal to n almost surely.     

Delay-Dependent Criterion for Guaranteed Cost Control of Neutral Delay Systems

In this article, the guaranteed cost control problem for a class of neutral delay systems is investigated. A linear--quadratic cost function is considered as a performance measure for the closed-loop system. Based on the Lyapunov method, delay-dependent criteria, which are expressed in terms of matrix inequalities, are proposed to guarantee the asymptotic stability of the system. The matrix inequalities can be solved easily by various efficient optimization algorithms.     

基于智能化信息处理的建筑工程造价短期预测

提出了一种新的基于智能化信息处理的建筑工程造价短期预测模型.该模型首次利用数据的高阶统计信息,提出了改进独立分量分析技术.通过构建适用于建筑工程造价的属性重构空间,挖掘出表征能力更强的造价独立属性,用于神经网络的学习和训练,从而建立了全新的建筑工程造价短期预测智能模型.该模型通过发挥独立分量分析强大的信号分离能力,增强了神经网络的学习效率,提高了预测精度.实例数据验证了文中所建模型的有效性.     

遗传算法求解带容量限制的最小费用流问题

研究了带容量限制的带固定费用和可变费用的最小费用流问题,发现该问题是混合0-1整数规划问题,不存在多项式算法.在研究了最优解的结构后,结合最优解的结构特点为之设计了遗传算法,然后构造了一个100个节点的特殊网络,用计算机做了100例计算,验证了该算法具有很好的近似比和很快的收敛速度.     

On computing average cost optimal policies with application to routing to parallel queues

The Approximating Sequence Method for computation of average cost optimal stationary policies in denumerahle state Markov decision chains, introduced in Sennott (1994), is reviewed. New methods for verifying the assumptions are given. These are useful for models with multidimensional state spaces that satisfy certain mild structural properties. The results are applied to four problems in the optimal routing of packets to parallel queues. Numerical results are given for one of the models.     

Zero-sum stochastic games with unbounded costs: Discounted and average cost cases

Zero-sum stochastic games with countable state space and with finitely many moves available to each player in a given state are treated. As a function of the current state and the moves chosen, player I incurs a nonnegative cost and player II receives this as a reward. For both the discounted and average cost cases, assumptions are given for the game to have a finite value and for the existence of an optimal randomized stationary strategy pair. In the average cost case, the assumptions generalize those given in Sennott (1993) for the case of a Markov decision chain. Theorems of Hoffman and Karp (1966) and Nowak (1992) are obtained as corollaries. Sufficient conditions are given for the assumptions to hold. A flow control example illustrates the results.     

Optimal allocation and processing time decisions on non-identical parallel CNC machines: ϵ-constraint approach

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. In this paper, we deal with making optimal machine-job assignments and processing time decisions so as to minimize total manufacturing cost while the makespan being upper bounded by a known value, denoted as ?-constraint approach for a bicriteria problem. We then give optimality properties for the resulting single criterion problem. We provide alternative methods to compute cost lower bounds for partial schedules, which are used in developing an exact (branch and bound) algorithm. For the cases where the exact algorithm is not efficient in terms of computation time, we present a recovering beam search algorithm equipped with an improvement search procedure. In order to find improving search directions, the improvement search algorithm uses the proposed cost bounding properties. Computational results show that our lower bounding methods in branch and bound algorithm achieve a significant reduction in the search tree size that we need to traverse. Also, our recovering beam search and improvement search heuristics achieve solutions within 1% of the optimum on the average while they spent much less computational effort than the exact algorithm.