Abstract: In this paper, scheduling problem of job-shop with a single transport robot is addressed. A parallel tabu search algorithm is presented to minimize the makespan. First, with the characteristic of the problem, two schedules are created as the initial solutions by using a heuristic. Then, the tabu search algorithm is used for parallel search. By this algorithm, a disjunctive graph model is established such that the critical path and the block are found. Then, a strategy of moving or changing on block is used for the neighborhood in the algorithm. Experimental results show that the algorithm is effective.