引入：
前段時間去銀行辦業務，排隊的人那是真多，自己正式辦理業務也就不到5分鐘，但是卻足足等了兩個小時（相信很多人都遇到過這種情況），對這種服務水平真的是無語了，但是問題又來了，銀行應該開幾個窗口，既能保證整體的服務質量，又能保證資源資源的利用率呢？下面我們就通過排隊論來模擬這個問題。
排隊論簡介
排隊論是研究系統隨機聚散現象和隨機系統工作工程的數學理論和方法，又稱隨機服務系統理論，為運籌學的一個分支。我們下面對排隊論做下簡化處理，先看下圖：
我們在圖的左側安排若干個藍色服務臺，右側為可能會過來的紅色顧客，中間為黃色的等候區，如果有服務臺處于空閑狀態，顧客可以直接去接受服務，否則就要在黃色區域等候，顧客服務的順序采用先到現服務的原則，現在如果我們知道顧客過來的概率分布，那么我們在左側安排幾個服務臺既能達到更好的服務水平，又能保證服務臺的使用率？下面我們就構建模型來模擬這個問題。
排隊論分步實現
1）對于排隊論，我們首先要確定顧客屬性，知道顧客什么時候到達，需要的服務耗時等，我們首先創建一個顧客類，在這里我們指定了顧客服務的最大、最小時間，這里我們為了簡化就直接認為服務時間完全隨機：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
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，但是通過概率計算并為滿足，則這個顧客不進入隊列，這樣設置的原因是盡可能的使顧客達到有很大的隨機性）和隊列中最大的排隊人數。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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）顧客和排隊的隊列都有了，我們就設置一個產生顧客的線程，讓它不斷的產生顧客，這里就有我們上面說的時間和概率分布。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
/** *@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）如果隊列中有顧客排隊切有空閑的服務臺，就需要獲取隊頭的顧客去接受服務
|
1
2
3
4
5
6
|
public synchronized CustomerBean getCustomerBean() { if (customers == null || customers.size() < 1) { return null; } return customers.removeFirst(); } |
5）顧客相關的屬性和方法都已經準備好，下面就設置下服務臺相關的屬性，這里我們直接把服務臺設置成線程，定義一些服務指標，如服務的顧客數目、總等待時間、總服務時間、最大等待時間等。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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方法中。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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）最后我們編寫一個測試模型，來驗證服務水平
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
/** *@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）顧客類
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
/** *@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）顧客隊列
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
/** *@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）服務臺線程
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
/** *@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）測試模型
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
/** *@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實現排隊論的原理詳細介紹，希望對大家的學習有所幫助。
