The process of manually constructing monthly working schedules for physicians in medium-sized and large departments at hospitals is a very time-consuming and error-prone task. The scheduler, typically a senior physician, is an expensive resource and oftentimes almost irreplaceable because of his acquired expertise in the scheduling process. We develop a mathematical model that formalizes every rule and regulation necessary to generate lawful schedules in the anesthesiology department of a 626-bed hospital in Berlin, Germany. We embed our detailed and complex mixed-integer programming formulation, which generates schedules superior to the ones currently in use, in an Excel environment to ensure ease of use, maximum flexibility with respect to changing all relevant inputs, and a visual output representation for practitioners. The presented approach reduces the workload for the scheduler dramatically, thereby increasing his availability for medical services. Our generated schedules outperform manually created schedules by significantly reducing the number of rule and regulation violations, while also improving key performance measures such as assigned overtime, granted employee-preferred shifts, and fairness considerations. Our approach also highlights important aspects in modeling the physician scheduling problem for practical implementation that have been widely ignored in the existing literature.