This paper evaluates and implements composite importance measures (CIM) for multi-state systems with multi-state components (MSMC). Importance measures are frequently used as a means to evaluate and rank the impact and criticality of individual components within a system yet they are less often used as a guide to prioritize system reliability improvements. For multi-state systems, previously developed measures sometimes are not appropriate and they do not meet all user needs. This study has two inter-related goals: first, to distinguish between two types of importance measures that can be used for evaluating the criticality of components in MSMC with respect to multi-state system reliability, and second, based on the CIM, to develop a component allocation heuristic to maximize system reliability improvements. The heuristic uses Monte-Carlo simulation together with the max-flow min-cut algorithm as a means to compute component CIM. These measures are then transformed into a cost-based composite metric that guides the allocation of redundant elements into the existing system. Experimental results for different system complexities show that these new CIM can effectively estimate the criticality of components with respect to multi-state system reliability. Similarly, these results show that the CIM-based heuristic can be used as a fast and effective technique to guide system reliability improvements.