Fair resource allocation for demands with sharp lower tail inequalities

We consider a fairness problem in resource allocation where multiple groups demand resources from a common source with the total fixed amount. We show that for many common demand distributions satisfying sharp lower-tail inequalities, a natural allocation that provides resources proportional to each group's average demand performs very well. More specifically, this natural allocation is approximately fair and efficient (i.e., it provides near maximum utilization). We also show that, when a small amount of unfairness is allowed, the Price of Fairness (PoF), in this case, is close to 1.     

Dynamic resource allocation: A flexible and tractable modeling framework

This paper presents a binary optimization framework for modeling dynamic resource allocation problems. The framework (a) allows modeling flexibility by incorporating different objective functions, alternative sets of resources and fairness controls; (b) is widely applicable in a variety of problems in transportation, services and engineering; and (c) is tractable, i.e., provides near optimal solutions fast for large-scale instances. To justify these assertions, we model and report encouraging computational results on three widely studied problems – the Air Traffic Flow Management, the Aircraft Maintenance Problems and Job Shop Scheduling. Finally, we provide several polyhedral results that offer insights on its effectiveness.     

Greedy primal-dual algorithm for dynamic resource allocation in complex networks

In Stolyar (Queueing Systems 50 (2005) 401–457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several “commodities.”) Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401–457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples. AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12     

A lexicographic minimax algorithm for multiperiod resource allocation

Resource allocation problems are typically formulated as mathematical programs with some special structure that facilitates the development of efficient algorithms. We consider a multiperiod problem in which excess resources in one period can be used in subsequent periods. The objective minimizes lexicographically the nonincreasingly sorted vector of weighted deviations of cumulative activity levels from cumulative demands. To this end, we first develop a new minimax algorithm that minimizes the largest weighted deviation among all cumulative activity levels. The minimax algorithm handles resource constraints, ordering constraints, and lower and upper bounds. At each iteration, it fixes certain variables at their lower bounds, and sets groups of other variables equal to each other as long as no lower bounds are violated. The algorithm takes advantage of the problem's special structure; e.g., each term in the objective is a linear decreasing function of only one variable. This algorithm solves large problems very fast, orders of magnitude faster than well known linear programming packages. (The latter are, of course, not designed to solve such minimax problems efficiently.) The lexicographic procedure repeatedly employs the minimax algorithm described above to solve problems, each of the same format but with smaller dimension.     

A generalized DEA model for centralized resource allocation

In this paper, we introduced a new generalized centralized resource allocation model which extends Lozano and Villa’s and Asmild et al.’s models to a more general case. In order to uncover the sources of such total input contraction in the generalized centralized resource allocation model, we applied the structural efficiency to further decompose it into three components: the aggregate technical efficiency, the aggregate allocative efficiency and re-transferable efficiency components. The proposed models are not only flexible enough for the central decision-maker to adjust the inputs and outputs to achieve the total input contraction but also identify the sources of such total input contraction, thereby giving rise to an important interpretation and understanding of the generalized centralized resource allocation model. Finally, an empirical example is used to illustrate the approach.     

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.     

Approximation algorithms for dynamic resource allocation

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility.     

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.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Centralized resource allocation with stochastic data

Data Envelopment Analysis (DEA) is a technique based on mathematical programming for evaluating the efficiency of homogeneous Decision Making Units (DMUs). In this technique inefficient DMUs are projected on to the frontier which constructed by the best performers. Centralized Resource Allocation (CRA) is a method in which all DMUs are projected on to the efficient frontier through solving just one DEA model. The intent of this paper is to present the Stochastic Centralized Resource Allocation (SCRA) in order to allocate centralized resources where inputs and outputs are stochastic. The concept discussed throughout this paper is illustrated using the aforementioned example.     

The resource allocation problem for demand forecasting and performance measurement

We consider a retailer investing in two monitoring functions for unobservable demand and salesperson’s effort. We show that improving effort monitoring is more effective. Moreover, demand monitoring may be less preferable when it becomes relatively cheaper and balancing these two may be worse when they become more complementary.     

Fixed cost and resource allocation based on DEA cross-efficiency

In many managerial applications, situations frequently occur when a fixed cost is used in constructing the common platform of an organization, and needs to be shared by all related entities, or decision making units (DMUs). It is of vital importance to allocate such a cost across DMUs where there is competition for resources. Data envelopment analysis (DEA) has been successfully used in cost and resource allocation problems. Whether it is a cost or resource allocation issue, one needs to consider both the competitive and cooperative situation existing among DMUs in addition to maintaining or improving efficiency. The current paper uses the cross-efficiency concept in DEA to approach cost and resource allocation problems. Because DEA cross-efficiency uses the concept of peer appraisal, it is a very reasonable and appropriate mechanism for allocating a shared resource/cost. It is shown that our proposed iterative approach is always feasible, and ensures that all DMUs become efficient after the fixed cost is allocated as an additional input measure. The cross-efficiency DEA-based iterative method is further extended into a resource-allocation setting to achieve maximization in the aggregated output change by distributing available resources. Such allocations for fixed costs and resources are more acceptable to the players involved, because the allocation results are jointly determined by all DMUs rather than a specific one. The proposed approaches are demonstrated using an existing data set that has been applied in similar studies.     

Skill-based framework for optimal software project selection and resource allocation

This paper presents a conceptual framework and a mathematical formulation for software resource allocation and project selection at the level of software skills. First, we introduce a skill-based framework that considers universities, software companies, and potential projects of a country. Based on this framework, we formulate a linear integer program PMax which determines the selection of projects and the allocation of human resources that maximize profit for a certain company. We show that PMax is NP-complete. Therefore, we devise a meta-heuristic, called Tabu Select and Greedily Allocate (TSGA), to overcome the computational complexities. When compared to PMax running on CPLEX, TSGA performs 15 times faster with an accuracy of 98% on small to large size problems where CPLEX converges. On larger problems where CPLEX does not return an answer, TSGA computes a feasible solution in the order of minutes.     

A resource allocation queueing fairness measure: properties and bounds

Fairness is an inherent and fundamental factor of queue service disciplines in a large variety of queueing applications, ranging from airport waiting lines to computer queueing systems. We study a newly proposed measure, a Resource Allocation Queueing Fairness Measure (RAQFM), first introduced in Raz, Levy, and Avi-Itzhak (Perform. Eval. Rev. 32(1):130–141, 2004). We analyze the properties of RAQFM and tie them to intuition, provide bounds for its values, and discuss briefly how it yields to analysis. This work was supported in part by the Israeli Ministry of Science and Technology, grant number 380-801, and by EURO-NGI network of excellence.     

Multi-level resource allocation for HIV prevention: A model for developing countries

Funds spent on HIV prevention commonly traverse several levels of distribution. For example, funds may be allocated to regions, and regional authorities may then allocate their funds to sub-regions or targeted risk groups. Decision makers at each level often make use of heuristics that may result in suboptimal allocation of resources. We examine the impact of equity-based heuristic allocation of HIV prevention funds versus optimal allocation of HIV prevention funds when there are two levels of decision making. Our results demonstrate that if optimization can only be applied to one level of the decision making process, there are more significant gains if it is applied at the lower level than at the upper level.     

Dynamic process scheduling and resource allocation in distributed environment: an agent-based modelling and simulation

This paper addresses the issues concerning resource allocation and process scheduling in a dynamic environment, where resources are distributed and availability of them is uncertain. In this context, we introduce a new multi-agent-based resource allocation and process scheduling approach, where agents communicate and cooperate among themselves to produce an optimal schedule. A distributed constraint optimization problem-based model in accordance with Markov Decision Process is proposed in this regard. We overcome the hardship of existing centralized approach and our technique optimizes not only the process completion delay but also the number of resources being idle, which is much more beneficial. Apart from the theoretical approach, we take a case study in its practical application domain to validate our claim. Analysis and experimental results show that this proposed method outperforms the state-of-the-art methods and bridges the gap between theory and its applications.     

Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity

This paper addresses a single machine scheduling problem in which the actual job processing times are determined by resource allocation function, its position in a sequence and a rate-modifying activity simultaneously. We discuss two objective functions with two resource allocation functions under the consideration of a rate-modifying activity. We show that the problems are solvable in O(n⁴)$O(n^4)$ time for a linear resource allocation function and are solvable in O(n²logn)$O(n^2\mathit{logn})$ time for a convex resource allocation function.     

Stochastic models for strategic resource allocation in nonprofit foreclosed housing acquisitions

Increased rates of mortgage foreclosures in the U.S. have had devastating social and economic impacts during and after the 2008 financial crisis. As part of the response to this problem, nonprofit organizations such as community development corporations (CDCs) have been trying to mitigate the negative impacts of mortgage foreclosures by acquiring and redeveloping foreclosed properties. We consider the strategic resource allocation decisions for these organizations which involve budget allocations to different neighborhoods under cost and return uncertainty. Based on interactions with a CDC, we develop stochastic integer programming based frameworks for this decision problem, and assess the practical value of the models by using real-world data. Both policy-related and computational analyses are performed, and several insights such as the trade-offs between different objectives, and the efficiency of different solution approaches are presented.     

Structuring resource allocation decisions: A framework for building multi-criteria portfolio models with area-grouped options

Multi-criteria portfolio modelling has been extensively employed as an effective means to allocate scarce resources for investment in projects when considering costs, benefits and risks. Some of these modelling approaches allow the grouping of projects into organisational areas, thus also supporting the decision of resource allocation among organisational units in a way that is collectively efficient for the organisation. However, structuring in practice a portfolio model using this latter type of approach is not a trivial task. How should areas be defined? Where should new projects be included? How should one define the criteria to evaluate performance? As far as we know, there is very little indication in the operational research and decision sciences literatures on how to structure this type of model. This paper suggests different ways to structuring portfolio models where projects are divided into areas and evaluated by multiple criteria, and illustrates their use in two action-research projects. Drawing on these experiences it then suggests a general framework for the structuring of such models in practice. Directions for future research are also identified.