This paper presents how to solve Physician Scheduling at an Emergency Department over the real datasets of King Khalid University Hospital in Saudi Arabia. Due to the complexity of this problem, we propose Iterated Local Search that provides Physician schedules with improved efficiency and staff satisfaction. A comparison between proposed schedules and mathematical model shows on outperformance of the proposed one.