We developed a method for workforce scheduling that models both the structure of the set of permissible shifts, and the stochastic and time-varying demand process. A prototype implementation uses a genetic algorithm to search for good schedules, and evaluates the service level resulting from a schedule by numerically solving the equations of motion for a time-varying queueing system. Comparison with a traditional approach using a ''stationary independent period-by-period'' (SIPP) assumption to set staffing requirements and an integer program (IP) to choose shifts indicates that the traditional approach can significantly overestimate the service level that results from a schedule. Further, our method sometimes generates schedules that result in both lower labor cost and higher service level than those found with the SIPP-IP approach. An additional benefit of our method is its applicability in ''rush hour'' situations where the arrival rate to the system temporarily exceeds its capacity to serve customers.