A shift schedule is absolutely necessary to manage the work of each employee. However, manually constructing the schedule taken account of employee preference can impose a large burden on a constructor. In private tutoring school, a shift schedule should make arrangement of the requests of students in addition to teachers’ preference, being necessary to construct simultaneously a shift schedule for each teacher and a timetable for each student. In this paper, we have proposed a two-phase optimization method to find such schedules: shift scheduling using memetic algorithms and timetabling using simulated annealing. We have demonstrated that the proposed method, in particular memetic algorithms in the first phase, can be more effective for constructing a shift schedule and timetable that are taken account of both requests of teachers and students than the previous method using simple genetic algorithms and simulated annealing. In addition, we have developed an interface that allows users to interactively check and make minor modifications to the automatically created shift schedule. This user interface can be useful for the user to instantly check where constraints have been violated and assist in making corrections by the user.