Java實(shí)現(xiàn)排隊(duì)論的原理

更新時間：2016年02月01日 17:02:38 作者：xiaojimanman

這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)排隊(duì)論的原理，對排隊(duì)論感興趣的小伙伴們可以參考一下

引入：

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

排隊(duì)論簡介

排隊(duì)論是研究系統(tǒng)隨機(jī)聚散現(xiàn)象和隨機(jī)系統(tǒng)工作工程的數(shù)學(xué)理論和方法，又稱隨機(jī)服務(wù)系統(tǒng)理論，為運(yùn)籌學(xué)的一個分支。我們下面對排隊(duì)論做下簡化處理，先看下圖：

我們在圖的左側(cè)安排若干個藍(lán)色服務(wù)臺，右側(cè)為可能會過來的紅色顧客，中間為黃色的等候區(qū)，如果有服務(wù)臺處于空閑狀態(tài)，顧客可以直接去接受服務(wù)，否則就要在黃色區(qū)域等候，顧客服務(wù)的順序采用先到現(xiàn)服務(wù)的原則，現(xiàn)在如果我們知道顧客過來的概率分布，那么我們在左側(cè)安排幾個服務(wù)臺既能達(dá)到更好的服務(wù)水平，又能保證服務(wù)臺的使用率？下面我們就構(gòu)建模型來模擬這個問題。

排隊(duì)論分步實(shí)現(xiàn)

1）對于排隊(duì)論，我們首先要確定顧客屬性，知道顧客什么時候到達(dá)，需要的服務(wù)耗時等，我們首先創(chuàng)建一個顧客類，在這里我們指定了顧客服務(wù)的最大、最小時間，這里我們?yōu)榱撕喕椭苯诱J(rèn)為服務(wù)時間完全隨機(jī)：

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

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

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

3）顧客和排隊(duì)的隊(duì)列都有了，我們就設(shè)置一個產(chǎn)生顧客的線程，讓它不斷的產(chǎn)生顧客，這里就有我們上面說的時間和概率分布。

/** 
 *@Description: 生成顧客線程 
 *@Version:1.1.0 
 */ 
private class CustomerThread extends Thread { 
 private CustomerThread(String name) { 
  super(name); 
 } 
 
 @Override 
 public void run() { 
  while (flag) { 
   //隊(duì)尾添加一個新顧客 
   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）如果隊(duì)列中有顧客排隊(duì)切有空閑的服務(wù)臺，就需要獲取隊(duì)頭的顧客去接受服務(wù)

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

5）顧客相關(guān)的屬性和方法都已經(jīng)準(zhǔn)備好，下面就設(shè)置下服務(wù)臺相關(guān)的屬性，這里我們直接把服務(wù)臺設(shè)置成線程，定義一些服務(wù)指標(biāo)，如服務(wù)的顧客數(shù)目、總等待時間、總服務(wù)時間、最大等待時間等。

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

6）服務(wù)臺最主要的工作就是服務(wù)顧客，這里我們把服務(wù)顧客相關(guān)的操作寫到線程的run方法中。

public void run() { 
 flag = true; 
 while (flag) { 
  CustomerBean customer = CustomerQuene.getCustomerQuene().getCustomerBean(); 
  //如果顧客線程已經(jīng)關(guān)閉且隊(duì)列中沒有顧客，服務(wù)臺線程關(guān)閉釋放 
  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; 
  } 
  //睡眠時間為顧客的服務(wù)時間，代表這段時間在服務(wù)顧客 
  try { 
   TimeUnit.MILLISECONDS.sleep(customer.getServeTime()); 
  } catch (Exception e) { 
   e.printStackTrace(); 
  } 
  System.err.println(name + " 服務(wù)顧客耗時：" + customer.getServeTime() + "ms\t顧客等待：" + waitTime + "ms"); 
  customerNum++; 
  sumWaitTime += waitTime; 
  sumServeTime += customer.getServeTime(); 
   
 } 
}

7）最后我們編寫一個測試模型，來驗(yàn)證服務(wù)水平

 /** 
 *@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("服務(wù)臺" + i); 
   thread.start(); 
  } 
  while (flag) { 
   long b = System.currentTimeMillis(); 
   if (b - a > 1 * 60 * 1000 && flag) { 
    //關(guān)門 
    flag = false; 
    CustomerQuene.getCustomerQuene().close(); 
    System.out.println("關(guān)門不接客啦！"); 
   } 
   System.out.println("系統(tǒng)運(yùn)行時間：" + (b -a) + "ms"); 
   System.out.println("系統(tǒng)空閑時間：" + ((b -a) * servantNum - ServantThread.getSumServeTime())); 
   ServantThread.print(); 
   try { 
    TimeUnit.SECONDS.sleep(2); 
   } catch (Exception e) { 
    e.printStackTrace(); 
   } 
  } 
 } 
 
}

運(yùn)行結(jié)果
1）運(yùn)行開始

2）顧客產(chǎn)生線程關(guān)閉

3）最后服務(wù)水平

通過修改服務(wù)臺的個數(shù)就可以評估在當(dāng)前的顧客情況下應(yīng)該設(shè)置幾個服務(wù)臺。

完整代碼

1）顧客類

 /** 
 *@Description:  
 */ 
package com.lulei.opsearch.quene; 
 
public class CustomerBean { 
 //最小服務(wù)時間 
 private static int minServeTime = 3 * 1000; 
 //最大服務(wù)時間 
 private static int maxServeTime = 15 * 1000; 
 //顧客達(dá)到時間 
 private long arriveTime; 
 //顧客需要服務(wù)耗時 
 private int serveTime; 
  
 public CustomerBean() { 
  //設(shè)置到達(dá)時間 
  arriveTime = System.currentTimeMillis(); 
  //隨機(jī)設(shè)置顧客的服務(wù)時間 
  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）顧客隊(duì)列

 /** 
 *@Description:  
 */ 
package com.lulei.opsearch.quene; 
 
import java.util.LinkedList; 
import java.util.concurrent.TimeUnit; 
 
public class CustomerQuene { 
 //等待顧客隊(duì)列 
 private LinkedList<CustomerBean> customers = new LinkedList<CustomerBean>(); 
 //下一個顧客過來最短時間 
 private int minTime = 0; 
 //下一個顧客過來最大時間 
 private int maxTime = 1 * 1000; 
 //來顧客的概率 
 private double rate = 0.9; 
 //標(biāo)識是否繼續(xù)產(chǎn)生顧客 
 private boolean flag = true; 
 //最大排隊(duì)人數(shù) 
 private int maxWaitNum = 0; 
  
 public int getMaxWaitNum() { 
  return maxWaitNum; 
 } 
  
 public boolean isFlag() { 
  return flag; 
 } 
 
 /** 
  * @return 
  * @Author:lulei 
  * @Description: 獲取排在隊(duì)頭的顧客 
  */ 
 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: 獲取等待顧客數(shù)量 
  */ 
 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) { 
    //隊(duì)尾添加一個新顧客 
    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("顧客產(chǎn)生線程"); 
  customerThread.start(); 
 } 
 public static CustomerQuene getCustomerQuene() { 
  return CustomerQueneDao.customerQuene; 
 } 
 //單例模式結(jié)束 
  
 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）服務(wù)臺線程

 /** 
 *@Description:  
 */ 
package com.lulei.opsearch.quene; 
 
import java.util.concurrent.TimeUnit; 
 
import com.lulei.util.ParseUtil; 
 
public class ServantThread extends Thread{ 
 //服務(wù)顧客數(shù)目 
 private static int customerNum = 0; 
 //總等待時間 
 private static int sumWaitTime = 0; 
 //總服務(wù)時間 
 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(); 
   //如果顧客線程已經(jīng)關(guān)閉且隊(duì)列中沒有顧客，服務(wù)臺線程關(guān)閉釋放 
   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; 
   } 
   //睡眠時間為顧客的服務(wù)時間，代表這段時間在服務(wù)顧客 
   try { 
    TimeUnit.MILLISECONDS.sleep(customer.getServeTime()); 
   } catch (Exception e) { 
    e.printStackTrace(); 
   } 
   System.err.println(name + " 服務(wù)顧客耗時：" + 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("服務(wù)顧客數(shù)目：" + customerNum); 
   System.out.println("最大等待時間：" + maxWaitTime); 
   System.out.println("等待顧客數(shù)目：" + CustomerQuene.getCustomerQuene().getWaitCustomerNum()); 
   System.out.println("最大等待顧客數(shù)目：" + CustomerQuene.getCustomerQuene().getMaxWaitNum()); 
   //輸出顧客平均等待時間，保留兩位小數(shù) 
   System.out.println("顧客平均等待時間：" + ParseUtil.parseDoubleToDouble((sumWaitTime * 1.0 / customerNum), 2) + "ms"); 
   System.out.println("顧客平均服務(wù)時間：" + ParseUtil.parseDoubleToDouble((sumServeTime * 1.0 / customerNum), 2) + "ms"); 
   System.out.println("系統(tǒng)總服務(wù)時間：" + 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("服務(wù)臺" + i); 
   thread.start(); 
  } 
  while (flag) { 
   long b = System.currentTimeMillis(); 
   if (b - a > 1 * 60 * 1000 && flag) { 
    //關(guān)門 
    flag = false; 
    CustomerQuene.getCustomerQuene().close(); 
    System.out.println("關(guān)門不接客啦！"); 
   } 
   System.out.println("系統(tǒng)運(yùn)行時間：" + (b -a) + "ms"); 
   System.out.println("系統(tǒng)空閑時間：" + ((b -a) * servantNum - ServantThread.getSumServeTime())); 
   ServantThread.print(); 
   try { 
    TimeUnit.SECONDS.sleep(2); 
   } catch (Exception e) { 
    e.printStackTrace(); 
   } 
  } 
 } 
 
}

以上就是關(guān)于Java實(shí)現(xiàn)排隊(duì)論的原理詳細(xì)介紹，希望對大家的學(xué)習(xí)有所幫助。

您可能感興趣的文章: