Making a high quality staff schedule is both difficult and time consuming for any company that has employees working on irregular schedules. We formulate a mixed integer program (MIP) to find a feasible schedule that satisfies all hard constraints while minimizing the soft constraint violations as well as satisfying as many of the employees' requests as possible. We present the MIP model and show the result from four real world companies and institutions. We also compare the results with those of a local search based algorithm that is designed to emulate the solution strategies when the schedules are created manually. The results show that using near-optimal solutions from the MIP model, with a relative MIP gap of around 0.01–0.1, instead of finding the optimal solution, allows us to find very good solutions in a reasonable amount of time that compare favorably with both the manual solutions and the solutions found by the local search based algorithm.