Dynamic programming with Pareto sets

Under study is the problem of optimal allocation of a resource, and a dynamic programming scheme is proposed for its solution. Instead of the recurrent equations, the stepwise computation of the Pareto-optimal points is used on the plane of values of the target function and resource. Some examples demonstrate the efficiency of this approach.     

Optimal response against bioterror attack on airport terminal

We consider a potential bioterror attack on an airport. After the attack is identified, the government is faced with the problem of how to allocate limited emergency resources (human resources, vaccines, etc.) efficiently. The government is assumed to make a one-time resource allocation decision. The optimal allocation problem is discussed and it is shown how available information on the number of infected passengers can be incorporated into the model. Estimation for parameters of the cost function (number of deaths after the epidemic is over) is provided based on known epidemic models. The models proposed in the paper are demonstrated with a case study using real airport data.     

On finding an envy-free Pareto-optimal division

This paper describes an algorithm to find an (α-)envy-free Pareto-optimal division in the case of a finite number of homogeneous infinitely divisible goods and linear utility functions. It is used to find an allocation in the classical cake division problem that is almost Pareto-optimal and α-envy-free.     

Product development resource allocation with foresight

Shortening project duration is critical to product development project success in many industries. As a primary driver of progress and an effective management tool, resource allocation among development activities can strongly influence project duration. Effective allocation is difficult due to the inherent closed loop flow of development work and the dynamic demand patterns of work backlogs. The Resource Allocation Policy Matrix is proposed as a means of describing resource allocation policies in dynamic systems. Simple system dynamics and control theoretic models of resource allocation in a product development context are developed. The control theory model is used to specify a foresighted policy, which is tested with the system dynamics model. The benefits of foresight are found to reduce with increasing complexity. Process concurrence is found to potentially reverse the impact of foresight on project duration. The model structure is used to explain these results and future research topics are discussed.     

A note ‘On a single machine-scheduling problem with separated position and resource effects’

This note concerns the paper [Janiak A, Kovalyov MY, Lichtenstein M. On a single machine-scheduling problem with separated position and resource effects. Optimization; 2013. doi:10.1080/02331934.2013.804077], which presents an analysis, a counterexample and a pseudocode related with our proof of optimality for a resource allocation algorithm given in [Rudek A, Rudek R. A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models. Comput. Math. Appl. 2011;62:1870–1878]. We show that the discussed analysis is based only on one part of our proof omitting its integral second part, which is the source of misunderstanding. The considered counterexample is applied for an algorithm, which was not the method presented in our paper, whereas our algorithm provides the correct result for the mentioned counterexample. The provided pseudocode of the resource allocation algorithm, which is presented as the correct method, is a pseudocode of the algorithm described in our paper. Therefore, we show that the results presented in our paper are correct.     

Structural properties of the optimal resource allocation policy for single-queue systems

This paper studies structural properties of the optimal resource allocation policy for single-queue systems. Jobs arrive at a service facility and are sent one by one to a pool of computing resources for parallel processing. The facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker allocates the servers dynamically to the facility. We consider two models: a limited resource allocation model, where the allocation of resources can only be changed at the start of a new service, and a fully flexible allocation model, where the allocation of resources can also change during a service period. In these two models, the objective is to minimize the average utilization costs whilst satisfying the time constraint. To this end, we cast these optimization problems as Markov decision problems and derive structural properties of the relative value function. We show via dynamic programming that (1) the optimal allocation policy has a work-conservation property, and (2) the optimal number of servers follows a step function with as extreme policy the bang-bang control policy. Moreover, (3) we provide conditions under which the bang-bang control policy takes place. These properties give a full characterization of the optimal policy, which are illustrated by numerical experiments.     

软件模块测试中的动态资源分配问题

为有效利用测度过程中投入的测试资源,提高测试效率,本文考虑将测试过程为多个阶段并为各个阶段动态分配测试资源的方法,为此提出两种动态分配测试资源模型,当测试资源总数一定时,测试约束时各软件模块中剩余错误平均数量小的模型;当给定测试约束时各软件模块中剩余错误平均数要达到的预定指标时,所用的测试资源最少的模型。     

具有凸资源约束的单机指数学习效应问题

研究在所有工件的正常加工时间均相同的情况下具有指数学习效应和凸资源约束的单机排序问题.给出了两种模型:在资源消耗总费用有限的情况下,以工件的最大完工时间为目标函数;在工件的最大完工时间有限的情况下,以资源消耗总费用为目标函数.求两种模型下的最优排序和最优资源分配,使得目标函数最小.证明这两个问题都是多项式时间可解的,并给出了相应的算法.     

Simple models for control of epidemics

This study considers the problem of resource allocation between one or several epidemics by reference to a model involving both the stochastic and the geographical nature of the spread of the disease. In the simplest models each epidemic spreads amongst a single line of populations and is controlled to minimize the expected number infected. For these we find that the optimal policy is to treat the population which is immediately at risk, and that if there is more than one epidemic it is optimal to treat the fastest moving epidemics first. Some more realistic models are also briefly discussed.     

Quasiconcave vector maximization: Connectedness of the sets of Pareto-optimal and weak Pareto-optimal alternatives

We study the sets of Pareto-optimal and weakly Pareto-optimal solutions to a vector maximization problem defined by a continuous vector-valued quasiconcave criterion functionf and a closed convex set of alternativesS. IfS is compact, it is shown that the set of weakly Pareto-optimal alternatives is connected, but that the set of Pareto-optimal alternatives is not necessarily connected. However, the set of Pareto optima is shown to be connected for some important subclasses of quasiconcave functions. We also provide some reasonable conditions under which the compactness assumption onS may be relaxed and connectedness maintained.     

Classification of two-person ordinal bimatrix games

The set of possible outcomes of a strongly ordinal bimatrix games is studied by imbedding each pair of possible payoffs as a point on the standard two-dimensional integral lattice. In particular, we count the number of different Pareto-optimal sets of each cardinality; we establish asymptotic bounds for the number of different convex hulls of the point sets, for the average shape of the set of points dominated by the Pareto-optimal set, and for the average shape of the convex hull of the point set. We also indicate the effect of individual rationality considerations on our results. As most of our results are asymptotic, the appendix includes a careful examination of the important case of 2×2 games.Supported by the Program in Discrete Mathematics and its Applications at Yale and NSF Grant CCR-8901484.     

Pareto-optimal reinsurance arrangements under general model settings

In this paper, we study Pareto optimality of reinsurance arrangements under general model settings. We give the necessary and sufficient conditions for a reinsurance contract to be Pareto-optimal and characterize all Pareto-optimal reinsurance contracts under more general model assumptions. We also obtain the sufficient conditions that guarantee the existence of the Pareto-optimal reinsurance contracts. When the losses of an insurer and a reinsurer are both measured by the Tail-Value-at-Risk (TVaR) risk measures, we obtain the explicit forms of the Pareto-optimal reinsurance contracts under the expected value premium principle. For the purpose of practice, we use numerical examples to show how to determine the mutually acceptable Pareto-optimal reinsurance contracts among the available Pareto-optimal reinsurance contracts such that both the insurer’s aim and the reinsurer’s goal can be met under the mutually acceptable Pareto-optimal reinsurance contracts.     

Probabilistic programming models for traffic incident management operations planning

This paper proposes mathematical programming models with probabilistic constraints in order to address incident response and resource allocation problems for the planning of traffic incident management operations. For the incident response planning, we use the concept of quality of service during a potential incident to give the decision-maker the flexibility to determine the optimal policy in response to various possible situations. An integer programming model with probabilistic constraints is also proposed to address the incident response problem with stochastic resource requirements at the sites of incidents. For the resource allocation planning, we introduce a mathematical model to determine the number of service vehicles allocated to each depot to meet the resource requirements of the incidents by taking into account the stochastic nature of the resource requirement and incident occurrence probabilities. A detailed case study for the incident resource allocation problem is included to demonstrate the use of proposed model in a real-world context. The paper concludes with a summary of results and recommendations for future research.     

Optimal resource allocation in survey designs

Resource allocation is a relatively new research area in survey designs and has not been fully addressed in the literature. Recently, the declining participation rates and increasing survey costs have steered research interests towards resource planning. Survey organizations across the world are considering the development of new mathematical models in order to improve the quality of survey results while taking into account optimal resource planning. In this paper, we address the problem of resource allocation in survey designs and we discuss its impact on the quality of the survey results. We propose a novel method in which the optimal allocation of survey resources is determined such that the quality of survey results, i.e., the survey response rate, is maximized. We demonstrate the effectiveness of our method by extensive numerical experiments.     

Scheduling controllable processing time jobs in a deteriorating environment

In many real-life applications, job processing times are a function of the waiting time prior to their execution. In the most general setting, each job comprises of a basic processing time, which is independent of its start time, and a start time-dependent deterioration function. Some common examples of deteriorating systems include fire fighting, pollution containment, and medical treatments. To date, research has focused on scheduling models where the basic processing time of jobs is constant. However, job processing times are often controllable through the allocation of a limited non-renewable resource. We study a single-machine setting that combines these two models under the assumptions of general linear deterioration and convex resource functions. We develop a polynomial time solution for minimizing the makespan. For the total flowtime criterion, we compute the optimal resource allocation policy for a given job instance and show that the sequencing problem is at least as hard as the case with non-controllable jobs. We follow by discussing the properties of several special cases.     

Identification of Pareto-efficient facets in data envelopment analysis

In Data Envelopment Analysis (DEA), identification of the Pareto-efficient frontier of an empirical production possibility set is a prerequisite step toward determining rates of change of outputs with changes in inputs along its piecewise linear facets. These rates of change, which will be different on different facets, have important economic and managerial implications in trade-off analysis, forecasting and resource allocation. Accurate and complete identification of the component members of each facet remains an open question. Such identification is important in certain procedures for determining these rates of change. This paper develops three modifications to the pivoiing criteria of the simplex algorithm, commonly used to solve DEA problems, as alternative strategies for more completely identifying facet members of the Pareto-optimal frontier common to several production possibility sets in DEA. Experimental results from implementing these strategies are presented.     

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。     

Optimal control policies for resource allocation in an activity network

In the paper a class of project-scheduling problems concerning the allocation of continuously divisible resources is considered. It is assumed that performing speeds of activities are continuous functions of the resource amount, and that the initial and terminal states of activities are known. For such mathematical models of project activities the problem of time-optimal resource allocation under instantaneous and integral constrains on a resource, and the problem of cost-optimal resource allocation with fixed project duration are formulated and a general solution concept is proposed. Necessary and sufficient conditions for the existence of a solution in particular cases are derived and properties of optimal schedules are given. The control policies for resource allocation are constructed for the example of the cost-optimal problem.     

水资源配置方案综合评价中的信息损失测度研究

水资源配置的多属性特征使得在方案综合评价中依据不同的聚合方法,能够获得不完全一致的方案排序结果。本文从水资源配置方案评价的决策矩阵及方案排序结果中的信息量大小入手,利用信息熵理论和斯皮尔曼等级相关系数提出衡量水资源配置方案综合评价中信息损失的香农斯皮尔曼测度。并构造由2种权重(熵权法权重、证据理论权重)与3种评价模型(简单加权法、模糊优选法、TOPSIS)组合而成的6种综合评价模型。最后,将香农斯皮尔曼测度运用到天津市水资源配置方案综合评价过程中的信息损失的衡量,并与文献中的综合评价模型所得结果进行比较。结果表明,采用证据理论权重-模糊优选评价模型所得评价结果的绝对信息损失和相对信息损失最小。通过水资源配置方案综合评价中的信息损失测度研究,能够使得水资源配置方案综合评价过程更加透明,并为决策部门选取理想的水资源配置方案综合评价方法提供决策支持。     

Optimal resource allocation across related channels

In this paper, we consider resource allocation strategies of a limited resource across two related channels in a multi-period setting. We study a stochastic control problem where the objective is to determine the optimal limited resource allocation policy across two related channels and optimal transshipment policy between these two channels. We characterize some structural results of the optimal resource allocation policy and show that it is determined by three monotone curves.