Consider a company which wants to set up an advertising campaign in preparation for the introduction of a new product. Several types of audiences have been identified as target audiences for the new product. In addition, there is a selection of media available to reach the various targets. However, there is no medium that will reach all audiences.

Consequently, several media need to be selected at the same time in order to cover all targets. The company wants to investigate various strategic advertising choices. The goal is not to stay within an a priori fixed budget, but to minimize the total cost of selecting media for each of the strategic choices.

The crosses in the table indicate which target audiences can be reached by each particular medium. Note that a cross does not say anything about the effectiveness of the medium. The right hand column gives the cost to use a particular medium. The table is deliberately small for simplicity reasons. In practical applications both the data set and the reality behind the scheduling problem is more extensive.