具k限制式服務策略之循環服務系統最佳化

Optimization of the Cyclic Service Systems with k-limited Service Discipline

陳炯文(Chiung-wen Chen)

指導教授 ： 洪士程

朝陽科技大學/資訊學院/資訊工程系/碩士(2010年)

摘要

在本論文中提出了一個混合演算法，結合以序列最佳化理論為基礎的演算法以及粒子群最佳化的演算法，目的是為了用來在有限的計算時間之內，找出一個擁有龐大搜尋空間的隨機模擬最佳化問題(SSOP)的足夠好的解，並應用此混合演算法來解決G/G/1/K循環服務系統與k-限制式服務策略的最佳化問題；以到達率在短時間內惡化的情況不明顯做為前提，我們將提出的方法採用兩個階段方式來進行。在第一個階段我們採用了粒子群最佳化演算法，首先以一個粗略的模型即使用少量的測試樣本做隨機模擬，用來做為粒子群最佳化的適應函數值評估標準，藉此由龐大的離散解答的空間中，挑選出排名較好的N個粗略好的解決方案。在第二階段的部分則包括了若干的子階段，由先前獲得的N個粗略好的解中，挑選出評估足夠好的解決辦法，而在最後的子階段獲得的最佳解，即為我們所尋找的足夠好的解。將本篇論文所提出的演算法應用在採用k-限制式服務策略的G/G/1/K循環服務系統，結果顯示藉由提出的演算法，來獲得k-限制式服務策略中足夠好的變數，在解答品質和計算效率的表現方面是大有可為的。

關鍵字

序列最佳化 ； 粒子群最佳化 ； 循環服務 ； k-限制式 ； 足夠好的解

並列摘要

In this dissertation, a hybrid algorithm of particle swarm optimization and ordinal optimization is proposed to solve for a good enough solution of the stochastic simulation optimization problem (SSOP) with huge search space using reasonable computation time. We applied the proposed algorithm to a G/G/1/K cyclic service system with k-limited service discipline. We assume that the arrival rates do not deteriorate visibly within a very short period. Our approach consists of two stages. In the first stage, we employ a particle swarm optimization algorithm to select N roughly good solutions from the huge discrete solution space Ω with a small amount of test samples. The second stage consists of several substages to select estimated good enough solutions from the previous N, and the solution obtained in the last substage is the good enough solution that we seek. The vector of good enough k-limited service discipline with G/G/1/K cyclic service system obtained by the proposed algorithm is promising in the aspects of solution quality and computational efficiency.

並列關鍵字

good enough solution ； cyclic service ； k-limited ； particle swarm optimization ； ordinal optimization

參考文獻

[1] H. Takagi, "Queuing Analysis of polling model," ACM computing surveys, Vol. 20, No.1, pp. 5-28, Mar., 1988.

[2] H. Levy, and M. Sidi, “Polling systems: applications, modeling, and optimization,” IEEE Transactions on Communications, Vol. 38, No. 10, pp.1750-1760, Oct., 1990.

[4] I. Eliazar, “Gated Polling Systems with Levy Inflow and Inter-Dependent Switchover Times: A Dynamical-Systems Approach,” Queueing Systems, Vol. 49, No. 1., pp. 49-72, Jan., 2005.

[5] K. K. Leung, “Cyclic-service systems with nonpreemptive, time-limited service,” IEEE Transactions on Communications, Vol. 42, No. 8, pp. 2521-2524, Aug., 1994X.

[6] Vishnevskii, V.M., Semenova, O.V.: Mathematical methods to study the polling systems. Autom. Remote Control 67(2), 173–220 (2006).