An on-line scheduling algorithm was proposed for simultaneous scheduling of machines and automated guided vehicles in flexible job shop. The problem was decomposed into two sub-problems: machine selection problem and vehicle dispatching problem. The machine selection problem was solved by enumerative method for small size and niche genetic algorithm otherwise. Local search was executed to improve the convergence speed of genetic algorithm. To keep a high degree of population diversity, Hamming distance based niche competition operation was adopted. For vehicle dispatching problem, a heuristic dispatching algorithm was proposed. To ensure the job shop to be deadlock-free, a remaining capacity based deadlock avoidance rule was employed. The simulation results showed that the proposed algorithm was feasible. 