generalized assignment problem algorithm

• DOI: 10.1007/3-540-56279-6_88
• Corpus ID: 206637011

Generalized Assignment Problems

• S. Martello , P. Toth
• Published in International Symposium on… 16 December 1992
• Mathematics, Computer Science

29 Citations

The generalized assignment problem with flexible jobs, the vehicle routing problem: an overview of exact and approximate algorithms, heuristic procedures for the capacitated vehicle routing problem, formulations and solution algorithms for a dynamic generalized assignment problem, a column generation heuristic for a dynamic generalized assignment problem, dantzig-wolfe and lagrangian decompositions in integer linear programming, generalized assignment for multi-robot systems via distributed branch-and-price, a truthful mechanism for the generalized assignment problem, heuristics for the generalised assignment problem: simulated annealing and tabu search approaches, new polynomial-time instances to various knapsack-type problems, 16 references, the generalized assignment problem: valid inequalities and facets, (1,k)-configuration facets for the generalized assignment problem, algorithms and codes for the assignment problem, a branch and bound algorithm for the generalized assignment problem, technical note - an improved dual based algorithm for the generalized assignment problem, knapsack problems: algorithms and computer implementations, a multiplier adjustment method for the generalized assignment problem, bottleneck generalized assignment problems, a new lagrangian relaxation approach to the generalized assignment problem, an effective subgradient algorithm for the generalized assignment problem, related papers.

Showing 1 through 3 of 0 Related Papers

Solving Generalized Assignment Problem using Branch-And-Price

Oct 27, 2021

Table of Contents

Generalized assignment problem, dantzig-wolfe decomposition, column generation, standalone model, initial solution, branching rule, branch-and-price.

One of the best known and widely researched problems in combinatorial optimization is Knapsack Problem:

• given a set of items, each with its weight and value,
• select a set of items maximizing total value
• that can fit into a knapsack while respecting its weight limit.

The most common variant of a problem, called 0-1 Knapsack Problem can be formulated as follows:

• \(m\) - number of items;
• \(x_i\) - binary variable indicating whether item is selected;
• \(v_i\) - value of each items;
• \(w_i\) - weight of each items;
• \(W\) - maximum weight capacity.

As often happens in mathematics, or science in general, an obvious question to ask is how the problem can be generalized. One of generalization is Generalized Assignment Problem. It answers question - how to find a maximum profit assignment of \(m\) tasks to \(n\) machines such that each task (\(i=0, \ldots, m\)) is assigned to exactly one machine (\(j=1, \ldots, n\)), and one machine can have multiple tasks assigned to subject to its capacity limitation. Its standard formulation is presented below:

• \(n\) - number of machines;
• \(m\) - number of tasks;
• \(x_{ij}\) - binary variable indicating whether task \(i\) is assigned to machine \(j\);
• \(v_{ij}\) - value/profit of assigning task \(i\) to machine \(j\);
• \(w_{ij}\) - weight of assigning task \(i\) to machine \(j\);
• \(c_j\) - capacity of machine \(j\).

Branch-and-price

Branch-and-price is generalization of branch-and-bound method to solve integer programs (IPs),mixed integer programs (MIPs) or binary problems. Both branch-and-price, branch-and-bound, and also branch-and-cut, solve LP relaxation of a given IP. The goal of branch-and-price is to tighten LP relaxation by generating a subset of profitable columns associated with variables to join the current basis.

Branch-and-price builds at the top of branch-and-bound framework. It applies column generation priori to branching. Assuming maximization problem, branching occurs when:

• Column Generation is finished (i.e. no profitable columns can be found).
• Objective value of the current solution is greater than best lower bound.
• The current solution does not satisfy integrality constraints.

However, if only first two conditions are met but not the third one, meaning the current solution satisfies integrality constraints, then the best solution and lower bound are updated (lower bound is tightened) with respectively the current solution and its objective value.

The crucial element needed to apply branch-and-price successfully is to find branching scheme. It is tailored to specific problem to make sure that it does not destroy problem structure and can be used in pricing subproblem to effectively generate columns that enter Restricted Master Problem (RMP) while respecting branching rules .

Below is flow diagram describing branch-and-price method:

The successful application B&P depends on tight/strong model formulation. Model formulation is considered tight if solution of its LP relaxation satisfies (frequently) integrality constraints. One of structured approaches to come up with such a formulation is to use Dantzig-Wolfe Decomposition technique. We will see example of it applied to Generalized Assignment Problem (GAP).

A standard formulation was described above. Now, let’s try to reformulate problem. Let

be a set containing all feasible solutions to Knapsack problem for \(j\)-th machine. Clearly, \(S_j\) contains finite number of points, so \(S_j = \{ \mathbf{z}_j^1, \ldots, \mathbf{z}_j^{K_j} \}\), where \(\mathbf{z}_j^k \in \{0, 1\}^{m}\). You can think about \(\mathbf{z}_j^k \in \{0, 1\}^{m}\) as 0-1 encoding of tasks that form \(k\)-th feasible solution for machine \(j\). Now, let \(S = \{ \mathbf{z}_1^1, \ldots, \mathbf{z}_1^{K_1}, \ldots, \mathbf{z}_n^1, \ldots, \mathbf{z}_n^{K_n} \}\) be a set of all feasible solution to GAP. It, potentially, contains a very large number of elements. Then, every point \(x_{ij}\) can be expressed by the following convex combination:

where \(z_{ij}^k \in \{0, 1\}\), and \(z_{ij}^k = 1\) iff task \(i\) is assigned to machine \(j\) in \(k\)-th feasible solution for the machine.

Now, let’s use this representation to reformulate GAP:

Note that we do not need capacity restrictions as they are embedded into definition of feasible solution for machine \(j\).

Now that we have formulation that is suitable for column generation, let’s turn our attention to it.

Column generation is another crucial component of branch-and-price. There are many great resources devoted to column generation so I will mention only core points:

• Column generation is useful when a problem’s pool of feasible solutions contains many elements but only small subset will be present in the optimal solution.
• There exists subproblem (called often pricing problem) that can be used to effectively generate columns that should enter RMP.
• Column generation starts with initial feasible solution.
• Pricing subproblem objective function is updated with dual of the current solution.
• Columns with positive reduced cost, in case of maximization problem, enter problem.
• Procedure continues until such columns exist.

Below is flow diagram describing column generation method:

Implementation

Let’s see how one can approach implementation of B&P to solve Generalized Assignment Problem. Below is discussion about main concepts and few code excerpts, a repository containing all code can be found on github .

An example of problem instance taken from [1] is:

It is always good idea to have a reference simple(r) implementation that can be used to validate our results using more sophisticated methods. In our case it is based on standard problem formulation. Implementation can be found in repo by checking classes GAPStandaloneModelBuilder and GAPStandaloneModel . Formulation for a problem instance presented above looks as follows:

Now let’s try to examine building blocks of B&P to discus main part at the end, once all the puzzles are there.

To start column generation process, we need to have an initial solution. One possible way to derive it is to use two-phase Simplex method. In first step, you add slack variables to each constraint and set objective function as their sum. Then you minimize the problem. If your solution has objective value \(0\), then first of all you have initial solution and you know that your problem is feasible. In case you end up with positive value for any of slack variables, you can conclude that the problem is infeasible. You can stop here.

I took a different approach and came up with simple heuristic that generate initial solution. I have not analyzed it thoroughly so I am not sure if it is guaranteed to always return feasible solution if one exists. Its idea is quite simple:

• Construct bipartite graph defined as \(G=(V, A)\), where \(V = T \cup M\) – \(T\) is set of tasks and obviously \(M\) is set of machines. There exists arc \(a = (t, m)\) if \(w_{tm} \le rc_{m}\), where \(rc_{m}\) is remaining capacity for machine \(m\). Initially remaining capacity is equal to capacity of machine and with each iteration, and assignment of task to machine it is being update. If \(\vert A \vert = 0\), then stop.
• Solve a minimum weight matching problem.
• Update assignments – say that according to solution task \(t_0\) should be assigned to machine \(m_0\), then \(\overline{rc}_{m_0} = rc_{m_0} - w_{t_0 m_0}\).
• Find a machine where task is contributing with the lowest weight – say machine \(m_0 = \arg\min \{ m: w_{t_0 m} \}\).
• Free up remaining capacity so there is enough space for \(t_0\) on machine \(m_0\). Any tasks that were de-assigned in a process are added to pool of unassigned tasks.
• Repeat until there are no unassigned tasks.

See details on github .

As we said before the most important piece needed to implement B&P is branching rules which does not destroy structure of subproblem. Let’s consider non-integral solution to RMP. Given convexity constraint it means that there exists machine \(j_0\) and at least two, and for sake of example say exactly two, \(0 < \lambda_{j_0} ^{k_1} < 1\) and \(0 < \lambda_{j_0} ^{k_2} < 1\) such that \(\lambda_{j_0} ^{k_1} + \lambda_{j_0} ^{k_2} = 1\). Since with each of \(\lambda\)s is connected different assignment (set of tasks), then it leads us to a conclusion that there exists task \(i_0\) such that \(x_{i_0 j_0} < 1\) expressed in variables from the original formulation. Now, let’s use this information to formulate branching rule:

• left child node: a task \(i_0\) must be assigned to a machine \(j_0\).
• right child node: a task \(i_0\) cannot be assigned to a machine \(j_0\).

We can say that branching is based on \(x_{ij}\) from standard formulation. And it can be represented by:

Note that we can use the branching rule to easily to filter out initial columns for each node that do not satisfy those conditions:

• \(j = j_0\) and task \(i_0 \in T_{j_0}\), or
• \(j \neq j_0\) and task \(i_0 \notin T_{j}\).
• \(j = j_0\) and task \(i_0 \in T_{j_0}\).

See on github .

Based on the same principle, subproblem’s pool of feasible solution are created - i.e. on left child node:

• knapsack subproblem for machine \(j_0\) – variable representing task \(i_0\) is forced to be \(1\).
• knapsack subproblem for machine \(j \neq j_0\) – variable representing task \(i_0\) is forced to be \(0\).

Similarly for right childe node. See on github .

Below is an outline of main loop of column generation. It is an implementation of flow diagram from above so I will not spend too much time describing it. The only part maybe worth commenting is stop_due_to_no_progress - it evaluates whether column generation did not make any progress in last \(k\)-iterations and it should be stop.

Now, let’s see how constructing subproblems, solving them and then adding back column(s) to RMP looks like. We have as many subproblems as machines. Once a solution is available, we check whether it has positive reduced cost. A solution to knapsack problem corresponds to column in RMP. So if the column with positive reduced cost was identified and added, then new iteration of column generation will be executed. Gurobi allows to query information about all other identified solutions, so we can utilize this feature and add all columns that have the same objective value as optimal solution, potentially adding more than one column and hoping it will positively impact solution time.

Note that each subproblem is independent so in principle they could be solved in parallel. However due to Python Global Interpreter Lock (GIL) that prevent CPU-bounded threads to run in parallel, they are solved sequentially. Additionally depending on your Gurobi license, you might not be allowed to solve all those models in parallel even if Python would allow it.

Below you can find example of one of the RMPs:

and subproblem with dual information passed:

Now that we have all building blocks prepared, then let’s turn our attention back to B&P.

In the blog post, Branch-and-Price technique for solving MIP was explained. An example of applying B&P for Generalized Assignment Problem was presented. The solution approach used Python as programming language and Gurobi as solver.

[1] Der-San Chen, Robert G. Batson, Yu Dang (2010), Applied Integer Programming - Modeling and Solution, Willey. [2] Lasdon, Leon S. (2002), Optimization Theory for Large Systems, Mineola, New York: Dover Publications. [3] Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, Pamela H. Vance, (1998) Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329.

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

How to solve large scale generalized assignment problem

I am looking for a way to solve a large scale Generalized assignment problem (To be precise, it is a relaxation of the Generalized assignment problem, because the second constraint has $\le$ instead of $=$ ). Here, $m$ is the number of agents and $n$ is the number of tasks. $$ \begin{aligned} &\text{maximize} && \sum_{i}^{m} \sum_{j}^{n} p_{ij}x_{ij} \\\ &\text{subject to} && \sum_{j}^{n} w_{ij}x_{ij} \le t_{i} &&& \forall i \\\ & && \sum_{i}^{m} x_{ij} \le 1 &&& \forall j \\\ & && x_{ij} \in \{0, 1\} \end{aligned} $$

• $m \le 1,000$
• $n \le 10,000,000$
• $p_{ij} \le 1,000$
• $w_{ij} \le 1,000$
• $t_i \le 200,000$
• valid agent-task pair(i.e. number of non zero $p_{ij}$ ) $\le 200,000,000$
• time limit : 6 hours

Generalized assignment problem is NP-hard, so I'm not trying to find an exact solution. Are there any approximation algorithm or heuristic to solve this problem?

Also, are there any other approaches to solving large scale NP-hard problems? For example, I was wondering if it is possible to reduce the number of variables by clustering agents or tasks, but I did not find such a method.

• assignment-problem

• $\begingroup$ All else failing, there is the greedy heuristic: sort the $p_{ij}$ in descending order, then make assignments in that order, tracking the remaining capacity of each agent and skipping assignments that would exceed that capacity. I did not put this in as an answer because it is such a low hanging fruit. $\endgroup$ –  prubin ♦ Commented Jul 29, 2021 at 18:13
• $\begingroup$ The problem that you wrote is not exactly the Generalized Assignment Problem, because the second set of constraints has $\le$ instead of $=$. This makes the problem much easier since finding a feasible solution is not an issue anymore in this case. Is it what you meant to write? $\endgroup$ –  fontanf Commented Jul 29, 2021 at 20:22
• $\begingroup$ @prubin Thank you. If there is no other way, I will use greedy algorithm. $\endgroup$ –  user5966 Commented Jul 30, 2021 at 6:02
• $\begingroup$ @fontanf Yes, I'm trying to solve the relaxation of the Generalized assignment problem. I've added this to the post $\endgroup$ –  user5966 Commented Jul 30, 2021 at 6:11

2 Answers 2

The instances you plan to solve are orders of magnitude larger than the ones from the datasets used in the scientific literature on the Generalized Assignment Problem. The largest instances of the literature have $m = 80$ and $n = 1600$ . Most algorithms designed for these instances won't be suitable for you.

What seems the most relevant in your case are the polynomial algorithms described in "Knapsack problems: algorithms and computer implementations" (Martello et Toth, 1990):

• Greedy: sort all agent-task pairs according to a given criterion, and then assign greedily from best to worst the unassigned tasks. Complexity: $O(n m \log (n m))$
• Regret greedy: for all tasks, sort its assignments according to a given criterion. At each step, assign the task with the greatest difference between its best assignment and its second-best assignment, and update the structures. Complexity: $O(n m \log m + n^2)$

Various sorting criteria have been proposed: pij , pij/wij , -wij , -wij/ti ... -wij and -wij/ti are more suited for the case where all items have to be assigned. In your case pij and pij/wij might yield good results

Then, they propose to try to shift each task once to improve the solution. With at most one shift per task, the algorithms remain polynomial, but you can try more shifts if you have more time.

Note that these algorithms might be optimized if not all pairs are possible, as you indicate in your case.

I have some implementations here for the standard GAP (and a min objective). You can try to play with them to get an overview of what might work or not in your case

You could try using the greedy heuristic to get an initial solution and then try out one of the many neighborhood-search type metaheuristics. I mentioned sorting on $p_{ij}$ in a comment, but it might (or might not) be better to sort on $p_{ij}/w_{ij}$ (or, time permitting, try both and pick the better solution). For improving on the starting solution, GRASP and simulated annealing would be possibilities. Tabu search is popular with some people, but the memory requirements of maintaining a table of tabu solutions might be prohibitive. I'm fond of genetic algorithms, but I think we can rule out a GA (or other "evolutionary" metaheuristic) based on memory considerations. Personally, I'd be tempted to check out GRASP first.

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged heuristics assignment-problem or ask your own question .

• Featured on Meta
• Upcoming sign-up experiments related to tags

Hot Network Questions

• What actual purpose do accent characters in ISO-8859-1 and Windows 1252 serve?
• How do I pour *just* the right amount of plaster into these molds?
• Can God transcend human logic and reasoning?
• Is it legal to discriminate on marital status for car insurance/pensions etc.?
• Exception handling: 'catch' without explicit 'try'
• How will the ISS be decommissioned?
• How to merge two videos with openshot?
• Is there a non-perfect field in which polynomials of large degree are reducible?
• Should mail addresses for logins be stored hashed to minimize impact of data loss?
• What is the translation of lawfare in French?
• sample size in chi-squared test
• Conveying 'odds and ends'
• What exactly is beef bone extract, beef extract, beef fat (all powdered form) and where can I find it?
• Isn't it problematic to look at the data to decide to use a parametric vs. non-parametric test?
• What's the best way to line up equals on a line of text?
• Would a spaceport on Ceres make sense?
• Could space habitats have large transparent roofs?
• Weird behavior by car insurance - is this legit?
• Binary Slashes Display
• Folk stories and notions in mathematics that are likely false, inaccurate, apocryphal, or poorly founded?
• Why did Geordi have his visor replaced with ocular implants between Generations and First Contact?
• Can a unique position be deduced if pieces are replaced by checkers (can see piece color but not type)
• Why does c show up in Schwarzschild's equation for the horizon radius?
• How to join two PCBs with a very small separation?

• Advanced Search

An approximation algorithm for the generalized assignment problem

• 181 citation

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.

• Luo Q Nagarajan V Sundt A Yin Y Vincent J Shahabi M (2023) Efficient Algorithms for Stochastic Ride-Pooling Assignment with Mixed Fleets Transportation Science 10.1287/trsc.2021.0349 57 :4 (908-936) Online publication date: 1-Jul-2023 https://dl.acm.org/doi/10.1287/trsc.2021.0349
• Aouad A Segev D (2023) Technical Note—An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem Operations Research 10.1287/opre.2022.2268 71 :4 (1414-1433) Online publication date: 1-Jul-2023 https://dl.acm.org/doi/10.1287/opre.2022.2268
• Krishnaswamy R Li S Suriyanarayana V Saha B Servedio R (2023) Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse Proceedings of the 55th Annual ACM Symposium on Theory of Computing 10.1145/3564246.3585222 (775-788) Online publication date: 2-Jun-2023 https://dl.acm.org/doi/10.1145/3564246.3585222
• Show More Cited By

Index Terms

Mathematics of computing

Mathematical analysis

Functional analysis

Approximation

Theory of computation

Design and analysis of algorithms

Approximation algorithms analysis

Scheduling algorithms

Online algorithms

Online learning algorithms

Theory and algorithms for application domains

Machine learning theory

Reinforcement learning

Sequential decision making

Recommendations

An online algorithm for a problem in scheduling with set-ups and release times.

We address the problem of sequential single machine scheduling of jobs with release times, where jobs are classified into types, and the machine must be properly configured to handle jobs of a given type. The objective is to minimize the maximum flow ...

Approximation Schemes for Minimizing the Maximum Lateness on a Single Machine with Release Times Under Non-availability or Deadline Constraints

In this paper, we consider four single-machine scheduling problems with release times, with the aim of minimizing the maximum lateness. In the first problem we have a common deadline for all the jobs. The second problem looks for the Pareto frontier ...

Scheduling of Project Networks by Job Assignment

A recurring problem in project management involves the allocation of scarce resources to the individual jobs comprising the project. In many situations such as audit scheduling, the resources correspond to individuals skilled labour. This naturally ...

Information

Published in.

Springer-Verlag

Berlin, Heidelberg

Publication History

Author tags.

• Approximation algorithms
• generalized assignment problem
• scheduling unrelated parallel machines

Contributors

Other metrics, bibliometrics, article metrics.

• 181 Total Citations View Citations
• 0 Total Downloads
• Downloads (Last 12 months) 0
• Downloads (Last 6 weeks) 0
• Zeng L Chopra S Smilowitz K (2022) A Bounded Formulation for The School Bus Scheduling Problem Transportation Science 10.1287/trsc.2022.1130 56 :5 (1148-1164) Online publication date: 1-Sep-2022 https://dl.acm.org/doi/10.1287/trsc.2022.1130
• Feldman J Segev D (2022) Technical Note—The Multinomial Logit Model with Sequential Offerings Operations Research 10.1287/opre.2021.2218 70 :4 (2162-2184) Online publication date: 1-Jul-2022 https://dl.acm.org/doi/10.1287/opre.2021.2218
• Fresa A Champati J Boukerche A Giannelli C Sun Z (2022) An Offloading Algorithm for Maximizing Inference Accuracy on Edge Device in an Edge Intelligence System Proceedings of the 25th International ACM Conference on Modeling Analysis and Simulation of Wireless and Mobile Systems 10.1145/3551659.3559044 (15-23) Online publication date: 24-Oct-2022 https://dl.acm.org/doi/10.1145/3551659.3559044
• Gorantla B Mehta N (2022) Interplay Between Interference-Aware Resource Allocation Algorithm Design, CSI, and Feedback in Underlay D2D Networks IEEE Transactions on Wireless Communications 10.1109/TWC.2021.3121874 21 :5 (3452-3463) Online publication date: 1-May-2022 https://dl.acm.org/doi/10.1109/TWC.2021.3121874
• Gálvez W Grandoni F Ingala S Heydrich S Khan A Wiese A (2021) Approximating Geometric Knapsack via L-packings ACM Transactions on Algorithms 10.1145/3473713 17 :4 (1-67) Online publication date: 4-Oct-2021 https://dl.acm.org/doi/10.1145/3473713
• Xiang J Xu G Ma C Hou J (2021) End-to-End Learning Deep CRF Models for Multi-Object Tracking Deep CRF Models IEEE Transactions on Circuits and Systems for Video Technology 10.1109/TCSVT.2020.2975842 31 :1 (275-288) Online publication date: 6-Jan-2021 https://dl.acm.org/doi/10.1109/TCSVT.2020.2975842
• Beaumont O Canon L Eyraud-Dubois L Lucarelli G Marchal L Mommessin C Simon B Trystram D (2020) Scheduling on Two Types of Resources ACM Computing Surveys 10.1145/3387110 53 :3 (1-36) Online publication date: 28-May-2020 https://dl.acm.org/doi/10.1145/3387110

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.

An approximation algorithm for the generalized assignment problem

• Published: February 1993
• Volume 62 , pages 461–474, ( 1993 )

Cite this article

• David B. Shmoys 1 &
• Éva Tardos 1  

2941 Accesses

449 Citations

6 Altmetric

Explore all metrics

The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly one machine; processing job j on machine i requires time p ij and incurs a cost of c ij ; each machine i is available for T i time units, and the objective is to minimize the total cost incurred. Our main result is as follows. There is a polynomial-time algorithm that, given a value C , either proves that no feasible schedule of cost C exists, or else finds a schedule of cost at most C where each machine i is used for at most 2 T i time units.

We also extend this result to a variant of the problem where, instead of a fixed processing time p ij , there is a range of possible processing times for each machine—job pair, and the cost linearly increases as the processing time decreases. We show that these results imply a polynomial-time 2-approximation algorithm to minimize a weighted sum of the cost and the makespan, i.e., the maximum job completion time. We also consider the objective of minimizing the mean job completion time. We show that there is a polynomial-time algorithm that, given values M and T , either proves that no schedule of mean job completion time M and makespan T exists, or else finds a schedule of mean job completion time at most M and makespan at most 2 T.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA) Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

New efficient algorithms for the two-machine no-wait chain-reentrant shop problem

Primal and dual mixed-integer least-squares: distributional statistics and global algorithm

The cluster problem in constrained global optimization.

J.L. Bruno, E.G. Coffmann Jr. and R. Sethi, “Scheduling independent tasks to reduce mean finishing time,” Communications of the ACM 17 (1974) 382–387.

Google Scholar  

W.A. Horn, “Minimizing average flow time with parallel machines,” Operations Research 21 (1973) 846–847.

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, “Sequencing and scheduling: algorithms and complexity,” in: A.H.G. Rinnooy Kan and P. Zipkin, eds., Handbooks in Operations Research and Management Science, Vol. 4: Logistics of Production and Inventory (North-Holland, Amsterdam, 1993) pp. 445–522.

J.K. Lenstra, D.B. Shmoys and É. Tardos, “Approximation algorithms for scheduling unrelated parallel machines,” Mathematical Programming 46 (1990) 259–271.

J.-H. Lin and J.S. Vitter, “ ε -approximations with minimum packing constraint violation,” in: Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (1992) pp. 771–782.

L. Lovász and M. Plummer, Matching Theory (Akademiai Kiado, Budapest, and North-Holland, Amsterdam, 1986).

S.A. Plotkin, D.B. Shmoys and É. Tardos, “Fast approximation algorithms for fractional packing and covering problems” Technical Report 999, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1992).

M.A. Trick, “Scheduling multiple variable-speed machines,” in: Proceedings of the 1st Conference on Integer Programming and Combinatorial Optimization (1990) pp. 485–494.

M.A. Trick, “Scheduling multiple variable-speed machines,” unpublished manuscript (1991).

Download references

Author information

Authors and affiliations.

School of Operations Research and Engineering, Cornell University, 232 ET&C Building, 14853, Ithaca, NY, USA

David B. Shmoys & Éva Tardos

You can also search for this author in PubMed   Google Scholar

Additional information

Research partially supported by an NSF PYI award CCR-89-96272 with matching support from UPS, and Sun Microsystems, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.

Research supported in part by a Packard Fellowship, a Sloan Fellowship, an NSF PYI award, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.

Rights and permissions

Reprints and permissions

About this article

Shmoys, D.B., Tardos, É. An approximation algorithm for the generalized assignment problem. Mathematical Programming 62 , 461–474 (1993). https://doi.org/10.1007/BF01585178

Download citation

Received : 10 April 1991

Revised : 14 January 1993

Issue Date : February 1993

DOI : https://doi.org/10.1007/BF01585178

Share this article

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

• Approximation algorithms
• generalized assignment problem
• scheduling unrelated parallel machines
• Find a journal
• Publish with us
• Track your research