Scheduling of AGVs in AGV-supported assembly lines consisting of zero-buffer workstations

Discrete assembly lines (DALs), in which each product is assembled workstation-by-workstation while AGVs take care of transporting products from one workstation to the next workstation, become increasingly popular due to their high flexibility. Scheduling AGVs is the most critical decision, as it significantly affects DALs’ production rate. This decision will be much more complicated when the buffer size at each workstation becomes smaller, because in this case AGVs’ schedules are more tightly coupled. This paper studies the scheduling of AGVs in a DAL consisting of zero-buffer workstations, aiming to minimize the total time required to complete the assembly of any given set of products. We first build a mixed integer programming model and prove that it is harder than a longstanding open problem. Note that zero-buffer means the highest coupling degree of each AGV’s schedule. We show that this makes the success rate of finding a feasible neighborhood solution from an initial feasible solution low, i.e., heuristics based on neighborhood moves often fail in our problem. Therefore, we develop a new constructive algorithm called “discrete-event-driven rule-based heuristic with tie-branching (DERHwTB)" as well as its accelerated variant called ADERHwTB. Numerical results show that for small-size instances, ADERHwTB is near-optimal because the average percentage gap between the objective value of solutions obtained using ADERHwTB and the optimal objective value obtained using Gurobi is no more than 2.99% in all tested instances (and most of those gaps are less than 2%); while for large-size instances, ADERHwTB can respectively bring at least 38.69%, 21.22%, 22.66%, 28.38%, and 29.06% performance improvement compared with five existing solution methods. We also derive three interesting managerial insights. First, 60%-80% of the total benefit from adding significantly more AGVs to a DAL with 10 workstations can be captured by a DAL with only 2 to 3 AGVs. Second, the role that each AGV plays is larger in a longer DAL, because the ratio between the minimum number of AGVs required to achieve 90% of the maximum possible benefit of a DAL and the number of workstations w decreases with increasing w. Third, the widely believed idea that “balanced allocation of a product’s assembly time among workstations improves the production rate of a continuous assembly line" does not always hold in a DAL, especially when the number of AGVs is small and the distance between two adjacent workstations is large.