Editing 2-satisfiability (section)

===Scheduling===
{{harvtxt|Even|Itai|Shamir|1976}} consider a model of classroom scheduling  in which a set of ''n'' teachers must be scheduled to teach each of ''m'' cohorts of students. The number of hours per week that teacher <math>i</math> spends with cohort <math>j</math> is described by entry <math>R_{ij}</math> of a matrix <math>R</math> given as input to the problem, and each teacher also has a set of hours during which he or she is available to be scheduled. As they show, the problem is [[NP-complete]], even when each teacher has at most three available hours, but it can be solved as an instance of 2-satisfiability when each teacher only has two available hours. (Teachers with only a single available hour may easily be eliminated from the problem.) In this problem, each variable <math>v_{ij}</math> corresponds to an hour that teacher <math>i</math> must spend with cohort <math>j</math>, the assignment to the variable specifies whether that hour is the first or the second of the teacher's available hours, and there is a 2-satisfiability clause preventing any conflict of either of two types: two cohorts assigned to a teacher at the same time as each other, or one cohort assigned to two teachers at the same time.<ref name="EIS76"/>

{{harvtxt|Miyashiro|Matsui|2005}} apply 2-satisfiability to a problem of sports scheduling, in which the pairings of a [[round-robin tournament]] have already been chosen and the games must be assigned to the teams' stadiums. In this problem, it is desirable to alternate home and away games to the extent possible, avoiding "breaks" in which a team plays two home games in a row or two away games in a row. At most two teams can avoid breaks entirely, alternating between home and away games; no other team can have the same home-away schedule as these two, because then it would be unable to play the team with which it had the same schedule. Therefore, an optimal schedule has two breakless teams and a single break for every other team. Once one of the breakless teams is chosen, one can set up a 2-satisfiability problem in which each variable represents the home-away assignment for a single team in a single game, and the constraints enforce the properties that any two teams have a consistent assignment for their games, that each team have at most one break before and at most one break after the game with the breakless team, and that no team has two breaks. Therefore, testing whether a schedule admits a solution with the optimal number of breaks can be done by solving a linear number of 2-satisfiability problems, one for each choice of the breakless team. A similar technique also allows finding schedules in which every team has a single break, and maximizing rather than minimizing the number of breaks (to reduce the total mileage traveled by the teams).<ref>{{citation|first1=Ryuhei|last1=Miyashiro|first2=Tomomi|last2=Matsui|title=A polynomial-time algorithm to find an equitable home–away assignment|journal=Operations Research Letters|volume=33|issue=3|year=2005|pages=235–241|doi=10.1016/j.orl.2004.06.004|citeseerx=10.1.1.64.240}}.</ref>