Computing a realistic velocity profile for a mobile robot is a challenging task due to the large number of kinematic and dynamic constraints involved. In order for a mobile robot to complete its task it must be able to plan and follow a trajectory. It may also be necessary to follow a given velocity profile, depending on the environment. Temporal planning, or following a given velocity profile, can be used to minimize time of motion and to avoid moving obstacles. For example, assuming the mobile robot is a smart wheelchair, it must follow a prescribed path while following a strict speed limit. This paper presents a temporal planning algorithm that is implemented on a wheeled mobile robot to be used in an indoor setting, such as a hospital ward. The path planning stage is accomplished by using cubic spline functions. A trajectory is created by assigning an arbitrary time of 1 s to each segment of the path. This trajectory is made feasible by applying a number of constraints and using a linear scaling technique. When a velocity profile is given, a non-linear time scaling technique is used to fit the mobile robot's linear velocity to the given velocity profile. A method for avoiding moving obstacles is also implemented. Simulation and experimental results showed good agreement with each other. The main contribution of this paper is in developing a temporal planning algorithm, which is capable of moving on an uneven surface (graded non-flat), and its implementation on the mobile robot at the robotics lab in the University of Saskatchewan. This algorithm is computationally very efficient as it requires low computation cost and does not involve major iterations.