In this paper we examine the minimum-time velocity profile generation problem which belongs to the second stage of the decoupled robot motion planning. The time-optimal profile generation problem can be translated to a convex optimal control task through a nonlinear change of variables. When the constraints of the problem have special structure, the time-optimal solution can be obtained by linear programming (LP). In this special case, the velocity of the robot along the path is maximised, instead of time minimising. The benefit of the LP solution is the lower computational time. Validation of the LP algorithm is also presented based on simulation results.