task assignment algorithms

• Trending Now
• Foundational Courses
• Data Science
• Practice Problem
• Machine Learning
• System Design
• DevOps Tutorial

What is Task Assignment Approach in Distributed System?

A Distributed System is a Network of Machines that can exchange information with each other through Message-passing. It can be very useful as it helps in resource sharing. In this article, we will see the concept of the Task Assignment Approach in Distributed systems.

Resource Management:

One of the functions of system management in distributed systems is Resource Management. When a user requests the execution of the process, the resource manager performs the allocation of resources to the process submitted by the user for execution. In addition, the resource manager routes process to appropriate nodes (processors) based on assignments. 

Multiple resources are available in the distributed system so there is a need for system transparency for the user. There can be a logical or a physical resource in the system. For example, data files in sharing mode, Central Processing Unit (CPU), etc.

As the name implies, the task assignment approach is based on the division of the process into multiple tasks. These tasks are assigned to appropriate processors to improve performance and efficiency. This approach has a major setback in that it needs prior knowledge about the features of all the participating processes. Furthermore, it does not take into account the dynamically changing state of the system. This approach’s major objective is to allocate tasks of a single process in the best possible manner as it is based on the division of tasks in a system. For that, there is a need to identify the optimal policy for its implementation.

Working of Task Assignment Approach:

In the working of the Task Assignment Approach, the following are the assumptions:

• The division of an individual process into tasks.
• Each task’s computing requirements and the performance in terms of the speed of each processor are known.
• The cost incurred in the processing of each task performed on every node of the system is known.
• The IPC (Inter-Process Communication) cost is known for every pair of tasks performed between nodes.
• Other limitations are also familiar, such as job resource requirements and available resources at each node, task priority connections, and so on.

Goals of Task Assignment Algorithms:

• Reducing Inter-Process Communication (IPC) Cost
• Quick Turnaround Time or Response Time for the whole process
• A high degree of Parallelism
• Utilization of System Resources in an effective manner

The above-mentioned goals time and again conflict. To exemplify, let us consider the goal-1 using which all the tasks of a process need to be allocated to a single node for reducing the Inter-Process Communication (IPC) Cost. If we consider goal-4 which is based on the efficient utilization of system resources that implies all the tasks of a process to be divided and processed by appropriate nodes in a system.

Note: The possible number of assignments of tasks to nodes:

But in practice, the possible number of assignments of tasks to nodes < m x n because of the constraint for allocation of tasks to the appropriate nodes in a system due to their particular requirements like memory space, etc.

Need for Task Assignment in a Distributed System:

The need for task management in distributed systems was raised for achieving the set performance goals. For that optimal assignments should be carried out concerning cost and time functions such as task assignment to minimize the total execution and communication costs, completion task time, total cost of 3 (execution, communication, and interference), total execution and communication costs with the limit imposed on the number of tasks assigned to each processor, and a weighted product of cost functions of total execution and communication costs and completion task time. All these factors are countable in task allocation and turn, resulting in the best outcome of the system.

Example of Task Assignment Approach:

Let us suppose, there are two nodes namely n1 and n2, and six tasks namely t1, t2, t3, t4, t5, and t6. The two task assignment parameters are:

• execution cost: x ab refers to the cost of executing a task an on node b.
• inter-task communication cost: c ij refers to inter-task communication cost between tasks i and j.

Note: The execution of the task (t2) on the node (n2) and the execution of the task (t6) on the node (n1) is not possible as it can be seen from the above table of Execution costs that resources are not available.

Case1: Serial Assignment

Cost of Execution in Serial Assignment:

Cost of Communication in Serial Assignment:

Case2: Optimal Assignment

Cost of Execution in Optimal Assignment:

Cost of Communication in Optimal Assignment:

Optimal Assignment using Minimal Cutset:

Cutset: The cutset of a graph refers to the set of edges that when removed makes the graph disconnected.

Minimal Cutset: The minimal cutset of a graph refers to the cut which is minimum among all the cuts of the graph.

Please Login to comment...

Similar reads.

• Distributed System

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Information

• Author Services

Initiatives

You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader.

All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess .

Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications.

Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers.

Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.

Original Submission Date Received: .

• Active Journals
• Find a Journal
• Proceedings Series
• For Authors
• For Reviewers
• For Editors
• For Librarians
• For Publishers
• For Societies
• For Conference Organizers
• Open Access Policy
• Institutional Open Access Program
• Special Issues Guidelines
• Editorial Process
• Research and Publication Ethics
• Article Processing Charges
• Testimonials
• Preprints.org
• SciProfiles
• Encyclopedia

Article Menu

• Subscribe SciFeed
• Recommended Articles
• PubMed/Medline
• Google Scholar
• on Google Scholar
• Table of Contents

Find support for a specific problem in the support section of our website.

Please let us know what you think of our products and services.

Visit our dedicated information section to learn more about MDPI.

JSmol Viewer

A two-stage distributed task assignment algorithm based on contract net protocol for multi-uav cooperative reconnaissance task reassignment in dynamic environments.

1. Introduction

2. task reassignment model, 2.1. background, 2.2. de-mcrtr model, 2.2.1. basic information of the model, 2.2.2. uav model, 2.2.3. target model, 2.2.4. decision variable, 2.2.5. constraint condition, 2.2.6. cost function, 3. two-stage distributed task assignment algorithm based on cnp, 3.1. tasks to be assigned, 3.2. the manager uav and contractor uav, 3.3. the framework of ts-dta, 3.4. the first assignment stage, 3.4.1. single-target insertion method.

3.4.2. Bidding Strategy with Bidding Benchmark

3.4.3. Bidding Strategy Based on Route Distance

3.5. The Second Assignment Stage

4. Performance Analysis of TS-DTA

4.1. validation of effectiveness, 4.1.1. background information, 4.1.2. task reassignment in the case of uav damage, 4.1.3. task reassignment in the case of new target occurrence, 4.1.4. task reassignment in the case of changing the location of targets, 4.1.5. task reassignment in the case of changing the time window of targets, 4.2. comparative analysis, 4.2.1. analysis of communication simplification effect, 4.2.2. analysis of solution speed and solution quality, 5. conclusions and future work, author contributions, institutional review board statement, informed consent statement, data availability statement, conflicts of interest.

• Frattolillo, F.; Brunori, D.; Iocchi, L. Scalable and Cooperative Deep Reinforcement Learning Approaches for Multi-UAV Systems: A Systematic Review. Drones 2023 , 7 , 236. [ Google Scholar ] [ CrossRef ]
• Yu, X.; Gao, X.; Wang, L.; Wang, X.; Ding, Y.; Lu, C.; Zhang, S. Cooperative Multi-UAV Task Assignment in Cross-Regional Joint Operations Considering Ammunition Inventory. Drones 2022 , 6 , 77. [ Google Scholar ] [ CrossRef ]
• Xu, S.; Zhang, J.; Meng, S.; Xu, J. Task allocation for unmanned aerial vehicles in mobile crowdsensing. Wirel. Netw. 2021 , 14 , 4185. [ Google Scholar ] [ CrossRef ]
• Rahman, D.A.; Sitorus, A.B.Y.; Condro, A.A. From Coastal to Montane Forest Ecosystems, Using Drones for Multi-Species Research in the Tropics. Drones 2022 , 6 , 6. [ Google Scholar ] [ CrossRef ]
• Xia, C.; Yongtai, L.; Liyuan, Y.; Lijie, Q. Cooperative Task Assignment and Track Planning for Multi-UAV Attack Mobile Targets. J. Intell. Robot. Syst. 2020 , 100 , 1383–1400. [ Google Scholar ] [ CrossRef ]
• Guo, J.; Huang, G.; Li, Q.; Xiong, N.N.; Zhang, S.; Wang, T. STMTO: A smart and trust multi-UAV task offloading system. Inf. Sci. 2021 , 573 , 519–540. [ Google Scholar ] [ CrossRef ]
• Muñoz, J.; López, B.; Quevedo, F.; Monje, C.A.; Garrido, S.; Moreno, L.E. Multi UAV Coverage Path Planning in Urban Environments. Sensors 2021 , 21 , 7365. [ Google Scholar ] [ CrossRef ] [ PubMed ]
• Zhang, J.; Xing, J. Cooperative task assignment of multi-UAV system. Chin. J. Aeronaut. 2020 , 33 , 2825–2827. [ Google Scholar ] [ CrossRef ]
• Chen, X.; Zhang, P.; Du, G.; Li, F. A distributed method for dynamic multi-robot task allocation problems with critical time constraints. Robot. Auton. Syst. 2019 , 118 , 31–46. [ Google Scholar ] [ CrossRef ]
• Huang, H.; Zhuo, T. Multi-model cooperative task assignment and path planning of multiple UCAV formation. Multimed. Tools Appl. 2019 , 78 , 415–436. [ Google Scholar ] [ CrossRef ]
• Fu, Z.; Mao, Y.; He, D.; Yu, J.; Xie, G. Secure Multi-UAV Collaborative Task Allocation. IEEE Access 2019 , 7 , 35579–35587. [ Google Scholar ] [ CrossRef ]
• Wang, Z.; Liu, L.; Long, T.; Wen, Y. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding. Chin. J. Aeronaut. 2018 , 31 , 339–350. [ Google Scholar ] [ CrossRef ]
• Jia, Z.; Yu, J.; Ai, X.; Xu, X.; Yang, D. Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm. Aerosp. Sci. Technol. 2018 , 76 , 112–125. [ Google Scholar ] [ CrossRef ]
• Yan, M.; Yuan, H.; Xu, J.; Yu, Y.; Jin, L. Task allocation and route planning of multiple UAVs in a marine environment based on an improved particle swarm optimization algorithm. EURASIP J. Adv. Signal Process. 2021 , 2021 , 39. [ Google Scholar ] [ CrossRef ]
• Cui, Y.; Dong, W.; Hu, D.; Liu, H. The Application of Improved Harmony Search Algorithm to Multi-UAV Task Assignment. Electronics 2022 , 11 , 1171. [ Google Scholar ] [ CrossRef ]
• Zhu, P.; Fang, X. Multi-UAV Cooperative Task Assignment Based on Half Random Q-Learning. Symmetry 2021 , 13 , 2417. [ Google Scholar ] [ CrossRef ]
• Yang, M.; Bi, W.; Zhang, A.; Gao, F. A distributed task reassignment method in dynamic environment for multi-UAV system. Appl. Intell. 2022 , 52 , 1582–1601. [ Google Scholar ] [ CrossRef ]
• Song, J.; Zhao, K.; Liu, Y. Survey on Mission Planning of Multiple Unmanned Aerial Vehicles. Aerospace 2023 , 10 , 208. [ Google Scholar ] [ CrossRef ]
• Chen, J.; Qing, X.; Ye, F.; Xiao, K.; You, K.; Sun, Q. Consensus-based bundle algorithm with local replanning for heterogeneous multi-UAV system in the time-sensitive and dynamic environment. J. Supercomput. 2022 , 78 , 1712–1740. [ Google Scholar ] [ CrossRef ]
• Oh, G.; Kim, Y.; Ahn, J.; Choi, H.-L. Market-Based Distributed Task Assignment of Multiple Unmanned Aerial Vehicles for Cooperative Timing Mission. J. Aircr. 2017 , 54 , 2298–2310. [ Google Scholar ] [ CrossRef ]
• Zhang, J.; Chen, Y.; Yang, Q.; Lu, Y.; Shi, G.; Wang, S.; Hu, J. Dynamic Task Allocation of Multiple UAVs Based on Improved A-QCDPSO. Electronics 2022 , 11 , 1028. [ Google Scholar ] [ CrossRef ]
• Lv, X.; Wang, G.; Chen, J. Multi-UAV Cooperative Reconnaissance Task Allocation Based on IEPPSO Algorithm. In Proceedings of the 2023 18th Chinese Conference on Computer Supported Cooperative Work and Social Computing, Harbin, China, 18–20 August 2023. [ Google Scholar ]
• Gerkey, B.P.; Matarić, M.J. A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems. Int. J. Robot. Res. 2004 , 23 , 939–954. [ Google Scholar ] [ CrossRef ]
• Chen, Y.; Di Yang Yu, J. Multi-UAV Task Assignment with Parameter and Time-Sensitive Uncertainties Using Modified Two-Part Wolf Pack Search Algorithm. IEEE Trans. Aerosp. Electron. Syst. 2018 , 54 , 2853–2872. [ Google Scholar ] [ CrossRef ]
• Ye, F.; Chen, J.; Sun, Q.; Tian, Y.; Jiang, T. Decentralized task allocation for heterogeneous multi-UAV system with task coupling constraints. J. Supercomput. 2021 , 77 , 111–132. [ Google Scholar ] [ CrossRef ]
• Zhen, Z.; Zhu, P.; Xue, Y.; Ji, Y. Distributed intelligent self-organized mission planning of multi-UAV for dynamic targets cooperative search-attack. Chin. J. Aeronaut. 2019 , 32 , 2706–2716. [ Google Scholar ] [ CrossRef ]
• Ghassemi, P.; Chowdhury, S. Multi-robot task allocation in disaster response: Addressing dynamic tasks with deadlines and robots with range and payload constraints. Robot. Auton. Syst. 2022 , 147 , 103905. [ Google Scholar ] [ CrossRef ]
• Choi, H.-L.; Brunet, L.; How, J.P. Consensus-Based Decentralized Auctions for Robust Task Allocation. IEEE Trans. Robot. 2009 , 25 , 912–926. [ Google Scholar ] [ CrossRef ]
• Smith, R.G. The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Trans. Comput. 1980 , 29 , 1104–1113. [ Google Scholar ] [ CrossRef ]
• Qin, B.; Zhang, D.; Tang, S.; Wang, M. Distributed Grouping Cooperative Dynamic Task Assignment Method of UAV Swarm. Appl. Sci. 2022 , 12 , 2865. [ Google Scholar ] [ CrossRef ]
• Zitouni, F.; Harous, S.; Maamri, R. A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System. IEEE Access 2020 , 8 , 27479–27494. [ Google Scholar ] [ CrossRef ]
• Deng, Z.; Chen, T. Distributed algorithm design for constrained resource allocation problems with high-order multi-agent systems. Automatica 2022 , 144 , 110492. [ Google Scholar ] [ CrossRef ]
• Zhang, Z.; Liu, H.; Wu, G. A Dynamic Task Scheduling Method for Multiple UAVs Based on Contract Net Protocol. Sensors 2022 , 22 , 4486. [ Google Scholar ] [ CrossRef ]
• Gao, X.; Wang, L.; Su, X.; Lu, C.; Ding, Y.; Wang, C.; Peng, H.; Wang, X. A Unified Multi-Objective Optimization Framework for UAV Cooperative Task Assignment and Re-Assignment. Mathematics 2022 , 10 , 4241. [ Google Scholar ] [ CrossRef ]
• Deng, Z.; Luo, J. Fully Distributed Algorithms for Constrained Nonsmooth Optimization Problems of General Linear Multi-Agent Systems and Their Application. IEEE Trans. Autom. Control 2023 . early access . [ Google Scholar ] [ CrossRef ]
• Shami, T.M.; El-Saleh, A.A.; Alswaitti, M.; Al-Tashi, Q.; Summakieh, M.A.; Mirjalili, S. Particle swarm optimization: A comprehensive survey. IEEE Access 2022 , 10 , 10031–10061. [ Google Scholar ] [ CrossRef ]
• Gao, S.; Wu, J.; Ai, J. Multi-UAV reconnaissance task allocation for heterogeneous targets using grouping ant colony optimization algorithm. Soft Comput. 2021 , 25 , 7155–7167. [ Google Scholar ] [ CrossRef ]
• Zhen, Z.; Wen, L.; Wang, B.; Hu, Z.; Zhang, D. Improved contract network protocol algorithm based cooperative target allocation of heterogeneous UAV swarm. Aerosp. Sci. Technol. 2021 , 119 , 107054. [ Google Scholar ] [ CrossRef ]
• Liu, W.; Wang, Z.; Zeng, N.; Yuan, Y.; Alsaadi, F.E.; Liu, X. A novel randomized particle swarm optimizer. Int. J. Mach. Learn. Cybern. 2021 , 12 , 529–540. [ Google Scholar ] [ CrossRef ]

Click here to enlarge figure

Share and Cite

Wang, G.; Lv, X.; Yan, X. A Two-Stage Distributed Task Assignment Algorithm Based on Contract Net Protocol for Multi-UAV Cooperative Reconnaissance Task Reassignment in Dynamic Environments. Sensors 2023 , 23 , 7980. https://doi.org/10.3390/s23187980

Wang G, Lv X, Yan X. A Two-Stage Distributed Task Assignment Algorithm Based on Contract Net Protocol for Multi-UAV Cooperative Reconnaissance Task Reassignment in Dynamic Environments. Sensors . 2023; 23(18):7980. https://doi.org/10.3390/s23187980

Wang, Gang, Xiao Lv, and Xiaohu Yan. 2023. "A Two-Stage Distributed Task Assignment Algorithm Based on Contract Net Protocol for Multi-UAV Cooperative Reconnaissance Task Reassignment in Dynamic Environments" Sensors 23, no. 18: 7980. https://doi.org/10.3390/s23187980

Article Metrics

Article access statistics, further information, mdpi initiatives, follow mdpi.

Subscribe to receive issue release notifications and newsletters from MDPI journals

• Trending Categories

• Selected Reading
• UPSC IAS Exams Notes
• Developer's Best Practices
• Questions and Answers
• Effective Resume Writing
• HR Interview Questions
• Computer Glossary

Task Assignment Approach in Distributed System

Introduction.

Distributed systems are a fundamental aspect of modern computing that has revolutionized the way we interact with technology. In essence, a distributed system is a collection of independent computers that work together as a single entity to achieve a common goal. These computers are connected through a communication network and interact with each other by exchanging messages.

A distributed system is an infrastructure consisting of multiple computers that are interconnected and communicate with each other using various communication protocols. The main feature of these systems is the fact that the resources and responsibilities are spread across different nodes in the network, rather than being centralized in one location.

Types of Task Assignment Approaches

Centralized task assignment approach.

The centralized task assignment approach is a method where there is a single point of control for the entire distributed system. In this approach, all the tasks are assigned from a central server, which allocates tasks to different nodes in the network.

The central server monitors the performance of each node and re−assigns tasks as needed. This approach requires that each node in the network communicates with the central server frequently to request task assignments or report on their current status.

One advantage of this approach is that it provides better control over task assignments and resource allocation, as all assignments are managed centrally. However, it also has some disadvantages such as high communication overhead since all systems communicate with a centralized entity which can increase latency and reduce response time especially if there is a large number of nodes in the system.

Decentralized Task Assignment Approach

The decentralized task assignment approach is a method where there is no central point of control in the distributed system. In this approach, every node in the network has equal responsibility for assigning and executing tasks. Each node decides what tasks to execute based on its current status and available resources without any interaction with other nodes or central servers.

The advantage of this approach is that it reduces communication overhead by eliminating frequent communications between nodes and central servers. It also provides better fault tolerance since if one node fails, other nodes in the system can continue working without disruption.

Factors Affecting Task Assignment Approach in Distributed Systems

Distributed systems are complex systems that operate in a network of interconnected computers. These systems are designed to handle a large amount of data and computation by distributing the tasks across multiple machines.

The task assignment approach plays a crucial role in the efficient operation of these distributed systems. Here, we discuss the factors that affect the task assignment approach in distributed systems.

Network Latency: The Barrier to Efficient Task Assignment

Network latency refers to how long it takes for data to travel from one point on a network to another. It is one of the primary factors affecting task assignment approaches in distributed systems.

High network latency can significantly slow down the process of task execution. For instance, if data has to be shuffled between different nodes frequently, it can cause significant delays and affect overall system performance.

A practical solution to address network latency is to employ techniques like caching or replication so that critical data is available locally for faster access. Another option is using algorithms that consider network latency as a factor while assigning tasks so that tasks are assigned closer together geographically where possible.

Load Balancing: The Challenge of Distributing Workload Equitably

In distributed computing, load balancing refers to distributing workloads evenly among different nodes for better utilization of resources and efficient task execution. In other words, load balancing ensures that no single node is overloaded with more tasks than it can handle while others remain underutilized.

The challenge with load balancing lies in identifying how much workload each node can handle, especially when dealing with heterogeneous infrastructure with varying capabilities such as CPU power or memory capacity. To address this challenge, several algorithms have been developed such as round−robin or least−loaded which distribute workload evenly among available nodes based on their capacity for handling tasks.

Resource Availability: Ensuring Adequate Resources for Task Execution

The availability of resources like CPU, memory, or storage is another factor affecting the task assignment approach in distributed systems. Inadequate resources can cause delays or system crashes if a task requires more resources than available on a node. For example, if a node running a task runs out of memory, the task cannot be completed.

To prevent such issues, task assignment algorithms must consider resource availability and allocate tasks only to machines with adequate resources to complete them. Additionally, monitoring tools can be used to track resource utilization and identify overutilized nodes that may need additional support or maintenance.

Network latency, load balancing and resource availability are critical factors affecting the performance of distributed systems. To ensure efficient execution of tasks in these systems, it is necessary to employ algorithms that consider these factors while assigning tasks among multiple available nodes.

Algorithms for Task Assignment in Distributed Systems

Round robin algorithm.

The Round Robin Algorithm is a popular task assignment approach used in distributed systems. It involves assigning tasks to nodes in a circular manner, with each node receiving an equal share of tasks.

The algorithm is simple and easy to implement, making it a preferred choice for many applications. In this approach, the system assigns tasks to the first available node, and then moves on to the next node in the list.

Least Loaded Algorithm

Another popular task assignment approach for distributed systems is Least Loaded Algorithm. This approach assigns new tasks to the least loaded node in the network at any given time. In other words, it selects a node that currently has fewer assigned tasks than others.

The Least Loaded Algorithm also helps maintain balanced workload distribution across all available resources and reduces processing delays caused by overburdened resources. One advantage of using this algorithm is that it automatically adjusts to changes in resource availability and processing capabilities by dynamically reassigning tasks as needed.

Practical Applications of Task Assignment Approach in Distributed Systems

Cloud computing: a game−changer for distributed systems.

Cloud computing has revolutionized the way distributed systems operate by providing access to a vast pool of resources on−demand. Cloud service providers deploy task assignment approaches to balance the workload and maximize resource utilization across their data centers. They use centralized or decentralized algorithms based on the specific needs of their cloud service offerings.

Distributed Database Management System: Efficiency through Task Assignment

Distributed database management systems (DDBMS) rely heavily on effective task assignment approaches to optimize query processing and improve transaction execution times. A DDBMS replicates data across multiple nodes, and each node independently processes queries or transactions to reduce response time for users.

Centralized or decentralized algorithms are used depending on the requirements of the DDBMS application. Load balancing is one of the main goals of task assignment in DDBMS since it ensures that each node gets a fair share of queries without being overwhelmed with requests.

As technology continues to evolve, researchers must continue exploring new and innovative algorithms for task assignment in distributed systems. The recent advancements in machine learning and artificial intelligence open up new avenues for developing intelligent algorithms that can predict performance, optimize resource allocation, and ensure fault tolerance. Researchers can further explore approaches such as genetic algorithms, particle swarm optimization, and other sophisticated techniques that may enhance the quality of task assignment.

• Related Articles
• Distributed Consensus in Distributed System
• Distributed operating System
• Logical Clock in Distributed System
• Event Ordering in Distributed System
• Exception Handling in Distributed System
• Distributed Database Management System
• Priority Assignment to Tasks in Operating System
• Atomic Commit Protocol in Distributed System
• File Model in Distributed Operating System
• Mutual exclusion in a distributed system
• File Accessing Models in Distributed System
• File Service Architecture in Distributed System
• Load Balancing Issues in Distributed System
• Difference Between Network Operating System and Distributed Operating System
• What is a distributed Operating System?

Kickstart Your Career

Get certified by completing the course

A Sequential Task Addition Distributed Assignment Algorithm for Multi-Robot Systems

• Regular paper
• Published: 31 May 2021
• Volume 102 , article number  51 , ( 2021 )

Cite this article

• Nathan Lindsay   ORCID: orcid.org/0000-0001-6448-7012 1 ,
• Russell K. Buehling 1 &
• Liang Sun 1  

398 Accesses

8 Citations

5 Altmetric

Explore all metrics

In this paper, we present a novel distributed task-allocation algorithm, namely the Sequential Task Addition Distributed Assignment Algorithm (STADAA), for autonomous multi-robot systems. The proposed STADAA can implemented in applications such as search and rescue, mobile-target tracking, and Intelligence, Surveillance, and Reconnaissance (ISR) missions. The proposed STADAA is developed by modifying an algorithm (i.e., the Task Oriented Distributed Assignment Algorithm (TODAA)) we previously developed based on the Hungarian algorithm. The STADAA employs a conflict-resolution mechanism that utilizes a slack variable, sequentially adding new admissible tasks to an admissible task list when there exists conflict in an assignment. The STADAA aims to minimize the resulting cost of the task assignments. We compare the STADAA with the Consensus-Based Auction Algorithm (CBAA), the Distributed Hungarian Based Algorithm (DHBA), and the TODAA in terms of the computational time, optimality, the number of steps to converge, and algorithmic complexity. The results show that the STADAA outperforms the CBAA and the TODAA in optimality and outperforms the DHBA in computational time.

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

Dynamic multi-robot task allocation under uncertainty and temporal constraints

Auction-Based Task Allocation and Motion Planning for Multi-Robot Systems with Human Supervision

Cooperative Multi-agent Systems for the Multi-target $$\upkappa $$ -Coverage Problem

Explore related subjects.

• Artificial Intelligence

Data Availability

The supporting data of the information presented in this manuscript is available from the corresponding author, Nathan Lindsay, upon reasonable request.

Abdallah, S., Lesser, V.: Learning the task allocation game. In: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pp. 850–857 (2006)

Bellingham, J., Tillerson, M., Richards, A., How, J. P.: Multi-task allocation and path planning for cooperating uavs. In: Cooperative control: models, applications and algorithms, pp. 23–41. Springer (2003)

Bertsekas, D.P.: Auction algorithms for network flow problems: A tutorial introduction. Comput. Optim. Appl. 1 (1), 7–66 (1992)

Article   MathSciNet   Google Scholar  

Binetti, G., Davoudi, A., Naso, D., Turchiano, B., Lewis, F.L.: A distributed auction-based algorithm for the nonconvex economic dispatch problem. IEEE Trans. Ind. Inf. 10 (2), 1124–1132 (2013)

Article   Google Scholar  

Burkard, R. E., Derigs, U.: Assignment and matching problems: solution methods with FORTRAN-programs, vol. 184. Springer Science & Business Media, Berlin (2013)

Google Scholar  

Choi, H. L., Brunet, L., How, J. P.: Consensus-based decentralized auctions for robust task allocation. IEEE Trans. Robot. 25 (4), 912–926 (2009)

Chopra, S., Notarstefano, G., Rice, M., Egerstedt, M.: A distributed version of the hungarian method for multirobot assignment. IEEE Trans. Robot. 33 (4), 932–947 (2017)

Choudhury, S., Gupta, J. K., Kochenderfer, M. J., Sadigh, D., Bohg, J.: Dynamic multi-robot task allocation under uncertainty and temporal constraints. arXiv: 2005.13109 (2020)

Dames, P. M.: Distributed multi-target search and tracking using the phd filter. Auton. Robot., 1–17 (2019)

Farmani, N., Sun, L., Pack, D. J.: A scalable multitarget tracking system for cooperative unmanned aerial vehicles. IEEE Trans. Aerosp. Electron. Syst. 53 (4), 1947–1961 (2017)

Hu, J., Yang, J.: Application of distributed auction to multi-uav task assignment in agriculture. Int. J. Precision Agricultural Aviation 1 (1) (2018)

Ismail, S., Sun, L.: Decentralized hungarian-based approach for fast and scalable task allocation. In: 2017 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 23–28. IEEE (2017)

Johnson, L., Ponda, S., Choi, H. L., How, J.: Asynchronous decentralized task allocation for dynamic environments. In: Infotech@ Aerospace 2011, p. 1441 (2011)

Kuhn, H. W.: The hungarian method for the assignment problem. Naval Res. Logist. Q. 2 (1-2), 83–97 (1955)

Lerman, K., Jones, C., Galstyan, A., Matarić, M. J.: Analysis of dynamic task allocation in multi-robot systems. Int. J. Robot. Res. 25 (3), 225–241 (2006)

Lin, C.: Online connectivity-aware dynamic distribution for heterogeneous multi-robot systems. Ph.D. thesis, Carnegie Mellon University Pittsburgh, PA (2020)

Lindsay, N., Sun, L.: A task-oriented distributed assignment algorithm for collaborative unmanned aerial systems. In: Proc. of 2020 IEEE International Conference on Unmanned Aircraft Systems, Athens, Greece, September 2020, accepted (2020)

Makkapati, V. R., Tsiotras, P.: Apollonius allocation algorithm for heterogeneous pursuers to capture multiple evaders. arXiv: 2006.10253 (2020)

Mills-Tettey, G.A., Stentz, A., Dias, M.B.: The dynamic hungarian algorithm for the assignment problem with changing costs. Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RI-TR-07-27 (2007)

Muhuri, P.K., Rauniyar, A.: Immigrants based adaptive genetic algorithms for task allocation in multi-robot systems. Int. J. Comput. Intell. Appl. 16 (04), 1750025 (2017)

Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5 (1), 32–38 (1957)

Naparstek, O., Leshem, A.: Fully distributed auction algorithm for spectrum sharing in unlicensed bands. In: 2011 4th IEEE International Workshop On Computational Advances In Multi-Sensor Adaptive Processing (CAMSAP), pp. 233–236. IEEE (2011)

Narayanan, A., Nagarathnam, B.B., Meyyappan, M., Mongkolsri, S.: Experimental comparison of hungarian and auction algorithms to solve the assignment problem. https://chalamy.tripod.com/Report.pdf . Accessed 04 October 2020 (2000)

Omara, F. A., Arafa, M. M.: Genetic algorithms for task scheduling problem. In: Foundations of Computational Intelligence Volume 3, pp. 479–507. Springer (2009)

Pang, Y., Liu, R.: Trust aware emergency response for a resilient human-swarm cooperative system. arXiv: 2006.15466 (2020)

Papadimitriou, C. H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Courier Corporation, Chelmsford (1998)

MATH   Google Scholar  

Samiei, A., Ismail, S., Sun, L.: Cluster-based hungarian approach to task allocation for unmanned aerial vehicles. In: 2019 IEEE National Aerospace and Electronics Conference (NAECON), pp. 148–154. IEEE (2019)

Samiei, A., Sun, L.: Distributed recursive hungarian-based approaches to fast task allocation for unmanned aircraft systems. In: AIAA Scitech 2020 Forum, pp. 0658 (2020)

Schwartz, R., Tokekar, P.: Robust multi-agent task assignment in failure-prone and adversarial environments. arXiv: 2007.00100 (2020)

Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artif. Intell. 101 (1-2), 165–200 (1998)

Sokol, V.: On some nonlinear assignment problems. Ph.D. thesis, Applied Sciences, School of Computing Science (2018)

Song, T., Yan, X., Liang, A., Chen, K., Guan, H.: A distributed bidirectional auction algorithm for multirobot coordination. In: 2009 International Conference on Research Challenges in Computer Science, pp. 145–148. IEEE (2009)

Sun, X., Qi, N., Yao, W.: Boolean networks-based auction algorithm for task assignment of multiple uavs. Math. Probl. Eng. 2015 (2015)

Suslova, E., Fazli, P.: Decentralized multi-robot task allocation with time window and ordering constraints. https://pooyanfazli.com/publications/Suslova_RSS2020W.pdf . Accessed 08 January 2021 (2017)

Zahedi, Z., Sengupta, S., Kambhampati, S.: Why not give this work to them?’explaining ai-moderated task-allocation outcomes using negotiation trees. arXiv: 2002.01640 (2020)

Zavlanos, M. M., Spesivtsev, L., Pappas, G. J.: A distributed auction algorithm for the assignment problem. In: 2008 47th IEEE Conference on Decision and Control, pp. 1212–1217. IEEE (2008)

Download references

This work was supported by the New Mexico Space Grant Consortium and the Laboratory Directed Research and Development program at Sandia National Laboratories. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology Engineering Solutions of Sandia, LLC, a wholly-owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525. The views expressed in the article do not necessarily represent the views of the U.S. Department of Energy or the United States Government.

Author information

Authors and affiliations.

New Mexico State University, Las Cruces, NM, USA

Nathan Lindsay, Russell K. Buehling & Liang Sun

You can also search for this author in PubMed   Google Scholar

Contributions

The first author, Nathan Lindsay, developed the algorithm proposed (Sequential Task Addition Distributed Assignment Algorithm - STADAA) in this paper and developed the code for the STADAA, the Consensus Based Auction Algorithm, and the Task Oriented Distributed Assignment Algorithm, which were all used in testing. Also, he wrote the first draft of this manuscript, analyzing the test results and providing insight into the algorithm’s performance. The second author, Russell Buehling, developed the code for the Distributed Hungarian Based Algorithm that was used in testing, developed the testing environment and ran the tests that generated the results displayed in this paper. The third author, Liang Sun, as the research advisor of the first and second authors, initiated the research work presented in the paper, developed the research plan for methodologies, simulations, experiments, analysis, and data collection, provided guidance for research discussions. All authors read and approved the revised manuscript.

Corresponding author

Correspondence to Nathan Lindsay .

Ethics declarations

Ethics approval.

We deemed no ethical approval was necessary.

Consent for Publication

All authors confirm that: - The research done in this paper has not been published before. - This is not considered for publication anywhere else. - All coauthors approve the publication of this information.

All authors willfully consent to having their information being published in the Journal of Intelligent and Robotic Systems. We understand that the test results and images published in this article will be published on an open access basis and will be freely available on the internet and may be seen by the general public. We reserve the right to revoke our consent for publication at any time prior to publication, but we acknowledge that once the information has been committed to publication, revocation of our consent is no longer possible.

Competing interests

All authors affirm that there is no known conflict of interest pertaining to the information presented in this manuscript.

Additional information

Consent to participate.

All mentioned authors voluntarily agreed to participate in this research topic.

Publisher’s Note

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

Previous paper “A Task-Oriented Distributed Assignment Algorithm for Collaborative Unmanned Aerial Systems” in proceedings of the 2020 International Conference on Unmanned Aircraft Systems (ICUAS’20), Athens, Greece

Rights and permissions

Reprints and permissions

About this article

Lindsay, N., Buehling, R.K. & Sun, L. A Sequential Task Addition Distributed Assignment Algorithm for Multi-Robot Systems. J Intell Robot Syst 102 , 51 (2021). https://doi.org/10.1007/s10846-021-01394-2

Download citation

Received : 06 October 2020

Accepted : 08 April 2021

Published : 31 May 2021

DOI : https://doi.org/10.1007/s10846-021-01394-2

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

• Task assignment
• Autonomous systems
• Optimization
• Multi-robot systems
• Distributed systems

Advertisement

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

• DSpace@MIT Home
• MIT Libraries
• Graduate Theses

Task assignment algorithms for teams of UAVs in dynamic environments

Other Contributors

Terms of use, description, date issued, collections.

Show Statistical Information

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.

• Corpus ID: 106841981

Task assignment algorithms for teams of UAVs in dynamic environments

• Mehdi Alighanbari
• Published 2004
• Engineering, Computer Science

Figures and Tables from this paper

102 Citations

Based on pso algorithm multiple task assignments for cooperating uavs, robust planning for coupled cooperative uav missions, cooperative task assignment of unmanned aerial vehicles in adversarial environments, a robust approach to the uav task assignment problem, dynamic assignment of multi-uav marine search and rescue missions under the condition of intelligence support, joint optimization of multi-uav target assignment and path planning based on multi-agent reinforcement learning, robust and decentralized task assignment algorithms for uavs, real-time multi-uav task assignment in dynamic and uncertain environments, a simple csp-based model for unmanned air vehicle mission planning, multi-uavs trajectory and mission cooperative planning based on the markov model, 53 references, coordination and control of multiple uavs with timing constraints and loitering, coordination and control of multiple uavs, cooperative path planning for multiple uavs in dynamic and uncertain environments, coordination and control of uav fleets using mixed-integer linear programming, uav cooperative path planning.

• Highly Influential

Receding horizon control of autonomous aerial vehicles

Cooperative real-time task allocation among groups of uavs*, dynamic routing of unmanned aerial vehicles using reactive tabu search, mixed integer programming for multi-vehicle path planning, robust planning for heterogeneous uavs in uncertain environments, related papers.

Showing 1 through 3 of 0 Related Papers

Task Assignment Algorithms for Heterogeneous Multiprocessors

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.

• Moulik S Devaraj R Sarkar A (2018) COST: A Cluster-Oriented Scheduling Technique for Heterogeneous Multi-cores 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC) 10.1109/SMC.2018.00337 (1951-1957) Online publication date: Oct-2018 https://doi.org/10.1109/SMC.2018.00337
• Andersson B Raravi G Plantec A Singhoff F Faucou S Pinho L (2016) Scheduling Constrained-Deadline Parallel Tasks on Two-type Heterogeneous Multiprocessors Proceedings of the 24th International Conference on Real-Time Networks and Systems 10.1145/2997465.2997482 (247-256) Online publication date: 19-Oct-2016 https://dl.acm.org/doi/10.1145/2997465.2997482
• Chwa H Seo J Lee J Shin I (2015) Optimal Real-Time Scheduling on Two-Type Heterogeneous Multicore Platforms Proceedings of the 2015 IEEE Real-Time Systems Symposium (RTSS) 10.1109/RTSS.2015.19 (119-129) Online publication date: 1-Dec-2015 https://dl.acm.org/doi/10.1109/RTSS.2015.19
• Show More Cited By

Index Terms

Computer systems organization

Embedded and cyber-physical systems

Embedded systems

Mathematics of computing

Mathematical software

Software and its engineering

Software organization and properties

Software system structures

Embedded software

Real-time systems software

Recommendations

Task assignment algorithms for two-type heterogeneous multiprocessors.

Consider the problem of assigning implicit-deadline sporadic tasks on a heterogeneous multiprocessor platform comprising two different types of processors--such a platform is referred to as two-type platform . We present two low degree polynomial time-...

Real-time scheduling with resource sharing on heterogeneous multiprocessors

Consider the problem of scheduling a task set of implicit-deadline sporadic tasks to meet all deadlines on a t-type heterogeneous multiprocessor platform where tasks may access multiple shared resources. The multiprocessor platform has m k ...

Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor ...

Information

Published in.

Virginia Tech, USA

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication history, permissions, check for updates, author tags.

• Heterogeneous multiprocessors
• real-time scheduling
• Research-article

Funding Sources

• FCT and the EU ARTEMIS JU funding, within projects ARTEMIS/0003/2012 - JU
• National Funds through FCT and by ERDF through COMPETE, within project(s) FCOMP-01-0124-FEDER-037281 (CISTER) and FCOMP-01-0124-FEDER-020447 (REGAIN)
• North Portugal Regional Operational Programme (ON.2 O Novo Norte), under the NSRF, through the ERDF
• Fundação para a Ciência e a Tecnologia

Contributors

Other metrics, bibliometrics, article metrics.

• 4 Total Citations View Citations
• 233 Total Downloads
• Downloads (Last 12 months) 11
• Downloads (Last 6 weeks) 0
• Emeretlis A Theodoridis G Alefragis P Voros N (2015) Mapping DAGs on Heterogeneous Platforms Using Logic-Based Benders Decompostion 2015 IEEE Computer Society Annual Symposium on VLSI 10.1109/ISVLSI.2015.98 (119-124) Online publication date: Jul-2015 https://doi.org/10.1109/ISVLSI.2015.98

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

View options.

View or Download as a PDF file.

View online with eReader .

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.

• View Record

TRID the TRIS and ITRD database

Task assignment algorithms for unmanned aerial vehicle networks: A comprehensive survey

Unmanned aerial vehicles (UAVs) have significant prospects in a plethora of public and civic spheres. Recently, UAVs have focused primarily on applications where human presence is either impossible or hazardous. A swarm of small UAVs can cooperatively complete operations more proficiently and economically than a single large UAV. However, many issues must be resolved before stable and reliable multi-UAV networks can be realized. Task assignment in fleets of UAVs is concerned with cooperative decision-making and control. UAVs possess various functional abilities and kinematic constraints while carrying limited resources onboard. UAVs are nominated to execute multiple sequential tasks supportively on numerous ground targets. The prime objective of task assignment is to minimalize the task accomplishment time and UAV energy consumption. To date, several task assignment algorithms have been designed for UAV networks, and they are comprehensively surveyed in this paper in terms of their main ideas, operational features, advantages, and limitations. These task assignment algorithms are then compared in terms of their significant characteristics and performance factors. To the best of the authors' knowledge, no survey on task assignment techniques for different UAV missions currently exists in the literature. The authors also discuss open issues and challenges and then suggest projections for task assignment algorithms concerning possible future directions.

• Record URL: https://doi.org/10.1016/j.vehcom.2022.100469
• Record URL: http://www.sciencedirect.com/science/article/pii/S221420962200016X
• Find a library where document is available. Order URL: http://worldcat.org/issn/22142096
• © 2022 Sabitri Poudel and Sangman Moh. Published by Elsevier Inc. Abstract reprinted with permission of Elsevier.
• Poudel, Sabitri

• Moh, Sangman
• Publication Date: 2022-6
• Media Type: Web
• Features: Figures; References; Tables;
• Pagination: 100469
• Vehicular Communications
• Issue Number: 0
• Publisher: Elsevier
• ISSN: 2214-2096
• Serial URL: http://www.sciencedirect.com/science/journal/22142096/1/2

Subject/Index Terms

• TRT Terms: Autonomous vehicles ; Coordination ; Drones ; Heterogeneity ; Networks ; Unmanned aircraft systems
• Subject Areas: Aviation; Data and Information Technology; Vehicles and Equipment;

Filing Info

• Accession Number: 01847064
• Record Type: Publication
• Files: TRIS
• Created Date: May 25 2022 9:40AM

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

Algorithm for fairly assigning tasks to workers based on skills

(Before anyone asks, this is not homework.)

I have a set of workers with interests, i.e.:

Bob: Java, XML, Ruby

Susan: Java, HTML, Python

Fred: Python, Ruby

Sam: Java, Ruby

(There are actually somewhere in the range of 10-25 "interests" for each worker, and I have around 40-50 workers)

At the same time, I have a very large set of tasks that need to be distributed among the workers. Each task has to be assigned to at least 3 workers, and the workers must match at least one of the tasks' interests:

Task 1: Ruby, XML Task 2: XHTML, Python

and so on. So Bob, Fred, or Sam could get Task 1; Susan or Fred could get Task 2.

This is all stored in a database thusly:

Each worker has a maximum number of assignments they will do, around 10. Some interests are more rare than others (i.e. only 1 or 2 workers have listed them as a interest), some interests are more common (i.e. half of the workers list them).

The algorithm must :

• Assign every task to 3 workers (it is assumed that at least 3 of the workers are interested in one of the interests of the task).
• Assign every worker 1 or more tasks

Ideally, the algorithm will:

• Assign each worker a number of tasks proportional to their maximum assignments and the total number of tasks. For example, if Susan says she will do 20 tasks and most people will only do 10 tasks and there are 50 workers and 300 tasks, she should be assigned 12 tasks (20/10*(300/50)).
• Assign a variety of tasks to each worker, so if Susan lists 4 interests she gets tasks that include 4 interests (rather than getting 10 tasks all with the same interest)

The most difficult aspect so far has been dealing with theses issues:

• tasks having interests with few corresponding workers
• workers who have few interests, especially
• workers who have a few interests, for which there are relatively few tasks

• 3 This is a GREAT question, but I'm curious if you could be a bit more specific about what you're trying to optimize. Is there some particular value you want to maximize or minimize? And, if so, could you tell us what it is? Right now this is an interesting question, but I think it's a bit underspecified. –  templatetypedef Commented Jan 21, 2011 at 23:51
• 1 The goal is honestly a fairer allocation of tasks. Currently there isn't a formal algorithm, more of a brute force "loop through the tasks, from ordering first by tasks with the fewest matching workers, then assign to workers, ordered by how many they already have assigned" This ends up with some workers getting too many or too few assignments. –  Jordan Reiter Commented Jan 25, 2011 at 7:16

4 Answers 4

This problem can be modeled as a Maximum Flow Problem .

In a max-flow problem, you have a directed graph with two special nodes, the source and the sink. The edges in the graph have capacities, and your goal is to assign a flow through the graph from the source to the sink without exceeding any of the edge capacities.

With a (very) carefully crafted graph, we can find an assignment meeting your requirements from the maximum flow.

Let me number the requirements.

I will assume that the maximum flow is found using the Edmonds-Karp Algorithm .

Let's first find a graph that meets requirements 1-3.

Picture the graph as 4 columns of nodes, where edges only go from nodes in a column to nodes in the neighboring column to the right.

In the first column we have the source node. In the next column we will have nodes for each of the workers. From the source, there is an edge to each worker with capacity equal to that worker's maximum assignments. This will enforce requirement 1.

In the third column, there is a node for each task. From each worker in the second column there is an edge to each task that that worker is interested in with a capacity of 1 (a worker is interested in a task if the intersection of their interests is non-empty). This will enforce requirement 2. The capacity of 1 will ensure that each worker takes only 1 of the 3 slots for each task.

In the fourth column we have the sink. There is an edge from each task to the sink with capacity 3. This will enforce requirement 3.

Now, we find a maximum flow in this graph using the Edmonds-Karp Algorithm. If this maximum flow is less than 3 * (# of tasks) then there is no assignment meeting requirements 1-3. If not, there is such an assignment and we can find it by examining the final augmented graph. In the augmented graph, if there is an edge from a task to a worker with capacity 1, then that worker is assigned to that task.

Now, we will modify our graph and algorithm to meet the rest of the requirements.

First, let's meet requirement 4. This will require a small change to the algorithm. Initially, set all the capacities from the source to the workers to 1. Find the max-flow in this graph. If the flow is not equal to the number of workers, then there is no assignment meeting requirement 4. Now, in your final residual graph, for each worker the edge from the source to that worker has capacity 0 and the reverse edge has capacity 1. Change these to that worker's maximum assignments - 1 and 0 , respectively. Now continue Edmonds-Karp algorithm as before. Basically what we have done is first find an assignment such that each worker is assigned to exactly one task. Then delete the reverse edge from that task so that the worker will always be assigned to at least one task(though it may not be the one assigned to in the first pass).

Now let's meet requirement 5. Strictly speaking, this requirement just means that we divide each worker's maximum assignments by sum of all worker's maximum assignments / number of tasks . This will quite possibly not have a satisfying assignment. But that's ok. Initialize our graph with these new maximum assignments. Run Edmonds-Karp. If it finds a flow that saturates the edges from tasks to sink, we are done. Otherwise we can increment the capacities from sink to workers in the residual graph and continue running Edmonds-Karp. Repeat until we saturate the edges into the sink. Don't increment the capacities so much that a worker is assigned too many tasks. Also, technically, the increment for each worker should be proportional to that worker's maximum assignments. These are both easy to do.

Finally let's meet requirement 6. This one is a bit tricky. First, add a column between workers and tasks and remove all edges from workers to tasks. In this new column, for each worker add a node for each of that workers interests. From each of these new nodes, add an edge to each task with a matching interest with capacity 1. Add an edge from each worker to each of its interest nodes with capacity 1. Now, a flow in this graph would enforce that if a worker is assigned to n tasks, then the intersection of the union of those task's interests with that worker's interests has size at least n. Again, it is possible that there is a satisfying assignment without this assignment, but there is not one with it. We can handle this the same as requirement 5: run Edmonds-Karp to completion, if no satisfying assignment, increment the capacities from workers to their interest nodes and repeat.

Note that in this modified graph we no longer satisfy requirement 3, as a single worker may be assigned to multiple/all slots of a task if the intersection of their interests has size greater than 1. We can fix that. Add a new column of nodes between the interest nodes and the task nodes and delete the edges between those nodes. For each employee, in the new column insert a node for each task (so each employee has its own node for each task). From these new nodes, to their corresponding task to the right, add an edge with capacity 1. From each worker's interests node to that worker's task nodes, add an edge with capacity 1 from each interest to each task that matches.

EDIT: Let me try to clarify this a little. Let -(n)-> be an edge with n capacity.

Previously we had worker-(1)->task for each worker-task pair with a matching interest. Now we have worker-(k)->local interest-(1)->local task-(1)->global task . Now, you can think of a task being matched to a worker-interest pair. The first edge says that for a worker, each of its interests can be matched to k tasks. The second edge says that each of a worker's interests can only be matched once to each job. The third edge says that each task can only be assigned once to each worker. Note that you could push multiple flow from the worker to a local task (equal to the size of the intersection of their interests) but only 1 flow from the worker to the global task node due to the third edge.

Also note that we can't really mix this incrementing with the one for requirement 5 correctly. However, we can run the whole algorithm once for each capacity {1,2,...,r} for worker->interest edges. We then need a way to rank the assignments. That is, as we relax requirement 5 we can better meet requirement 6 and vice versa. However, there is another approach that I prefer for relaxing these constraints.

A better approach to requirement relaxation (inspired-by/taken-from templatetypedef)

When we want to be able to relax multiple requirements (e.g. 5 and 6), we can model it as a min-cost max-flow problem. This may be simpler than the incremental search that I described above.

For example, for requirement 5, set all the edge costs to 0. We have the initial edge from the source to the worker with the capacity equal to worker's maximum assignments / (sum of all worker's maximum assignments / number of tasks) and with cost 0. Then you can add another edge with the remaining capacity for that worker and cost 1. Another possibility would be to use some sort of progressive cost such that as you add tasks to a worker the cost to add another task to that user goes up. E.g. you could instead split a worker's remaining capacity up into individual edges with costs 1,2,3,4,... .

A similar thing could then be done between the worker nodes and the local-interest nodes for requirement 6. The weighting would need to be balanced to reflect the relative importance of the different requirements.

This method is also sufficient to enforce requirement 4. Also, the costs for requirement 5 should probably be made such that they are proportional to a worker's maximum assignments. Then assigning 1 extra task to a worker with max 100 would not cost as much as assigning an extra to a worker with max 2.

Complexity Analysis

Let n = # of employees , m = # of tasks , k = max interests for a single task/worker , l = # of interests , j = maximum of maximum assignments .

Requirement 3 implies that n = O(m). Let's also assume that l = O(m) and j = O(m) .

In the smaller graph (before the change for req. 6), the graph has n + m + 2 = O(m) vertices and at most n + m + k*min(n, m) = O(km) edges.

After the change it has 2 + n + n * l + n * m + m = O(nm) vertices and n + k * n + k * m * n + n * m + m = O(kmn) edges (technically we may need j * n + j * l more nodes and edges so that there are not multiple edges from one node to another, but this wouldn't change the asymptotic bound). Also note that no edge need have capacity > j.

Using the min-cost max-flow formulation, we can find a solution in O(VEBlogV) where V = # vertices , E = # edges , and B = max capacity on a single edge . In our case this gives O(kjn^2m^2log(nm)) .

• There are standard algorithms for solving max-flow problems with lower-bounds on the flow on some edges; would that simplify the analysis and description a bit? Also, can you clarify how step six works? It seems like this could make some problems where legal assignments exist no longer have a solution. –  templatetypedef Commented Jan 22, 2011 at 21:51
• Also, is there a reason for picking Edmonds-Karp instead of, say, a fast push-relabel variant? –  templatetypedef Commented Jan 22, 2011 at 22:26
• I assumed Edmonds-Karp because I know it well. I do not know if the method that I used for satisfying requirement 4 will work with other algorithms. –  Chris Hopman Commented Jan 22, 2011 at 23:32
• @templatetypedef I added a slight clarification for step six. If it is not clear, I can explain more. –  Chris Hopman Commented Jan 22, 2011 at 23:57
• Wow, It's going to take some time to read through this answer! This is where a CS degree would have really helped. :) –  Jordan Reiter Commented Jan 25, 2011 at 6:15

For problems where finding a direct solution is difficult it can be a good idea to use an approximation algorithm, an evaulation function and a method to improve the solution. There are a variety of approaches, such as genetic algorithms and simulated annealing .

The basic idea is to use some sort of simple algorithm (such as a greedy algorithm) to get something that is vaguely usable and make random modifications, keeping those modifications that improve the evaluation score and discarding those that make it worse.

With genetic algorithms a group of for example 100 random solutions is generated and scored and the best are kept and "bred" to produce a new generation of solutions with characteristics similar to the previous generations, but with some random mutations.

For simulated annealing the probablility of a slightly worse solutions being accepted is high initially, but decreases over time. This reduces the risk of getting stuck at a local optimium early on.

Try mapping your task to the stable marriage problem . Tasks become prospective wives `, and your staff become suitors.

You might want to add some extra algorithm for assigning preferences of each task to the staff, and vice-versa - you could assign some ideal proficiency neccessary for the components of each task, and then allow your staff to rank each task. You could assign a proficiency for each component that each staff member posses and use that to get each tasks preference in staff members.

Once you have the preferences then run the algorithm, post the results, then allow people to apply in pairs to you to swap assignments - after all this is a people problem and people work better when they have a degree of control.

• Actually, this is a "these are your tasks and you'll like them" problem -- this is not a scenario where the individual "workers" can pick and choose, the number of "workers" is huge, as are the number of "tasks" and as a result, changes after the fact really aren't feasible. That's why it's so crucial that we get it as right as possible the first time. –  Jordan Reiter Commented Jan 25, 2011 at 6:14
• Then miss out the worker interaction sections. I've read that the stable marriage problem's solution algorithm is used to map interns to hospitals in the US, so it has the capacity. –  Paddy3118 Commented Jan 25, 2011 at 22:58
• Coming in to finally mark one as an answer. Note that this isn't because the other two aren't also good answers, just that this one is probably the most straightforward to attempt. –  Jordan Reiter Commented Jul 7, 2011 at 15:55

So I gave this problem some thought and I think that you can get a good solution (for some definition of "good") by reducing it to an instance of min-cost max-flow (see this , for example). The idea is as follows. Suppose you are given as input a set of jobs J, each of which has a set of skills necessary, along with a set of workers W, each of whom has a set of talents. You are also given for each worker a constant k_i saying how many jobs you'd like them to do, as well as a constant m_i saying the maximum number of jobs you can allocate to them. Your goal is to assign the jobs to the workers in such a way that each job is done by a worker who has the skills, no worker does more than m_i jobs, and the number of the "excess" jobs done by the workers is minimized. For example, if the re are five workers who each want to do four tasks and the load is balanced so that two workers do four jobs, one does three, and one does five, the total excess is one, since one worker did one more job than was expected.

The reduction is as follows. For now, we'll ignore the balancing requirement and just see how tom reduce this to max-flow; we'll add load balancing at the end. Construct a graph G with a designated start node s and sink node t. Add to this graph a node for each job j and each worker w. There will be an edge from s to each of these j nodes of cost zero and capacity one. There will also be an edge from each w node to t with cost zero and capacity m_i. Finally, for each job j and worker w, if worker w has the talents necessary to complete job j, there is an edge from j to w with cost zero and capacity one.

The idea is that we want to push flow from s to t through the j and w nodes such that each flow path going through some j node to a w node means that job j should be given to worker w. The capacity restrictions on the edges from s to j nodes ensures that at most one unit of flow enters the j node, so the job is only assigned at most once. The capacity restriction on the edges from the w nodes to the node t prevent each worker from being assigned too many times. Since all capacities are integral, an integral max flow exists from s to t, and so a max-flow in this graph corresponds to an assignments of jobs to workers that is legal and doesn't exceed any worker's maximum load. You can check whether all jobs are assigned by looking at the total flow in the graph; if it's equal to the number of jobs, they've all been assigned.

This above construction, however, does nothing to balance worker loads. To fix this, we'll modify the construction a bit. Rather than having an edge from each w node to t, instead, for each w node, add two nodes to the graph, c and e, and connect them as follows. There is an edge from w_i to c_i with capacity k_i and cost zero, and an identical edge from c_i to t. There is also an edge from w_i to e_i with cost 1 and capacity m_i - k_i. There is also an edge from e_i to t with equal capacity and zero cost.

Intuitively, we haven't changed the amount of flow that leaves any w node, but we have changed how much that flow costs. Flow shunted to t via the c node is free, and so the worker can take on k_i jobs without incurring cost. Any jobs after that have to be routed through e, which costs one for each unit of flow crossing it. Finding a max-flow in this new graph still determines an assignment, but finding the min-cost max-flow in the graph finds the assignment that minimizes the excess jobs divvied up to workers.

Min-cost max flows can be solved in polynomial time with a few somewhat-well-known algorithms, so hopefully this is a useful answer!

• Very nice solution (it should probably be the accepted answer, despite I don't see how it deals with the "variety of tasks" desired for the workers, but this is a relatively unimportant point). Also, I think that to satisfy the requirement of the OP that each job has to be taken by 3 workers, the edges from s to j should have capacity 3 (and not 1). –  MikeTeX Commented Dec 20, 2017 at 21:10

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 task or ask your own question .

• The Overflow Blog
• Navigating cities of code with Norris Numbers
• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Bringing clarity to status tag usage on meta sites
• Feedback requested: How do you use tag hover descriptions for curating and do...

Hot Network Questions

• Giant War-Marbles of Doom: What's the Biggest possible Spherical Vehicle we could Build?
• How to cite a book if only its chapters have DOIs?
• Proof that a Function is Uniformly Continuous
• Why is たってよ used in this sentence to denote a request?
• Why isn't openvpn picking up my new .conf file?
• Do "Whenever X becomes the target of a spell" abilities get triggered by counterspell?
• Does the expansion of space imply anything about the dimensionality of the Universe?
• How to handle stealth before combat starts?
• Why does the definition of a braided monoidal category not mention the braid equation?
• Why HIMEM was implemented as a DOS driver and not a TSR
• How to read data from Philips P2000C over its serial port to a modern computer?
• Very old fantasy adventure movie where the princess is captured by evil, for evil, and turned evil
• Questions about best way to raise the handlebar on my bike
• How to satisfy the invitation letter requirement for Spain when the final destination is not Spain
• What are these commands in the code?
• Is a *magnetized* ferrite less ideal as a core?
• What is the meaning of these Greek words ἵπποπείρην and ἐπεμβάτην?
• Name of a YA book about a girl who undergoes secret experimental surgery that makes her super smart
• Simple JSON parser in lisp
• What makes a new chain suck other than a worn cassette?
• Stargate "instructional" videos
• Garage door not closing when sunlight is bright
• Does the Ghost achievement require no kills?
• Making wobbly 6x4’ table stable