多重類型顧客在串聯佇列中的排程問題

Abstract

我們針對一個開放式的網路系統做最佳化的處理，而此網路是由一串聯佇列所組成，其中第一個佇列有兩種類型（類型0與類型1）的顧客進入，其餘的每個佇列都會有一種與其他佇列不同類型的顧客光臨，它們依照佇列順序分為類型2、3、4、…、m。每個佇列中只有一個服務員，並且服務的時間都是固定且相同的。在這篇論文中，我們的目的是對上述的網路求最小的期望存貨成本，但由於網路中的總人數與成本是成正比例的，所以在處理上，我們改以求最小的期望人數。在方法上，則藉由線性規劃的方式。並且我們發現到假如第二個佇列中的顧客人數大於所觀察的期數減一時，即(n-1)，則最好的策略處理原則是選取類型0的顧客到第一個佇列中做服務，以達到我們期望成木最小的目的。

We deal with the optimal scheduling in an open queueing network a serip of queues in tandem with multi-class customers. Each queue is associated with only one server where all service times are constant and equal. The objective of this paper is to minimize the expected total discounted holding cost over a finite horizon n. Since the holding cost is proportional to the total numbe of customers in the network, we consider minimizing the expected number of customers over n horizons. By Linear Programming arguments we show that an optimal policy gives priority to class-0 customers at node 1 if the number of customers in queue 2 is larger than n-1.