Approximate Dynamic Programming for Stochastic Resource Allocation Problems

A stochastic resource allocation model, based on the principles of Markov decision processes(MDPs), is proposed in this paper. In particular, a general-purpose framework is developed, which takes into account resource requests for both instant and future needs. The considered framework can handle two types of reservations(i.e., specified and unspecified time interval reservation requests), and implement an overbooking business strategy to further increase business revenues. The resulting dynamic pricing problems can be regarded as sequential decision-making problems under uncertainty, which is solved by means of stochastic dynamic programming(DP) based algorithms. In this regard, Bellman’s backward principle of optimality is exploited in order to provide all the implementation mechanisms for the proposed reservation pricing algorithm. The curse of dimensionality, as the inevitable issue of the DP both for instant resource requests and future resource reservations,occurs. In particular, an approximate dynamic programming(ADP) technique based on linear function approximations is applied to solve such scalability issues. Several examples are provided to show the effectiveness of the proposed approach.

Resource Planning and Allocation Problem Under Uncertain Environment

This paper generalizes the classic resource allocation problem to the resource planning and allocation problem, in which the resource itself is a decision variable and the cost of each activity is uncertain when the resource is determined. The authors formulate this problem as a two-stage stochastic programming. The authors first propose an efficient algorithm for the case with finite states.Then, a sudgradient method is proposed for the general case and it is shown that the simple algorithm for the unique state case can be used to compute the subgradient of the objective function. Numerical experiments are conducted to show the effectiveness of the model.

Egalitarian Allocations and the Inverse Problem for the Shapley Value

In a cooperative transferable utilities game, the allocation of the win of the grand coalition is an Egalitarian Allocation, if this win is divided into equal parts among all players. The Inverse Set relative to the Shapley Value of a game is a set of games in which the Shapley Value is the same as the initial one. In the Inverse Set, we determined a family of games for which the Shapley Value is also a coalitional rational value. The Egalitarian Allocation of the game is efficient, so that in the set called the Inverse Set relative to the Shapley Value, the allocation is the same as the initial one, but may not be coalitional rational. In this paper, we shall find out in the same family of the Inverse Set, a subfamily of games with the Egalitarian Allocation is also a coalitional rational value. We show some relationship between the two sets of games, where our values are coalitional rational. Finally, we shall discuss the possibility that our procedure may be used for solving a very similar problem for other efficient values. Numerical examples show the procedure to get solutions for the efficient values.

Using the Simplex Method for a Type of Allocation Problems

In this study we discuss the use of the simplex method to solve allocation problems whose flow matrices are doubly stochastic. Although these problems can be solved via a 0 - 1 integer programming method, H. W. Kuhn [1] suggested the use of linear programming in addition to the Hungarian method. Specifically, we use the existence theorem of the solution along with partially total unimodularity and nonnegativeness of the incidence matrix to prove that the simplex method facilitates solving these problems. We also provide insights as to how a partition including a particular unit may be obtained.

Mathematical Model and Algorithm for the Task Allocation Problem of Robots in the Smart Warehouse

In the smart warehousing system adopting cargo-to-person mode, all the items are stored in the movable shelves. There are some warehouse robots transporting the shelves to the working platforms for completing order picking or items replenishment tasks. When the number of robots is insufficient, the task allocation problem of robots is an important issue in designing the warehousing system. In this paper, the task allocation problem of insufficient warehouse robots (TAPIR) is investigated. Firstly, the TAPIR problem is decomposed into three sub-problems: task grouping problem, task scheduling problem and task balanced allocation problem. Then three sub-problems are respectively formulated into integer programming models, and the corresponding heuristic algorithms for solving three sub-problems are designed. Finally, the simulation and analysis are done on the real data of online bookstore. Simulation results show that the mathematical models and algorithms of this paper can provide a theoretical basis for solving the TAPIR problem.

The Capacitated Location-Allocation Problem in the Presence of <i>k</i>Connections

We consider a capacitated location-allocation problem in the presence of k connections on the horizontal line barrier. The objective is to locate a set of new facilities among a set of existing facilities and to allocate an optimal number of existing facilities to each new facility in order to satisfy their demands such that the summation of the weighted rectilinear barrier distances from new facilities to existing facilities is minimized. The proposed problem is designed as a mixed-integer nonlinear programming model. To show the efficiency of the model, a numerical example is provided. It is worth noting that the global optimal solution is obtained.

Multi-stage attack weapon target allocation method based on defense area analysis

For better reflecting the interactive defense between targets in practical combat scenarios,the basic weapon-target allocation(WTA)framework needs to be improved.A multi-stage attack WTA method is proposed.First,a defense area analysis is presented according to the targets’positions and the radii of the defense areas to analyze the interactive coverage and protection between targets’defense areas.Second,with the coverage status and coverage layer number,a multi-stage attack planning method is proposed and the multi-stage attack objective function model is established.Simulation is conducted with interactive defense combat scenarios,the traditional WTA method and the multi-stage WTA method are compared,and the objective function model is validated with the Monte-Carlo method.The results suggest that if the combat scenario involves interactive coverage of targets’defense areas,it is imperative to analyze the defense areas and apply the multi-stage attack method to weakening the target defense progressively for better combat effectiveness.

Dynamic Promotional Resource Allocation for Segment Specific and Spectrum Effect of Promotion for a Product Line Incorporating Repeat Purchase Behavior

Promotion is an essential element in the marketing mix. It is used by businesses to inform, influence and persuade customers to adopt the products and services they offer. Without promotion, business would be stagnant and lack substantial growth because the brands would have low visibility in the market. Moreover, today’s vast and assorted markets comprise of customers with different needs and varied behavior. So it is rarely possible for companies to satisfy all customers by treating them alike. Thus there arises a need to divide the market into segments having customers with similar traits/characteristics. After identifying appropriate market segments, firms can design differentiated promotional campaigns for each segment. At the same time there can be a mass market promotional campaign that reaches different segments with a fixed spectrum. Also since promotional effort resources are limited, one must use them judiciously. In this paper, we formulate mathematical programming problem under repeat purchase scenario, which optimally allocates mass promotional effort resources and differentiated promotional effort resources across the segments dynamically in order to maximize the overall sales obtained from multiple products of a product line under budgetary and minimum sales aspiration level constraint on each product under consideration in each segment. The planning horizon is divided into multi periods, the adoption pattern of each product in each segment is observed in every subinterval and accordingly promotional effort allocations are determined for the next period till we reach the end of planning period. The optimization model has been further extended to incorporate minimum aspiration level constraints on total sales for each product under consideration from all the segments taken together. The non linear programming problem so formulated is solved using differential evolution approach. A numerical example has been discussed to illustrate applicability of the model.

Shuffled frog leaping algorithm with non-dominated sorting for dynamic weapon-target assignment

The dynamic weapon target assignment(DWTA)problem is of great significance in modern air combat.However,DWTA is a highly complex constrained multi-objective combinatorial optimization problem.An improved elitist non-dominated sorting genetic algorithm-II(NSGA-II)called the non-dominated shuffled frog leaping algorithm(NSFLA)is proposed to maximize damage to enemy targets and minimize the self-threat in air combat constraints.In NSFLA,the shuffled frog leaping algorithm(SFLA)is introduced to NSGA-II to replace the inside evolutionary scheme of the genetic algorithm(GA),displaying low optimization speed and heterogeneous space search defects.Two improvements have also been raised to promote the internal optimization performance of SFLA.Firstly,the local evolution scheme,a novel crossover mechanism,ensures that each individual participates in updating instead of only the worst ones,which can expand the diversity of the population.Secondly,a discrete adaptive mutation algorithm based on the function change rate is applied to balance the global and local search.Finally,the scheme is verified in various air combat scenarios.The results show that the proposed NSFLA has apparent advantages in solution quality and efficiency,especially in many aircraft and the dynamic air combat environment.

基于质量问题统计数据的某型车辆备件配置研究

基于交付用户使用后的某型特种车辆质量问题统计数据,对发生的质量问题进行了分类和分析,梳理出车辆易损件备件清单。最后对该产品备件配置存在的问题进行了探讨并提出了建议,以期对其他产品备件配置提供一定的借鉴。

基于两阶段搜索与动态资源分配的约束多目标进化算法

解决约束多目标优化问题(CMOP)的难点在于平衡目标优化和约束满足的同时兼顾解集的收敛性和多样性。为解决具有大型不可行区域和较小可行区域的复杂约束多目标优化问题,提出一种基于两阶段搜索与动态资源分配的约束多目标进化算法(TSDRA)。该算法在第一阶段通过忽略约束跨越不可行区域;然后在第二阶段通过动态分配两种计算资源协调局部开发和全局探索,兼顾算法的收敛性和多样性。在LIRCMOP和MW系列测试问题上进行的仿真实验结果表明,与四个代表性的算法CMOEA-MS(Constrained Multi-Objective Evolutionary Algorithm with Multiple Stages)、ToP(Two-phase)、PPS(Push and Pull Search)和MSCMO(Multi Stage Constrained Multi-Objective evolutionary algorithm)相比,所提算法在反转世代距离(IGD)和超体积(HV)上得到了更优异的结果。在LIRCMOP系列测试问题上,TSDRA获得了10个最佳的IGD值和9个最佳的HV值;在MW系列测试问题上,TSDRA获得了9个最佳的IGD值和10个最佳的HV值,表明所提算法可以更有效地解决具有大型不可行区域和较小可行区域的问题。

考虑物料装卸点的过道布置问题及改进灰狼算法求解方法

针对制造和服务系统中假定物料装卸点重合以及设施间物流量对称的不足,结合实际生产布局对过道布置问题进行拓展,以最小化物流成本为目标,提出考虑物料装卸点及非对称流量的过道布置问题,并建立混合整数规划模型。根据问题与模型的特征,设计一种改进灰狼算法进行求解,该算法采用双层整数编码生成初始解,通过将收敛因子非线性化、比例权重动态化对原始灰狼算法进行改进。通过融合反向学习机制和种群更新机制进一步扩大搜索解空间,并添加双阈值停止准则降低多余的迭代次数。将该算法与LINGO求解器对5~49不同规模算例的计算结果进行比较,证明了模型的正确性以及算法的有效性。最后,运用该算法对初始过道布置问题进行求解,并与其他算法的求解结果进行比对,进一步证明了所提算法的优越性。

二分图匹配模型下的武器目标分配问题

武器目标分配问题是研究双方交战时,按照一定分配原则将武器分配给多个能造成威胁的对方目标,从而达到最佳打击效果的问题,也是军事运筹学领域经典的组合优化问题。提出了二分图匹配模型下的武器目标分配问题,并建立了相关的数学模型,最后运用结合了贪心策略的Kuhn-Munkres算法对模型进行求解。通过使用随机生成的20个规模不同的实例来测试所提模型与算法的有效性。计算实验结果表明,提出的模型与算法求解精度高、求解速度快,可以满足武器目标分配问题快速做出最优决策的要求。

混合泊位分配与专用泊位租赁的联合优化研究

针对港口同时存在普通泊位与专用泊位的现象,以及班轮公司难以制定合理专用泊位租赁策略的问题,本文提出混合泊位分配问题,并研究与专用泊位租赁的联合优化。以船舶运营成本、货物装卸成本和班轮公司租赁专用泊位成本最小化为目标,建立混合整数规划模型。为方便求解大规模问题,将模型转化为使用两组决策变量分别表示靠泊计划与泊位租赁策略的集划分模型,并设计考虑枚举的列生成算法求解模型。最后,以4家班轮公司在三大港口的船舶数据为基础进行算例测试与灵敏度分析。数值结果表明:本文构建的联合优化模型相较于传统泊位分配问题模型可分别降低28.38%的运营成本和26.25%的总成本;本文设计的算法能够在较短时间内求解300艘船的大规模问题,且相较于传统列生成算法有81.86%的计算速度提升;同时为港口与航运公司协调专用泊位出租价格、制定租赁策略提供建议。

基于鲁棒性模拟的停机位分配问题的数值方法比较

为了提升机场停机坪分配的鲁棒性,针对大型国际机场航班延误常态化对机场运行稳定性的影响,构建了两种整数线性规划模型,并引入爬山算法与大邻域搜索(LNS)元启发式算法进行效能比较。同时,采用Monte Carlo方法对不同目标函数在处理航班冲突时的效果进行评估。测试结果表明LNS算法在提升大型机场停机位分配方案的鲁棒性方面表现卓越,在求解速度和方案质量上均有显著提升。特别是,当以空闲时间的平方作为目标函数时,其效果尤为突出。

SOME EXTENDED KNAPSACK PROBLEMS INVOLVING JOB PARTITION BETWEEN TWO PARTIES

一些新奇应用；背囊问题(KP ) 的实用变化被介绍；构造了，它被提出；从以二人的分离合作游戏从工作的分区在利润分配上在这篇论文开始的一个模型发展了。

Generative Neural Network Based Spectrum Sharing Using Linear Sum Assignment Problems

Spectrum management and resource allocation(RA)problems are challenging and critical in a vast number of research areas such as wireless communications and computer networks.The traditional approaches for solving such problems usually consume time and memory,especially for large-size problems.Recently different machine learning approaches have been considered as potential promising techniques for combinatorial optimization problems,especially the generative model of the deep neural networks.In this work,we propose a resource allocation deep autoencoder network,as one of the promising generative models,for enabling spectrum sharing in underlay device-to-device(D2D)communication by solving linear sum assignment problems(LSAPs).Specifically,we investigate the performance of three different architectures for the conditional variational autoencoders(CVAE).The three proposed architecture are the convolutional neural network(CVAECNN)autoencoder,the feed-forward neural network(CVAE-FNN)autoencoder,and the hybrid(H-CVAE)autoencoder.The simulation results show that the proposed approach could be used as a replacement of the conventional RA techniques,such as the Hungarian algorithm,due to its ability to find solutions of LASPs of different sizes with high accuracy and very fast execution time.Moreover,the simulation results reveal that the accuracy of the proposed hybrid autoencoder architecture outperforms the other proposed architectures and the state-of-the-art DNN techniques.

Strict greedy design paradigm applied to the stochastic multi-armed bandit problem

The process of making decisions is something humans do inherently and routinely,to the extent that it appears commonplace. However,in order to achieve good overall performance,decisions must take into account both the outcomes of past decisions and opportunities of future ones. Reinforcement learning,which is fundamental to sequential decision-making,consists of the following components: 1 A set of decisions epochs; 2 A set of environment states; 3 A set of available actions to transition states; 4 State-action dependent immediate rewards for each action.At each decision,the environment state provides the decision maker with a set of available actions from which to choose. As a result of selecting a particular action in the state,the environment generates an immediate reward for the decision maker and shifts to a different state and decision. The ultimate goal for the decision maker is to maximize the total reward after a sequence of time steps.This paper will focus on an archetypal example of reinforcement learning,the stochastic multi-armed bandit problem. After introducing the dilemma,I will briefly cover the most common methods used to solve it,namely the UCB and εn- greedy algorithms. I will also introduce my own greedy implementation,the strict-greedy algorithm,which more tightly follows the greedy pattern in algorithm design,and show that it runs comparably to the two accepted algorithms.

数字化转型提升企业资本配置效率的机制研究

企业数字化转型具有信息环境改善效应、公司治理完善效应以及融资约束缓解效应,从而能够优化企业的投资决策,促进企业资本配置效率提升。以2007—2020年沪深A股上市公司为样本,采用调节效应模型检验数字化转型对企业资本配置效率的影响,分析发现:数字化转型会增强企业投资水平与投资机会的正相关性,表明数字化转型促进了企业资本配置效率提升;数字化转型对信息不对称程度较高、代理问题较大、融资约束较强企业具有更为显著的资本配置效率提升作用,表明数字化转型能够通过缓解企业的信息不对称、代理问题和融资约束等提升资本配置效率;对于研发强度较高、金融化程度较高、银企关联程度较低、成长期、规模较小的企业,数字化转型具有更为显著的资本配置效率提升作用;数字化转型还可以显著促进企业的会计业绩提升。因此,企业应持续推进数字化转型,并积极改善信息环境、完善公司治理、缓解融资约束,以更好地把握投资机会,提高投资决策质量和资本配置效率。