User needs-driven and computer-supported development of pervasive heterogeneous and dynamic multi-agent systems remains a great challenge for agent research community. This paper presents an innovative approach to composing, validating and supporting multi-agent systems at run-time. Multi-agent systems (MASs) can and should be assembled quasi-automatically and dynamically based on high-level user specifications which are transformed into a shared and common goal-mission. Dynamically generating agents could also be supported as a pervasive service. Heterogeneity of MASs refers to diverse functionality and constituency of the system which include mobile as well as host associated software agents. This paper proposes and demonstrates on-demand and just-in-time agent composition approach which is combined with run-time support for MASs. Run-time support is based on mission cost-efficiency and shared objectives which enable termination, generation, injection and replacement of software agents as the mission evolves at run-time. We present the formal underpinning of our approach and describe the prototype tool - called eHermes, which has been implemented using available agent platforms. Analysis and results of evaluating eHermes are presented and discussed.