This paper focuses on the enhancement of automatic robot programming techniques for laser cutting applications. Such technology has already gained essential industrial acceptance, but its application for small lot production is limited by the tedious and time-consuming process of robot programming. Currently, even sophisticated graphical simulation systems do not allow optimization of robot motion using multiple criteria, nor does it take into account redundancy caused by the tool axial symmetry. The particular contribution of this paper lies in the area of multiobjective optimization of robot motions via graph representation of the search space and dynamic programming procedures. It presents algorithms that allow generation of smooth manipulator trajectories within acceptable time, simultaneously considering kinematics, collision and singularities constraints of the robotic system, as well as the limitations of the robot control units. The efficiency of the algorithms has been carefully investigated via computer simulation. The presented results are implemented in a commercial software package and verified for real-life applications in the automotive industry.