計程車廣告系統之排程與允入控制設計

Scheduling and Admission Control for Taxi Advertising System

盧柏亨(Bo-Heng Lu)

指導教授 ： 林一平 ； 逄愛君

國立交通大學/資訊學院/網路工程研究所/碩士(2015年)

https://doi.org/10.6842/NCTU.2015.00946

摘要

多媒體廣告行銷已成為許多企業一大收入來源，計程車廣告系統的設計可以使廣告系統營運商(operators)更有效的管理系統容量(system capacity)，本論文希望經由設計排程演算法，提升系統容量利用率，並增加廣告系統營運商的潛在收益。對於廣告系統營運商而言，每一筆廣告訂單都代表一項由廣告提供者(advertisement providers) 來的收益，為了幫助廣告系統營運商決定是否可接收新進廣告訂單，我們必須先了解系統整體有多少容量，進而設計排程機制。本論文的目的是要在不影響已接受訂單的前提下，確保新接受訂單可播放完成。針對以上議題，本論文將分為兩個部分：(i)系統容量預測；以及(ii)訂單排程與允入控制方法設計。系統容量預測部分，基於大數定律 (Law of Large Number ; LLN)， 我們設計四個方法比較預測與實際系統容量誤差；訂單排程與允入控制方法設計部分，本論文提出三個排程方法相互比較。結果顯示區分星期有助增加預測的精準度，且預測時間上，單看前一個月的結果準確性較高，而排程與允入控制部分，比例分配方法較天平均次方法有更佳的訂單接受度與系統容量利用率。

關鍵字

系統容量預測 ； 廣告排程 ； 允入控制

並列摘要

Multimedia advertising provides a large proportion of income for many enterprises. The operators of advertising systems can manage system capacity using advanced taxi advertising systems. This study sought to enhance the utilization of system capacity by developing a job-scheduling algorithm for operators. From the operator’s perspective, every advertising job represents income from advertisement providers; however, determining whether a new advertising job should be accepted requires that the availability of system capacity be evaluated in order to plan a job-scheduling scheme. The objective of the proposed algorithm is to ensure that new advertising jobs can be completed without affecting the delivery of current advertising jobs. The proposed algorithm is based on (i) prediction and (ii) admission control and scheduling. Based on the “Law of Large Number” (LLN), we developed four means of comparing errors between predicted and actual system capacity. Three methods were also developed to deal with admissions control and scheduling. Experiment results show that weekly information is an important factor in prediction accuracy, and the data related to the previous month is useful. The method involving the “Proportional Allocation” (PA) outperformed the “Average Count by Day” (ACD) method with regard to the utilization of system capacity and the acceptance of advertising jobs.

並列關鍵字

system capacity prediction ； advertisements scheduling ； admission control

參考文獻

[2] (2014)Facebook, “Facebook Reports Fourth Quarter and Full Year 2014 Results,”. [Online]. Available: http://investor.fb.com/releasedetail.cfm?ReleaseID=893395

[7] Zhang, Wenfeng, Zhongke Shi, and Qin Liu. "Research on the Prediction of Urban Passenger Transport based on Support Vector Machine." Automation and Logistics, 2007 IEEE International Conference on. IEEE, 2007.

[8] Chen, Xiaogang. "Railway Passenger Volume Forecasting Based on Support Vector Machine and Genetic Algorithm." Future Computer and Communication, 2009. FCC'09. International Conference on. IEEE, 2009

[9] Moridpour, Sara, et al. "A genetic algorithm-based support vector machine for bus travel time prediction." Transportation Information and Safety (ICTIS), 2015 International Conference on. IEEE, 2015.

[12] Jia, Qiong, and Yoonho Seo. "An improved particle swarm optimization for the resource-constrained project scheduling problem." The International Journal of Advanced Manufacturing Technology 67.9-12 (2013): 2627-2638.