Fluid mixing in two- and three-dimensional time-periodic cavity flows as a function of rheological fluid parameters is studied. Computational methods are applied to obtain accurate descriptions of the velocity fields, which form the basis of the mixing analysis. In addition to some classical techniques, like Poincare maps and the analysis of periodic points, a recently developed mapping method is used to determine mixing efficiency over a wide range of different flow parameters. Within this framework, different mixing protocols can be evaluated with respect to their long term mixing behaviour and compared quantitatively. It is shown that local 'optimal' parameter settings for mixing of Newtonian fluids can result in a considerable worse mixing behaviour for non-Newtonian fluids, and vice versa, illustrating the importance of taking the rheology of the fluid into account.