On-Call Weekends? (Linear Programming) There are 9 persons. On every weekend two of them has to be on-call. I want to create on-call calendar so that

*

*every person will have at least two free weekends after an on-call weekend

*on-call pairs will always change

Possible pairs are (persons are 1...9), total 36 different pairs:
12 13 14 15 16 17 18 19 23 24 25 26 27 28 29 34 35 36 37 38 39 45 46 47 48 49 56 57 58 59 67 68 69 78 79 89
How can i solve this with Excel solver, or GLPK?
> lp beginner, Finland

Excel may help. List all the 36 pairs, then manually or automatically take every pair down the list if it does not obey the free weekend constraints. Repeat as necessary. Manually, I found the following pairs for the 36 weeks, in order:
(1,2),(3,4),(5,6),(2,9),(7,8),(1,3),(6,9),(2,4),(5,7),(8,9),(1,4),(2,3),(5,8),(6,7),(3,9),(1,5),(2,8),(3,6),(4,5),(7,9),(1,6),(4,8),(2,5),(3,7),(1,8),(4,6),(5,9),(1,7),(2,6),(3,5),(4,7),(6,8),(1,9),(2,7),(3,8),(4,9).
