座席指派資訊系統

A Seat Assignment Information System

林志餘(Lin, Chih-Yu)

指導教授 ： 方鄒昭聰 ； 詹景裕

國立臺北大學/商學院/資訊管理研究所/碩士(2010年)

摘要

有效率的座席指派策略是火車訂票系統在面臨全球化競爭必要的條件，本文提出一種快速且可將團體購票的車票指派至相鄰座席的演算法，靈感來自Hashimoto和 Steven提出的左端點演算法(Left-Edge Algorithm, LEA)，傳統的左端點演算法僅可指派出最少座席，而本演算法利用多維度的Buckets不僅保有原來LEA之優點，更將LEA的時間複雜度由O(N log N)降低至O(N)以及增加團體票放置相鄰座位之功能。

關鍵字

通道指派 ； 桶狀資料結構 ； 火車座席管理系統 ； 左端點演算法

並列摘要

This article presents an optimal seat assignment algorithm with the minimal number of tracks, based on the famous Left-Edge Algorithm (LEA) and the data structure of hierarchical buckets. The time and space complexities are both O(N), where N is the number of tickets. Meanwhile, this algorithm can be applied to scheduling and channel assignment for Printed Circuit Boards (PCB) and Electronic Design Automation (EDA).

並列關鍵字

buckets ； channel assignment ； EDA ； Left-Edge Algorithm ； PCB ； scheduling

參考文獻

[1] D. Bozda, F. Ozgner, and U.V. Catalyurek, “Compac- tion of Schedules and a Two-Stage Approach for Duplication-Based DAG Scheduling,” IEEE Transac- tions on Parallel and Distributed Systems, vol. 20, no. 6, 2009, pp. 857-871.

[2] T. Chiueh, K. Gopalan, and A. Raniwala, “Centralized channel assignment and routing algorithms for multi- channel wireless mesh networks,” ACM SIGMO BILE Mobile Computing and Communications Review Archive, vol. 8, no. 2, 2004, pp. 50-65-

[3] R. Chavez-Santiago, E. Gigi and V. Lyandres, “Chan- nel assignment for cellular mobile networks with nonuni -form cells – an improved heuristic algorithm,” IEE Proceedings on communications, vol. 153, issue.1,2006, pp. 61-68.

[4] A.J. Goldsmith, and S.B. Wicker, “Design challenges for energy-constrained ad hoc wireless networks,” IEEE Wireless Communications, vol. 9, no. 4, 2002, pp. 8-27.

[5] A. Hashimoto, and J. Stevens, “Wire routing by optimizing channel assignment within large apertures,” Annual ACM/IEEE Design Automation Conference, Proceedings of the 8th Design Automation Workshop, 1971, pp. 155-169.