With the emergence of more complex and sophisticated real time applications, the user’s expectations on the Reliability and Availability (R & A) of these systems are becoming even more demanding. A major issue is to be able to capture these requirements faithfully at the beginning of the design cycle, given the fact that user’s often express their R & A assessments in an approximate and uncertain manner and change them under varying situations. Moreover the designer’s choice in assigning importance levels to various components must support the user’s viewpoint on the importance of various services offered by the system. In this paper, we employ a fuzzy-rule based engine that evaluates the user’s availability requirements. We recognize that the mere presence of a service is not enough to measure its ”availability” because the user expects a certain level of accuracy in the results to be able to utilize it properly. We define a quality metric that combines accuracy with availability, defined as Qualitative Availability. Our modified task graph model incorporates AND nodes and OR nodes that integrate a task’s inputs using the appropriate logic. In addition, there are ’Q’ nodes to model tasks that utilize their inputs in a quality-scaled manner. Using the fuzzy-availability model and a deadline-based priority scheduling technique, a Genetic Algorithm (GA) drives the design exploration process to generate a set of heterogeneous multiprocessor architectures satisfying the multiple objectives of high system availability, accuracy and real-time performance at an acceptable cost. Experiments carried out with a CAD tool built upon the proposed methodology show that we can generate a range of solutions for a variety of representative applications and obtain alternative solutions to tradeoff between different objectives.