If it's a laptop (you never mentioned the make and model) this the issue could very well be cooling related. Also somewhat if it's a desktop, but not nearly as important as with a laptop.

If it's a laptop, did the service include the cleaning of the airways and fan(s), applying new thermal grease etc.?