# Hybrid Task Allocation of an AGV System for Task Groups of an Assembly Line
## 1 Introduction  
An automatic guided vehicle (AGV) system is a logistic robot system for material transportation. It has been applied in many fields, especially manufacturing shops [1, 2], port transportation [3, 4] and warehousing distribution [5, 6]. Research on AGV systems mainly focuses on task allocation [7], traffic control [8], guide-path network design [9, 10] and path planning [11, 12]. Among them, task allocation is always a hot research direction. The key to the task allocation problem is to determine the assignment relationship between tasks and AGVs, and the order in which AGVs execute tasks. In a large equipment assembly shop, such as bus chassis assembly line (BCAL), a fleet of homogeneous AGVs with limited transport capacity is responsible to deliver assembly materials to assembly stations. The materials include regular-size parts and large-size components. For a regular-size part, its size and weight are both within the capacity of an AGV, a single AGV transports it individually, and the corresponding material handling task is a single-AGV task. While, for a large-size component, several AGVs are combined as a multi-AGV group to carry it, and the corresponding material handling task is a multi-AGV task. In the above assembly shop, the hybrid task allocation problem is involved. It is important for these assembly shops to solve the hybrid task allocation problem because an efficient task allocation can increase productivity. However, there are few studies on hybrid task allocation problems. An assembly operation at a station needs to consume several materials. When a station sends a signal to the control system to request materials for the next operation, several tasks transporting materials for the operation, are generated simultaneously. Moreover, these tasks are packaged as a task group. An operation can begin only when all tasks in the corresponding task group have been completed. So, for an operation, the tasks in a task group are not independent of each other. We call this non-independence a cooperative relationship. Each task has the best delivery time interval with two time attributes: the start time and the end time. The start time is set for the limited storage space in the storage area beside the station, and there is no space available for unloading when materials are delivered earlier than the start time. The operating delay occurs when materials are delivered later than the end time. So, for each task, the AGV or the multi-AGV group must deliver the material on its best delivery time interval. As described above, the completeness of materials and the punctuality of material delivery are two important points that must be considered when solving the task allocation problem. Although many studies have been carried out on the task allocation problem, there is no research on the hybrid task allocation problem with consideration of the cooperative relationship between tasks. Our study aims to fill this research gap by proposing new algorithms for the problem. Therefore, in this paper, an effective hybrid task allocation method is proposed for the considered hybrid task allocation problem, and the proposed method takes the cooperative relationship between tasks and the best delivery time interval of tasks into account. Our highlights and main contributions are four-fold: (1) A mathematical model is established in view of the completeness of materials and the punctuality of material delivery; (2) a task binding strategy is proposed to reduce coding effort and to improve the quality of random solutions in initial population; (3) several heuristic rules are proposed to generate promising heuristic solutions for initial population; (4) an improved particle swarm optimization (IPSO) algorithm is developed with a mutation operation to help the algorithm jumping out of local optimums. The remainder of the paper is organized as follows. The next section summarizes related work. The problem definition is dedicated in Section 3.