Multiple mobile robots become more and more significant in industrial, commercial and scientific applications. Also, these multiple mobile robots can be applied to public area using service robots like office and hospital. In these environments, humans request robot's service concurrently and irregularly, and then multiple robots have to process multiple tasks simultaneously. In these situations, for mobile robots to serve satisfactorily human's request, the task assignment must be efficiently performed without any error. Since the task assignment problem occurs and the task assignment method of robots affects a performance of multiple mobile robots system, task scheduling of robots is very important. The conventional scheduling methods are classified to the robot initiated task assignment rule and the station initiated task assignment rule. However, the conventional scheduling methods may not function effectively in these dynamic environments because they are one directional scheduling method. This thesis presents a protocol between robot and station for on-line and decentralized scheduling which improves a performance of multiple mobile robots. The proposed protocol considers both robot initiated task assignment rule and station initiated task assignment rule simultaneously. That protocol is modeled by Petri net to check resource conflict and deadlock problem. In order to confirm the feasibility of the proposed protocol, the computer simulation is carried out. The simulation results are compared with those of conventional methods.