A branch and bound algorithm for optimal television commercial scheduling
In the current era of multimedia, television (TV) plays an important role in transmitting advertising messages. In addition, advertising is the primary source of revenue for the TV industry. Thus, a critical issue for TV stations is the scheduling of commercials in suitable advertising breaks on dif...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2022-03-01
|
| Series: | Mathematical Biosciences and Engineering |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/mbe.2022231?viewType=HTML |
| _version_ | 1818775816939503616 |
|---|---|
| author | Lu-Wen Liao |
| author_facet | Lu-Wen Liao |
| author_sort | Lu-Wen Liao |
| collection | DOAJ |
| description | In the current era of multimedia, television (TV) plays an important role in transmitting advertising messages. In addition, advertising is the primary source of revenue for the TV industry. Thus, a critical issue for TV stations is the scheduling of commercials in suitable advertising breaks on different TV channels to maximize revenue and minimize penalties. This type of TV commercial scheduling problem is similar to the machine scheduling problem, and both have availability constraints. However, the literature on TV commercial scheduling has not considered this perspective. Motivated by this, we consider the problem of scheduling commercials with specific service-level requirements on TV channels while minimizing the maximum lateness. The lateness of a commercial is defined to be its completion time minus its due date, and the maximum lateness is the maximum value of lateness among all commercials. We propose an exact branch and bound algorithm based on the LFJ (least flexible job first)/EDD (earliest due date first) rules and network flow methods, which were developed to solve the machine scheduling problem with availability constraints. Computational analysis shows that the bounding scheme proposed is highly effective, and a very low percentage of nodes is generated by the branch and bound algorithm. The algorithm can obtain an optimal solution for the problem. |
| first_indexed | 2024-12-18T11:03:03Z |
| format | Article |
| id | doaj.art-d82b144a0a844eaf85f81fd91e2f2cf8 |
| institution | Directory Open Access Journal |
| issn | 1551-0018 |
| language | English |
| last_indexed | 2024-12-18T11:03:03Z |
| publishDate | 2022-03-01 |
| publisher | AIMS Press |
| record_format | Article |
| series | Mathematical Biosciences and Engineering |
| spelling | doaj.art-d82b144a0a844eaf85f81fd91e2f2cf82022-12-21T21:10:11ZengAIMS PressMathematical Biosciences and Engineering1551-00182022-03-011954933494510.3934/mbe.2022231A branch and bound algorithm for optimal television commercial schedulingLu-Wen Liao0Department of Intelligent Production Engineering, National Taichung University of Science and Technology, Taichung 40401, TaiwanIn the current era of multimedia, television (TV) plays an important role in transmitting advertising messages. In addition, advertising is the primary source of revenue for the TV industry. Thus, a critical issue for TV stations is the scheduling of commercials in suitable advertising breaks on different TV channels to maximize revenue and minimize penalties. This type of TV commercial scheduling problem is similar to the machine scheduling problem, and both have availability constraints. However, the literature on TV commercial scheduling has not considered this perspective. Motivated by this, we consider the problem of scheduling commercials with specific service-level requirements on TV channels while minimizing the maximum lateness. The lateness of a commercial is defined to be its completion time minus its due date, and the maximum lateness is the maximum value of lateness among all commercials. We propose an exact branch and bound algorithm based on the LFJ (least flexible job first)/EDD (earliest due date first) rules and network flow methods, which were developed to solve the machine scheduling problem with availability constraints. Computational analysis shows that the bounding scheme proposed is highly effective, and a very low percentage of nodes is generated by the branch and bound algorithm. The algorithm can obtain an optimal solution for the problem.https://www.aimspress.com/article/doi/10.3934/mbe.2022231?viewType=HTMLtv commercialsservice level requirementschedulinglfj/edd rulebranch and bound algorithm |
| spellingShingle | Lu-Wen Liao A branch and bound algorithm for optimal television commercial scheduling Mathematical Biosciences and Engineering tv commercials service level requirement scheduling lfj/edd rule branch and bound algorithm |
| title | A branch and bound algorithm for optimal television commercial scheduling |
| title_full | A branch and bound algorithm for optimal television commercial scheduling |
| title_fullStr | A branch and bound algorithm for optimal television commercial scheduling |
| title_full_unstemmed | A branch and bound algorithm for optimal television commercial scheduling |
| title_short | A branch and bound algorithm for optimal television commercial scheduling |
| title_sort | branch and bound algorithm for optimal television commercial scheduling |
| topic | tv commercials service level requirement scheduling lfj/edd rule branch and bound algorithm |
| url | https://www.aimspress.com/article/doi/10.3934/mbe.2022231?viewType=HTML |
| work_keys_str_mv | AT luwenliao abranchandboundalgorithmforoptimaltelevisioncommercialscheduling AT luwenliao branchandboundalgorithmforoptimaltelevisioncommercialscheduling |