A mathematical programming system named SilverScreener uses a 0-1 integer programming model to help theater managers decide which movies to show on a weekly basis in a multiple-screen theater (Interfaces, May/June 2001). Suppose that management of Valley Cinemas would like to investigate the potential of using a similar scheduling system for their chain of multiple-screen theaters. Valley selected a small two-screen movie theater for the pilot testing and would like to develop an integer programming model to help schedule movies for the next four weeks. Six movies are available. The first week each movie is available, the last week each movie can be shown, and the maximum number of weeks that each movie can run is shown here.
|
Movie
|
First Week Available
|
Last Week Available
|
Max. Run (weeks)
|
|
1
|
1
|
2
|
2
|
|
2
|
1
|
3
|
2
|
|
3
|
1
|
1
|
2
|
|
4
|
2
|
4
|
2
|
|
5
|
3
|
6
|
3
|
|
6
|
3
|
5
|
3
|
The overall viewing schedule for the theater is composed of the individual schedules for each of the six movies. For each movie a schedule must be developed that specifies the week the movie starts and the number of consecutive weeks it will run. For instance, one possible schedule for movie 2 is for it to start in week 1 and run for two weeks. Theater policy requires that once a movie is started it must be shown in consecutive weeks. It can not be stopped and restarted again. To represent the schedule possibilities for each movie, the following decision variables were developed:
Xijw = 1 if movie i is scheduled to start in week j and run for w weeks; 0 otherwise
For example, x532 = 1 means that the schedule selected for movie 5 is to begin in week 3 and run for two weeks. For each movie, a separate variable is given for each possible schedule.
a. Three schedules are assigned with movie 1. Define the variables that represent these schedules.
b. Develop a constraint requiring that only one schedule be selected for movie 1.
c. Develop a constraint requiring that only one schedule be selected for movie 5.
d. Develop a constraint that restricts the number of movies selected for viewing in week 1.
e. Develop a constraint that restricts the number of movies selected for viewing in week 3.