Return to the model of Exercise 15-21 and consider applying Genetic Algorithm 15E.

(a) First consider encoding solutions by taking professors in p order (adding p = 21,c, 25 for rooms assigned to graduate assistants), then recording the room r to which each is assigned. Sketch what would happen if two solutions such as this were combined in crossover.

What kinds of infeasibility could result?

Explain. Then discuss how it might be managed by penalizing infeasibility with suitable “big M” terms in the objective function.

(b) Now consider encoding solutions by taking rooms in r order, recording the professor

(or graduate assistants) p assigned to the room. Sketch what would happen if two solutions were combined in crossover with cut points limited to the 5 boundaries between session lists for particular time slots, that is, after entry 5, 10, 15, 20, and 25. What kinds of infeasibility could result? Explain. Then discuss how it might be managed by penalizing infeasibility with suitable “big M” terms in the objective function.

(c) Finally, consider the method of Random Keys defined in 15.13 . Specifically, the solution would be encoded indirectly with 25 random numbers corresponding to rooms as in part (b). To recover the implied solution and evalute the objective function, the room with the lowest random number would be assigned to professor 1, the second to professor 2, and so on with the last 5 assigned to graduate students. Explain why infeasiblity could not result from crossovers between 2 such solutions, and how that could make Algorithm 15E more effective.