Some design methodologies for Parallel Kinematic Machines (PKM) have been proposed but with limitations regarding two main problems: how to improve multiple properties of different nature such as accuracy, force or singularity poses, and how to check these properties for all poses inside the PKM workspace. To address these problems, this work proposes to formulate the design problem as a feasibility problem and use a data representation which takes into account the uncertainty or variation of the involved parameters. This method, based on interval analysis, allows to evaluate several performance indexes of a PKM design. For validation purposes, this methodology is applied to a PKM, obtaining a continuous set of possible kinematic parameters values for its architecture which is capable of fulfilling several performance requirements over a desired workspace.