The traditional relaxation labeling (RL) scheme [1] suffers from the difficulty of computing correlations or compatibilities. We extend RL into an extended relaxation labeling (ERL) scheme by redesigning the way of calculating compatibilities. Furthermore, a new scheme using Dempster-Shafer theory to combine the uncertain knowledge sources, called the evidential relaxation labeling (EVRL) scheme, is proposed. These two schemes accept relational and constraint information from problem domains and translate them into numerical compatibilities so that a relaxational weight updating process can be carried out. We show that the EVRL scheme has advantages over the RL scheme as well as the ERL scheme. Firstly, it provides a more general framework for expressing uncertain knowledge. Secondly, it avoids the difficulty of computing numerical or probabilistic compatibilities. Thirdly, it takes less iterations to converge.