Scheduling Commercial Videotapes in Broadcast Television

This web page provides the interested reader of with material to reproduce the numerical results presented in the paper. Please download

Models and algorithms have been implemented in GAMS (distribution 20.8 and higher). The collection of GAMS models implements P2, P3, Delta P3, Batch P3 and the Assignment Heuristic. The various options for the models and the algorithms can be passed on through the command line. For example,

  gams cc --curid=12 --alg=ah

All options are also described in the header of the GAMS model cc.gms:

This model computes an optimal or near optimal schedule for the ISCI problem:

Major advertisers purchase several slots to air commercials during a given time
period on a broadcast network.  We study the problem of scheduling advertiser's
commercials in the slots it purchased when the same commercial is to be aired
multiple times.  Under such a situation, the advertisers typically want the
airings of a commercial to be as much evenly spaced as possible.

Following options are possible:

curid       - Identifier of the problem instance (0-40)
alg         - Algorithm/Model used to solve instance:
                p2    GAMS/CPLEX P2
                p3    GAMS/CPLEX P3
                d3    P3/Delta Heuristic
                b3    P3/Batching Heuristic
                ah    Assignment Heuristic
resmax      - Maximum time available to solve the instance
preplaced   - use instance with preplaced balls (not available with alg=ah)
By default the model runs the Batch Heuristic (b3) for instance 1 with a maximum of 600 CPU second.

The model creates appends to a log file res.txt. Here is an example of a log record:

ID: 34   p2 SOBJ:  298.4941 BND:  112.2695 T:   625s
The instance 34 has been solve with model P2. The model found a solution of value 298.4941 and established a lower bound of 112.2695 and ran for 625 seconds.

Please download the Excel Spreadsheet with result for running P2, P3, Delta P3 and the Batch P3 Heuristic for the instances with preplaced balls.

In order to run the models you need a license for GAMS and GAMS/CPLEX.