Analysis of Server Scheduling in Multi-Class Single-Server Queueing System

Analysis of Server Scheduling in Multi-Class Single-Server Queueing System

周明蓉(Ming-Jung Chou)

指導教授 ： 葉丁鴻

國立中正大學/管理學院/企業管理學系/碩士(2014年)

摘要

本論文主要探討多類別、單一服務者的等候系統，該等候系統中考慮兩種類別的顧客，彼此獨立且遵從卜瓦松分配。等候系統的服務機制如下: 服務者必須等到到達的顧客總人數等於固定的服務批量時，才開始啟動服務; 而且所有顧客是以整批服務的方式，其服務時間遵從指數分配。該等候系統實際應用領域如大眾運輸系統，包括：循環巴士系統、鐵路運輸系統等。
論文中包括兩部分：一、我們透過平衡方程組，求解該等候系統的穩態機率分配；二、我們建構該等候系統的成本模型，其中包括顧客的等候成本與服務者的服務成本，並利用該成本模型找出等候系統的最佳服務批量。

關鍵字

服務排程 ； 單一服務者 ； 多類別 ； 成本模型

並列摘要

In this thesis we consider a multi-class single-server queueing system, in which there are two types of customers with independent Poisson arrivals. Customers arrive at the system must wait for the service, and the single-server starts its service when the number of customer arrived is equal to the fixed-size service capacity. All customers are served in a batch by the single-server with exponential service times. Typical examples of the queueing system considered include public transportation service systems such as: shuttle bus transit system, railway transportation system, etc.
The objective of this thesis is to solve the server scheduling problem for the queueing system considered in this thesis. There are two parts in this thesis: first, we use balance equations to derive the steady-state probabilities for the queueing system; second, we develop a cost model to find the optimal fixed-size service capacity in order to minimize the total system cost including the waiting cost of customers and service cost of the single-server.

並列關鍵字

Server scheduling ； Single-server ； Multi-class ； Cost model

參考文獻

Deb, R. K., & Schmidt, C. P. (1987). Optimal average cost policies for the two-terminal shuttle. Management Science, 33(5), 662-669

Liu, Y., & Wang, Z. (2013). A simple policy for multiple queues with size-independent service times. Operations Research Letters, 41(5), 535-539.

Newell, G. F. (1971). Dispatching policies for a transportation route. Transportation Science, 5(1), 91-105.

Salzborn, F. J. (1972). Optimum bus scheduling. Transportation Science, (2), 137-148.

Sakuma, Y., & Inoie, A. (2012). Stationary distribution of a multi-server vacation queue with constant impatient times. Operations Research Letters, 40(4), 239-243.