the dynamic hungarian algorithm for the assignment problem with changing costs

The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs

• January 2007
• This person is not on ResearchGate, or hasn't claimed this research yet.

• Carnegie Mellon University

Abstract and Figures

Discover the world's research

• 25+ million members
• 160+ million publication pages
• 2.3+ billion citations
• SENSORS-BASEL
• Xudong Yang
• Lianhe Shao
• Madhuri Gollapalli

• Satish Mahadevan Srinivasan

• George Okereke
• Stephenson Echezona
• Joshua B Agbogun
• Yongju Tong

• Xiaoning Jiao
• Siping Wang
• Chenyan Jia
• Zhitao Cheng
• Yanlin Leng
• Sven Koenig

• Xiaowen Zhang

• Ori Manasherov
• Amir Degani
• INFORM SCIENCES

• IEEE Trans Acoust Speech Signal Process
• Christos H. Papadimitriou

• J. A. Bondy
• U. S. R. Murty
• James Munkres
• Nav Res Logist Q
• Eugene L Lawler
• Michael Z. Spivey

• R E Burkard
• Recruit researchers
• Join for free
• Login Email Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google Welcome back! Please log in. Email · Hint Tip: Most researchers use their institutional email address as their ResearchGate login Password Forgot password? Keep me logged in Log in or Continue with Google No account? Sign up

The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs

Publisher statement, usage metrics.

• Adaptive Agents and Intelligent Robotics

• by Academic Documents
• Access the best Study Guides Lecture Notes and Practice Exams Log In Sign Up

The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs G Ayorkor Mills Tettey Anthony Stentz M Bernardine Dias CMU RI TR 07 27 July 2007 Robotics Institute Carnegie Mellon University Pittsburgh Pennsylvania 15213 c Carnegie Mellon University Abstract In this paper we present the dynamic Hungarian algorithm applicable to optimally solving the assignment problem in situations with changing edge costs or weights This problem is relevant for example in a transportation domain where the unexpected closing of a road translates to changed transportation costs When such cost changes occur after an initial assignment has been made the new problem like the original problem may be solved from scratch using the well known Hungarian algorithm However the dynamic version of the algorithm which we present solves the new problem more efficiently by repairing the initial solution obtained before the cost changes We present proofs of the correctness and efficiency of our algorithm and present simulation results illustrating its efficiency I Contents 1 Introduction 1 2 Background 2 1 Terminology and Notation 2 2 Hungarian Algorithm 2 3 Related Work 2 3 1 The incremental assignment problem 2 3 2 The dynamic assignment problem 2 2 3 5 5 5 3 The Assignment Problem with Changing Costs 6 4 Example 8 5 Proofs 10 6 Numerical Results 12 7 Conclusions 13 III 1 Introduction The assignment problem also known as the maximum weighted bipartite matching problem is a widely studied problem applicable to many domains 2 It can be stated as follows given a set of workers a set of jobs and a set of ratings indicating how well each worker can perform each job determine the best possible assignment of workers to jobs such that the total rating is maximized 5 More generally given a bipartite graph made up of two partitions V and U and a set of weighted edges E between the two partitions the problem requires the selection of a subset of the edges with a maximum sum of weights such that each node vi V or ui U is connected to at most one edge 6 The problem may also be phrased as a minimization problem by considering instead of edge weights wij a set of non negative edge costs cij W wij where W is at least as large as the maximum of all the edge weights Unless otherwise stated this paper considers the minimization formulation of the problem The classical solution to the assignment problem is given by the Hungarian or Kuhn Munkres algorithm originally proposed by H W Kuhn in 1955 3 and refined by J Munkres in 1957 5 The Hungarian algorithm solves the assignment problem in O n3 time where n is the size of one partition of the bipartite graph This and other existing algorithms for solving the assignment problem assume the a priori existence of a matrix of edge weights wij or costs cij and the problem is solved with respect to these values In the many domains however things are dynamic and given an optimal solution to an assignment problem the problem itself may change before or during the execution of the computed solution edge weights may change new nodes may be added to the graph or nodes may be deleted For example consider a problem in which the nodes in the graph represent workers and jobs to be performed by these workers and the edges represent transportation costs between the worker locations and job locations In this domain a given road may be unexpectedly closed significantly increasing the costs of reaching some jobs by some workers While the optimal solution for the new problem could be obtained by solving it from scratch using the Hungarian algorithm a significant computational overhead will result especially in large problems if such changes to the edge weights occur frequently This paper presents a dynamic version of the Hungarian algorithm which given an initial optimal solution to an assignment problem efficiently repairs the assignment when some of the edge weights change A generalization of Toroslu and U c oluk s incremental assignment algorithm 8 the new algorithm is provably correct and optimal with a computational complexity of O kn2 where k is a measure of the number of cost changes As shown in the results section the presented algorithm can solve the modified problem orders of magnitude more efficiently by repairing the old solution than can be done by solving the problem from scratch using the original Hungarian algorithm 1 2 Background 2 1 Terminology and Notation With a few exceptions this paper employs the terminology and mathematical notation of Papadimitriou and Steiglitz 6 The Hungarian algorithm assumes the existence of a bipartite graph G V U E as illustrated in Figure 1 a where V and U are the sets of nodes in each partition of the graph and E is the set of edges The edge weights may be stored in a matrix as shown in Fig 1 b Missing edges are assumed to have zero weight The minimization form of the problem assumes a matrix of edge costs cij W wij where W max wij Missing edges may be given a large cost W as illustrated in Figure 1 c v1 u1 v2 u2 v3 u3 v4 u4 v5 u5 v6 u6 a wij u1 v1 0 v2 0 v3 7 v4 3 v5 0 v6 0 u2 u3 u4 u5 u6 8 4 0 0 6 8 9 0 0 0 0 0 0 5 9 8 7 0 6 5 0 8 0 9 0 8 0 0 0 3 b cij u1 v1 v2 v3 3 v4 7 v5 v6 u2 u3 u4 u5 u6 2 6 4 2 1 5 1 2 3 4 5 2 1 2 7 c Figure 1 a A bipartite graph b A matrix of edge weights c An alternative representation showing edge costs Each node in the graph may be matched assigned or unmatched unassigned Unmatched nodes are also called exposed Edges likewise may be matched or unmatched An edge vi uj is matched if vi is matched to uj and unmatched otherwise For clarity we designate matched edges with solid lines and unmatched edges with dotted lines as shown in Fig 2 a If vi is matched to uj we call uj the mate of vi and vice versa An alternating path is a path through the graph such that each matched edge is followed by an unmatched edge and vice versa In Fig 2 a v5 u2 v1 u1 v3 is an example of an alternating path An augmenting path such as v5 u2 v1 u3 in Fig 2 a is an alternating path that begins and ends with an exposed node All alternating paths originating from a given unmatched node form a Hungarian tree Searching for an augmenting path in a graph involves exploring these alternating paths in a breadth first manner and the process can be called growing a Hungarian tree Figure 2 b illustrates the process of growing a Hungarian tree rooted at node v5 based on the graph in Figure 2 a 2 v1 v5 u1 v2 u2 u6 v3 u3 v2 …

The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs

• Terms Of Use
• Privacy Policy
• Recent Documents
• Students with Disabilities
• Become a Note-Taker

Please select your school

Join to view The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs and access 3M+ class-specific study document.

-->

We couldn't create a GradeBuddy account using Facebook because there is no email address associated with your Facebook account.

Link an email address with your Facebook below or create a new account.

-->

• Corpus ID: 15996572

ALGORITHMS FOR THE ASSIGNMENT AND TRANSIORTATION tROBLEMS*

• Published 1957
• Mathematics, Computer Science

3,526 Citations

The dynamic hungarian algorithm for the assignment problem with changing costs, transportation and assignment, incremental processing applied to steinberg's placement procedure, an extension of the munkres algorithm for the assignment problem to rectangular matrices.

• Highly Influenced

A Primal Method for the Assignment and Transportation Problems

Theory and practice in large carpooling problems, extension of egervàry theorem on optimal solution of assignment problem: logical approach, solving the many to many assignment problem by improving the kuhn-munkres algorithm with backtracking, a noniterative algorithm for tridiagonal transportation problems and its generalization, advances in assignment problem and comparison of algorithms, one reference, related papers.

Showing 1 through 3 of 0 Related Papers

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures

Hungarian Algorithm for Assignment Problem | Set 2 (Implementation)

Given a 2D array , arr of size N*N where arr[i][j] denotes the cost to complete the j th job by the i th worker. Any worker can be assigned to perform any job. The task is to assign the jobs such that exactly one worker can perform exactly one job in such a way that the total cost of the assignment is minimized.

Input: arr[][] = {{3, 5}, {10, 1}} Output: 4 Explanation: The optimal assignment is to assign job 1 to the 1st worker, job 2 to the 2nd worker. Hence, the optimal cost is 3 + 1 = 4. Input: arr[][] = {{2500, 4000, 3500}, {4000, 6000, 3500}, {2000, 4000, 2500}} Output: 4 Explanation: The optimal assignment is to assign job 2 to the 1st worker, job 3 to the 2nd worker and job 1 to the 3rd worker. Hence, the optimal cost is 4000 + 3500 + 2000 = 9500.

Different approaches to solve this problem are discussed in this article .

Approach: The idea is to use the Hungarian Algorithm to solve this problem. The algorithm is as follows:

• For each row of the matrix, find the smallest element and subtract it from every element in its row.
• Repeat the step 1 for all columns.
• Cover all zeros in the matrix using the minimum number of horizontal and vertical lines.
• Test for Optimality : If the minimum number of covering lines is N , an optimal assignment is possible. Else if lines are lesser than N , an optimal assignment is not found and must proceed to step 5.
• Determine the smallest entry not covered by any line. Subtract this entry from each uncovered row, and then add it to each covered column. Return to step 3.

Consider an example to understand the approach:

Let the 2D array be: 2500 4000 3500 4000 6000 3500 2000 4000 2500 Step 1: Subtract minimum of every row. 2500, 3500 and 2000 are subtracted from rows 1, 2 and 3 respectively. 0   1500  1000 500  2500   0 0   2000  500 Step 2: Subtract minimum of every column. 0, 1500 and 0 are subtracted from columns 1, 2 and 3 respectively. 0    0   1000 500  1000   0 0   500  500 Step 3: Cover all zeroes with minimum number of horizontal and vertical lines. Step 4: Since we need 3 lines to cover all zeroes, the optimal assignment is found.   2500   4000  3500  4000  6000   3500   2000  4000  2500 So the optimal cost is 4000 + 3500 + 2000 = 9500

For implementing the above algorithm, the idea is to use the max_cost_assignment() function defined in the dlib library . This function is an implementation of the Hungarian algorithm (also known as the Kuhn-Munkres algorithm) which runs in O(N 3 ) time. It solves the optimal assignment problem. 

Below is the implementation of the above approach:

Time Complexity: O(N 3 ) Auxiliary Space: O(N 2 )

Please Login to comment...

Similar reads.

• Mathematical

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

IEEE Account

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Index     Assignment problem     Hungarian algorithm     Solve online    

The assignment problem

The assignment problem deals with assigning machines to tasks, workers to jobs, soccer players to positions, and so on. The goal is to determine the optimum assignment that, for example, minimizes the total cost or maximizes the team effectiveness. The assignment problem is a fundamental problem in the area of combinatorial optimization.

Assume for example that we have four jobs that need to be executed by four workers. Because each worker has different skills, the time required to perform a job depends on the worker who is assigned to it.

The matrix below shows the time required (in minutes) for each combination of a worker and a job. The jobs are denoted by J1, J2, J3, and J4, the workers by W1, W2, W3, and W4.

	82	83	69	92
	77	37	49	92
	11	69	5	86
	8	9	98	23

Each worker should perform exactly one job and the objective is to minimize the total time required to perform all jobs.

It turns out to be optimal to assign worker 1 to job 3, worker 2 to job 2, worker 3 to job 1 and worker 4 to job 4. The total time required is then 69 + 37 + 11 + 23 = 140 minutes. All other assignments lead to a larger amount of time required.

The Hungarian algorithm can be used to find this optimal assignment. The steps of the Hungarian algorithm can be found here , and an explanation of the Hungarian algorithm based on the example above can be found here .

HungarianAlgorithm.com © 2013-2024

Provide details on what you need help with along with a budget and time limit. Questions are posted anonymously and can be made 100% private.

Studypool matches you to the best tutor to help you with your question. Our tutors are highly qualified and vetted.

Your matched tutor provides personalized help according to your question details. Payment is made only after you have completed your 1-on-1 session and are satisfied with your session.

• Homework Q&A
• Become a Tutor

All Subjects

Mathematics

Programming

Health & Medical

Engineering

Computer Science

Foreign Languages

Access over 35 million academic & study documents

The dynamic hungarian algorithm for the assignment problem with changing costs.

Sign up to view the full document!

24/7 Study Help

Stuck on a study question? Our verified tutors can answer all questions, from basic  math  to advanced rocket science !

Similar Documents

working on a study question?

Studypool is powered by Microtutoring TM

Copyright © 2024. Studypool Inc.

Studypool is not sponsored or endorsed by any college or university.

Ongoing Conversations

Access over 35 million study documents through the notebank

Get on-demand Q&A study help from verified tutors

Read 1000s of rich book guides covering popular titles

Sign up with Google

Sign up with Facebook

Already have an account? Login

Login with Google

Login with Facebook

Don't have an account? Sign Up

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

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

Get early access and see previews of new features.

detailed hungarian algorithm(assignment problem) question

I have implemented the hungarian algorithm, a solution to the assignment problem, as described by this article , but it fails on a few percent of random costs matrices.

I've spent weeks debugging it(I started when I asked this question , not full time though). I took random cost matrices for which the algorithm fails and performed the algorithm with good old pen and paper, and compared that with my implementation to see what went wrong. This led me to a few bugs which I've corrected now, but I have encountered an example for which I do not get the right solution when solving it by hand. For anyone who is interested: the costmatrix of that example is {{0,6,4,3},{3,2,1,2},{0,7,6,4},{3,8,5,3}} , for which the correct solution has the sum of 9=4+2+0+3 (in that order). In that example there is eventually a matched edge not on the equality subgraph, and I think that is impossible, indicating something is wrong.

Either I don't fully understand the solution, which is a viable option, or an extremely subtle bug in the presented solution, which I will elaborate on below.

I realize I have to introduce some terminology, but since this is a detailed question I am not going to explain all concepts in full detail, as anyone needing that explanation probably wouldn't be able to answer my question anyway.

• The input of the problem is a weighted complete bipartite graph with n nodes on each partition.
• The presented method specifies to find n augmenting paths.
• An augmenting path is an alternating path starting and ending at a unmatched nodes.
• An alternating path is a path alternating between matched an unmatched edges on the equality subgraph.
• An augmenting path is found or
• the alternating paths cannot be grown any further.
• And a crucial fact to the possible bug: the algorithm remembers what nodes the alternating paths have encountered, which affects the algorithm in a part irrelevant to this question.

When an augmented path is found, the presented method says to stop growing the alternating paths. I believe this is incorrect. I think all alternating paths need to be grown up to the cost of the found augmented path. Notice that the alternating paths are grown in a breadth first manner, so this only grows paths whose costs can tie with the found path. This small change might result in some nodes being marked as 'visited by alternating path' which otherwise wouldn't have been marked, which affect the algorithm further on.

The actual question: Should I consider alternating paths with costs equal to the costs of the augmented path (and starting at the same node) explored? This is contrary to the presented method, which says to stop as soon as an augmented path is found, regardless of any ties in costs with other paths.

• variable-assignment
• graph-algorithm

Looking at the presentation of the Hungarian algorithm in "The Stanford GraphBase" you can track its progress towards a solution as adding a constant to every cell in a row of the cost matrix, or every cell in a column of the cost matrix, and see that you have a solution when you have a complete set of independent zeros in the altered matrix.

I have read just once the paper you refer to. Is it the case that finding an augmenting path allows you to increase the number of independent zeros in the altered matrix? If so, then finding n augmenting paths, as in their Figure 3 step 2, will find a good solution, because you must then have n independent zeros. If so, then you can check your implementation of the algorithm by checking that each augmenting path found adds an independent zero, even in the case when there are other paths that it could have found but stopped short of finding.

• Each augmenting path does add an independent zero to the altered matrix, and the solution will therefore always have n independent zeros, that is correct. But that doesn't mean it's the optimal solution, which it isn't in the case here. –  JBSnorro Commented Aug 6, 2011 at 13:22
• I expect that a solution with n independent solutions will be an optimal solution because it is an optimal solution on the adjusted matrix (can't do better than 0 + 0 + ...) and because the adjustments don't change the relative costs of answers. –  mcdowella Commented Aug 6, 2011 at 14:27
• There seems to be some confusion over your example matrix. If I get to pick 4 squares, using each row and each column exactly once, I think I want to pick the 0 in the top left, the three in the bottom right, and two diagonal 1s from the middle square. I think that gives me a cost of 5 for a valid solution. What is going on here? –  mcdowella Commented Aug 6, 2011 at 14:29
• I'm awfully sorry, I made an error in copying the example matrix. A 1 should be a 7 . –  JBSnorro Commented Aug 6, 2011 at 17:29
• I worked your (edited) example by hand and found your solution at the position of n independent zeros. Coupled with my argument above that n independent zeros mark a perfect solution of the adjusted matrix, and therefore of the original matrix, I suggest you check that if your program has found n independent zeros at something that is not a solution, that it really has got to that position by adding constants to all cells in a series of rows or columns. –  mcdowella Commented Aug 7, 2011 at 4:21

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

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 algorithm graph variable-assignment graph-algorithm or ask your own question .

• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Announcing a change to the data-dump process

Hot Network Questions

• Always trust localhost certificates
• Can I use a 1" reusable filter in a furnace designed for a 5" filter?
• What is the difference between the complex numbers i and -i?
• Space UN – non human focalpoints
• How to enable access to my local hard disk (from browsers) after it was unintentionally denied?
• Lexicographically earliest permutation of the initial segment of nonnegative integers subject to divisibility constraints
• Mottled polygon fill using QGIS
• Using \worldflags within a table
• Why do doctors seem to overcharge for services?
• PhD in computational mathematics without a strong mathematical background
• How is clang able to evaluate loops without getting stuck in an infinite loop?
• Can "the" mean "enough"? — E.g.: "She will bake a pie, if she has the ingredients."
• Assessing model fit in logistic regression with multiple imputation
• How to handle situations when it is ambiguous whether ～られる is potential or passive?
• How to cover large patch of damp?
• How to increase the amount of tokens per parameter during training?
• Gaussian integral with a positive fraction term
• Does space dust fall on the roof of my house and if so can I detect it with a cheap home microscope?
• How to become Emperor of the Galaxy
• How to combine some ordered pairs
• tikz & amsmath: how can I align math formulas within a tikz matrix?
• Can I solder aged copper with patina on it?
• Arrange yourselves in a more interesting order
• Why do tip vortices seem to 'bend' inwards at the tip of a plane wing?

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.

Hungarian algorithm / assignment problem with cost function depending on resultant matching

The standard Hungarian algorithm solves the problem of assigning n workers to n jobs with a given cost function.

In my variant, the cost function depends on the final matching produced by the algorithm. Explaining with an example:

if cost[w1][j1] = 10\$, in the new variant, if the final matching has w2 and j2 matching, then cost[w1][j1] = 5\$.

It's like saying that if I'm a worker and I charge 10\$ for some job j1 and if this other worker is assigned a j2 job, then I'm going to reduce my price to 5\$ for the j1 job.

Edit: I think it's safe to assume that any (wp, jp) pairing might or might not have relation to (wq, jq). If the relationship exists then the cost of (wp, jp) reduces if (wq, jq) is part of the final matching. The relationship between the pairings is pre-defined. Mathematically, we can assume that we know there exists a function f, where f(wp, jp, wq, jq) will return a tuple (boolean, discount). If the boolean is true and wp matches with jp then we apply the discount to the cost of wq and jq.

• linear-programming
• bipartite-graphs

• $\begingroup$ I suspect that you must specify just how the final assignment affects the cost. I can begin to imagine a formulation that has no solution. What if every worker is prepared to underbid on every job? $\endgroup$ –  Ethan Bolker Commented Oct 27, 2021 at 19:37
• $\begingroup$ Sure..I have tried to explain it in the edit. Hope it makes sense. $\endgroup$ –  Him Commented Oct 27, 2021 at 19:51

You can capture each such interaction via a weighted product of two binary decision variables. The linear objective becomes quadratic, and the resulting problem is called the quadratic assignment problem .

You must log in to answer this question.

Not the answer you're looking for browse other questions tagged linear-programming bipartite-graphs ..

• Featured on Meta
• Announcing a change to the data-dump process
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Upcoming Moderator Election
• 2024 Moderator Election Q&A – Question Collection

Hot Network Questions

• How to increase the amount of tokens per parameter during training?
• Passport Renewals
• Boundedness of sum of sin(sin(n))
• Assessing model fit in logistic regression with multiple imputation
• How many of the 16 cells of the grid could contain the black dot?
• Can I solder aged copper with patina on it?
• Can I use a 1" reusable filter in a furnace designed for a 5" filter?
• Determine the area of region satisfying the given condition
• Ampleness verifiable over faithfully flat cover
• Why do tip vortices seem to 'bend' inwards at the tip of a plane wing?
• Animate Objects on vials of Holy Water
• Using \worldflags within a table
• What does it mean to write to the Register of an IC?
• Why do many CVT cars appear to index gears during normal automatic operation?
• What's wrong with constructions like "Dragons are big, green, and eat people."?
• How does Ashaya, Soul of the Wild and Realm Razor interact?
• Use of the passive in this sentence?
• Always trust localhost certificates
• Why is my custom package not found with Mathematica 14.1?
• Is there a ring with zero divisors but no nilpotents?
• Why is transfer of heat very slow as compared to transfer of sound in solids?
• Can I replace the Sun with a non-nuclear equivalent?
• On a stopover, a space tourist who is in fact a gamesharp joins what looks like a casino game
• A novel where evolution from Neanderthals to us, and from us to superhumans is just by shedding facial skin to become less prognathous

The assignment of project managers to projects in an uncertain dynamic environment

• Original Research
• Published: 02 August 2024

Cite this article

• Aidin Rezaeian 1 ,
• Hamidreza Koosha   ORCID: orcid.org/0000-0002-5155-0040 1 ,
• Mohammad Ranjbar 1 &
• Saeed Poormoaied 2  

11 Accesses

Explore all metrics

In this paper, we consider a project-based organization that deals with an assignment problem in which a set of projects must be assigned to a group of project managers. This assignment is done based on the relative contributions of projects to the organizational mission and a matching score between each pair of a project and a project manager. We assume that some projects are deterministic, and the organization has signed their corresponding contracts while others are stochastic, i.e. the organization has submitted bids for these projects and may or may not win them in the future. Furthermore, we consider a finite planning horizon and presume a predetermined start time for each deterministic and stochastic project. We develop two models including a multi-stage stochastic integer programming model and a stochastic dynamic programming model to solve the problem. The latter shows better performance for small-size and less complex instances whereas the former gives better performance for more complex instances. We also developed a heuristic algorithm to solve large-size and more complex instances. Computational results indicate that the developed heuristic algorithm can reach near-optimal solutions in reasonable CPU run times and dominates the two other solution approaches particularly for large-size instances.

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

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Dynamic Resource Constrained Multi-Project Scheduling Problem with Weighted Earliness/Tardiness Costs

A generic heuristic for multi-project scheduling problems with global and local resource constraints (rcmpsp).

Theoretical and Practical Fundamentals

Albareda-Sambola, M., Vlerk, M. H., & Fernández, E. (2006). Exact solutions to a class of stochastic generalized assignment problems. European Journal of Operational Research, 173 (2), 465–487.

Article   Google Scholar  

Castanon, D. A., & Wohletz, J. M. (2009). Model predictive control for stochastic resource allocation. IEEE Transactions on Automatic Control, 54 (8), 1739–1750.

Crawford, L., Hobbs, B., & Turner, J. R. (2006). Aligning capability with strategy: Categorizing projects to do the right projects and to do them right. Project Management Journal, 37 (2), 38–50.

Dvir, D. O., Sadeh, A., & Malach-Pines, A. (2006). Projects and project managers: The relationship between project managers’ personality, project types, and project success. Project Management Journal, 37 (5), 36–48.

Fricke, S. E., & Shenbar, A. J. (2000). Managing multiple engineering projects in a manufacturing support environment. IEEE Transactions on Engineering Management, 47 (2), 258–268.

Hadad, Y., Keren, B., & Laslo, Z. (2013). A decision-making support system module for project manager selection according to past performance. International Journal of Project Management, 31 (4), 532–541.

Hauschildt, J., Keim, G., & Medcof, J. W. (2000). Realistic criteria for project manager selection and development. Project Management Journal, 31 (3), 23–32.

Heydar, M., O’Reilly, M. M., Trainer, E., Fackrell, M., Taylor, P. G., & Tirdad, A. (2022). A stochastic model for the patient-bed assignment problem with random arrivals and departures. Annals of Operations Research, 315 , 813–845.

IPMA. (2015). ICB-IPMA competence baseline version 4.0. Nijkerk: International Project Management Association

Kang, K., Shanthikumar, J. G., & Altinkemer, K. (2016). Postponable acceptance and assignment: A stochastic dynamic programming approach. Manufacturing & Service Operations Management, 18 (4), 493–508.

Kerzner, H. (2017). Project management: A systems approach to planning, scheduling, and controlling . John Wiley & Sons.

Google Scholar  

Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 (1–2), 83–97.

LeBlanc, L. J., Randels, D., & Swann, T. K. (2000). Heery International’s spreadsheet optimization model for assigning managers to construction projects. Interfaces, 30 (6), 95–106.

Müller, R., & Turner, R. (2010). Leadership competency profiles of successful project managers. International Journal of Project Management, 28 (5), 437–448.

Oliveira, E. C., Alencar, L. H., & Costa, A. P. (2018). Decision process of allocating projects to project managers. Production Planning & Control, 29 (8), 645–654.

Palmowski, Z., & Sidorowicz, A. (2020). An application of dynamic programming to assign pressing tanks at wineries. European Journal of Operational Research, 287 (1), 293–305.

Patanakul, P. (2011). Project manager assignment and its impact on multiple project management effectiveness: An empirical study of an IT organization. Engineering Management Journal, 23 (4), 14–23.

Patanakul, P., Milosevic, D. Z., & Anderson, T. R. (2007). A decision support model for project manager assignments. IEEE Transactions on Engineering Management, 54 (3), 548–564.

Pentico, D. W. (2007). Assignment problems: A golden anniversary survey. European Journal of Operational Research, 176 (2), 774–793.

Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems . New York: Springer.

Book   Google Scholar  

Pinto, J. K., & Slevin, D. P. (1987). Critical factors in successful project implementation. IEEE Transactions on Engineering Management, EM-34 (1), 22–27.

Project Management Institute. (2021). A guide to the project management body of knowledge (PMBOK guide) (7 ed.). Newtown Square, PA: Project Management Institute

Russell, L. (2015). Project management for trainers . American Society for Training and Development.

Seboni, L., & Ssegawa, J. (2022). Does a project manager assignment process affect project management performance indicators? An empirical study. Sustainability, 14 (13), 7637.

Varajão, J., & Cruz-Cunha, M. M. (2013). Using AHP and the IPMA Competence Baseline in the project managers selection process. International Journal of Production Research, 51 (11), 3342–3354.

Ward, S., & Chapman, C. (1988). Developing competitive bids: A framework for information processing. Journal of the Operational Research Society, 39 (2), 123–134.

Xu, Y., & Yeh, C. H. (2014). A performance-based approach to project assignment and performance evaluation. International Journal of Project Management, 32 (2), 218–228.

Xue, M., Fu, C., & Yang, S.-L. (2020). Group consensus reaching based on a combination of expert weight and expert reliability. Applied Mathematics and Computation, 369 , 124902.

Yang, J., He, F., Lin, X., & Shen, M.Z.-J. (2021). Mechanism design for stochastic dynamic parking resource allocation. Production and Operations Management, 30 (10), 3615–3634.

Zavadskas, E. K., Turskis, Z., Tamošaitiené, J., & Marina, V. (2008). Multicriteria selection of project managers by applying grey criteria. Technological and Economic Development of Economy, 14 (4), 462–477.

Download references

Author information

Authors and affiliations.

Department of Industrial Engineering, Ferdowsi University of Mashhad, Mashhad, Iran

Aidin Rezaeian, Hamidreza Koosha & Mohammad Ranjbar

Department of Industrial Engineering and Innovation Sciences, Eindhoven University of Technology, Eindhoven, The Netherlands

Saeed Poormoaied

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Hamidreza Koosha .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Rezaeian, A., Koosha, H., Ranjbar, M. et al. The assignment of project managers to projects in an uncertain dynamic environment. Ann Oper Res (2024). https://doi.org/10.1007/s10479-024-05958-x

Download citation

Received : 04 February 2023

Accepted : 15 March 2024

Published : 02 August 2024

DOI : https://doi.org/10.1007/s10479-024-05958-x

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

• Project management
• Stochastic generalized assignment problem
• Multi-stage stochastic programming
• Stochastic dynamic programming
• Heuristic algorithm
• Find a journal
• Publish with us
• Track your research