Markéta Kocourková · Digital Repository (National Repository of Grey Literature) · 2012
The generalized assignment problem is a topic of this thesis. The knapsack problem in general belongs to among classical operation research problems and belongs to the category of integer linear programming. It is very often formulated as a binary problem or 0-1. There are several types of knapsack problems which are described in this thesis. Some of the knapsack problems are so large and although exist exact algorithms for finding optimal solution, heuristics are rather used. They are not so exact but they find solution much earlier. Therefore some of the knapsack problems belong to NP-hard problems. This thesis is focused on one type particularly, the generalized assignment problem, which is demonstrated on practical example how the problem can be used.
Cited by 0
Ulvi Findik, O. Erhun Kundakcioglu, Saed Alizamir · Encyclopedia of Optimization · 2012
Cited by 0
O. Erhun Kundakcioglu, Saed Alizamir · Encyclopedia of Optimization · 2008
Cited by 37
Arash Khatibi · IDEALS (University of Illinois Urbana-Champaign) · 2017
The Sequential Stochastic Assignment Problem (SSAP) deals with assigning sequentially arriving tasks with stochastic parameters to workers with fixed success rates. The reward of each assignment is the product of the worker's success rate and the task value assigned to the worker. The objective is to maximize the total expected reward. There has been a surge of interest in studying sequential assignment problems due to their applications in online matching markets, asset selling, and organ transplant. \n \nThis dissertation studies several variations of SSAP by relaxing the main assumptions. The first part assumes that the workers' success rates are random values coming from a known distribution. This generalization modifies the SSAP from a problem with a single random value (i.e., the task value) at each stage to an online matching problem with several random parameters (i.e., the task value and the workers' success rates). The optimal assignment policy uses backward induction to first solve smaller subproblems, and then use them to optimally assign tasks to workers from the first stage. An approximation algorithm is proposed that achieves a fraction of the optimal reward in a polynomial time. \n \nAssuming that the value of sequentially arriving elements are independently drawn from a known distribution is unrealistic in many applications. The second part of thesis relaxes this assumption and uses the well-known Secretary Problem to derive constant-competitive algorithms for SSAP with tasks having a random arrival order. Several deterministic and randomized algorithms are proposed and their performance are compared with the maximum offline reward. These algorithms use the first stages of the problem as a training phase to compute thresholds for the task values. These thresholds are used to assign tasks to workers after the training phase. \n \nThe third part uses the linear programming technique to derive bounds on the performance of optimal policy for several variations of SSAP. Formulating an online matching problem as a linear program is a useful tool. In addition to deriving bounds on performance of optimal policies, the linear programming technique can be used to formulate extensions of the problem as linear programs by simple changes in the objective function and constraints of the basic formulation. The linear programming formulation of the incentive compatible problem and the sequential assignment problem with unknown number of elements are also proposed. The edge-weighted online bipartite matching problem is used to design assignment policies for each of the formulated problems. \n \nThe last part relaxes the assumption that at most one task must be assigned to each worker in SSAP. It is assumed that a worker is available for possible future assignments after performing the previously assigned task. The number of stages that the worker is not available due to a prior task assignment is referred to as the task duration. This problem is studied under various models for the task duration. First, it is assumed that the task duration is fixed. Then, assignment policies are proposed for the problem with a memoryless model for the task duration. The proposed algorithms are extensions of the optimal algorithm for the sequential assignment problem. They divide the n-stage assignment process to periods whose lengths are equal to the expected task duration. Then, they assign tasks to workers in each period by applying the optimal algorithm of the sequential assignment problem.
Cited by 0Open access
2014
Cited by 0
Vittorio Maniezzo, Marco Antonio Boschetti, Thomas Stützle · EURO advanced tutorials on operational research · 2021
Cited by 7
Marcel Büther · Journal of the Operational Research Society · 2009
Abstract The elastic generalized assignment problem (eGAP) is a natural extension of the generalized assignment problem (GAP) where the capacities are not fixed but can be adjusted; this adjustment can be expressed by continuous variables. These variables might be unbounded or restricted by a lower or upper bound, respectively. This paper concerns techniques aiming at reducing several variants of eGAP to GAP, which enables us to employ standard approaches for the GAP. This results in a heuristic, which can be customized in order to provide solutions having an objective value arbitrarily close to the optimal.
Cited by 2
T.E. Djaferis, Sanjoy K. Mitter · 1979
For some Linear, strictly proper system given by its transfer function, two dynamic output feedback problems can be posed. The first one is that of using dynamic-output feedback to assign the closed-loop characteristic polynomial and the second that of assigning the closed-loop invariant factors. We are concerned with these problems and their inter-relationships. The formulation is done in the frequency domain and the investigation carried out from an algebraic point of view, in terms of linear equations over rings of polynomials. Using the notion of genericity, we express several necessary and sufficient conditions.
Cited by 4
David R. Spoerl, R. Kevin Wood · 2004
We develop a stochastic version of the Elastic Generalized Assignment Problem (EGAP) that incorporates independent, normally distributed resource-consumption coefficients and other random parameters. The Stochastic EGAP (SEGAP) is a stochastic integer program with simple recourse. We construct two deterministic equivalents: The “proportional mean-variance model” (PMVM) assumes a common mean-to-variance ratio for all coefficients associated with a single resource, while the “general mean-variance model ” (GMVM) relaxes this assumption. Models for more general distributions are also described. We test PMVM and GMVM to assign a set of petroleum-order deliveries with uncertain durations to a set of trucks; overtime pay accrues when regular working hours are exceeded. Realistic instances of SEGAP solve in times that are comparable to the EGAPs, sometimes faster, and the relative value of the stochastic solution can exceed 24%.
Cited by 15
Ma Zhong · TSpace · 2003
We study a generalization of the quadratic assignment problem (QAP) by allowing multiple equipments to be assigned at a single location as long as resources at the location permit. This problem arises in many real world applications such as facility location problem and logistics network design. We call the problem as the generalized quadratic assignment problem (GQAP) and show that this relaxation increases the complexity of the problem dramatically. We propose three linearization approaches and a branch and bound algorithm to optimally solve the GQAP. Computational studies have been conducted to demonstrate the performance of the proposed approaches.
Cited by 0Open access
Arash Khatibi, Sheldon H. Jacobson · Stochastic Systems · 2018
The sequential stochastic assignment problem (SSAP) assigns sequentially arriving tasks with stochastic parameters (coming from a known distribution) to workers with fixed success rates so as to maximize the total expected reward. This paper studies the generalized SSAP (GSSAP), an extension of SSAP with no prior information on task values. GSSAP is described as a generalization of the secretary problem, in which the set of selected elements in the secretary problem are assigned to distinct positions in GSSAP. The weighted secretary problem is used to design two deterministic and one randomized algorithm for GSSAP. The proposed algorithms have a threshold structure: the first few stages of the problem are used as a training phase to compute thresholds. These thresholds are then used to assign tasks to workers after the training phase. These algorithms provide intuitive models to assign tasks arriving in the training phase to workers. Although the expected reward achieved by the deterministic algorithms has a better lower bound, the randomized algorithm provides fairness by assigning each task to any of the workers with equal probability.
Cited by 4Open access
Jianfeng Ren · Far East Journal of Applied Mathematics · 2023
Cited by 0Open access
Jay Michael Rosenberger, Hee Sung Hwang, Ratna P. Pallerla et al. · Defense Technical Information Center (DTIC) · 2005
Dynamic command and control and battle management functions require fast and effective decision aids to provide optimal allocation of resources (object/sensor pairing, weapon/target assignment) for effective engagement and real-time battle damage assessment. The basic Weapon Target Assignment (WTA) problem considers the assignment of a set of platforms/weapons to a set of targets such that the overall expected effect is maximized. In the present study, we extend the basic WTA problem by allowing for multiple target assignments per platform, subject to the number of weapons available and their effectiveness. We formulate the problem as a linear integer programming problem and investigate two solution methods. The first method is a greedy approach based on the sequential application of the auction algorithm that was generalized for assigning n assets/resources to m targets. The second method is built on a branch-and-bound framework that enumerates feasible tours of assets/resources a process that can become computationally intensive with increasing number of sources and targets but will find an optimal solution. We provide results of Monte Carlo experiments and provide comparative evaluation of the two solution methods. Finally, we extend the brand-and bound technique to assigning multiple platforms per target and thereby demonstrate its utility for collaborative asset planning. While this study focuses on weapon target pairing for illustration purposes, the methods and results herein are readily applicable to sensor tasking and similar resource allocation problems.
Cited by 32
Saeed Alaei, MohammadTaghi Hajiaghayi, Vahid Liaghat · Lecture notes in computer science · 2013
Cited by 44
2013
The generalized assignment problem is one of the representative combinational optimization problems known to be NP-hard. Generally, the objective is to minimize the total cost when assigning J jobs to M agents with constrained capacity such that each job is assigned to exactly one agent. Some agents are better suited to particular jobs than
Cited by 0
Konstantin Kogan, Avraham Shtub · Annals of Operations Research · 1997
Cited by 29
Lale Özbakır, Adil Baykasoğlu, Pınar Tapkan · Applied Mathematics and Computation · 2009
Cited by 184
Artur Alves Pessoa, Peter M. Hahn, Monique Guignard et al. · 2014
This paper is concerned with solving GQAPs (generalized quadratic assignment problems) to optimality. In these problems, given M facilities and N locations, the facility space requirements, the location available space, the facility installation costs, the flows between facilities, and the distance costs between locations, one must assign each facility to exactly one location so that each location has sufficient space for all facilities assigned to it and the sum of the products of the facility flows by the corresponding distance costs plus the sum of the installation costs is minimized. This problem generalizes the well-known quadratic assignment problem (QAP), one of the most difficult problems in the combinatorial optimization field. 1
Cited by 0
Mutsunori Yagiura, Toshihide Ibaraki · 2014
The generalized assignment problem is a classical combinatorial optimization problem that models a variety of real world applications including flexible manufacturing systems [6], facility location [11] and vehicle routing problems [2]. Given n jobs J = {1, 2,..., n} and m agents I = {1, 2,..., m}, the goal is to determine a minimum cost assignment subject to assigning each job to exactly one agent and satisfying a resource constraint for each agent. Assigning job j to agent i incurs a cost of cij and consumes an amount aij of resource, whereas the total amount of the resource available at agent i is bi. An assignment is a mapping σ: J → I, where σ(j) = i means that job j is assigned to agent i. Then the generalized assignment problem (GAP) is formulated as follows: minimize cost(σ) = ∑ subject to j∈J σ(j)=i j∈J c σ(j), j
Cited by 0
Ľudmila Jánošíková · 2021
The generalized assignment problem is a classical optimization problem. Its modifications and extensions occur frequently in practical problems in the area of industry, telecommunications, computer networks, logistics, and many others. It is a hard problem, thus an optimal solution to practical instances cannot be calculated in an acceptable amount of time. That is why approximate methods must be applied. The kernel search is one of the recently developed heuristics that exploit a mathematical programming formulation of the problem. It is a general and simple heuristic framework based on the idea of decomposition of the original problem into smaller sub-problems and using a mathematical programming solver as a black-box to solve them. In this paper we propose an implementation of the kernel search algorithm for the general assignment problem and evaluate the efficiency of the algorithm on benchmark instances.
Cited by 2