Distributed Algorithm for Solving the Bottleneck Assignment Problem

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.

Task preference-based bottleneck assignment problem

  • Published: 02 September 2022
  • Volume 41 , article number  298 , ( 2022 )

Cite this article

  • Ekta Jain   ORCID: orcid.org/0000-0001-6099-6848 1 ,
  • Kalpana Dahiya   ORCID: orcid.org/0000-0002-4571-7254 2 ,
  • Anuj Sharma   ORCID: orcid.org/0000-0003-2219-2528 3 &
  • Vanita Verma 4  

206 Accesses

Explore all metrics

The paper discusses a task preference-based bottleneck assignment problem in which there are n tasks that are divided into three phases in order of preference of performance of various tasks. The assignment problem is balanced with an equal number of agents and tasks. An agent can perform only one task and each task can be accomplished by exactly one agent. Tasks belonging to a particular phase cannot be commenced until the tasks of the previous phase have been completed. Given the performance time of each task by each agent, the aim is to find an assignment of agents to the tasks that minimize the total completion time of all tasks. The total completion time here refers to the sum of the overall completion times of three phases. An iterative algorithm for solving such a task preference-based bottleneck assignment problem is proposed in the paper. The proposed algorithm is validated with the help of theoretical results and numerical illustration. The algorithm has been coded in MATLAB and the computational results show that the algorithm performs well in terms of computing time for finding optimal assignments for task preference-based assignment problems of different sizes.

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

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

agent bottleneck generalized assignment problem

Similar content being viewed by others

agent bottleneck generalized assignment problem

A novel strategy for deterministic workflow scheduling with load balancing using modified min-min heuristic in cloud computing environment

Anjali Choudhary & Ranjit Rajak

agent bottleneck generalized assignment problem

Multi-Agent Path Finding – An Overview

agent bottleneck generalized assignment problem

An optimization model for the real-time truck dispatching problem in open-pit mining operations

Hossein Mirzaei-Nasirabad, Mehrnaz Mohtasham, … Behrooz Alizadeh

Adewumi AO, Ali MM (2010) A multi-level genetic algorithm for a multi-stage space allocation problem. Math Comput Model 51(1–2):109–26

Article   MathSciNet   Google Scholar  

Aggarwal V (1983) The assignment problem under categorized jobs. Eur J Oper Res 14:193–195

Article   Google Scholar  

Aggarwal V, Tikekar VG, Hsu LF (1986) Bottleneck assignment problems under categorization. Comput Oper Res 13(1):11–26

Biermann FM, Naroditskiy V, Polukarov M, Nguyen TD, Rogers A, Jennings NR (2014) Task assignment with controlled and autonomous agents. Math Soc Sci 71:116–121

Burkard R, Dell’Amico M, Martello S (2012) Assignment problems: revised reprint. Soc Ind Appl Math

Carpenato G, Toth P (1981) Algorithm for the solution of the bottleneck assignment problem. Computing 27:179–187

Derigs U, Zimmermann U (1978) An Augmenting path method for solving linear bottleneck assignment problems. Computing 19:285–295

Dokka T, Kouvela A, Spieksma FC (2012) Approximating the multi-level bottleneck assignment problem. Oper Res Lett 40(4):282–286

Faudzi S, Abdul-Rahman S, Rahman RA (2018) An assignment problem and its application in education domain: a review and potential path. Adv Oper Res. https://doi.org/10.1155/2018/8958393

Article   MathSciNet   MATH   Google Scholar  

Garfinkel RS (1971) An improved algorithm for the bottleneck assignment problem. Oper Res 19:1747–1751

Hu J, Jiang Y, Zhou P, Zhang A, Zhang Q (2017) Total completion time minimization in online hierarchical scheduling of unit-size jobs. J Comb Optim 33:866–881

Ioannis P, Dimitrios GP (2020) Optimal server assignment in a two-stage tandem queueing system. Oper Res Lett 63:71–77

MathSciNet   MATH   Google Scholar  

Jain E, Dahiya K, Sharma A, Verma V (2019) An improved algorithm for two stage time minimization assignment problem. J Comb Optim 37:713–736

Jain E, Dahiya K, Verma V (2021) Three-phase time minimization transportation problem. Eng Optim 53(3):461–473

Karademir S, Kong N, Prokopvev OA (2014) On greedy approximation algorithms for a class of two-stage stochastic assignment problems. Optim Methods Softw 29(1):42–67

Kaur P, Sharma A, Verma V, Dahiya K (2016) A priority based assignment problem. Appl Math Model 40(7):7784–7795

Kuhn HW (1955) The Hungarian method for the assignment problem. Nav Res Logist 55(2):83–97

Lahiri S (2002) Robust multivalued solutions for assignment problems: a note. Math Soc Sci 44(1):85–90

Li J, Chen J, Xin B, Dou L (2015) Solving multi-objective multi-stage weapon target assignment problem via adaptive NSGA-II and adaptive MOEA/D: A comparison study . IEEE Congress on Evolutionary Computation (CEC): 3132–3139, https://doi.org/10.1109/CEC.2015.7257280

Ortega J (2020) Multi-unit assignment under dichotomous preferences. Math Soc Sci 103:15–24

Pentico DW (2007) Assignment problems: A golden anniversary survey. Eur J Oper Res 176(2):774–793

Pferschy U (1997) Solution methods and computational investigations for the linear bottleneck assignment problem. Computing 59(3):237–258

Punnen AP (2004) On bottleneck assignment problems under categorization. Comput Oper Res. https://doi.org/10.1016/S0305-0548(02)00181-8

Article   MATH   Google Scholar  

Punnen AP, Aneja YP (1993) Categorized assignment scheduling: a tabu search approach. J Oper Res Soc 44(7):673–679

Punnen AP, Aneja YP (2004) Lexicographic balanced optimization problems. Oper Res Lett 32(1):27–30

Rathi K, Balamohan S (2016) Two stage decision making appproach for sensor mission. RAIRO-Oper Res 50:797–807

Sonia Puri M C (2008) Two-stage time minimizing assignment problem. Omega 36(5):730–740

Volgenant A, Duin CW (2010) On a pair of job-machine assignment problems with two stages. Comput Oper Res 37:334–340

Xie F, Butt MM, Li Z (2017) A feasible flow-based iterative algorithm for the two-level hierarchical time minimization transportation problem. Comput Oper Res 86:124–139

Xie F, Sharma A, Li Z (2022) An alternate approach to solve two-level priority based assignment problem. Comput Optim Appl 2:1–44

Zhang S, Guo H, Zhu K, Yu S, Li J (2017) Multistage assignment optimization for emergency rescue teams in the disaster chain. Knowl-Based Syst 137:123–137

Download references

Acknowledgements

The author Ekta Jain is very thankful to the mentor Dr. Anuj Sharma for his continuous guidance and encouragement.

The author Ekta Jain is thankful to Council of Scientific and Industrial Research, India (Sanction No. 09/135/(0724)/2015-EMR-I) and the author Kalpana Dahiya is thankful to Science and Engineering Research Board (File no. MTR/2019/000723) for financial support required to carry out this research work.

Author information

Authors and affiliations.

Department of Mathematics, MCM DAV College for Women, Chandigarh, India

University Institute of Engineering and Technology, Panjab University, Chandigarh, 160014, India

Kalpana Dahiya

Department of Computer Science and Applications, Panjab University, Chandigarh, 160014, India

Anuj Sharma

Department of Mathematics, Panjab University, Chandigarh, 160014, India

Vanita Verma

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Kalpana Dahiya .

Ethics declarations

Conflict of interest.

The authors declare that they have no conflict of interest.

Availability of data and material

Not applicable

Code availabilty

Additional information.

Communicated by Hector Cancela.

Publisher's Note

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

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file 1 (pdf 197 KB)

Rights and permissions.

Springer Nature or its licensor 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

Jain, E., Dahiya, K., Sharma, A. et al. Task preference-based bottleneck assignment problem. Comp. Appl. Math. 41 , 298 (2022). https://doi.org/10.1007/s40314-022-01999-9

Download citation

Received : 29 June 2021

Revised : 01 July 2022

Accepted : 08 August 2022

Published : 02 September 2022

DOI : https://doi.org/10.1007/s40314-022-01999-9

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

  • Three phase
  • Task preference
  • Time minimization

Mathematics Subject Classification

  • Find a journal
  • Publish with us
  • Track your research

IMAGES

  1. (PDF) The multi-resource agent bottleneck generalised assignment problem

    agent bottleneck generalized assignment problem

  2. The unsolved special case of the generalized assignment problem

    agent bottleneck generalized assignment problem

  3. What is a Bottleneck in Project Management?

    agent bottleneck generalized assignment problem

  4. (PDF) A multi-start iterated tabu search algorithm for the multi

    agent bottleneck generalized assignment problem

  5. A Determinant Elimination Method for Bottleneck Assignment and

    agent bottleneck generalized assignment problem

  6. Table 2 from A multi-start iterated tabu search algorithm for the multi

    agent bottleneck generalized assignment problem

VIDEO

  1. Solving the bottleneck assignment problem with distributed agents

  2. Assignment Problem (Part-1) Introduction/Formulation/Balanced/Unbalanced AP

  3. Assignment Problem

  4. Maximization and Unbalanced Assignment problem

  5. Assignment Problem

  6. Lec-32 Maximization Assignment Problem

COMMENTS

  1. The bottleneck generalized assignment problem

    Theory and methodologyThe bottleneck generalized assignment problem. 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 ...

  2. A robust optimization solution to bottleneck generalized assignment

    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 ...

  3. The multi-resource agent bottleneck generalised assignment problem

    In this study, we consider the multi resource agent bottleneck generalised assignment problem. Our aim is to minimise the maximum load over all agents. We take our motivation from an assignment problem faced in heating, ventilating and air conditioning sector. We study the linear programming (LP) relaxation of the problem.

  4. The multi-resource agent bottleneck generalised assignment problem

    In the bottleneck generalized assignment problem (BGAP), more than one job can be assigned to an agent, and the objective function is to minimize the maximum load over all agents.

  5. The multi-resource agent bottleneck generalised assignment problem

    This study considers the multi resource agent bottleneck generalised assignment problem, and defines a tabu search algorithm and α approximation algorithm that can find high quality solutions to large sized instances very quickly. In this study, we consider the multi resource agent bottleneck generalised assignment problem. Our aim is to minimise the maximum load over all agents.

  6. Bottleneck generalized assignment problems

    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 (BGAP ...

  7. The bottleneck generalized assignment problem

    Semantic Scholar extracted view of "The bottleneck generalized assignment problem" by S. Martello et al. ... This study considers the multi resource agent bottleneck generalised assignment problem, and defines a tabu search algorithm and α approximation algorithm that can find high quality solutions to large sized instances very quickly.

  8. Procedures for Solving Bottleneck Generalized Assignment Problems

    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.

  9. PDF arXiv:2008.10804v1 [math.OC] 25 Aug 2020

    to a set of agents. The bottleneck assignment problem (BAP) has the objective of minimising the most costly allocation of a task to an agent. Under certain conditions the structure of the BAP can be exploited such that subgroups of tasks are assigned separately with lower complexity and then merged to form a combined assignment.

  10. Generalized Assignment Problem

    The generalized assignment problem (GAP) seeks the minimum cost assignment of n tasks to m agents such that each task is assigned to precisely one agent subject to capacity restrictions on the agents. The formulation of the problem is: where \ ( c_ {ij} \) is the cost of assigning task j to agent i , \ ( a_ {ij} \) is the capacity used when ...

  11. Bottleneck generalized assignment problems

    Semantic Scholar extracted view of "Bottleneck generalized assignment problems" by J. Mazzola et al. ... This study considers the multi resource agent bottleneck generalised assignment problem, and defines a tabu search algorithm and α approximation algorithm that can find high quality solutions to large sized instances very quickly.

  12. PDF A multi-start iterated tabu search algorithm for the multi-resource

    bottleneck generalized assignment problem Gulcin Bektur* Department of Industrial Engineering, Iskenderun Technical University, Turkey ... In this study, a multi-resource agent bottleneck ...

  13. PDF Sensitivity Analysis for Bottleneck Assignment Problems

    in minimum time. For the bottleneck assignment problem there are many algorithms which provide solution in polynomial time, reviewed in Pentico (2007) and Pferschy (1997). In many applications the weight associated with the assignment of an agent toatask carries with it some uncertainty. Measurement errors, commu-nication delays, or a dynamic ...

  14. 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 are a number of agents and a number of tasks. Any ...

  15. Distributed Algorithm for Solving the Bottleneck Assignment Problem

    Assignment problems are found in multiagent systems, where there is a need to allocate multiple tasks to agents. The bottleneck assignment problem (BAP) is an assignment problem where the objective is to minimise the worst individual cost in the assignment. Distributed algorithms for assignments with other objectives have been proposed, yet to date no distributed algorithm for the BAP exists ...

  16. A robust optimization solution to bottleneck generalized assignment

    Two versions of bottleneck (or min-max) generalized assignment problem (BGAP) under capacity uncertainty are considered: Task-BGAP and Agent- BGAP and a robust optimization approach is employed. We consider two versions of bottleneck (or min-max) generalized assignment problem (BGAP) under capacity uncertainty: Task-BGAP and Agent-BGAP.

  17. (PDF) A multi-start iterated tabu search algorithm for the multi

    In the bottleneck generalized assignment problem (BGAP), more than one job can be assigned to an agent, and the objective function is to minimize the maximum load over all agents.

  18. Task preference-based bottleneck assignment problem

    The assignment problem is one of the fundamental combinatorial optimization problems. An assignment problem is defined as the problem of assigning n tasks to n agents in an optimal manner such that each agent is assigned exactly one task and vice versa. When the objective function to be minimized is a linear function comprising the sum of costs of each task-agent assignment, then it is called ...

  19. Assignment problems: A golden anniversary survey

    The classic assignment problem recognizing agent qualificationIn their work on a particular version of the assignment problem with side constraints (Section 2.13), ... so there may be a minimax objective for the GAP, which leads to the Bottleneck Generalized Assignment Problem (BGAP). Mazzola and Neebe ...

  20. [PDF] Investigation of Task Bottleneck Generalized Assignment Problems

    This paper aims to look at the notion of optimization in a supply chain to avoid bottlenecks that exists frequently in manufacturing area. Supply chain consists of raw material supplier, manufacturer, wholesaler, retailer and customer. Here attention is given to a specific chain link called process operations in which the inspection line process operations of Liquefied Petroleum Gas (LPG ...

  21. THE BOTTLENECK ASSIGNMENT PROBLEM

    A simple algorithm for solving either of two different bottleneck assignment problems, which requires finding an assignment of men to machines in a serial production line to maximize the rate of flow through the line. Abstract : A simple algorithm for solving either of two different bottleneck assignment problems is described in this paper. The one problem requires finding an assignment of men ...