On the problem of movie selection and scheduling to maximize revenue

Abstract

We consider a problem of the selection and scheduling of movies for a multiplex (i.e., a theater with multiple screens) to maximize the exhibitor's cumulative revenue over a fixed planning horizon. Effective and timely decisions on screen management directly and crucially relate to the effective capacity and resources usage, productivity and successful economical performance of the theater. In the problem under study, the release times of the movies that can potentially be selected during the planning horizon are known a priori. If selected for screening, a movie must be played continuously through its obligatory duration, after which its run may or may not be extended. The problem involves two primary decisions: (i) the selection of movies to play and (ii) the determination of the duration of screening for the selected movies. We show that revenue optimization problem under the preempt-resume policy is strongly NP-hard even in the minimal case, thus completely resolving the complexity status of the problem. We also consider the optimization problem under the non-preempt policy for a case of unequal screen capacities and show that an optimal solution may significantly differ from the solution obtained for the equal-capacity case.