# Hybrid Task Allocation of an AGV System for Task Groups of an Assembly Line
## 4 Hybrid Task Allocation Method Based on Task Binding Strategy and IPSO
### Initial Population Generation
#### 4.3.1 Task Binding Strategy  
To reduce the number of rows in the coding matrix and improve the quality of random individuals in the initial population, a task binding strategy is proposed. The task binding strategy contains the task group layering strategy and task binding method and involves the feasibility of binding and similarity between task groups. First, the task group layering strategy is used to divide task groups into different layers; then, the similarity between task groups in adjacent layers is calculated; after that, the task binding method is used to bind the tasks of two task groups with non-zero similarity in adjacent layers; finally, the task after binding is obtained. A. Feasibility of binding between task groups  
It is assumed that tasks \(T_{i}\) and \(T_{j}\) belong to task group \(TG_{n}\) and \(TG_{n^{\prime}}\), respectively, and they require the same number of AGVs to handle. If an AGV or a multi-AGV group can deliver \(T_{j}\) at \(Pt_{T_{i}}\) after delivering \(T_{i}\), it is considered that binding \(TG_{n^{\prime}}\) to \(TG_{n}\) is feasible. The conditions under which \(TG_{n^{\prime}}\) can be bound to \(TG_{n}\) can be expressed as:  
\[\left\{ \begin{array}{l}t_{T_{j}}^{e}\geq t_{T_{i}}^{s}+\left(D_{T_{i}}^{l}+D _{T_{j}}^{u}\right)/v\\ t_{T_{j}}^{s}\leq t_{T_{i}}^{e}+\left(D_{T_{i}}^{l}+D_{T_{j}}^{u}\right)/v\\ N_{G,T_{i}}=N_{G,T_{j}}\end{array} \right.\quad\exists T_{i}\in TG_{n},\; \exists T_{j}\in TG_{n^{\prime}} \tag{14}\]  
Figure 3: An example of coding and decoding. If an AGV or a multi-AGV group delivers task \(T_{i}\) at \(t_{T_{i}}^{e}\) and then handle \(T_{j}\), the delivery time of \(T_{j}\) is still earlier than \(t_{T_{i}}^{s}\), \(TG_{n}\) is called the forward task group of \(TG_{n^{\prime}}\). The conditions under which \(TG_{n}\) is the forward task group of \(TG_{n^{\prime}}\) can be expressed as:  
B. Similarity between task groups  
It is assumed that task group \(TG_{n^{\prime}}\) can be bound to the task group \(TG_{n}\). The task arrays of \(TG_{n}\) and \(TG_{n^{\prime}}\) are [\(a\ b\ b\ c\)] and [\(b\ b\ c\)], respectively, the number of elements in a task array is equal to the number of tasks in the task group, and the element is the number of AGVs required by each task in the task group. A similar array of \(TG_{n}\) and \(TG_{n^{\prime}}\) is [b b c]. The formula for calculating the similarity between task groups is as follows:  
\[f_{s}=0.5(b+b+c)/(a+b+b+c)+0.5(b+b+c)/(b+b+c+d) \tag{15}\]  
If \(TG_{n^{\prime}}\) cannot be bound to \(TG_{n}\) and \(TG_{n}\) cannot be bound to \(TG_{n^{\prime}}\), the similarity between them is zero. C. Task binding based on task group layering strategy  
The task group layering strategy is used to divide task groups one by one and gradually forms multiple layers storing task groups. Task groups with binding feasibility are placed in adjacent layers. The main steps of the task group layering strategy are given in Algorithm 1. Every time a layer is formed, the task binding method is used to bind task groups with non-zero similarity in adjacent layers, and then to bind tasks of the task groups bound. The task group binding follows the principle that task groups with bigger similarities are preferred. Moreover, task binding acquires that tasks require the same number of AGVs to handle. One task group or task can bind or be bound only once. For example, task groups \(TG_{n^{\prime}}=\{T_{5},T_{6},T_{7},T_{8}\}\) is bound to \(TG_{n}=\{T_{1},T_{2},T_{3},T_{4}\}\), and the task arrays of \(TG_{n^{\prime}}\) and \(TC_{n}\) are [b b c d] and [a b b c], respectively, so the binding scheme between \(TG_{n}\) and \(TG_{n^{\prime}}\) is \(T_{5}\) to \(T_{2},\ T_{6}\) to \(T_{3}\) and \(T_{7}\) to \(T_{4}\), while \(T_{1}\) and \(T_{8}\) are free. The main steps of the task binding method are given in Algorithm 2.