Academia.edu no longer supports Internet Explorer.
To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser .
Enter the email address you signed up with and we'll email you a reset link.
- We're Hiring!
- Help Center
Sensitivity analysis for bottleneck assignment problems
European Journal of Operational Research
Related Papers
In assignment problems, decision makers are often interested in not only the optimal assignment, but also the sensitivity of the optimal assignment to perturbations in the assignment weights. Typically, only perturbations to individual assignment weights are considered. We present a novel extension of the traditional sensitivity analysis by allowing for simultaneous variations in all assignment weights. Focusing on the bottleneck assignment problem, we provide two different methods of quantifying the sensitivity of the optimal assignment, and present algorithms for each. Numerical examples as well as a discussion of the complexity for all algorithms are provided.
Naval Research Logistics
Charles Wells
Electronic Notes in Discrete Mathematics
Roberto Aringhieri
The Multilevel Bottleneck Assignment Problem is defined on a weighted graph of L levels and consists in finding L− 1 complete matchings between contiguous levels, such that the heaviest path formed by the arcs in the matchings has a minimum weight. The problem, introduced by Carraresi and Gallo (1984) to model the rostering of bus drivers in order to achieve an even balance of the workload among the workers, though frequently cited, seems to have never been applied or extended to more general cases. In this paper, we ...
Operations Research Letters
Frits Spieksma
Uwe Zimmermann
Optimization Letters
International Journal for Research in Applied Science & Engineering Technology (IJRASET)
IJRASET Publication
In this paper a new method is proposed for finding an optimal solution of a wide range of assignment problems, directly. A numerical illustration is established and the optimality of the result yielded by this method is also checked. The most attractive feature of this method is that it requires very simple arithmetical and logical calculations. The method is illustrated through an example.
RELATED PAPERS
Portuguese Journal of Mental Health Nursing
Teresa Kurimoto
Phillip Wolff
Artificial Neural Networks - Application
Adriano Siqueira
wen-yaw chung
arXiv (Cornell University)
Leandro Pinto Rodrigues Pimentel
The International journal of developmental biology
Keitaro Yamanouchi
The Classical World
Physical Review D
Donato Bini
Cogent Food & Agriculture
Moses Mensah
Ahmad Mahmud
Journal of Zoology
marcell molnár
Macromolecules
Vojnosanitetski pregled
Vladan Zivaljevic
European Journal of Nutrition & Food Safety
Ismail Kassim
Semiconductor Science and Technology
Damien Deleruyelle
Md Sazid Hasan
London, Modernism and 1914
Sarah MacDougall
IEEE Transactions on Pattern Analysis and Machine Intelligence
Qiaoling Ye
Springer eBooks
Inorganic Chemistry
Abdelkrim REDJAIMIA
RELATED TOPICS
- We're Hiring!
- Help Center
- Find new research papers in:
- Health Sciences
- Earth Sciences
- Cognitive Science
- Mathematics
- Computer Science
- Academia ©2024
The Linear Bottleneck Assignment Problem
Cite this chapter.
- Rainer E. Burkard 5 &
- Ulrich Derigs 6
Part of the book series: Lecture Notes in Economics and Mathematical Systems ((LNE,volume 184))
215 Accesses
2 Citations
The Linear Bottleneck Assignment Problem (LBAP) is strongly related to LSAP. Here we associate with every permutation φ ∊ l n the costs
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Compact, lightweight edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Unable to display preview. Download preview PDF.
Author information
Authors and affiliations.
Mathematisches Institut, Universität zu Köln, Weyertal 86, 5000, Köln 41, Federal Republic of Germany
Rainer E. Burkard
Industrieseminar, Universität zu Köln, Albertus-Magnus-Platz, 5000, Köln 41, Federal Republic of Germany
Ulrich Derigs
You can also search for this author in PubMed Google Scholar
Rights and permissions
Reprints and permissions
Copyright information
© 1980 Springer-Verlag Berlin Heidelberg
About this chapter
Burkard, R.E., Derigs, U. (1980). The Linear Bottleneck Assignment Problem. In: Assignment and Matching Problems: Solution Methods with FORTRAN-Programs. Lecture Notes in Economics and Mathematical Systems, vol 184. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-51576-7_2
Download citation
DOI : https://doi.org/10.1007/978-3-642-51576-7_2
Publisher Name : Springer, Berlin, Heidelberg
Print ISBN : 978-3-540-10267-0
Online ISBN : 978-3-642-51576-7
eBook Packages : Springer Book Archive
Share this chapter
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
Help | Advanced Search
Mathematics > Optimization and Control
Title: sensitivity analysis for bottleneck assignment problems.
Abstract: In assignment problems, decision makers are often interested in not only the optimal assignment, but also the sensitivity of the optimal assignment to perturbations in the assignment weights. Typically, only perturbations to individual assignment weights are considered. We present a novel extension of the traditional sensitivity analysis by allowing for simultaneous variations in all assignment weights. Focusing on the bottleneck assignment problem, we provide two different methods of quantifying the sensitivity of the optimal assignment, and present algorithms for each. Numerical examples as well as a discussion of the complexity for all algorithms are provided.
Submission history
Access paper:.
- Other Formats
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bibliographic and Citation Tools
Code, data and media associated with this article, recommenders and search tools.
- Institution
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .
- Help & FAQ
On the bottleneck assignment problem
- Marcus Department of Industrial and Manufacturing Engineering
Research output : Contribution to journal › Article › peer-review
In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is shown that any critical solution yields a global optimum. This theorem is then used as a basis to develop a general method to solve max-min permutation problems.
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Management Science and Operations Research
- Applied Mathematics
Access to Document
- 10.1007/BF00933089
Other files and links
- Link to publication in Scopus
- Link to the citations in Scopus
Fingerprint
- Bottleneck Problem Mathematics 100%
- Assignment Problem Business & Economics 79%
- Permutation Mathematics 53%
- Min-max Mathematics 28%
- Global Optimum Mathematics 16%
- Theorem Mathematics 5%
- Class Mathematics 3%
T1 - On the bottleneck assignment problem
AU - Ravindran, A.
AU - Ramaswami, V.
PY - 1977/4
Y1 - 1977/4
N2 - In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is shown that any critical solution yields a global optimum. This theorem is then used as a basis to develop a general method to solve max-min permutation problems.
AB - In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is shown that any critical solution yields a global optimum. This theorem is then used as a basis to develop a general method to solve max-min permutation problems.
UR - http://www.scopus.com/inward/record.url?scp=0347497381&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0347497381&partnerID=8YFLogxK
U2 - 10.1007/BF00933089
DO - 10.1007/BF00933089
M3 - Article
AN - SCOPUS:0347497381
SN - 0022-3239
JO - Journal of Optimization Theory and Applications
JF - Journal of Optimization Theory and Applications
Subscribe to the PwC Newsletter
Join the community, edit social preview.
Add a new code entry for this paper
Remove a code repository from this paper, mark the official implementation from paper authors, add a new evaluation result row, remove a task, add a method, remove a method, edit datasets, exploiting structure in the bottleneck assignment problem.
25 Aug 2020 · Khoo Mitchell , Wood Tony A. , Manzie Chris , Shames Iman · Edit social preview
An assignment problem arises when there exists a set of tasks that must be allocated to a set of agents. The bottleneck assignment problem (BAP) has the objective of minimising the most costly allocation of a task to an agent. Under certain conditions the structure of the BAP can be exploited such that subgroups of tasks are assigned separately with lower complexity and then merged to form a combined assignment. In particular, we discuss merging the assignments from two separate BAPs and use the solution of the subproblems to bound the solution of the combined problem. We also provide conditions for cases where the solution of the subproblems produces an exact solution to the BAP over the combined problem. We then introduce a particular algorithm for solving the BAP that takes advantage of this insight. The methods are demonstrated in a numerical case study.
The bottleneck assignment problem
Available online, at the library.
SAL3 (off-campus storage)
More options.
- Find it at other libraries via WorldCat
- Contributors
Description
Creators/contributors, bibliographic information, browse related items.
- Stanford Home
- Maps & Directions
- Search Stanford
- Emergency Info
- Terms of Use
- Non-Discrimination
- Accessibility
© Stanford University , Stanford , California 94305 .
COMMENTS
In combinatorial optimization, a field within mathematics, the linear bottleneck assignment problem (LBAP) is similar to the linear assignment problem.. In plain words the problem is stated as follows: There are a number of agents and a number of tasks.Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment.
In this sensitivity analysis, we provide a sufficient but not necessary condition for the invariance of the optimal assignment, in the form of an interval test. n×m Let Λ ⊆ R be an n × m array of intervals over the extended reals. For each edge e ∈ E, let [−λe, λe] be the interval corresponding to edge e. Remark 1.
In this sensitivity analysis, we provide a sufficient but not necessary condition for the invariance of the optimal assignment, in the form of an interval test. Let Λ ⊆ R n × m be an n × m array of intervals over the extended reals. For each edge e ∈ E, let [ − λ e, λ e] be the interval corresponding to edge e. Remark 1.
The linear bottleneck assignment problem (LBAP), which is a variation of the classical assignment problem (CAP), seeks to minimize the longest completion time rather than the sum of the completion times when a number of jobs are to be assigned to the same number of workers. Several procedures have been proposed in the current literature to convert the LBAP into an equivalent CAP and then apply ...
An assignment problem arises when there exists a set of tasks that must be allocated to a set of agents. The bottleneck assignment problem (BAP) has the objective of minimising the most costly allocation of a task to an agent. Under certain conditions the structure of the BAP can be exploited such that subgroups of tasks are assigned separately ...
The bottleneck assignment problem is concerned only with the maximum weight edge in an assignment, with no mechanism to differentiate between various assignments with the same maximum weight edge. Motivated by this, we may define a related sensitivity problem, focusing only on the maximum weight edge rather than the entire assignment ...
The Linear Bottleneck Assignment Problem. In: Assignment and Matching Problems: Solution Methods with FORTRAN-Programs. Lecture Notes in Economics and Mathematical Systems, vol 184.
2 Spivey: Bottleneck Assignment Problem Mathematics of Operations Research (), pp. , c 20 INFORMS of maxft ijgover all possible matchings.But the former is, by de nition, R, and the latter is ˝(match;B~). (Lemma 1.1 is similar to the ideas behind the class of threshold algorithms used to solve the bottleneck
In assignment problems, decision makers are often interested in not only the optimal assignment, but also the sensitivity of the optimal assignment to perturbations in the assignment weights. Typically, only perturbations to individual assignment weights are considered. We present a novel extension of the traditional sensitivity analysis by allowing for simultaneous variations in all ...
and we want to minimize the time at which the last task is completed, then we have a bottleneck assignment problem. Formally, the bottleneck assignment problem is defined as follows, where c;. is the cost of assigning resource i to task j: For a summary of major results on and algorithms for solving the bottleneck assignment problem, see §6.2 ...
These. problems can be formulated as follows. Let A = {ajj} fJ=1 be a n x n matrix of real numbers. which we further call weights. In the bottleneck (capacity) assignment problem, we ask to. minimize (maximize) the largest (smallest) element over all possible sets of n entries in A, one. from each row and column.
The bottleneck assignment problem (BAP) has the objective of minimising the most costly allocation of a task to an agent. Under certain conditions the structure of the BAP can be exploited such that subgroups of tasks are assigned separately with lower complexity and then merged to form a combined assignment. In particular, we discuss merging ...
A simple algorithm for solving either of two different bottleneck assignment problems, which requires finding an assignment of men to machines in a serial production line to maximize the rate of flow through the line. Abstract : A simple algorithm for solving either of two different bottleneck assignment problems is described in this paper. The one problem requires finding an assignment of men ...
N2 - In this paper, a new approach for solving the bottleneck assignment problem is presented. The problem is treated as a special class of permutation problems which we call max-min permutation problems. By defining a suitable neighborhood system in the space of permutations and designating certain permutations as critical solutions, it is ...
Description. Default. Custom. Image. Default. Custom. None Upload an image to customize your repository's social media preview. ... We study the multi-level bottleneck assignment problem (MBA), which has important applications in scheduling and quantitative finance. Given a weight matrix, the task is to rearrange entries in each column such ...
The problem BAPC2 is to Minimize ∑ i=1 m max 1⩽j⩽n {c ij: x ij =1} subject to the constraints given above. When m=1, BAPC1 reduces to the bottleneck assignment problem and BAPC2 reduces to the sum assignment problem. When m=n, BAPC1 reduces to a trivial case of the knapsack problem with generalized upper bounds and BAPC2 reduces to its ...
The bottleneck assignment problem (BAP) has the objective of minimising the most costly allocation of a task to an agent. Under certain conditions the structure of the BAP can be exploited such that subgroups of tasks are assigned separately with lower complexity and then merged to form a combined assignment.
The three dimensional bottleneck assignment problem and some of its variants are studied in the present paper. A procedure is developed for each of these bottleneck assignment problems. Keywords: Bottleneck assignment problem. bi-linear programming. AMS 1980 Subject Classifications: Primary: 90C08. Secondary: 90C09.
A simple algorithm for solving either of two different bottleneck assignment problems is described in this paper. The one problem requires finding an assignment of men to machines in a serial production line to maximize the rate of flow through the line; the other requires finding an assignment for parallel production lines (one man per line) so as to minimize the time to do a given job.
Abstract. The min-max version of the generalized assignment problem is considered. We introduce relaxations and show that they produce, as sub-problems, min-max versions of the multiple-choice knapsack problem and of the 0-1 knapsack problem. It is proved that such problems can be solved exactly in polynomial time.
1.1 TBGAP in relation to SCM: The Task Bottleneck Assignment Problem [15, 16] is the Combinatorial Optimization Problem in the branch of optimization. Maximum cost" is "maximum duration", which is the bottleneck to schedule the overall job, to be minimized. When there are a number of suppliers and a number of
The bottleneck assignment problem. Responsibility [O. Gross]. Imprint Santa Monica, Calif. : Rand, 1959. Physical description ii, 8 p. ; 28 cm. Online. Available online At the library. SAL3 (off-campus storage) Stacks Request (opens in new tab) Items in Stacks; Call number Note