I think it be best to have the cleaner shrimp in the tank first, that way their not being introduced and though of as food... Usually the fish just somehow instinctively know not to eat them and know they're beneficial, but that doesn't always go. Things don't always go as planned, I mean I had a goldflake moray munch on a fist sized Volitan Lion...
Will cleaner shrimp do ok on fake coral though? does that not really matter to them?