A branch and bound algorithm for optimal television commercial scheduling

1.   Introduction

Television (TV) plays an important role in transmitting advertising messages in the current era of multimedia. In fact, TV advertising is one of the most effective channels to provide fast propagation of advertising messages to audiences ^[1]. In India, TV is the largest and fastest growing medium and is expected to grow at a compound annual growth rate of 15%, with total revenue reaching USD 15.2 billion in 2019 ^[2]. According to an NBC Universal report, its TV advertising business generated more than 5 billion U.S. dollars in revenue each year from 2012 to 2020 ^[3]. The website Statista predicted that television advertising revenue in the United States will grow from 72.3 billion U.S. dollars in 2021 to 81 billion in 2025. Further, global TV advertising revenue has been projected to increase from 151 billion U.S. dollars to 162 billion between 2020 and 2024 ^[4]. Thus, TV advertising, which is the primary source of revenue for the TV industry, is very big business ^[5] and ^[6].

In TV advertising, there are two major participants: TV channels (or networks/stations) and advertisers. TV channels need to schedule programs into appropriate time slots or spots (advertising breaks) for the next scheduling horizon. Then, the marketing department of the TV channel sells the spots based on associated audience ratings. Advertisers buy the advertising breaks with the goal of achieving the most efficient media plan within a limited budget ^[7]. Thus, TV advertising scheduling allocates a number of advertisement time slots to advertisers while satisfying advertisers' requirements or choosing the advertisers to whom the time slots are sold ^[8]. This is one of the most important decisions for a TV channel, providing a vital source of revenue for the TV station ^[9]. This type of scheduling is becoming more and more competitive and turbulent because of the fast development of communication and broadcasting means. Over the past two decades, this challenging problem has attracted much research.

Brown ^[10] discussed various difficulties in scheduling TV commercials manually and developed an algorithm to exchange commercials of different lengths between advertising slots to gain space for other commercials. Hägele, Ó Dúnlaing, and Riis ^[11] proved that the problem defined by Brown ^[10] is NP-complete. Bollapragada et al. ^[12], Bollapragadae et al. ^[13] and Brusco ^[14] dealt with the advertising scheduling challenges faced by NBC. Bollapragada et al. ^[12] defined an optimization model to generate sales plans to meet the requirements of a single advertiser. The problem was modelled as mixed-integer programming, and solutions were found sequentially for each advertiser using mathematical programming-based heuristics.

Bollapragada et al. ^[13] and Brusco ^[14] also discussed the scheduling of multiple commercials such that the output schedule allows for the appropriate spacing of multiple airings of the same commercials. Brusco ^[14] developed an enhanced version of the branch and bound algorithm of Bollapragada et al. ^[13] and a simulated annealing heuristic for handling larger instances of the problem studied. Bollapragada and Garbiras ^[15] formulated the commercial scheduling problem as a goal programming model and designed a two-stage heuristic algorithm for the automatic scheduling of commercials that minimized the penalty cost for the television network while incorporating the costs of sales personnel and meeting promised positions with consideration of product conflicts. Gaur, Krishnamurti, and Kohli ^[16] extended the model proposed by Bollapragada and Garbiras ^[15]. They considered the differential weighting of conflicts between the pairs of commercials by formulating the problem as a binary integer program that was a generalization of the max k-cut.

Ghassemi-Tari and Alaei ^[5] considered the concept of a combinatorial auction and formulated a combinatorial auction-based mathematical programming model to maximize the revenue of the television network via commercial placement. García-Villoria and Salhi ^[7] considered the possibility of multiple airings of each commercial being as evenly spaced as possible during the airing period. Furthermore, advertisers may request a minimum number of times for which each commercial is aired in high- and medium-audience-rating spots. Thus, García-Villoria and Salhi ^[7] presented two mixed-integer linear programming models, local search procedures, and a simulated annealing algorithm to solve the proposed problem.

Guerriero, Miglionico, and Olivito ^[17] addressed the problem of accepting commercials for TV slots with the aim of maximizing TV revenue. They developed mathematical programming models and defined several constructive heuristics together with some local searches to solve the problem. Díaz-Núñez, Halman, and Vásquez ^[9] discussed a TV channel considering a TV rating points function and willingness to pay coefficients with the aim of scheduling a set of TV commercials in a single time slot to maximize the total revenue. Sinha, Dharmarha, and Kumar ^[1] proposed a goal programming model to determine the optimal schedule of commercials for a TV channel, advertising breaks, and the frequency of commercials.

Czerniachowska ^[6] considered the scheduling problem from the perspective of the advertisers, proposing a genetic algorithm to allocate TV commercials according to the requirements of the advertisers and their limited budget while maximizing the total viewership. Fontes, Pereira, and Fontes ^[8] considered the problem of scheduling self-promotion commercials to a given set of advertising breaks while maximizing audience ratings between TV programs for a TV station. For comprehensive surveys in this area, we refer the readers to ^[2].

Considering the literature described above, we find that a critical issue faced by TV channels is how to schedule commercials in advertising breaks to maximize the revenue or minimize the penalties incurred for not satisfying the requirements of the clients. This is similar to the machine scheduling problem, which also faces availability constraints. The machine availability constraint denotes a set of identical machines that are not continuously available for processing; in other words, the machines can only serve jobs on a set of availability intervals ^[18,19]. To the best of our knowledge, the existing literature has not considered the TV advertising scheduling problem from this perspective. Thus, we are motivated to deal with the TV advertising scheduling problem by applying the methods developed for solving the machine scheduling problem with availability constraints. Therefore, we propose a branch and bound algorithm to address the TV commercial scheduling problem.

The remainder of the paper is organized as follows. In Section 2, we describe the problem and notations used throughout this paper. In Section 3, we construct a branch and bound algorithm for the problem. Computational experiments are given in Section 4, and Section 5 concludes.

2.   Definition of the problem and notations

In a typical parallel machine scheduling problem with machine availability constraints, there are n jobs, each with given processing time and due date, and m machines, which are only available for processing in specified availability intervals. The goal is to find a schedule that minimizes the maximum lateness. The lateness of a job is defined to be its completion time minus its due date. The maximum lateness problem consists of finding a schedule that minimizes the maximum lateness over all jobs. In other words, jobs should be completed at available times on machines as close as possible to their due dates. In this paper, the studied problem is similar to the stated parallel machine scheduling problem with machine availability constraints.

Next, we define the scheduling in the context of TV advertising as follows. We consider the problem of scheduling n commercials with service-level requirements on m TV channels. Each commercial has a due date, release time, processing time, and required service level. Each TV channel has a number of advertising breaks. These advertising breaks are classified into different levels according to certain properties, such as the audience rating on TV programs, which is used as the service level in this study. The service level constraint denotes that a commercial can only be processed within a specified set of the advertising breaks. A lower service-level requirement of a commercial can be satisfied by advertising breaks with the same or higher service level. However, a TV channel that provides a lower service level cannot broadcast commercials that require higher service levels. The objective is to minimize the maximum lateness of the schedule, as most TV channels do not want to delay the time taken to broadcast their clients' commercials because the delay can incur penalties.

2.1.   Assumptions

● A system has m TV channels, which do not operate continuously; each channel is ready for processing only in certain advertising breaks.

● The start and finish times of each advertising break and the number of all advertising breaks are known in advance.

● At any time, a commercial can be assigned to a maximum of one TV channel, and a TV channel can execute a maximum of one commercial.

● Advertising breaks can be classified into different service levels, and each advertising break is characterized by only one type of service level in the system.

● No commercials are allowed to be preempted.

● Each commercial can be processed only on a specified set of TV channels.

● Each commercial has a specific service-level requirement to be broadcasted. For example, a commercial with service level k implies that the commercial must be broadcast in an advertising break with service level k or below.

2.2.   Notations

We are given m TV channels and n commercials with the following notations (Table 1) throughout this paper.

3.   A branch and bound algorithm

In this section, we propose a branch and bound algorithm to find an optimal solution for the studied problem. We introduce the proposed algorithm in the following three stages. First, we introduce the bounding scheme in Section 3.1. We extend the modified LFJ (least flexible job first)-based algorithm proposed by Liao ^[20] to construct an LFJ/EDD (earliest due date first) algorithm to find a feasible solution and use the result as the upper bound. Then, we apply a two-phase binary search algorithm, proposed by Sheen and Liao ^[21], to find an optimal solution for scheduling machine-dependent jobs on machines with availability constraints and use this result as the lower bound of the studied problem. Following this, we discuss the branching scheme in Section 3.2. Finally, we propose the complete branch and bound algorithm in Section 3.3.

3.1.   Bounding scheme

We introduce the procedures for obtaining a lower bound $\underline{LB}$ and an upper bound $\overline{UB}$ of the maximum lateness.

3.1.1.   The procedure of the upper bounding

Our proposed algorithm to find a feasible schedule extends the modified LFJ algorithm provided by Liao ^[20]. Liao's algorithm solved the problem with identical machines in the presence of machine availability for minimizing makespan in polynomial time, where makespan is defined as the total length of the schedule. However, this approach did not account for due date constraints and only incorporated unit processing time. Hence, we extend the modified LFJ algorithm to integrate the LFJ and EDD rules to find a feasible schedule that allocates commercials in advertising breaks that satisfy the service-level requirements. The algorithm derives an upper bound of the maximum lateness for the following problem formulation:

Assume that there are m TV channels and each channel is only available for processing within each of N(i) specified advertising breaks $\left[{b}_{i}^{r}, {f}_{i}^{r}\right]$ with service level ${rs}_{i}^{r}$. There are n commercials to be scheduled. Each commercial j is associated with a release time ${r}_{j}$, a processing time ${p}_{j}$, a due date ${d}_{j}$, and a required service level $r{s}_{j}$. Commercial j can only be processed for a specific set $S{L}_{j}$. A commercial is selected to be scheduled when it belongs to the least flexible commercial with the earliest due date in the unscheduled commercial set ${J}_{}^{c}$, namely, the commercial with the minimum value of $\left|S{L}_{j}\right|$. The selected job j will be allocated to $\left[{b}_{i}^{r}, {f}_{i}^{r}\right]$ as early as possible. The commercials continue being allocated to suitable advertising breaks until all commercials are fully scheduled or there exists no feasible schedule. We derive an upper bound of the maximum lateness for the studied problem when the proposed algorithm obtains a feasible schedule.

Theorem 1. Assume n commercials and total $\sum _{i = 1}^{m}N\left(i\right)$ advertising breaks in m TV channels, as well as h service levels in the TV advertising scheduling problem. The time complexity of the LFJ/EDD rule algorithm is $O\left({n}^{2}\sum _{i = 1}^{m}N\left(i\right)\right)$.

Proof. The worst-case complexity is analyzed as follows:

Step 0: Need $O\left(n\sum _{i = 1}^{m}N\left(i\right)\right)$ time for initialization.

0.1) $O\left(n\sum _{i = 1}^{m}N\left(i\right)\right)$ time for initializing sets SL_j.

0.2) $O\left(1\right)$ time.

Step 1: Need$O\left(n\right)$ time to choose least flexible commercial j*.

Step 2: Need $O\left(\sum _{i = 1}^{m}N\left(i\right)\right)$ time at Step 2 since there are, at most, $\sum _{i = 1}^{m}N\left(i\right)$ available advertising breaks in SL_j.

Step 3: O(1) time.

3.1) O(1) time.

3.2) O(1) time.

3.3) O(1) time.

Step 4: Need $O\left(n\sum _{i = 1}^{m}N\left(i\right)\right)$ time to update the $\left[{b}_{i}^{r}, {f}_{i}^{r}\right]$ in set SL_j, for $j\in {J}^{c}$).

Step 5: O(1) time.

The algorithm needs to iterate Step 1 to Step 5 n times. As such, the worst-case complexity of the algorithm is dominated by Step 4 and is $O\left({n}^{2}\sum _{i = 1}^{m}N\left(i\right)\right)$. The proof is complete.

3.1.2.   The procedure of the lower bounding

In this section, we derive the lower bound $\underline{LB}$ of the maximum lateness of the studied problem by applying the two-phase binary search algorithm proposed by Sheen and Liao ^[21]. In Sheen and Liao's article ^[21], the machine scheduling problem had n pre-emptive jobs on m machines under machine availability constraints with the objective of minimizing maximum lateness. The polynomial time two-phase binary search algorithm solved the problem optimally by solving a series of maximum flow problems. The time complexity of this algorithm is O((n + (2n + 2x)⁾³ log(UB − LB)), where $x = {\sum }_{i = 1}^{m}N\left(i\right)$. We omit the detail because the algorithm is obtained directly from the work of Sheen and Liao ^[21].

3.2.   Branching scheme

Each node $\alpha$ in the search tree is defined by ${J}_{\alpha }^{}$, ${J}_{\alpha }^{c}$, ${L}_{max}\left(\alpha \right)$, $\overline{UB}\left(\alpha \right)$, and$\underline{LB}\left(\alpha \right)$, which are defined as follows. ${J}_{\alpha }^{}$represents the scheduled commercials on the TV channel i for $i\in A$. ${J}_{\alpha }^{c}$ represents all commercials that are not yet scheduled. ${L}_{max}\left(\alpha \right)$ indicates the maximum lateness among the scheduled commercials in ${J}_{\alpha }^{}$. $\overline{UB}\left(\alpha \right)$ and $\underline{LB}\left(\alpha \right)$ denote the upper and lower bounds of node $\alpha$, respectively.

There is only one root node at the top of the search tree. Let $\alpha$ be the root node. There are no commercials in the corresponding ${J}_{\alpha }^{}$, and ${J}_{\alpha }^{c}$ contains all commercials. In node $\alpha$, the proposed LFJ/EDD rule algorithm is applied to calculate the value of $\overline{UB}\left(\alpha \right)$ based on the commercials in ${J}_{\alpha }^{c}$. Then, a two-phase binary search algorithm is uesd to find the lower bound $\underline{LB}\left(\alpha \right).$A newly created node, say $\beta$, branching out from node $\alpha$ is created by taking m commercials in ${J}_{\alpha }^{c}$ and arranging these commercials into sequence ${J}_{\beta }^{}$. This means that node $\beta$ corresponds to a partial schedule with m commercials scheduled as compared to node $\alpha$. In the following, we offer a proposition that aims to eliminate unnecessary node branching.

Proposition 1. Assume two commercials j and l. Job j cannot be processed before job l on machine i if the following condition is satisfied, where $j, l\in {J}^{c}$, j≠l

Proof. This proposition is easy to prove. If job j satisfies this inequality, then selecting job l before job j on machine i does not increase the value C_j and L_max. Therefore, scheduling job j at the current position on machine i is not an optimal schedule. The proposition follows.

From Proposition 1, it is not necessary to consider every node generated from the branching process. If job j is scheduled before job l and satisfies Eq (1), the node should be eliminated rather than branched.

3.3.   The proposed branching and bound algorithm

In this section, we develop a branch and bound algorithm, which follows the branching and bounding schemes stated above. In the branch and bound tree, the root node has no commercials scheduled. The upper and lower bounds of the root node are obtained by applying the procedures of the upper and lower bounding, respectively. During the branching process, each other node in the tree is generated when there is a commercial that is unscheduled. Each node has at most m commercials scheduled during the available advertising breaks on m TV channels. If Proposition 1 is satisfied, the node is eliminated. According to the branching process, the upper and lower bounds can also be used to eliminate nodes that are not an optimal solution. Each iteration of the algorithm can obtain a partial schedule with at most m commercials on m TV channels. The node is then checked and new nodes are generated by performing the branching scheme and the upper and lower bounding procedures. In the following, we propose a branch and bound algorithm for solving the problem optimally.

3.3.1.   The proposed branch and bound algorithm

Step 0: Initialization

0.1) Set q = 0; r(i) = 1 and M(i) = False, for $i\in A$.

0.2) Create a root node, root of the search tree.

● Set ${J}_{root} = \left\{\right\}$ and ${J}_{root}^{c} = \left\{\mathrm{1, 2}, \dots, n\right\}$.

● Calculate the upper bound $\overline{UB}\left(root\right)$ and ${L}_{max}\left(root\right)$ for commercials in ${J}_{root}^{c}$ by the LFJ/EDD rule algorithm.

Set $UB = \overline{UB}\left(root\right) = {L}_{max}\left(root\right)$.

● Calculate the lower bound$\underline{LB}\left(root\right)$ by the two-phase binary search algorithm.

If $\underline{LB}\left(root\right) = UB$, then stop the algorithm and output the optimal schedule.

0.3) Set node $\mathrm{\alpha } = root$ node.

Step 1: If ${J}_{\alpha }^{c}\ne \varnothing$, then branch out child nodes of node $\mathrm{\alpha }$and set q = q + 1.

If $\left|{J}_{\alpha }^{c}\right| < m$, then take $(m-\left|{J}_{\alpha }^{c}\right|)$ artificial commercials into set ${J}_{\alpha }^{c}$.

Create a child node $\mathrm{\beta }$ for each combination of m commercials in ${J}_{\alpha }^{c}$ and put these m commercials into sequence ${J}_{\beta }^{}$.

1.1) For $i\in A$, let $\left[{b}_{i}^{r\left(i\right)}, {f}_{i}^{r\left(i\right)}\right]$ be an advertising break with service level k and commercial j in the ith position of sequence${J}_{\beta }^{}$.

● If M(i) = True, then remove commercial j in the ith position of${J}_{\beta }^{}$and replace it with artificial commercial X.

● If Proposition 1 is satisfied, then remove node $\mathrm{\beta }$.

1.2) Set ${J}_{\beta }^{c} = {J}_{\alpha }^{c}\backslash \left\{{J}_{\beta }\right\}$; ${L}_{max}\left(\beta \right) = {L}_{max}\left(\alpha \right)$; ${ACTIVE}_{\beta } = False$.

1.3) For $i\in A$, let commercial j be scheduled in the ith position of sequence ${J}_{\beta }^{}$.

● Set ${t}_{j} = max\left\{{r}_{j}, {b}_{i}^{r\left(i\right)}\right\}$ and ${C}_{j} = max\left\{{r}_{j}, {b}_{i}^{r\left(i\right)}\right\}+{p}_{j}$;

If ${L}_{max}\left(\beta \right) < {C}_{j}-{d}_{j}$, then set ${L}_{max}\left(\beta \right) = {C}_{j}-{d}_{j}$.

If ${L}_{max}\left(\beta \right)\ge UB$, then remove node $\mathrm{\beta }$.

● Update the advertising break set of node $\mathrm{\beta }$.

If ${C}_{j} = {f}_{i}^{r\left(i\right)}$, set ${f}_{i}^{r\left(i\right)} = {t}_{j}$ and r(i) = r(i) + 1.

Else If ${b}_{i}^{r\left(i\right)} = {t}_{j}$, set ${b}_{i}^{r\left(i\right)} = {C}_{j}$.

Otherwise,

● Set $\left[{b}_{i}^{\alpha +1}, {f}_{i}^{\alpha +1}\right] = \left[{b}_{i}^{\alpha }, {f}_{i}^{\alpha }\right]$ for $\mathrm{\alpha }$ = r(i) + 1, …, N(i).

● $N\left(i\right) = N\left(i\right)+1$.

● Set ${b}_{i}^{r\left(i\right)+1} = {C}_{j}$; ${f}_{i}^{r\left(i\right)+1} = {f}_{i}^{r\left(i\right)}$; ${f}_{i}^{r\left(i\right)} = {t}_{j}$.

● Set $r\left(i\right) = r\left(i\right)+1$.

While ${(f}_{i}^{r\left(i\right)}-{b}_{i}^{r\left(i\right)}) < {p}_{j}$ and $r\left(i\right)\le N\left(i\right)$, for all $j\in {J}_{\beta }^{c}\cap {R}_{k}$,

do $r\left(i\right) = r\left(i\right)+1$;

if $\left(i\right) = N\left(i\right)$, then set M(i) = True.

1.4) Calculate the lower bound and the upper bound of node $\mathrm{\beta }$.

● Calculate the upper bound $\overline{UB}\left(\beta \right)$ by the LFJ/EDD rule algorithm.

If $\overline{UB}\left(\beta \right)\le UB$, then set $UB = \overline{UB}\left(\beta \right)$.

● Calculate the lower bound $\underline{LB}\left(\beta \right)$ by the two-phase binary search algorithm.

If $\underline{LB}\left(\beta \right) > UB$, then remove node $\mathrm{\beta }$.

Step 2: If $q\ne 0$, then select the node with the lowest lower bound and its ${ACTIVE}_{\alpha } = false$s at level q.

2.1) Set node $\mathrm{\alpha } =$ selected node; ${ACTIVE}_{\alpha } = True$, go to Step 1.

2.2) If no node with $Active = False$ exists at level q, then set q = q − 1 and repeat Step 2.

Otherwise, stop the algorithm and output the optimal schedule.

4.   Computational analysis

Here, we discuss a computational analysis for the proposed branch and bound algorithm. To conduct the evaluation of the proposed algorithm, we code the branch and bound algorithm in Visual C++ and test it on a number of randomly generated problems. The computational experiments are run on a PC Intel Core(TM) i5-4570 3.2 GHz with 4 GB RAM. The test instances are generated according to the following scheme. We select the values of parameters based on the information that we observe from TV stations in Taiwan. A TV station has three to eight different channels to broadcast different types of TV programs. In the given planning horizon, which is usually an hour, there are four to eight advertising breaks that can air commercials. Each advertising break has a length $\left[{b}_{i}^{r}, {f}_{i}^{r}\right]$ between 50 to 70 s and is categorized according to the higher, average, and lower TV rating points. Therefore, each advertising break is classified into the three types of service levels. For each commercial, the processing time p_j is set to 5, 10, 15, 20, 25 or 30 s, and a specific service-level requirement to be broadcasted is applied.

We set $n\in \left\{\mathrm{5, 10, 20, 30, 40}\right\}$, $m\in \left\{\mathrm{3, 5}, 8\right\}$, ${r}_{max} = 3000$, ${p}_{max} = 6$, ${rs}_{max} = 3$, ${l}_{max} = 600$, and ${l}_{min} = 50$. For each job j, the release time r_j, processing time p_j, due date d_j, and required service level rs_j are randomly drawn from uniform distributions on the intervals $[0, {r}_{max}]$, $\left[1, {p}_{max}\right]\times 5$, $\left[0, {r}_{max}+600\right]+{r}_{j}+{p}_{j}$, and$\left[1, {rs}_{max}\right]$, respectively. Each TV station is capable of processing job j with a probability equal to 0.5. For each TV channel i, the number of advertising breaks $N\left(i\right)$ is randomly drawn from the discrete uniform distribution ^[4,8]. For each advertising break r on TV channel i, the start time ${b}_{i}^{r}$ and end time ${f}_{i}^{r}$, as well as the service level ${rs}_{i}^{r}$, are generated as follows.

● ${b}_{i}^{1}$ is randomly drawn from the uniform distribution $\left[0, {l}_{max}\right]$;

● ${b}_{i}^{r}$ is randomly drawn from the uniform distribution $\left[0, {l}_{max}\right]+{f}_{i}^{r-1}$, $r\in F$;

● ${f}_{i}^{r}$ is randomly drawn from the uniform distribution $\left[{l}_{min}, 70\right]+{b}_{i}^{r}$, $r\in F$.

● ${rs}_{i}^{r}$ is randomly drawn from the uniform distribution $\left[1, {rs}_{max}\right]$, $i\in A$ and $r\in F$.

In total, there are 20 test instances for each combination of n and m tested. The computational results are presented in Table 2. The columns labelled Max. (Min.) indicate the maximum (minimum) number of nodes created and the maximum (minimum) computational time among the test instances, respectively. The columns labelled "Average" give the average number of nodes created and the average computational time, respectively. From Table 2, we can obtain optimal solutions using the branch and bound algorithm for the problem size of 40 commercials and eight TV channels within a moderate CPU time. The larger the problem size, the more nodes created, and the more computational time will be required.

5.   Conclusions

In this paper, we presented an exact branch and bound algorithm to find an optimal solution for scheduling TV commercials to minimize the maximum lateness. The branch and bound algorithm incorporates the LFJ and EDD rules to find feasible schedules as upper bounds and lower bounds based on an algorithm that combines a binary search and a network flow technique for pruning nodes. In the studied problem, commercials had service-level constraints and processing times and could not be split at any point in time. This problem is more general than the scheduling problem discussed in ^[20] and ^[21]. A large number of nodes can be eliminated by upper and lower bounds, and only a very small percentage of potential nodes are generated. The branch and bound algorithm can be used to solve the problem optimally for up to 40 commercials and eight TV channels.

Acknowledgments

The author is grateful for the financial support from the Ministry of Science and Technology in Taiwan under grant 108-2622-E-025-001-CC3 and from National Taichung University of Science and Technology under grant NTCUST110-19.

Conflict of interest

The author declares that there are no conflicts of interest regarding the publication of this paper.