This research addresses a shift scheduling problem in which physicians at a German university hospital are assigned to demand periods over a planning horizon that can extend up to several weeks. When performing the scheduling it is necessary to take into account a variety of legal and institutional constraints that are imposed by a national labor agreement, which governs all physicians in German university hospitals. Currently, most medical departments develop their staff schedules manually at great cost and time. To solve the problem, a new modeling approach is developed that requires shifts to be generated implicitly. Rather than beginning with a predetermined number of shift types and start times, shifts are allowed to start at every pre-defined period in the planning horizon and extend up to 13 h with an hour-long break included. The objective is to find an assignment such that the total hours that have to be paid out as overtime are minimal under the restrictions given by the labor agreement. The problem is formulated as a mixed-integer program and solved with CPLEX. During the solution process individual lines-of-work are constructed for each physician. Using data from an anesthesia department, computational results indicate that high quality schedules can be obtained much more quickly than by current practice.