Java實現排隊論的原理

引入：

前段時間去銀行辦業務，排隊的人那是真多，自己正式辦理業務也就不到5分鐘，但是卻足足等了兩個小時（相信很多人都遇到過這種情況），對這種服務水平真的是無語了，但是問題又來了，銀行應該開幾個窗口，既能保證整體的服務質量，又能保證資源資源的利用率呢？下面我們就通過排隊論來模擬這個問題。

排隊論簡介

排隊論是研究系統隨機聚散現象和隨機系統工作工程的數學理論和方法，又稱隨機服務系統理論，為運籌學的一個分支。我們下面對排隊論做下簡化處理，先看下圖：

我們在圖的左側安排若干個藍色服務台，右側為可能會過來的紅色顧客，中間為黃色的等候區，如果有服務台處於空閒狀態，顧客可以直接去接受服務，否則就要在黃色區域等候，顧客服務的順序採用先到現服務的原則，現在如果我們知道顧客過來的概率分佈，那麼我們在左側安排幾個服務台既能達到更好的服務水平，又能保證服務台的使用率？下面我們就構建模型來模擬這個問題。

排隊論分步實現

1）對於排隊論，我們首先要確定顧客屬性，知道顧客什麼時候到達，需要的服務耗時等，我們首先創建一個顧客類，在這裡我們指定了顧客服務的最大、最小時間，這裡我們為了簡化就直接認為服務時間完全隨機：

 public class CustomerBean { //最小服務時間private static int minServeTime = 3 * 1000; //最大服務時間private static int maxServeTime = 15 * 1000; //顧客達到時間private long arriveTime; //顧客需要服務耗時private int serveTime; public CustomerBean() { //設置到達時間arriveTime = System.currentTimeMillis(); //隨機設置顧客的服務時間serveTime = (int) (Math.random() * (maxServeTime - minServeTime) + minServeTime); } }

2）上面我們定義了顧客，緊接著就需要定義一個排隊隊列，我們先看下隊列的屬性，這裡我們定義一個數組，用它來保存排隊的顧客，定義下一個顧客到來的最小、最大時間間隔以及顧客來不來的概率（這裡簡單說明下，如果下一個顧客的間隔時間是3，但是通過概率計算並為滿足，則這個顧客不進入隊列，這樣設置的原因是盡可能的使顧客達到有很大的隨機性）和隊列中最大的排隊人數。

 public class CustomerQuene { //等待顧客隊列private LinkedList<CustomerBean> customers = new LinkedList<CustomerBean>(); //下一個顧客過來最短時間private int minTime = 0; //下一個顧客過來最大時間private int maxTime = 1 * 1000; //來顧客的概率private double rate = 0.9; //標識是否繼續產生顧客private boolean flag = true; //最大排隊人數private int maxWaitNum = 0; }

3）顧客和排隊的隊列都有了，我們就設置一個產生顧客的線程，讓它不斷的產生顧客，這裡就有我們上面說的時間和概率分佈。

 /** *@Description: 生成顧客線程*@Version:1.1.0 */ private class CustomerThread extends Thread { private CustomerThread(String name) { super(name); } @Override public void run() { while (flag) { //隊尾添加一個新顧客if (Math.random() < rate) { customers.addLast(new CustomerBean()); if (maxWaitNum < customers.size()) { maxWaitNum = customers.size(); } } int sleepTime = (int) (Math.random() * (maxTime - minTime) + minTime); try { TimeUnit.MILLISECONDS.sleep(sleepTime); } catch (Exception e) { e.printStackTrace(); } } } }

4）如果隊列中有顧客排隊切有空閒的服務台，就需要獲取隊頭的顧客去接受服務

public synchronized CustomerBean getCustomerBean() { if (customers == null || customers.size() < 1) { return null; } return customers.removeFirst(); }

5）顧客相關的屬性和方法都已經準備好，下面就設置下服務台相關的屬性，這裡我們直接把服務台設置成線程，定義一些服務指標，如服務的顧客數目、總等待時間、總服務時間、最大等待時間等。

 public class ServantThread extends Thread{ //服務顧客數目private static int customerNum = 0; //總等待時間private static int sumWaitTime = 0; //總服務時間private static int sumServeTime = 0; //最大等待時間private static int maxWaitTime = 0; private boolean flag = false; private String name; }

6）服務台最主要的工作就是服務顧客，這裡我們把服務顧客相關的操作寫到線程的run方法中。

 public void run() { flag = true; while (flag) { CustomerBean customer = CustomerQuene.getCustomerQuene().getCustomerBean(); //如果顧客線程已經關閉且隊列中沒有顧客，服務台線程關閉釋放if (customer == null) { if (!CustomerQuene.getCustomerQuene().isFlag()) { flag = false; print(); } continue; } long now = System.currentTimeMillis(); int waitTime = (int) (now - customer.getArriveTime()); //保存最大的等待時間if (waitTime > maxWaitTime) { maxWaitTime = waitTime; } //睡眠時間為顧客的服務時間，代表這段時間在服務顧客try { TimeUnit.MILLISECONDS.sleep(customer.getServeTime()); } catch (Exception e) { e.printStackTrace(); } System.err.println(name + " 服務顧客耗時：" + customer.getServeTime() + "ms/t顧客等待：" + waitTime + "ms"); customerNum++; sumWaitTime += waitTime; sumServeTime += customer.getServeTime(); } }

7）最後我們編寫一個測試模型，來驗證服務水平

/** *@Description: */ package com.lulei.opsearch.quene; import java.util.concurrent.TimeUnit; public class Test { public static void main(String[] args) { //開門System.out.println("開門接客啦！"); boolean flag = true; CustomerQuene.getCustomerQuene(); long a = System.currentTimeMillis(); int servantNum = 10; for (int i = 0; i < servantNum; i++) { ServantThread thread = new ServantThread("服務台" + i); thread.start(); } while (flag) { long b = System.currentTimeMillis(); if (b - a > 1 * 60 * 1000 && flag) { //關門flag = false; CustomerQuene.getCustomerQuene().close(); System.out.println("關門不接客啦！"); } System.out.println("系統運行時間：" + (b -a) + "ms"); System.out.println("系統空閒時間：" + ((b -a) * servantNum - ServantThread.getSumServeTime())); ServantThread.print(); try { TimeUnit.SECONDS.sleep(2); } catch (Exception e) { e.printStackTrace(); } } } }

運行結果
1）運行開始

2）顧客產生線程關閉

3）最後服務水平

通過修改服務台的個數就可以評估在當前的顧客情況下應該設置幾個服務台。

完整代碼

1）顧客類

/** *@Description: */ package com.lulei.opsearch.quene; public class CustomerBean { //最小服務時間private static int minServeTime = 3 * 1000; //最大服務時間private static int maxServeTime = 15 * 1000; //顧客達到時間private long arriveTime; //顧客需要服務耗時private int serveTime; public CustomerBean() { //設置到達時間arriveTime = System.currentTimeMillis(); //隨機設置顧客的服務時間serveTime = (int) (Math.random() * (maxServeTime - minServeTime) + minServeTime); } public static int getMinServeTime() { return minServeTime; } public static void setMinServeTime(int minServeTime) { CustomerBean.minServeTime = minServeTime; } public static int getMaxServeTime() { return maxServeTime; } public static void setMaxServeTime(int maxServeTime) { CustomerBean.maxServeTime = maxServeTime; } public long getArriveTime() { return arriveTime; } public void setArriveTime(long arriveTime) { this.arriveTime = arriveTime; } public int getServeTime() { return serveTime; } public void setServeTime(int serveTime) { this.serveTime = serveTime; } }

2）顧客隊列

/** *@Description: */ package com.lulei.opsearch.quene; import java.util.LinkedList; import java.util.concurrent.TimeUnit; public class CustomerQuene { //等待顧客隊列private LinkedList<CustomerBean> customers = new LinkedList<CustomerBean>(); //下一個顧客過來最短時間private int minTime = 0; //下一個顧客過來最大時間private int maxTime = 1 * 1000; //來顧客的概率private double rate = 0.9; //標識是否繼續產生顧客private boolean flag = true; //最大排隊人數private int maxWaitNum = 0; public int getMaxWaitNum() { return maxWaitNum; } public boolean isFlag() { return flag; } /** * @return * @Author:lulei * @Description: 獲取排在隊頭的顧客*/ public synchronized CustomerBean getCustomerBean() { if (customers == null || customers.size() < 1) { return null; } return customers.removeFirst(); } public void close() { if (flag) { flag = false; } } /** * @return * @Author:lulei * @Description: 獲取等待顧客數量*/ public int getWaitCustomerNum() { return customers.size(); } /** *@Description: 生成顧客線程*@Version:1.1.0 */ private class CustomerThread extends Thread { private CustomerThread(String name) { super(name); } @Override public void run() { while (flag) { //隊尾添加一個新顧客if (Math.random() < rate) { customers.addLast(new CustomerBean()); if (maxWaitNum < customers.size()) { maxWaitNum = customers.size(); } } int sleepTime = (int) (Math.random() * (maxTime - minTime) + minTime); try { TimeUnit.MILLISECONDS.sleep(sleepTime); } catch (Exception e) { e.printStackTrace(); } } } } //單例模式開始private static class CustomerQueneDao { private static CustomerQuene customerQuene = new CustomerQuene(); } private CustomerQuene() { CustomerThread customerThread = new CustomerThread("顧客產生線程"); customerThread.start(); } public static CustomerQuene getCustomerQuene() { return CustomerQueneDao.customerQuene; } //單例模式結束public int getMinTime() { return minTime; } public void setMinTime(int minTime) { this.minTime = minTime; } public int getMaxTime() { return maxTime; } public void setMaxTime(int maxTime) { this.maxTime = maxTime; } public double getRate() { return rate; } public void setRate(double rate) { this.rate = rate; } }

3）服務台線程

/** *@Description: */ package com.lulei.opsearch.quene; import java.util.concurrent.TimeUnit; import com.lulei.util.ParseUtil; public class ServantThread extends Thread{ //服務顧客數目private static int customerNum = 0; //總等待時間private static int sumWaitTime = 0; //總服務時間private static int sumServeTime = 0; //最大等待時間private static int maxWaitTime = 0; private boolean flag = false; private String name; public ServantThread(String name) { super(name); this.name = name; } public static int getMaxWaitTime() { return maxWaitTime; } public static int getSumServeTime() { return sumServeTime; } @Override public void run() { flag = true; while (flag) { CustomerBean customer = CustomerQuene.getCustomerQuene().getCustomerBean(); //如果顧客線程已經關閉且隊列中沒有顧客，服務台線程關閉釋放if (customer == null) { if (!CustomerQuene.getCustomerQuene().isFlag()) { flag = false; print(); } continue; } long now = System.currentTimeMillis(); int waitTime = (int) (now - customer.getArriveTime()); //保存最大的等待時間if (waitTime > maxWaitTime) { maxWaitTime = waitTime; } //睡眠時間為顧客的服務時間，代表這段時間在服務顧客try { TimeUnit.MILLISECONDS.sleep(customer.getServeTime()); } catch (Exception e) { e.printStackTrace(); } System.err.println(name + " 服務顧客耗時：" + customer.getServeTime() + "ms/t顧客等待：" + waitTime + "ms"); customerNum++; sumWaitTime += waitTime; sumServeTime += customer.getServeTime(); } } public static void print() { if (customerNum > 0) { System.out.println("--------------------------------------"); System.out.println("服務顧客數目：" + customerNum); System.out.println("最大等待時間：" + maxWaitTime); System.out.println("等待顧客數目：" + CustomerQuene.getCustomerQuene().getWaitCustomerNum()); System.out.println("最大等待顧客數目：" + CustomerQuene.getCustomerQuene().getMaxWaitNum()); //輸出顧客平均等待時間，保留兩位小數System.out.println("顧客平均等待時間：" + ParseUtil.parseDoubleToDouble((sumWaitTime * 1.0 / customerNum), 2) + "ms"); System.out.println("顧客平均服務時間：" + ParseUtil.parseDoubleToDouble((sumServeTime * 1.0 / customerNum), 2) + "ms"); System.out.println("系統總服務時間：" + sumServeTime + "ms"); } } }

4）測試模型

/** *@Description: */ package com.lulei.opsearch.quene; import java.util.concurrent.TimeUnit; public class Test { public static void main(String[] args) { //開門System.out.println("開門接客啦！"); boolean flag = true; CustomerQuene.getCustomerQuene(); long a = System.currentTimeMillis(); int servantNum = 10; for (int i = 0; i < servantNum; i++) { ServantThread thread = new ServantThread("服務台" + i); thread.start(); } while (flag) { long b = System.currentTimeMillis(); if (b - a > 1 * 60 * 1000 && flag) { //關門flag = false; CustomerQuene.getCustomerQuene().close(); System.out.println("關門不接客啦！"); } System.out.println("系統運行時間：" + (b -a) + "ms"); System.out.println("系統空閒時間：" + ((b -a) * servantNum - ServantThread.getSumServeTime())); ServantThread.print(); try { TimeUnit.SECONDS.sleep(2); } catch (Exception e) { e.printStackTrace(); } } } }

以上就是關於Java實現排隊論的原理詳細介紹，希望對大家的學習有所幫助。