Browse Econ Literature
- Working papers
- Software components
- Book chapters
- JEL classification
More features
- Subscribe to new research
RePEc Biblio
Author registration.
- Economics Virtual Seminar Calendar NEW!
Some searches may not work properly. We apologize for the inconvenience.
The bottleneck generalized assignment problem
- Author & abstract
- 7 References
- 10 Citations
- Most related
- Related works & more
Corrections
- Martello, Silvano
- Toth, Paolo
Suggested Citation
Download full text from publisher, references listed on ideas.
Follow serials, authors, keywords & more
Public profiles for Economics researchers
Various research rankings in Economics
RePEc Genealogy
Who was a student of whom, using RePEc
Curated articles & papers on economics topics
Upload your paper to be listed on RePEc and IDEAS
New papers by email
Subscribe to new additions to RePEc
EconAcademics
Blog aggregator for economics research
Cases of plagiarism in Economics
About RePEc
Initiative for open bibliographies in Economics
News about RePEc
Questions about IDEAS and RePEc
RePEc volunteers
Participating archives
Publishers indexing in RePEc
Privacy statement
Found an error or omission?
Opportunities to help RePEc
Get papers listed
Have your research listed on RePEc
Open a RePEc archive
Have your institution's/publisher's output listed on RePEc
Get RePEc data
Use data assembled by RePEc
An algorithm for the bottleneck generalized assignment problem
New citation alert added.
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
New Citation Alert!
Please log in to your account
Information & Contributors
Bibliometrics & citations, view options.
- Xie F Sharma A Li Z (2022) An alternate approach to solve two-level priority based assignment problem Computational Optimization and Applications 10.1007/s10589-021-00340-0 81 :2 (613-656) Online publication date: 10-Jan-2022 https://dl.acm.org/doi/10.1007/s10589-021-00340-0
- Hill R Reilly C (2000) The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance Management Science 10.5555/2786232.2786241 46 :2 (302-317) Online publication date: 1-Feb-2000 https://dl.acm.org/doi/10.5555/2786232.2786241
- Osman I (1995) Heuristics for the generalised assignment problem OR Spectrum 10.1007/BF01720977 17 :4 (211-225) Online publication date: 1-Dec-1995 https://dl.acm.org/doi/10.1007/BF01720977
Index Terms
Mathematics of computing
Mathematical analysis
Mathematical optimization
Mixed discrete-continuous optimization
Integer programming
Theory of computation
Design and analysis of algorithms
Recommendations
Algorithms for the multi-resource generalized assignment problem.
<P>The multi-resource generalized assignment problem is encountered when a set of tasks have to be assigned to a set of agents in a way that permits assignment of multiple tasks to an agent subject to the availability of a set of multiple resources ...
An Algorithm for the Generalized Assignment Problem with Special Ordered Sets
The generalized assignment problem (GAP), the 0--1 integer programming (IP) problem of assigning a set of n items to a set of m knapsacks, where each item must be assigned to exactly one knapsack and there are constraints on the availability of ...
Solving the Many to Many assignment problem by improving the Kuhn-Munkres algorithm with backtracking
The Many to Many (M-M) assignment problem is an important open problem where one task is assigned to many, but different, agents and one agent may undertake many, but different, tasks. The Kuhn-Munkres (K-M) algorithm is a famous and traditional process ...
Information
Published in.
Elsevier Science Ltd.
United Kingdom
Publication History
Contributors, other metrics, bibliometrics, article metrics.
- 3 Total Citations View Citations
- 0 Total Downloads
- Downloads (Last 12 months) 0
- Downloads (Last 6 weeks) 0
View options
Login options.
Check if you have access through your login credentials or your institution to get full access on this article.
Full Access
Share this publication link.
Copying failed.
Share on social media
Affiliations, export citations.
- Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
- Download citation
- Copy citation
We are preparing your search results for download ...
We will inform you here when the file is ready.
Your file of search results citations is now ready.
Your search export query has expired. Please try again.
- Corpus ID: 67452292
THE BOTTLENECK ASSIGNMENT PROBLEM
- Published 6 March 1959
- Engineering
75 Citations
Parallel line assignment problems, the three-dimensional bottleneck assignment problem with capacity constraints, variants of the time minimization assignment problem, an algorithm for the bottleneck generalized assignment problem, a new method to solve the bottleneck assignment problem, european journal of operational research a variant of time minimizing assignment problem, linear assignment problems and extensions, the bottleneck generalized assignment problem, general bottleneck assignment problem and its algorithm, an algorithm for solving intuitionistic fuzzy linear bottleneck assignment problems, related papers.
Showing 1 through 3 of 0 Related Papers
Navigation Menu
Search code, repositories, users, issues, pull requests..., provide feedback.
We read every piece of feedback, and take your input very seriously.
Saved searches
Use saved searches to filter your results more quickly.
To see all available qualifiers, see our documentation .
- Notifications You must be signed in to change notification settings
Bottleneck Generalized Assignment Problems
yasuoman/BGAP
Folders and files.
| Name | Name | |||
|---|---|---|---|---|
| 3 Commits | ||||
Repository files navigation
参考文献 ：Mazzola J B, Neebe A W. Bottleneck generalized assignment problems[J]. Engineering Costs and Production Economics, 1988, 14(1): 61-65.
1初始化相关的输入数据
2 根据cij与ck的关系建立新的tgbap(k)问题, 3 找到z的下限，从这个下限开始往更大的数方向寻找, 4 tgbap(k)是否存在可行解，如果不存在的话，继续往下个数找，直到找到一个可行的tgbap(k), 5 输出这个可行方案和对应的最小最大时间.
- Python 100.0%
The Generalized Assignment Problem
- First Online: 10 February 2021
Cite this chapter
- Vittorio Maniezzo 6 ,
- Marco Antonio Boschetti 6 &
- Thomas Stützle 7
Part of the book series: EURO Advanced Tutorials on Operational Research ((EUROATOR))
1350 Accesses
5 Citations
The generalized assignment problem (GAP) asks to assign n clients to m servers in such a way that the assignment cost is minimized, provided that all clients are assigned to a server and that the capacity of each server is not exceeded. It is a problem that appears, by itself or as a subproblem, in a very high number of practical applications and has therefore been intensively studied. We use this problem as a test case example of all algorithms presented in the text. This section reviews the state of the art of research on GAP and shows the application of several mathematical programming techniques on GAP instances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Subscribe and save.
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Available as EPUB and PDF
- Compact, lightweight edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
- Durable hardcover edition
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Vectors and matrices are denoted by small bold letters throughout the text, and these definitions depart from the standard for compliance with much of the literature on the GAP. Furthermore, as stated in Sect. 1.1 , remind that all variables in this chapter are indexed from 1, but in the computational traces they will appear as indexed from 0.
In this, and in all algorithms in the text, the input of all GAP instance data is implicit.
Avella P, Boccia M, Vasilyev I (2010) A computational study of exact knapsack separation for the generalized assignment problem. Comput Optim Appl 45(3):543–555
Article Google Scholar
Beasley JE (1993) Lagrangian relaxation. In: Reeves CR (ed) Modern heuristic techniques for combinatorial problems. Wiley, New York, pp 243–303
Google Scholar
Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4:280–322
Benders JF, van Nunen JA (1983) A property of assignment type mixed linear programming problems. Oper Res Lett 32:47–52
Boschetti M, Maniezzo V (2009) Benders decomposition, Lagrangean relaxation and metaheuristic design. J Heurist 15:283–312
Bressoud TC, Rastogi R, Smith MA (2003) Optimal configuration for BGP route selection. In: IEEE INFOCOM 2003, twenty-second annual joint conference of the IEEE computer and communications societies, San Francisco, CA, vol 2, pp 916–926
Campbell GM (1999) Cross-utilization of workers whose capabilities differ. Manage Sci 45(5):722–732
Cattrysse DG, Van Wassenhove LN (1992) A survey of algorithms for the generalized assignment problem. Eur J Oper Res 60(3):260–272
Cattrysse DG, Degraeve Z, Tistaert J (1998) Solving the generalised assignment problem using polyhedral results. Eur J Oper Res 108(3):618–628
Chalmet LG, Gelders LF (1976) Lagrangian relaxations for a generalized assignment-type problem. In: Proceedings of the second european congress operations research. North-Holland, Amsterdam, pp 103–109
Chu PC, Beasley JE (1997) A genetic algorithm for the generalised assignment problem. Comput Oper Res 24(1):17–23
Cordeau JF, Gaudioso M, Laporte G, Moccia L (2006) A memetic heuristic for the generalized quadratic assignment problem. INFORMS J Comput 18(4):433–443
Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper Res 8:101–111
De Farias IR, Johnson EL Jr, Nemhauser GL (2000) A generalized assignment problem with special ordered sets: a polyhedral approach. Math Program Ser A 89:187–203
Dobson G, Nambimadom RS (2001) The batch loading and scheduling problem. Oper Res 49(1):52–65
Drexl A (1991) Scheduling of project networks by job assignment. Manage Sci 37(12):1590–1602
Fisher ML, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Networks 11:109–124
Fisher ML, Jaikumar R, Van Wassenhove LN (1986) A multiplier adjustment method for the generalized assignment problem. Manage Sci 32(9):1095–1103
Foulds L, Wilson J (1997) A variation of the generalized assignment problem arising in the New Zealand dairy industry. Ann Oper Research 69:105–114
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co, New York, NY
Gavish B, Pirkul H (1985) Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math Program 33(1):31–78
Geoffrion AM (1974) Lagrangean relaxation for integer programming. Math Program Stud 2:82–114
Glover F (1965) A multiphase-dual algorithm for the zero-one integer programming problem. Oper Res 13:879–919
Glover F (1968) Surrogate constraints. Oper Res 16:741–749
Glover F (1975) Surrogate constraint duality in mathematical programming. Oper Res 23:434–451
Glover F, Hultz H, Klingman D (1979) Improved computer based planning techniques, part 2. Interfaces 9(4):12–20
Gottlieb ES, Rao MR (1990) Generalized assignment problem. Valid inequalities and facets. Math Program Ser A 46(1):31–52
Greenberg HJ, Pierskalla WP (1970) Surrogate mathematical programming. Oper Res 18:924–939
Guignard M, Kim S (1987) Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Math Program 39:215–228
Harvey NJA, Ladner RE, Lovász L, Tamir T (2006) Semi-matchings for bipartite graphs and load balancing. J Algorith 59(1):53–78
Higgins AJ (1999) Optimizing cane supply decisions within a sugar mill region. J Sched 2:229–244
Jeet V, Kutanoglu E (2007) Lagrangean relaxation guided problem space search heuristic for generalized assignment problems. Eur J Oper Res 182(3):1039–1056
Jörnsten K, Nasberg M (1986) A new Lagrangian relaxation approach to the generalized assignment problem. Eur J Oper Res 27:313–323
Lee CG, Ma Z (2004) The generalized quadratic assignment problem. Tech. Rep. 5, Department of Mechanical and Industrial Engineering, University of Toronto, Toronto
Maniezzo V (2019) Bridging the GAP. Some generalized assignment problem instances. http://astarte.csr.unibo.it/gapdata/gapinstances.html
Martello S, Toth P (1981) An algorithm for the generalized assignment problem. In: Brans J (ed) Operations research ’81. North-Holland, Amsterdam, pp 589–603
Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York, NY
Mazzola JB, Neebe AW (1993) An algorithm for the bottleneck generalized assignment problem. Comput Oper Res 20(4):355–362
Mazzola JB, Neebe AW, Dunn CVR (1989) Production planning of a flexible manufacturing system in a requirements planning environment. Int J Flex Manuf Syst 1:115–142
Mitrović-Minić S, Punnen AP (2008) Very large-scale variable neighborhood search for the generalized assignment problem. J Interdiscipl Math 11(5):653–670
Morales DR, Romeijn HE (2004) The generalized assignment problem and extensions. In: Du D, Pardalos PM (eds) Handbook of combinatorial optimization. Springer, Boston, pp 259–311
Narciso MG, Lorena L (2007) Lagrangean/surrogate relaxation for generalized assignment problems. Eur J Oper Res 182:1039–1056
Nauss RM (2003) Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J Comput 15(3):249–266
Nauss RM (2004) The elastic generalized assignment problem. J Oper Res Soc 55:1333–1341
Öncan T (2007) A survey of the generalized assignment problem and its applications. Inf Syst Oper Res 45(3):123–141
Pigatti A, Poggi de Aragao M, Uchoa E (2005) Stabilized branch-and-cut-and-price for the generalized assignment problem. Electron Notes Discr Math 19:389–395
Pirkul H, Gavish B (1986) Computer and database location in distributed computer systems. IEEE Trans Comput 35:583–590
Posta M, Ferland JA, Michelon P (2012) An exact method with variable fixing for solving the generalized assignment problem. Comput Optim Appl 52(3):629–644
Ross GT, Soland RM (1975) A branch and bound algorithm for the generalized assignment problem. Math Program 8(1):91–103
Ruland KS (1999) A model for aeromedical routing and scheduling. Int Trans Oper Res 6:57–73
Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23(3):555–565
Savelsbergh MWP (1997) A branch-and-price algorithm for the generalized assignment problem. Oper Res 45:831–841
Wilson JM (1997) A genetic algorithm for the generalised assignment problem. J Oper Res Soc 48:804–809
Zhang CW, Ong HL (2007) An efficient solution to biobjective generalized assignment problem. Adv Eng Softw 38:50–58
Download references
Author information
Authors and affiliations.
University of Bologna, Cesena, Italy
Vittorio Maniezzo & Marco Antonio Boschetti
Université Libre de Bruxelles, Brussels, Belgium
Thomas Stützle
You can also search for this author in PubMed Google Scholar
Rights and permissions
Reprints and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Maniezzo, V., Boschetti, M.A., Stützle, T. (2021). The Generalized Assignment Problem. In: Matheuristics. EURO Advanced Tutorials on Operational Research. Springer, Cham. https://doi.org/10.1007/978-3-030-70277-9_1
Download citation
DOI : https://doi.org/10.1007/978-3-030-70277-9_1
Published : 10 February 2021
Publisher Name : Springer, Cham
Print ISBN : 978-3-030-70276-2
Online ISBN : 978-3-030-70277-9
eBook Packages : Business and Management Business and Management (R0)
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
IMAGES
VIDEO
COMMENTS
Conclusion The Bottleneck Generalized Assignment Problem considered in this paper has several important applications in scheduling and allocation problems. It is strongly NP-hard, but our approach can efficiently solve it in practice for various randomly generated instances. To our knowledge, this is the first time exact and approximate ...
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.
France, April 6-10, 1987. The generalized assignment problem (GAP) is to determine the optimal assignment of jobs to agents such that all jobs are performed, and the total resource requirements placed on any agent does not exceed its available capacity. The objective function is to minimize the sum of the costs corresponding to the assignments.
A branch and bound algorithm for the generalized assignment problem in which bounds are obtained from a Lagrangian relaxation with the multiplier adjustment method appears to be about one order of magnitude faster than the best previously existing algorithms for this problem.
We consider two versions of bottleneck (or min-max) generalized assignment problem (BGAP) under capacity uncertainty: Task-BGAP and Agent-BGAP. A robust optimization approach is employed to study this issue. The decision maker's degree of risk aversion and the penalty weighting parameter are incorporated into the objective function. A state-of-the-art linearization method is introduced ...
We discuss bottleneck (or minimax) versions of the generalized assignment problem. The basic problem involves the assignment of a number of jobs to a number of agents such that each job is performed by a unique agent, and capacity limitations on the agents are not exceeded. Two versions of the bottleneck generalized problem (BGAP) are defined.
We briefly describe a simple algorithm which solves the bottleneck assignment problem: Let Π be an assignment over the graph. If there does not exist an assignment consisting of edges with strictly lower weight than Π, then Π is optimal. If there does, replace Π with the found assignment. Repeat until Π is optimal.
A variety of well-known facility location and location-allocation models are shown to be equivalent to, and therefore solvable as, generalized assignment problems GAP's and it is shown how certain types of constraints limiting the site and capacity combinations allowed can be incorporated into these models through their treatment as GAPs.
"Bicriteria multiresource generalized assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(8), pages 621-636, December. Martello, Silvano & Toth, Paolo, 1995. "A note on exact algorithms for the bottleneck generalized assignment problem," European Journal of Operational Research, Elsevier, vol. 83(3), pages 711-712, June.
A Generalized Bottleneck Assignment Problem. Abstract. A solution procedure is presented fora generalization of the standard bottleneck assignment problem in which a secondary criterion is automatically provided. problem is modeled A partitioning by this bottleneck problem to provide an of its example application. KeyWords.
Abstract. We discuss bottleneck (or minimax) versions of the generalized assignment problem. The basic problem involves the assignment of a number of jobs to a number of agents such that each job is performed by a unique agent, and capacity limitations on the agents are not exceeded. Two versions of the bottleneck generalized assignment problem ...
The generalized assignment problem (GAP), the 0--1 integer programming (IP) problem of assigning a set of n items to a set of m knapsacks, where each item must be assigned to exactly one knapsack and there are constraints on the availability of ...
Bottleneck generalized assignment problem (BGAP), is the min-max version of the well-known (min-sum) generalized assignment problem. In the BGAP, the maximum penalty incurred by assigning each task to an agent is minimized. Min-sum objective functions are commonly used in private sector applications, while min-max objective function can be ...
DOI: 10.1016/0305-0548(93)90079-X Corpus ID: 30952272; An algorithm for the bottleneck generalized assignment problem @article{Mazzola1993AnAF, title={An algorithm for the bottleneck generalized assignment problem}, author={Joseph B. Mazzola and Alan W. Neebe}, journal={Comput.
Bottleneck generalized assignment problem 359 Step 2. This step attempts to find a feasible solution to TBGAP by finding a feasible solution to a corresponding minisum GAP. First construct the cost matrix F = {f, j} such that for iel and j e J. fi} = 'l ifCy<ZH oo otherwise. Using a heuristic for the (minisum) generalized assignment problem ...
In applied mathematics, the maximum generalized assignment problem is a problem in combinatorial optimization. This problem is a generalization of the assignment problem in which both tasks and agents have a size. Moreover, the size of each task might vary from one agent to the other. This problem in its most general form is as follows: There ...
A solution procedure is presented for a generalization of the standard bottleneck assignment problem in which a secondary criterion is automatically provided. A partitioning problem is modeled by this bottleneck problem to provide an example of its application.
Abstract. We discuss a bottleneck (or minimax) version of the generalized assignment problem, known as the task bottleneck generalized assignment problem (TBGAP). TBGAP involves the assignment of a number of jobs to a number of agents such that each job is performed by a unique agent, and capacity limitations on the agents are not exceeded.
THE BOTTLENECK ASSIGNMENT PROBLEM. O. Gross. Published 6 March 1959. Engineering. TLDR. 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. Expand.
Bottleneck Generalized Assignment Problems 参考文献 ：Mazzola J B, Neebe A W. Bottleneck generalized assignment problems[J]. Engineering Costs and Production Economics, 1988, 14(1): 61-65.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH ELSEVIER European Journal of Operational Research 83 (1995) 711-712 Short Communication A note on exact algorithms for the bottleneck generalized assignment problem Silvano Martello, Paolo Toth DEIS, Universit~ di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy Abstract We give a computational comparison between the algorithms of Mazzola-Neebe (1993 ...
The generalized assignment problem appears often in the literature, both in itself and as a subproblem in some specialized situations. It was first introduced as a model for applications that "include assigning software development tasks to programmers, assigning jobs to computers in computer networks, scheduling variable length television commercials into time slots, and scheduling payments ...