A survey of algorithms for the generalized assignment problem

DOI10.1016/0377-2217(92)90077-MzbMath0760.90071OpenAlexW1978264569MaRDI QIDQ1199507

Dirk G. Cattrysse, Luk N. Van Wassenhove

Publication date: 16 January 1993

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(92)90077-m

zbMATH Keywords

heuristicsbranch-and-boundminimum cost assignment of jobs to agents

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Boolean programming (90C09) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Maximal covering code multiplexing access telecommunication networks, Reducing multivalued discrete variables in solving separable task assignment problems, Heuristics for the multi-resource generalized assignment problem, On solving the Lagrangian dual of integer programs via an incremental approach, Assignment problems: a golden anniversary survey, Elitist genetic algorithm for assignment problem with imprecise goal, A genetic algorithm for the generalised assignment problem, Fast machine reassignment, Multi-neighborhood local search optimization for machine reassignment problem, Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches, A PERCENTILE SEARCH HEURISTIC FOR GENERALIZED ASSIGNMENT PROBLEMS WITH A VERY LARGE NUMBER OF JOBS, Supply capacity acquisition and allocation with uncertain customer demands, A comparison of two methods for solving 0-1 integer programs using a general purpose simulated annealing algorithm, Lagrangian relaxation guided problem space search heuristics for generalized assignment problems, Product allocation to different types of distribution center in retail logistics networks, A hybrid heuristic for the generalized assignment problem, A three-phase matheuristic algorithm for the multi-day task assignment problem, Two stage decision making approach for Sensor Mission Assignment Problem, Approximating solutions to a bilevel capacitated facility location problem with customer's patronization toward a list of preferences, A Survey of the Generalized Assignment Problem and Its Applications, Sensitivity analysis of combinatorial optimization problems using evolutionary bilevel optimization and data mining, Utilizing individual picker skills to improve order batching in a warehouse, The equilibrium generalized assignment problem and genetic algorithm, A Lagrangian relaxation-based heuristic for the vehicle routing with full container load, Stochastic binary problems with simple penalties for capacity constraints violations, Tight Approximation Bounds for the Seminar Assignment Problem, Effective algorithm and heuristic for the generalized assignment problem., Unnamed Item, New mathematical models for team formation of sports clubs before the match, An exact algorithm for the minimum squared load assignment problem, Improved Online Algorithms for Knapsack and GAP in the Random Order Model, The capacitated mobile facility location problem, On a class of assignment problems., Overcoming human trafficking via operations research and analytics: opportunities for methods, models, and applications, Repulsive assignment problem, A genetic algorithm for the project assignment problem, A new extended formulation of the generalized assignment problem and some associated valid inequalities, The stochastic generalised assignment problem with Bernoulli demands, A COMPREHENSIVE SURVEY OF THE REVIEWER ASSIGNMENT PROBLEM, A tabu search heuristic for the generalized assignment problem, Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique, A dynamic tabu search for large-scale generalized assignment problems, Exact solutions to a class of stochastic generalized assignment problems, Very large-scale variable neighborhood search for the generalized assignment problem, Optimal ABC inventory classification using interval programming, Improved online algorithms for Knapsack and GAP in the random order model, Fair task allocation problem, Optimizing cane supply decisions within a sugar mill region, Loading tow trains ergonomically for just-in-time part supply, Exploiting process plan flexibility in production scheduling: A multi-objective approach, Lagrangean/surrogate relaxation for generalized assignment problems, Relaxation heuristics for a generalized assignment problem, Optimization-Based Very Large-Scale Neighborhood Search for Generalized Assignment Problems with Location/Allocation Considerations, Exact Solution Methods for a Generalized Assignment Problem with Location/Allocation Considerations, Low earth orbit satellite based communication systems -- research opportunities, A class of greedy algorithms for the generalized assignment problem, Local search intensified: very large-scale variable neighborhood search for the multi-resource generalized assignment problem, Distribution requirements and compactness constraints in school timetabling, A branching algorithm to solve binary problem in uncertain environment: an application in machine allocation problem, Constructing a course schedule by solving a series of assignment type problems, Heuristic sensitivity analysis in a combinatoric environment: An exposition and case study, Solving the generalised assignment problem using polyhedral results, A multiplier adjustment technique for the capacitated concentrator location problem, Improving defensive air battle management by solving a stochastic dynamic assignment problem via approximate dynamic programming, Development and evaluation of an assignment heuristic for allocating cross-trained workers, Online generalized assignment problem with historical information, A set partitioning heuristic for the generalized assignment problem, The generalized assignment problem with minimum quantities, A tabu search approach to the constraint satisfaction problem as a general problem solver, Competitive strategies for an online generalized assignment problem with a service consecution constraint

Cites Work

• Unnamed Item
• Unnamed Item
• Improved Lagrangean decomposition: An application to the generalized assignment problem
• Zero-one integer programs with few contraints - lower bounding theory
• The bound improving sequence algorithm
• Zero-one integer programs with few constraints - Efficient branch and bound algorithms
• Exact methods for the knapsack problem and its generalizations
• A new Lagrangian relaxation approach to the generalized assignment problem
• A revised bound improvement sequence algorithm
• An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
• An application-oriented guide for designing Lagrangean dual ascent algorithms
• A property of assignment type mixed integer linear programming problems
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• Nonlinear 0–1 programming: I. Linearization techniques
• Nonlinear 0–1 programming: II. Dominance relations and algorithms
• A hybrid algorithm for the generalized assignment problem
• Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
• Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem
• Generalized Assignment with Nonlinear Capacity Interaction
• A Dual-Based Procedure for Uncapacitated Facility Location
• Pivot and Complement–A Heuristic for 0-1 Programming
• Note—On the Maximal Covering Location Problem and the Generalized Assignment Problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• A branch and bound algorithm for the generalized assignment problem
• Facets of the knapsack polytope
• An Integer Generalized Transportation Model for Optimal Job Assignment in Computer Networks
• Modeling Facility Location Problems as Generalized Assignment Problems