The task Scheduling parent–teacher conferences involves finding a time that suits both parents and teachers with their existing time constraints and finding locations for the meetings. If all meetings would be independent without any dependencies, the planning of the meetings simplifies to unordered
timetabling rather than full-scale
scheduling where events need to be scheduled in a certain order, often because the output of one event forms an input for another. In most cases, certain dependencies exist: parents prefer not to wait too long between different interviews but need long enough breaks to move from one location to another or locations in close proximity. Also sometimes these conferences can be done online. These conferences talk about a child's or student's grade.
Methods Various methods exist for scheduling parent–teacher conferences. In the simplest case, the meetings are not pre-scheduled at all, parents come to school and line up to see each teacher they want to see. Meetings happen on a
first-come basis. Meetings can be scheduled in person, by phone or online.
In person In person scheduling can be done in two ways: • Parents come to school's administrative office to schedule meetings; scheduling is done by a school administrator. • Students schedule meeting times with teachers by carrying a booking sheet and asking teachers to allocate times that are still available. Teachers have their own booking sheet and they mark the time on both sheets. Parents usually have the option of indicating which teachers they wish to see and the preferred times. The advantage of the first is that teachers need not be involved in scheduling, the disadvantages are that a special middleman is required. The method is centralized in the sense that it is directed by neither a parent nor a teacher. The advantage of the second is that parents need not be involved in scheduling, the disadvantages are that teachers need to do the scheduling after their classes are over or during break times that they would otherwise need for rest, prepare for classes or advising students, parents do not know which slots the teachers have available and often get times that aren't suitable or optimal (booking schedules are optimized from the point of view of the teacher, not the parent); if a student doesn't want his/her parent to see teachers, all he/she may just not make the bookings, or leave it so late that there are no times available.
By phone Scheduling by phone also involves a parent and a school administrator to do the scheduling without parents needing to be physically at school at the time of the scheduling. In principle, the middlemen could be avoided by automated scheduling by phone but is currently hindered by the lack of sophisticated speech analysis. This process can cause high levels of demand on school offices.
Online Online scheduling is done by using
appointment scheduling software on the internet. The advantages of the system are that it is automated without a need for a middleman, centrally optimized both for parents and for teachers without the need to involve students.
Complexity Computationally, the scheduling problem is a
NP-complete problem and in the same
complexity class with other problems that involve
constraint satisfaction and
combinatorial optimization (so no fast algorithms are known for solving it). This can be seen as follows. We can check in time polynomial to the input size whether certain time slot assignment satisfies parent–teacher conference scheduling (PTCS) constraints. Therefore, PTCS ∈ NP. Ignoring constraints that complicate scheduling even further, let's only consider the constraints on parent availability (e.g. assuming that all teachers, rooms and time slots are always available). Then there exists a simple
polynomial transformation of the class-teacher assignment problem with teacher availability constraints (CTTA) in school timetable construction to the PTCS problem: namely, map class instances to teacher instances, teacher instances to parent instances, time slots to time slots (identity map), and teacher availability to parent availability. So if the PTCS problem were polynomial-time solvable by some algorithm, the transformation described above and the algorithm could be used to solve the CTTA problem too and the CTTA task would be polynomially solvable as well. But CTTA has been earlier proved to be NP-complete by the reduction from the NP-complete
3-SAT problem, so the PTC scheduling problem cannot be polynomially solvable either, and has to be NP-complete. ==Management==