1 Introduction

Task assignment is one of the core steps in effectively exploiting the capabilities of distributed or parallel computing systems. The task assignment problem (TAP) is one of the most important research topics in multi-agent systems (MAS). It is defined as the allocation of (T) tasks to (A) agents in a distributed system. General solutions (A*T) exist for the allocation of tasks to agents; the challenges are principally related to identifying optimal allocation of all tasks while accommodating the design constraints that apply to the domain of interest. Addressing these challenges is an NP-hard problem [1–4]. Kartik and Murthy in [5] demonstrated that the computational complexity of the reliability problem in distributed systems is NP-hard in a strong sense. NP-hard problems are difficult to solve, and no polynomial time algorithms have been established to solve them [6].

Addressing TAP essentially involves assigning a set of tasks to a set of agents in a distributed system; the objective is to minimize the communication and task processing cost among cooperating agents. In other words, approaches designed to manage TAP (and assign tasks to agents) attempt to determine the minimal computational costs in constrained multi-agent cooperative systems while optimizing task assignment to allow for the effective and efficient functioning of distributed systems.

Given the critical importance of task assignment, TAP has been the subject of extensive research. Allocation schemes can be classified into the following two categories [6].

  • Exact methods: methods that attempt to identify the optimal location for a given objective

  • Heuristic algorithms: methods that aim to provide a fast and effective means of obtaining sub-optimal solutions

The first category (exact methods) includes numerous exact methods, such as the family of branch and X algorithms that includes branch and bound algorithm, branch and cut algorithm, branch and price algorithm, linear programming, and dynamic programming [6] to name a few. However, as observed by Jourdan et al. [6], such approaches are limited in their capabilities to resolve moderately sized problem instances. When instances become too large for exact methods, heuristics (particularly meta-heuristic methods) are often employed [6]. Heuristic approaches have been studied more extensively than exact methods and have been demonstrated to provide an effective basis upon which sub-optimal solutions can be achieved. Examples of heuristic approaches include evolutionary algorithms (EA), evolutionary strategies (ES), genetic programming (GP), scatter search (SS), immune systems (IS), and swarm intelligence (SI), which is central to the approach posited in this study. Heuristic algorithms generally incur lower computational overhead (computation time) than exact methods and can be very useful in applications where an optimal solution is unobtainable within a critical time limit.

As discussed above, a number of approaches, including exact methods and heuristic algorithms, have been designed to address task assignment and scheduling in distributed systems [5–8, 10–12, 14–21]. SI employs nature-inspired algorithms in optimization problems [22] and has been shown to produce significant improvements in performance in comparison with alternative approaches in simulating group-based actions. This condition is attributed to the fact that SI is inspired by the activities of social animals or insects in nature. As a basis for task assignment in a multi-agent system, SI has demonstrated the capability to achieve improved performance in terms of optimization and accuracy in classifying tasks.

In this paper, we present a novel approach to solve TAP in a multi-agent system. The approach is based on SI using the artificial bee colony (ABC) algorithmic approach. The contributions provided by this proposed novel approach to task assignment are summarized below.

  1. 1.

    The proposed approach defines TAP in multi-agent systems and provides a dynamic resource assignment algorithm based on ABC.

  2. 2.

    Compared with alternative approaches, the proposed approach has the following benefits and advantages: (1) memory, (2) multi-character, (3) local search, and (4) a solution improvement mechanism. To realize these advantages, we selected the ABC algorithmic approach to model and solve complex TAP.

  3. 3.

    A design example of CA610 lathe is presented for task assignment, and the effectiveness of the ABC algorithm is compared with that of other popular intelligent algorithms through experiments. Computational simulations and comparative analyses are conducted via testing through the use of three test suites. The obtained results support the conclusion that the proposed approach allows for significant improvements in solving complex TAPs when compared with alternative methods, including other nature-inspired approaches such as genetic algorithms and particle swarm optimization techniques.

  4. 4.

    An important aspect of the proposed novel SI-based approach is that it is designed to solve NP-hard problems.

The remainder of this paper is organized as follows. Section 2 presents an overview of related research on TAP and SI, with a focus on ABC approaches. Section 3 introduces a multi-agent cooperative design system. In Section 4, a dynamic task assignment approach based on the bee colony principle and the use of the ABC algorithm is presented. Section 5 presents the experimental results obtained from tests using three test suites. The last chapter provides the conclusions and recommendations for future research.

2 Related work

This section considers task assignment and the approaches to enable the effective allocation of tasks in dynamic and complex environments. SI is considered a potential solution to TAP in dynamic environments, with a focus on the ABC algorithmic approach. The design of the proposed ABC approach is discussed in the following sections.

2.1 TAP

Resource distribution is a type of TAP in which multiple agents are required to capture and deliver resources at a number of pre-defined locations while minimizing the average waiting and delivery times for both resources and clients [6]. Agents in a resource distribution system must (1) cooperate in dynamic and complex environments, (2) implement unexpected requests (this may be viewed in terms of the lack of a priori knowledge related to upcoming requests for service), and (3) achieve effective performance levels in a robust system (i.e., accommodate possible failures of individual agents). Therefore, multi-agent systems designed for resource distribution tasks should be scalable, adaptive, and robust [6].

Many approaches to task assignment and scheduling in distributed systems have been proposed in literature [7]; these approaches include heuristic methods, as discussed by Lo in [8]. In the field of multi-agent coordination (which includes resource distribution and TAPs), two methods are commonly used: (a) multi-agent planning and (b) nature-inspired approaches. The disadvantage of planning-based systems is that either global information is required or agents must communicate extensively; meanwhile, nature-inspired methods have been demonstrated to perform successfully and enable the resolution of both research and real-world problems. A comprehensive overview of multi-agent planning is provided in [9].

An alternative approach initially proposed by Shatz et al. in [10] employs state space search algorithms (SSAs). The SSA approach has been subsequently improved by Kartik and Murthy [5] by using the notion of branch and bound (BB) search with underestimates and module independence to reduce the average computational effort required in establishing optimal task allocation. Although they are useful for small-scale problems, SSA approaches are limited in their capability to handle large and complex problems (such as TAP) and are therefore unsuitable for TAP in general. Meanwhile, heuristic algorithms can derive near-optimal or optimal solutions with a reasonable amount of computing time. Therefore, in recent years, research on TAP has tended to focus on developing meta-heuristic search algorithms to address the problem. A number of constructive heuristics have been proposed for meta-task assignment. Vidyarthi and Tripathi [11] presented a solution that employs a simple GA to identify a near-optimal allocation solution. Attiya and Hamam [12] developed a simulated annealing algorithm to address TAP; evaluation of the algorithm’s performance (in comparison with a BB technique) produced satisfactory results.

Yin et al. [13] proposed a hybrid algorithm that combines particle swarm optimization (PSO) and a hill climbing heuristic; the researchers claimed that their solution outperforms GA in terms of effectiveness and efficiency. Given the intractable nature of TAP when taken with the constantly growing demand for distributed computing, exploring other avenues for developing good heuristic algorithms for TAP is useful.

With regard to the question “can agents coordinate their activity using only communication within their local environment” De Jong et al. [14] found that research has investigated nature as a source of inspiration. Hence, learning-based methods have been proposed. For example, Strens and Windelinckx [15] considered the combination of planning with reinforcement learning for multi-robot task allocation. Examples of documented research that addresses natureinspired systems can be found in [16–21]. However De Jong et al. in [14] noted that “these systems often lack a certain degree of pragmatism required for real-world applications.”

2.2 SI and ABC approaches

SI is a research area that employs nature-inspired algorithms in optimization problems [22]. SI research has produced a number of algorithms that are based on SI; these algorithms involve modeling the behavior of a range of insects and animals, including termites, birds, ants, bees, wasps, and fish [22]. SI is based on models of collective intelligence in swarms of insects or animals and has been defined as “the collective behavior of decentralized and self-organized swarms” [23]. The capability of ant colony optimization (based on the swarming behavior of ants) and PSO (based on bird flocks and fish schools) to solve optimization problems in a number of areas was demonstrated in the 1990s [22]. A fertile area of research within the general area of SI is the investigation of bee swarming; ABC is a relatively recent SI algorithm.

The foraging behavior and learning, memorizing, and information sharing characteristics of bees have been one of the most interesting research areas in SI [24]. ABC algorithms can be viewed in terms of the behavioral characteristics of honey bees, namely, (1) foraging behaviors, (2) marriage behaviors, and (3) the queen bee concept. A detailed description of the behavior of bees in nature with a review and categorization of studies on artificial bee systems can be found in [24]; for a detailed exposition on the ABC approach to optimization, one may refer to [22, 24–28]. The ABC algorithm generally attempts to model the foraging behavior of honeybee colonies [23].

An enhanced ABC optimization algorithm called interactive artificial bee colony (IABC) was developed for numerical optimization problems by Tsai et al. [28]. In the IABC approach, an onlooker bee is designed to move directly to the selected coordinate indicated by an employed bee and evaluate the fitness values near it (in the original ABC algorithm) in an attempt to reduce computational complexity. Essentially, IABC is an extension of the ABC algorithm. It has been tested through the use of five benchmark functions in simulated experiments to compare the accuracy/quality of IABC, ABC, and PSO; its proponents reported that IABC exhibits superior performance in terms of accuracy when compared with other methods [28].

A novel use of the ABC algorithm was developed by [26]. In this approach, the ABC algorithm employs fuzzy clustering. The algorithm has also been tested against a range of data sets, including cancer, diabetes and cardio-vascular datasets obtained from the UCI Library’s database [29], which contains a collection of classification benchmark problems. Successful performance outcomes were obtained. The results revealed the good performance of the ABC optimization algorithm when used in conjunction with fuzzy clustering.

SI involves a social component in that social insect colonies can be considered dynamic systems that gather information from the environment and modify behaviors in accordance with the environmental conditions. While gathering information and setting behavioral patterns (driven by environmental conditions), individual insects do not perform all the tasks as in social insect colonies because of the existence of specialisms (e.g., the queen as well as drone and worker bees). Virtually all social insect colonies behave according to their own division of labor related to their morphology. Bees exist in highly organized colonies with a strict hierarchical structure. A colony of bees is made up of three categories of adults: the queen, the drones, and the workers. Bees are one of the most studied social insects because the highly developed organizational structure of a bee colony makes bees a very attractive source of research inspiration. Bee colonies are in fact communities divided into several social layers. Communication is interesting as bees communicate by (1) dancing and (2) producing pheromones. Bees cooperate to realize various tasks, such as construction and maintenance of the hive and harvesting of pollen. An interesting survey of algorithms inspired by the behavior of bees can be found in [22, 30].

The ABC algorithm, which was proposed by Karaboga [31] and further developed by Karaboga and Basturk [32], is a relatively new population-based meta-heuristic approach. ABC is inspired by the intelligent foraging behavior of the honeybee swarm. Karaboga and Basturk [33] and Karaboga and Akay [34] compared the performance of the ABC algorithm with that of differential evolution, which has been claimed by Sun et al. in [35] to be “very successful in solving the global continuous optimization problem,” PSO, and evolutionary algorithms according to a set of well-known test functions. The performance of ABC was also analyzed under a change in control parameter values. The simulation results showed that the ABC algorithm performs better than the abovementioned algorithms and can be efficiently employed to solve multimodal engineering problems with high dimensionality.

Approaches have been proposed and applied as solutions to solve combinatorial-type problems [36, 37]. Specifically, in consideration of TAP, Lale et al. [38] developed an algorithm based on SI and bee behaviors and with an ejection chain neighborhood mechanism to solve generalized assignment problems [16]. Yeh and Hsieh [39] in their paper entitled “Solving reliability redundancy allocation problems using an artificial bee colony algorithm,” proposed a penalty-guided artificial bee colony algorithm to solve the reliability redundancy allocation problem (RAP). Investigations have been conducted on RAP over the past four decades [39]; Yeh and Hsieh [39] stated that “to the best of our knowledge, the ABC algorithm can search over promising feasible and infeasible regions to find the feasible optimal/near-optimal solution effectively and efficiently.” Investigations that involved the use of numerical examples support the conclusion that the penalty-guided ABC approach performs well in the reliability–redundancy allocation design problems considered in the study; the computational results compare favorably with those of previously developed algorithms in literature [39].

This brief overview of the research related to task assignment and resource distribution considered the approaches to task assignment. The ABC optimization algorithm has been widely studied and has been successfully applied to resolve real-world problems. ABC approaches have significant advantages in terms of memory, multi-character, local search, and the solution improvement mechanism; hence, ABC methods are capable of identifying optimal and near-optimal solutions. However, notwithstanding the efficacy of the ABC approach in its basic form as discussed above and in literature, the approach is limited when used to address TAP. A meta-heuristic optimization approach that employs a penalty-guided algorithm based on the ABC approach to solve TAP in a multi-agent cooperative design system is proposed in this paper.

3 Multi-agent cooperative design system

A multi-agent collaborative design system is essentially concerned with how a group of intelligent agents can cooperate to jointly solve problems. Design is a complex process of knowledge discovery, in which information and knowledge from a broad and diverse range of sources is processed simultaneously by a team of designers involved in the life cycle of a project or product. Complex designs generally combine automated software components and human decision makers; hence, providing support for both human and computational participants in the design process is imperative.

The general architecture of a multi-agent collaborative design system is organized as a population of asynchronous semi-autonomous agents to enable the integration of design and engineering tools with human experts and specialists in an open environment. Each tool (or interface for a human specialist) can be encapsulated as an agent. These tools and human specialists are connected by a local network; they communicate via this network. Each can also communicate directly with other agents located in other local networks through the Internet. Agents exchange design data and knowledge via a local network (Internet) or the Internet through the management agent [40]. All agents in the system form an agent group, in which three classes of agents exist: (1) management, (2) tool, and (3) design agents. The agents are situated on different layers, and the hierarchical relation limits the authority of the agents within the group.

The management agent is located on a server and manages the interactions of the entire design group. The action of the management agent usually shows the inquiry made and the resultant decision for a particular problem, the control function, and the supervision functions for the lower-layer agents. The knowledge in the knowledge base (KB) of a management agent includes all relevant information (e.g., a design agent’s name, address, skills or competencies, historical records for the task being undertaken, and reward in the group). When an agent is added to or deleted from the group, the corresponding knowledge of the management agent is modified.

Tool agents include design and management tools; they provide assistance to the management agent in the completion of the system management tasks. Typical tasks include communication management, task assignment, database management, knowledge management, collaboration management, and system maintenance. The role and functions of the various agents that combine to make up the design system can be summarized as follows [41].

  • The task assignment agent helps design engineers decompose a large design task into several sub-tasks and assigns them to suitable design agents.

  • The collaborative agent deals with conflict coordination during the collaborative design process.

  • Design tool agents include software packages, such as AutoCAD, Pro-Engineer, Inventor, MicroStation, and SolidWorks. They also include a video conferencing system for a synchronous collaborative design that provides run-time support.

  • Communication agents provide support for the interaction among agents and designers through e-mail, text, file, image, graph, audio, and video. The exchange of data and files is based on the file transfer protocol (FTP) and TCP/IP protocol.

  • The process monitor agent monitors the entire design process via its event monitor and dynamically maintains information related to the current prevailing state of each design agent and the status of current design sub-tasks. The event monitor is triggered when a design event occurs, and the correlative message is passed to relevant and suitable agents.

  • The assemble agent checks the assembly constraints for finished design components. When a constraint violation is found, this agent asks collaborative and communication agents to solve problem by coordinating with design agents.

  • The knowledge maintenance and database agents maintain the knowledge base and database, respectively.

The collaborative design process is shown in Fig. 1. When a large design task arrives, the task composition agent helps the design engineer decompose the task into subtasks and sends the subtasks to the collaborative agent. The collaborative agent then matches the subtasks and design agents according to the latter’s capability. After processing by a dynamic task assistant, the design agents and designers perform their respective assigned design tasks. During the design process, the communication agent takes charge of the interaction among agents; the knowledge maintenance and database agents maintain and update the knowledge base and database. The process monitor agent monitors the entire design process. When the assembly agent finds a constraint violation, it informs the collaborative and communication agents with the goal of solving the issue through coordination among design agents. When the design phase is over, experts evaluate the design result to determine if the design process is completed or should be restarted [42].

Fig. 1
figure 1

Collaborative design process

Full size image

4 Dynamic task assignment process

The task assignment agent employs a method that divides a design task into a sequence of subtasks and assigns them to suitable design agents.

4.1 Formal description of task assignment

The formal definition of the task assignment approach posited in this study is as follows.

Definition 4.1

DAs denotes a design agent, where D is the type of agent and s is a character string that represents which group the agent belongs to and its serial number in the group. For example, DA11 is a design agent with number 1 in group 1.

Definition 4.2

Ts stands for a design task, and c is a character string that represents the decomposed layer of the design task and the dependency relation. For example, an initial design task can be represented as T1. Its subtasks are T11, T12,…,T1n, and the sub-processes of T1i are T1i1, T1i2,…,T1im, i.e., the length of the string denotes the decomposed depth, and the value expresses the dependency relation (i).

The dependency relation of design tasks forms a design task tree.

Definition 4.3

\({T_{i}^{j}} \)denotes that task i is being implemented by design agent j.

The group members performing task Ti can be determined by vector \(\left (T_{i}^{j1} ,T_{i}^{j2} ,{\ldots } , T_{i}^{jk}\right )\) and the current tasks of design agent j by vector \(\left (T_{i1}^{j} ,T_{i2}^{j},\ldots , T_{il}^{j} \right )\).

Definition 4.4

The prior relation of a design task is indicated by pair PRIOR (Ts1, Ts2), which means that Ts2 takes the fulfillment of Ts1 as the starting pre-condition; Ts1 and Ts2 are the sequences of tasks.

Definition 4.5

The concurrent relation is indicated by CONCUR (Ti, Tj), which expresses that design tasks Ti and Tj can be implemented simultaneously.

Definition 4.6

The exclusive relation is indicated by EXCLUDE (Ti, Tj), which denotes that two tasks (Ti a n dTj) cannot be performed simultaneously.

Definition 4.7

Event is expressed by E (i).

Table 1 presents the notations used in TAP formulation.

Table 1 Notations used in TAP formulation
Full size table

The general formulation of TAP can be described as follows:

$$ \text{Min}~\qquad \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} c_{ij}x_{ij} $$
(1)
$$\begin{array}{@{}rcl@{}} \text{Subject to} && {\sum\limits_{i=1}^{n}r_{ij}x_{ij}\leq b_{j}} \quad \forall j~~1\geq j \leq m~ \end{array} $$
(2)
$$\begin{array}{@{}rcl@{}} && \sum\limits_{j=1}^{m} x_{ij}=1 \quad \forall i~~1\leq i \leq n ~ \end{array} $$
(3)
$$\begin{array}{@{}rcl@{}} && ~~x_{ij} \in \{0,1\} \end{array} $$
$$\begin{array}{@{}rcl@{}} && ~~\forall i ~~1\leq i \leq n \end{array} $$
(4)
$$\begin{array}{@{}rcl@{}} && ~~\forall j~~1\geq j \leq m. \end{array} $$

According to (1) and Table 1, this problem is a 0–1 quadratic integer programming problem, and its objective function is the total sum of execution and communication costs. This problem is limited by two sets of constraints. The first constraint set in (2) means that the task assigned to agent j cannot exceed the resource capacity of agent j, and the second constraint set in (3) ensures that each task is assigned to only one agent.

4.2 Dynamic task assignment approach based on ABC algorithm

The proposed approach is presented in this section. After a description of bee colony initialization, we discuss the design solution for the proposed resource assignment approach.

4.2.1 Bee colony initialization

The initial bee colony is constructed using the initial task assignment algorithm, where the greedy heuristic constructs a solution as follows.

  1. 1.

    At each step, the next task to be assigned to an agent is selected.

    figure e
  2. 2.

    The agent to whom the selected task will be assigned to is determined.

  3. 3.

    Steps 1 and 2 are repeated until all tasks have been assigned to agents.

In the algorithm, probabilistic bias can be implemented to a probability function. This function is updated at each iteration with reinforcement by using the features in good solutions.

4.2.2 Proposed solution design

The ABC algorithm is iterative. A colony of artificial bees in the ABC algorithm is analogous to its natural counterpart (a real colony of bees) in that three categories of bees exist: employed, onlooker, and scout bees. The first half of the bee colony comprises employed bees, and other half contains onlooker bees. The ABC algorithm proposed in this study functions as follows. Initially, all employed bees are associated with randomly generated food sources (solutions). Iterative processing then occurs; in each iteration, every employed bee determines a (new) food source in the neighborhood of its currently associated food source and evaluates its nectar value (amount), which represents fitness. If the nectar value of the new food source is greater than the nectar value of the currently associated food source, then the employed bee moves to this new food source and leaves the old (current) food source; otherwise, it retains its old food source. When all employed bees have finished this process, they share the nectar information relating to the food sources with the onlooker bees. At this stage, each of the onlooker bees selects a food source according to a probability proportional to the nectar value of that food source.

The ABC algorithm assumes that only one employed bee exists for every food source (a design parameter for the entire system). Hence, in the ABC algorithm, the number of food sources is similar to the number of employed bees. The employed bee for an abandoned food source becomes a scout bee. When it finds a new food source, it returns to being an employed bee. ABC generates a randomly distributed initial population of SN solutions (food source, positions, and the reliability) during initialization, and the SN parameter denotes the population size of the employed or onlooker bees. Below is a detailed description of the process.

Each solution X h (h = 1, 2, ⋯ , S N) is a d-dimensional vector, where d is the number of optimization parameters. The population of the positions (solutions) is subject to repeated cycles [(C = 1,2… , maximum cycle number (MCN)] of the search processes for the employed, onlooker, and scout bees. After building potential solutions, the subsequent task is to evaluate the food source (solutions) using the fitness function, which is a common feature of nature-inspired approaches for optimization. The design of the fitness function is a crucial feature in ABC (as in all nature-inspired approaches) and performs a vital task in determining the optimization function in the ABC algorithm.

The fitness values are utilized to determine the probability of the individual bees being selected. In computing the value of the fitness function, a penalty term is added to the fitness function to convert the constrained problem into an unconstrained one. While constructing initial solutions (in the ABC algorithm), the proposed approach may produce infeasible solutions. Therefore, an additional term, which is determined by penalizing the infeasible solutions with α j (α j > 0), is introduced to the fitness function. The fitness function is formally defined as follows:

$$ fit(\sigma^{p})\,=\,\sum\limits_{j=1}^{m} {\sum\limits_{i=1}^{n} {c_{ij} x_{ij} } } +(\sum\limits_{j=1}^{m} \alpha_{j} \max \left(\!0,\sum\limits_{i=1}^{n} {r_{ij} x_{ij} -b_{j} } \!\!\right)\!, $$
(5)

where

  • σ p is the solution for employed bee p

  • fit(σ p) is the fitness function value for employed bee p

  • σ best is the best solution, and

  • α j is the cost of using one overloaded capacity of agent j.

The first term in the fitness function denotes the total cost of assigning tasks to agents. The second term is defined as an additional penalty function for minimization. α j represents the cost of using one overloaded capacity of agent j. The initial values of α j ’s are set by the user. If a solution is not feasible, the second term will be positive. Therefore, the search will be directed to a feasible solution. If the capacity is not exceeded, this term will be zero to ensure that the solution is not penalized. The parameter can be increased during the run to penalize infeasible solutions and drive the search to feasible ones; this condition denotes the adaptive control of penalty costs.

The solutions for each task are selected using the probabilities established by (6). The probability p h of selecting a solution X h is then determined.

$$ p_{h}=\frac{fit(\sigma^{h})}{\sum\limits_{i=1}^{SN}fit(\sigma^{i})} $$
(6)

With this scheme, good food sources will obtain more onlookers than the bad ones. After all onlookers have selected their food sources, each of them determines a food source in the neighborhood of his selected food source and computes its fitness. The best food source among all the neighboring food sources determined by the onlookers (associated with a particular food source i itself) will be the new location of food source i.

Local search for solution improvement

After being generated, a solution is improved through a local search process called greedy selection. This process is implemented by onlooker and employed bees. In greedy selection, if the nectar value (fitness) of the candidate source is greater than that of the current source, the bee forgets the current source and memorizes the new candidate source. This condition is achieved by adding to the current value of the selected parameter the product of a uniform variable within the range [-1, 1] and the difference in values of the parameter of this food source and of several other randomly selected food sources.

We suppose that each solution consists of d parameters and let X h = (X h1,X h2,K, X h d ) be a potential solution. To determine a new solution N e w X h in the neighborhood of X h , a solution parameter j and another solution X k = (X k1, X k2, K, X k d ) are selected randomly. Except for the value of the selected parameter j, all other parameter values of N e w X h are similar to X h , i.e., N e w X h = (X h1, X h2, K, X h, j−1, Z h, j , X h, j+1, L, X h d ). The value of the selected solution N e w X h is determined with (7) as follows:

$$ NewX_{hj} =X_{hj} +u(X_{hj} -X_{kj} ), $$
(7)

where u is a uniform variable within the range [-1,1]. If the resulting value falls outside the acceptable range for parameter j, it is set to a corresponding extreme value in that range.

Solution intensity update

The entire process is iterative in that it is repeated until the termination condition is satisfied. In the ABC algorithm, providing that a position cannot be improved further through a predetermined number of cycles, then that food source is assumed to be abandoned. Assuming that the abandoned source is X h , the scout bee will look for a new food source to replace X h . This operation can be defined as (8).

$$ X_{h}^{j} =X_{\min}^{j} + rand[0.1]\left(X_{\max}^{j} -X_{\min }^{j}\right)\quad j=1,2,\ldots,d $$
(8)

Dynamic resource assignment algorithm

This section introduces the dynamic resource assignment algorithm that is based on the ABC approach. The algorithm involves three steps as shown below.

figure f

5 Experimental results

In this section, a design example and two test suites are provided to show the performance of the proposed ABC algorithm. Figure 2 presents an image of a CA6140 lathe, and Fig. 3 presents its design sketch. This lathe design is regarded as an example in this section.

Fig. 2
figure 2

CA6140 lathe

Full size image
Fig. 3
figure 3

Design sketch of CA6140 lathe

Full size image

The performance criteria considered to evaluate the quality of the solutions are (1) the assignment (communication) cost and (2) amount of CPU time used for the benchmarks. G (V, E) is utilized to create the task interaction graph (TIG), where V is a set of n nodes indicating the n tasks to be executed and E is a set of edges indicating the communication requirements among these tasks. Each edge (i, j) ∈ E is associated with a communication cost c i j . Figure 4 shows an example of a TIG (related to Fig. 3) showing the communication requirements among six tasks.

Fig. 4
figure 4

Example of a TIG

Full size image

Two key factors affect the complexity of the problem. One factor is the task interaction density (d) of G (V, E) that quantifies the ratio of the inter-task communication demands for a TIG. The other factor is the number of tasks (n) and agents (m). We define d as (9).

$$ d=\frac{\left| E \right|}{r(r-1)/2}, $$
(9)

where |E| calculates the number of existing communication demands in the TIG and n(n−1)/2 indicates the maximal number of communication demands among n tasks. To be specific, a brief description and the parameter values that control each algorithm are provided as follows.

  1. 1.

    PSO

    1. (a)

      The size of the population is equal to twice the number of tasks.

    2. (b)

      Inertia weight w is set to 0.9.

    3. (c)

      c 1 = c 2 = 1.0.

  2. 2.

    GA

    1. (a)

      Crossover probability = 0.9.

    2. (b)

      Mutation probability =1/total number of tasks.

    3. (c)

      Population size = twice the number of tasks.

    4. (d)

      Elitism is used.

    5. (e)

      Roulette wheel selection.

  3. 3.

    ABC

    1. (a)

      The number of employed bees is equal to the number of onlookers and tasks.

    2. (b)

      MCN = 1000.

    3. (c)

      Limit = 20.

    4. (d)

      α j = 1.

5.1 Test suite 1

With this test suite, TIGs that represent real-life tree and Fork–Join problems are generated. The structures of the two TIGs are fixed, and each of them requires a different number of vertices. The size of the TIGs is varied. The cost of each node is randomly selected from a normal distribution, with the mean equal to the specified average computational cost. The cost of each edge is also randomly selected from a normal distribution, with the mean equal to the product of the average computational cost and density d equivalent to 0.1, 0.5, 1.0, 2.0, and 10.0.

Tables 2 and 3 show the results for the two graph structures in a homogeneous system with 10 agents. The experimental results are presented in Figs. 5, 6, 7, and 8 in bar line format. Each result is an average of 20 test cases. Algorithm performance varies depending on the structure of TIGs. The ABC algorithm outperforms GA and PSO in terms of task assignment problems; the ABC algorithm achieves the best solutions with the added benefit of requiring the least amount of computation time. In fact, the harder the problem is, the larger the cost difference among the three algorithms. This condition supports the conclusion obtained from the testing, which indicates that the proposed ABC algorithm is more scalable against problem complexity. These results illustrate that the proposed algorithm is a competent solution for task assignment problems at both small and large scales.

Table 2 Comparison of results for the tree-type graph structure
Full size table
Table 3 Comparison of results for the Fork–Join type of graph structure
Full size table
Fig. 5
figure 5

Comparison of time consumed for the tree-type graph structure

Full size image
Fig. 6
figure 6

Comparison of costs for the tree-type graph structure

Full size image
Fig. 7
figure 7

Comparison of time consumed for the Fork–Join type of graph structure

Full size image
Fig. 8
figure 8

Comparison of costs for the Fork–Join type of graph structure

Full size image

5.2 Test suite 2

To analyze the convergence behavior of the proposed algorithm, randomly generated TIGs are considered by using test suite 2. The value of (m, n) is set to (10, 6) and (20, 12), respectively, to verify the algorithm’s performance at different problem scales. For each pair of (m, n), three different TIGs are generated randomly. The values of the other parameters are generated randomly; the execution cost is between 1 and 200, the communication cost is between 1 and 50, and the memory and processing capacity of each agent varies from 50 to 250. Figure 9 shows the typical convergence behaviors of ABC, PSO, and GA approaches for instance (m, n, d) = (50, 8, 0.3), and Fig. 10 shows the same for instance (m, n, d) = (80, 10, 0.5).

Fig. 9
figure 9

Comparison for (m, n, d)=(50,8,0.3)

Full size image
Fig. 10
figure 10

Comparison for (m, n, d) = (80, 10, 0.5)

Full size image

The results show that the proposed ABC algorithm has a clear advantage in terms of convergence. It runs faster than GA and PSO, and its solution quality is better than that of GA and PSO on the average. These results also indicate that the proposed algorithm has an advantage in addressing the demands of dynamic task assignment because of its stability, multi-character, and iteration speed. It can combine global and local search and is able to discover new optimal solutions over time. It is a potential means to solve TAP.

6 Conclusion

In this study, we considered TAPs in relation to distributed multi-agent systems. A range of potential approaches to address the demands and complexity of TAP in multi-agent systems were analyzed. A novel approach that is based on SI and employs a honeybee optimization algorithm was developed. The proposed approach employs the ABC algorithm to effectively allocate tasks to agents in a system. The algorithm is designed to provide a platform upon which system design can be achieved. The use of the ABC algorithm to realize this objective is the focus of the paper.

The proposed approach to task assignment is a modified version of the basic ABC algorithm initially proposed by Karaboga [31] and is expected to provide an effective platform upon which autonomous task assignment can be achieved to produce an effective cooperative design. The results support the conclusion that the proposed approach allows for more significant improvements in solving complex task assignment problems compared with alternative methods, including other nature-inspired approaches (e.g., GAs and PSO techniques).

Unlike traditional heuristics, approaches that employ the ABC algorithm incorporate have a number of advantages, including memory, multi-character, local search, and a solution improvement mechanism. These attributes provide an effective basis to enable the discovery of new optimal solutions over time. As demonstrated in the study of Karaboga and Basturk [32, 33], the optimal solutions produced by ABC approaches exhibit improved performance when compared with the results obtained by other heuristic methods. In the current study, the proposed method achieved the global or near-global solution in each sample problem tested.

Previous research has identified SI, particularly bee inspired algorithms, as approaches that have a very promising potential for modeling and solving complex optimization problems. Through the proposed approach, we have resolved a number of challenges. However, remaining challenges must be addressed if we are to fully utilize the potential of bee-inspired algorithms as a solution to optimization problems in general and TAP in particular. Addressing these challenges represents the direction of our future work, given that the potential of the proposed approach offers exciting opportunities for search and optimization.