How do I create a task scheduler to restart a software service in Windows Server 2008 R2

Following the suggestions in the comments, I ended up creating a batch file containing the proper restart sequence with timeouts. Timeouts were necessary because of the dependencies between the services. I scheduled it to run as admin every night at 4AM using the task scheduler.

net stop "Service B"
net stop "Service A"
timeout /T 10
net start "Service B"
timeout /T 10
net start "Service A"

It's not ideal, but it will do for this scenario — a remote desktop deployment with less than 10 users.

Instead of creating a bat file, which can become corrupt or missing, you can create a scheduled task with multiple actions. One action to stop the service, and another one to restart the service. Both executed with the NET command. Give them a STOP and START argument, followed by the service name.

NET STOP "Service A" 
NET START "Service A"

Here's a post on StackOverflow explaining how.