Resent advances in computer vision and arc-welding technology motivate rethinking of some postulates and conventions incorporated in the existing robot off-line programming methods. This reserch addresses relaxing of the downhand-position assumption, which became a de-facto standard in robotic welding and requires the weld joint to be oriented in such way that the weldline is horizontal and the weld normal vector is directed strictly opposite to gravity. In contrast to the standard techniques, the developed method explicitly assumes that a weld may be processed in the out-of-position location, which differs from the downhand one within given tolerances. But, to ensure the prescribed quality, the corresponding downhand deviation is charged by reduction of the welding speed in order to satisfy the quality specifications. For such settings, it is proposed a novel method for the cluster-level welding operations planning for a robotic cell with a positioning table. The objective is to minimise the overall manufacturing time, by finding a reasonable trade-off between the positioner motion times and the cluster processing times, since ensuring the downhand orientation for each cluster reduces the cluster processing time but requires more time for the re-configuration of the positioner. It is shown, that associated optimisation problem may be presented as a specific case of the generalised traveling salesman problem, for which has been developed an efficient heuristic algorithm that produces both the optimal welding cluster sequence and corresponding optimal motions of the positioner. The algorithm effectiveness was verified for a number of randomly generated problems, which results are reported and analysed in detail. It is also presented an industrial case study confirming validity of the developed technique and its ability to generate, in reasonable amount of time, solutions accepted by practicing engineers.