Allocation Problems

8 Key excerpts on "Allocation Problems"

• 

  eBook - PDF

  Handbook of Computational Social Choice

  • Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia(Authors)
  • 2016(Publication Date)
  • Cambridge University Press

    (Publisher)

  We introduce several standard, and some not so standard, classes of Allocation Problems. Next, we introduce the principles that constitute the conceptual core of the literature under review. We hope to show that in spite of the great diversity in the axioms that have been studied, they can all be seen as expressions of just a few general principles. However, because each class of problems has its own mathematical structure, these principles often have to be adapted. Also, the implications of a particular combination of principles often 1 1 . 2 what is a resource allocation problem? 263 differ significantly from one class to the other. It is also the case that for some classes of problems, additional concepts may be available that are not meaningful in others. 11.2 What Is a Resource Allocation Problem? We begin with a presentation of the data needed to specify an allocation problem, and we continue with a sample of problem types. We chose them to illustrate the scope of the program surveyed here. 11.2.1 The Components of an Allocation Problem An economy has several of the following components: 1. A set of agents: this term may refer to individual people, to government agencies, to firms, or to other entities, such as “artificial” agents acting on behalf of “real” agents. 2. Resource data concerns unproduced endowments of goods that can be either consumed as such or, when production opportunities are specified, used as input in the production process; in that case, we also specify production sets and we may attach productivity parameters to agents or to groups. From all of the data we derive feasible sets or oppor- tunity sets open to agents or to groups. In general equilibrium theory, a production plan is a point in commodity space interpreted as a feasible input-output combination.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Approximate Dynamic Programming

  Solving the Curses of Dimensionality

  • Warren B. Powell(Author)
  • 2011(Publication Date)
  • Wiley

    (Publisher)

  Chapter 14 Dynamic Resource Allocation Problems

  There is a vast array of problems that fall under the umbrella of “resource allocation.” We might be managing a team of medical specialists who have to respond to emergencies, or technicians who have to provide local support for the installation of sophisticated medical equipment. Alternatively, a transportation company might be managing a fleet of vehicles, or an investment manager might be trying to determine how to allocate funds among different asset classes. We can even think of playing a game of backgammon as a problem of managing a single resource (the board), although in this chapter we are only interested in problems that involve multiple resources where quantity is an important element of the decision variable.

  Aside from the practical importance of these problems, this problem class provides a special challenge. In addition to the usual challenge of making decisions over time under uncertainty (the theme of this entire book) we now have to deal with the fact that our decision x t is suddenly of very high dimensionality, requiring that we use the tools of math programming (linear, nonlinear, and integer programming). For practical applications it is not hard to find problems in this class where x t has thousands, or even tens of thousands, of dimensions. This problem class clearly suffers from all three “curses of dimensionality.”

  We illustrate the ideas by starting with a scalar problem, after which we move to a sequence of multidimensional (and in several cases, very high-dimensional) resource Allocation Problems. Each problem offers different features, but they can all be solved using the ideas we have been developing throughout this volume.

  14.1 An Asset Acquisition Problem

  Perhaps one of the simplest resource Allocation Problems is the basic asset acquisition problem where we acquire assets (money, oil, water, aircraft) to satisfy a future, random demand. In our simple illustration we purchase assets at time t

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Applications of Combinatorial Optimization, Volume 3

  • Vangelis Th. Paschos(Author)
  • 2013(Publication Date)
  • Wiley-ISTE

    (Publisher)

  In many cases, we must cope with constraints that are imposed by real systems. Thus we may have limited resources in terms of memory, which introduces a capacity constraint on the processors. We can also limit the number of tasks that can be executed by a given processor. There may also be availability constraints: certain tasks can only be executed by a subset of the processors.

  2.2.7.3. Objectives of the allocation

  The task allocation problem is by nature a combinatorial problem insofar as a very large number of possible solutions exist. Indeed, if we have n tasks and m processors, the number of possible allocations is

  mn

  (not all of them are necessarily feasible). To distinguish between different concurrent solutions, we need to equip ourselves with a measure for evaluating the quality of the allocation. This measure, which we generally call the objective function in the context of optimization problems, can be very varied. It naturally depends on the objective that we wish to achieve with the allocation. It appears explicitly in all Allocation Problems based on mathematical programming techniques. However, in certain heuristic algorithms, it is implicit. Generally, the allocation must allow us to optimize the use of the resources. We will look at some of the most-studied criteria. First we need to explain the notations.

  We consider a set of n tasks denoted by {T 1 ,… ,

  Tn

  } and of m processors denoted by {P 1 ,…,

  Pm

  }. Let exec : T × P → IN be a function that gives the execution cost of a task t ∈ T on a processor p ∈ P. This function is general and can represent all systems of processors, homogenous, uniform or heterogenous. In the same way, we define a very general function, comm :T × T × P × P → IN, that gives the cost of communication between two tasks t 1 ∈ T and t 2 ∈ T when they are allocated to the processors p 1 ∈ P and p 2 ∈ P , respectively. We denote an allocation by f : T → P .

  2.2.7.3.1. Minimizing the execution duration

  If we consider that the execution and communication costs are expressed in terms of duration then a possible objective is minimizing the total execution time of the program [BOU 95, HUI 97, WOO 93]:

  2.2.7.3.2. Minimizing the global execution and communication cost

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Applications of Combinatorial Optimization

  • Vangelis Th. Paschos(Author)
  • 2014(Publication Date)
  • Wiley-ISTE

    (Publisher)

  In many cases, we must cope with constraints that are imposed by real systems. Thus we may have limited resources in terms of memory, which introduces a capacity constraint on the processors. We can also limit the number of tasks that can be executed by a given processor. There may also be availability constraints: certain tasks can only be executed by a subset of the processors.

  2.2.7.3. Objectives of the allocation

  The task allocation problem is by nature a combinatorial problem insofar as a very large number of possible solutions exist. Indeed, if we have n tasks and m processors, the number of possible allocations is

  mn

  (not all of them are necessarily feasible). To distinguish between different concurrent solutions, we need to equip ourselves with a measure for evaluating the quality of the allocation. This measure, which we generally call the objective function in the context of optimization problems, can be very varied. It naturally depends on the objective that we wish to achieve with the allocation. It appears explicitly in all Allocation Problems based on mathematical programming techniques. However, in certain heuristic algorithms, it is implicit. Generally, the allocation must allow us to optimize the use of the resources. We will look at some of the most-studied criteria. First we need to explain the notations.

  We consider a set of n tasks denoted by {T 1 , …,

  Tn

  } and of m processors denoted by {P 1 , …,

  Pm

  }. Let exec : T × P → IN be a function that gives the execution cost of a task t ∈ T on a processor p ∈ P . This function is general and can represent all systems of processors, homogenous, uniform or heterogenous. In the same way, we define a very general function, comm : T × T × P × P → IN, that gives the cost of communication between two tasks t 1 ∈ T and t 2 ∈ T when they are allocated to the processors p 1 ∈ P and p 2 ∈ P , respectively. We denote an allocation by f : T → P .

  2.2.7.3.1. Minimizing the execution duration

  If we consider that the execution and communication costs are expressed in terms of duration then a possible objective is minimizing the total execution time of the program [BOU 95, HUI 97, WOO 93]:

  2.2.7.3.2. Minimizing the global execution and communication cost

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Resource Allocation Problems in Supply Chains

  • K. Ganesh, Sanjay Mohapatra, R. A. Malairajan, M. Punniyamoorthy(Authors)
  • 2015(Publication Date)
  • Emerald Group Publishing Limited

    (Publisher)

  SECTION 2 Literature Review 2.1. Resource Allocation Problem RA involves the distribution and utilization of available resources across the system. Because resource availability is usually scarce and expensive, it becomes important to fi nd optimal or even “ good ” solutions to such problems. Thus, RA problems represent an impor-tant class of problems faced by mathematical programmers. A conceptual framework for RA problems based on literature review is detailed in Figure 2.1 Single Sourcing Capacitated with demand allocation Un-capacitated No restriction in demand allocation Single Single Multiple Multiple Multiple Sourcing Demand Type Objective Model Approach Period Shape/ Topography Capacity Constraints AP Number of Products No. of Facility & Stages Recti-Linear Euclidean Man-Hattan Actual Distance Distance Measures Objectives Type Elastic Single Multiple Deterministic Stochastic Qualitative Quantitative Single Multiple Plane/Continuous Network Location Discrete Location (MIP) MinSum MinMax In-Elastic Figure 2.1: Conceptual Framework for Resource Allocation Problems. 13 2.2. Review of the RA Variants Addressed in Current Research Literature on the RA variants addressed in this study is presented in next few paragraphs. 2.2.1. BI-OBJECTIVE GENERALIZED ASSIGNMENT PROBLEM Literature pertaining to bi-objective/multi-objective Generalized Assignment Problem (GAP) is very limited. Hajri Gabouj (2003 ) investigated a fuzzy genetic multi-objective optimization algorithm for a multi-level GAP, an application encountered in clothing indus-try. Zhou et al. (2003 ) explored a Genetic Algorithm (GA) approach for Bi-Objective Generalized Assignment Problem (BGAP), an appli-cation of allocation of customers to warehouses. From the literature review, it was inferred that the BGAP was addressed less in the lit-erature and also there would be a lot of opportunity to explore sev-eral solution approaches to solve BGAP to fi nd Pareto optimal solutions.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Operations Planning

  Mixed Integer Optimization Models

  • Joseph Geunes(Author)
  • 2014(Publication Date)
  • CRC Press

    (Publisher)

  4 The Generalized Assignment Problem 4.1 Introduction The allocation of limited resources to various activities required in produc-tion and distribution of a good or service forms the basis of a majority of difficult operations planning problems. The knapsack problem, discussed in Chapter 2, considers the allocation of a single resource to multiple activities that essentially compete for the resource. In the knapsack problem class, we are free to omit items from the knapsack. In operations planning contexts where the knapsack capacity represents machine capacity and the items rep-resent jobs, for example, this corresponds to leaving jobs unperformed. Many operations planning problems require that all members of a candidate set of jobs are assigned to some available resource, ensuring that all job processing requirements are met. In this chapter, we consider such a class of problems, where each member of a set of items must be assigned to some member of a set of available resources, and where each available resource has an associated capacity limit. The goal of this problem is to assign each item to a resource at minimum total cost while respecting resource capacities, where a cost is asso-ciated with the assignment of a given item to a specific resource. Unlike the knapsack problem, this generalized assignment problem (GAP) falls into the class of problems that are NP -Hard in the strong sense , which implies that we are not likely to find even a pseudopolynomial time algorithm for its solution (unless P = NP ). We will therefore focus on methods for determining good lower bounds on the optimal solution value, as well as high-quality heuristic solutions. These methods include Lagrangian relaxation, branch-and-price, and the use of an asymptotically optimal greedy heuristic approach. As with the knapsack problem, the GAP considers a single dimension for measuring resource capacity.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Applied Dynamic Programming

  • Richard E. Bellman, Stuart E Dreyfus(Authors)
  • 2015(Publication Date)
  • Princeton University Press

    (Publisher)

  C H A P T E R I One-dimensional Allocation Processes 1. Introduction We shall begin our discussion with an investigation of a simple class of allocation processes arising in mathematical economics and operations research. The basic question is that of using resources of various types in efficient ways. In order to permit the reader to assimilate the techniques we shall employ throughout, we initially shall consider some rudimentary models involving a minimum of mathematical difficulties. The simplicity of these preliminary problems permits us to examine and analyze methods which will be applied in later pages to study more realistic and complex matters. As we shall see, processes of significance in applica- tions possess a number of simultaneous features of difficulty. Generally speaking, these require a variety of methods applied in unison, and often some amount of ingenuity. All our efforts will be directed towards the primary goal of obtaining numerical answers to numerical questions. The first computation we perform is directed towards the determination of the maximum of the function of N variables (1) R(x v X 2 , . . . , x N ) = S r 1(X1) + g2(x2) -i h SS-(^v) taken over the region of values determined by the relations (2) (a) X1 -)- x2 -j- · · · -)- X^1 = x, (b) X1 > 0. There are many difficulties encountered in treating this apparently simple and straightforward problem. In the course of a careful and detailed examination of these obstacles, we shall generate sufficient motivation to present a new approach—the functional equation technique of dynamic programming. The allocation process giving rise to the foregoing optimization will be used to introduce the basic ideas of dynamic programming and to illustrate the computational aspects in detail. In this discussion, and throughout, we shall provide the reader with basic information concerning coding times, running times, accuracy, stability, and flow charts.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Analytics and Decision Support in Health Care Operations Management

  • Yasar A. Ozcan(Author)
  • 2017(Publication Date)
  • Jossey-Bass

    (Publisher)

  Chapter 10 Resource Allocation

  Learning Objectives

  • Recognize the concept of resource allocation in health care organizations.
  • Describe linear programming methodology and its use for allocation in health care facilities.
  • Recognize the diff erence in applications of maximization and minimization problems.
  • Recognize the use of integer linear programming in staff scheduling.

  Among the frequent operational problems in health care are resource allocation, service mix, scheduling, and assignment. Linear programming (LP) is an excellent tool to apply to those problems. In practice, software for nurse scheduling and operating room scheduling, empowered by linear programming and its extensions such as integer programming, provides optimal resource allocation and scheduling. In this chapter, we will describe both linear and integer programming applications in health care.

  Linear Programming

  Linear programming is a powerful tool that can incorporate many decision variables into a single model to attain an optimal solution. For example, a nurse scheduling problem in a medical center would involve many decision variables: various shift assignments and patterns, rotations, off days, weekend day designations, vacation requests, and holidays—all of which have to be considered simultaneously. When the requirements set up for health care management problems are translated into what is called constraints, it is possible for there to be so many that no solution to the problem appears to be feasible. However, health care managers can then reassess the requirements and relax some to seek possible solutions. To do that, one has to understand the nature of linear programming, and its structure. One must be able to observe simple problems (with few decision variables) graphically, and be able to conceptualize problems with many decision variables and constraints.

  Sign up to read

  Learn more about book