引入：
前段時(shí)間去銀行辦業(yè)務(wù)，排隊(duì)的人那是真多，自己正式辦理業(yè)務(wù)也就不到5分鐘，但是卻足足等了兩個(gè)小時(shí)（相信很多人都遇到過(guò)這種情況），對(duì)這種服務(wù)水平真的是無(wú)語(yǔ)了，但是問(wèn)題又來(lái)了，銀行應(yīng)該開(kāi)幾個(gè)窗口，既能保證整體的服務(wù)質(zhì)量，又能保證資源資源的利用率呢？下面我們就通過(guò)排隊(duì)論來(lái)模擬這個(gè)問(wèn)題。
排隊(duì)論簡(jiǎn)介
排隊(duì)論是研究系統(tǒng)隨機(jī)聚散現(xiàn)象和隨機(jī)系統(tǒng)工作工程的數(shù)學(xué)理論和方法，又稱(chēng)隨機(jī)服務(wù)系統(tǒng)理論，為運(yùn)籌學(xué)的一個(gè)分支。我們下面對(duì)排隊(duì)論做下簡(jiǎn)化處理，先看下圖：
我們?cè)趫D的左側(cè)安排若干個(gè)藍(lán)色服務(wù)臺(tái)，右側(cè)為可能會(huì)過(guò)來(lái)的紅色顧客，中間為黃色的等候區(qū)，如果有服務(wù)臺(tái)處于空閑狀態(tài)，顧客可以直接去接受服務(wù)，否則就要在黃色區(qū)域等候，顧客服務(wù)的順序采用先到現(xiàn)服務(wù)的原則，現(xiàn)在如果我們知道顧客過(guò)來(lái)的概率分布，那么我們?cè)谧髠?cè)安排幾個(gè)服務(wù)臺(tái)既能達(dá)到更好的服務(wù)水平，又能保證服務(wù)臺(tái)的使用率？下面我們就構(gòu)建模型來(lái)模擬這個(gè)問(wèn)題。
排隊(duì)論分步實(shí)現(xiàn)
1）對(duì)于排隊(duì)論，我們首先要確定顧客屬性，知道顧客什么時(shí)候到達(dá)，需要的服務(wù)耗時(shí)等，我們首先創(chuàng)建一個(gè)顧客類(lèi)，在這里我們指定了顧客服務(wù)的最大、最小時(shí)間，這里我們?yōu)榱撕?jiǎn)化就直接認(rèn)為服務(wù)時(shí)間完全隨機(jī)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class CustomerBean { //最小服務(wù)時(shí)間 private static int minServeTime = 3 * 1000; //最大服務(wù)時(shí)間 private static int maxServeTime = 15 * 1000; //顧客達(dá)到時(shí)間 private long arriveTime; //顧客需要服務(wù)耗時(shí) private int serveTime; public CustomerBean() { //設(shè)置到達(dá)時(shí)間 arriveTime = System.currentTimeMillis(); //隨機(jī)設(shè)置顧客的服務(wù)時(shí)間 serveTime = (int) (Math.random() * (maxServeTime - minServeTime) + minServeTime); } } |
2）上面我們定義了顧客，緊接著就需要定義一個(gè)排隊(duì)隊(duì)列，我們先看下隊(duì)列的屬性，這里我們定義一個(gè)數(shù)組，用它來(lái)保存排隊(duì)的顧客，定義下一個(gè)顧客到來(lái)的最小、最大時(shí)間間隔以及顧客來(lái)不來(lái)的概率（這里簡(jiǎn)單說(shuō)明下，如果下一個(gè)顧客的間隔時(shí)間是3，但是通過(guò)概率計(jì)算并為滿(mǎn)足，則這個(gè)顧客不進(jìn)入隊(duì)列，這樣設(shè)置的原因是盡可能的使顧客達(dá)到有很大的隨機(jī)性）和隊(duì)列中最大的排隊(duì)人數(shù)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public class CustomerQuene { //等待顧客隊(duì)列 private LinkedList<CustomerBean> customers = new LinkedList<CustomerBean>(); //下一個(gè)顧客過(guò)來(lái)最短時(shí)間 private int minTime = 0; //下一個(gè)顧客過(guò)來(lái)最大時(shí)間 private int maxTime = 1 * 1000; //來(lái)顧客的概率 private double rate = 0.9; //標(biāo)識(shí)是否繼續(xù)產(chǎn)生顧客 private boolean flag = true; //最大排隊(duì)人數(shù) private int maxWaitNum = 0; } |
3）顧客和排隊(duì)的隊(duì)列都有了，我們就設(shè)置一個(gè)產(chǎn)生顧客的線程，讓它不斷的產(chǎn)生顧客，這里就有我們上面說(shuō)的時(shí)間和概率分布。
|
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) { //隊(duì)尾添加一個(gè)新顧客 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ù)臺(tái)，就需要獲取隊(duì)頭的顧客去接受服務(wù)
|
1
2
3
4
5
6
|
public synchronized CustomerBean getCustomerBean() { if (customers == null || customers.size() < 1) { return null; } return customers.removeFirst(); } |
5）顧客相關(guān)的屬性和方法都已經(jīng)準(zhǔn)備好，下面就設(shè)置下服務(wù)臺(tái)相關(guān)的屬性，這里我們直接把服務(wù)臺(tái)設(shè)置成線程，定義一些服務(wù)指標(biāo)，如服務(wù)的顧客數(shù)目、總等待時(shí)間、總服務(wù)時(shí)間、最大等待時(shí)間等。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public class ServantThread extends Thread{ //服務(wù)顧客數(shù)目 private static int customerNum = 0; //總等待時(shí)間 private static int sumWaitTime = 0; //總服務(wù)時(shí)間 private static int sumServeTime = 0; //最大等待時(shí)間 private static int maxWaitTime = 0; private boolean flag = false; private String name; } |
6）服務(wù)臺(tái)最主要的工作就是服務(wù)顧客，這里我們把服務(wù)顧客相關(guān)的操作寫(xiě)到線程的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(); //如果顧客線程已經(jīng)關(guān)閉且隊(duì)列中沒(méi)有顧客，服務(wù)臺(tái)線程關(guān)閉釋放 if (customer == null) { if (!CustomerQuene.getCustomerQuene().isFlag()) { flag = false; print(); } continue; } long now = System.currentTimeMillis(); int waitTime = (int) (now - customer.getArriveTime()); //保存最大的等待時(shí)間 if (waitTime > maxWaitTime) { maxWaitTime = waitTime; } //睡眠時(shí)間為顧客的服務(wù)時(shí)間，代表這段時(shí)間在服務(wù)顧客 try { TimeUnit.MILLISECONDS.sleep(customer.getServeTime()); } catch (Exception e) { e.printStackTrace(); } System.err.println(name + " 服務(wù)顧客耗時(shí)：" + customer.getServeTime() + "ms\t顧客等待：" + waitTime + "ms"); customerNum++; sumWaitTime += waitTime; sumServeTime += customer.getServeTime(); } } |
7）最后我們編寫(xiě)一個(gè)測(cè)試模型，來(lái)驗(yàn)證服務(wù)水平
|
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) { //開(kāi)門(mén) System.out.println("開(kāi)門(mén)接客啦！"); boolean flag = true; CustomerQuene.getCustomerQuene(); long a = System.currentTimeMillis(); int servantNum = 10; for (int i = 0; i < servantNum; i++) { ServantThread thread = new ServantThread("服務(wù)臺(tái)" + i); thread.start(); } while (flag) { long b = System.currentTimeMillis(); if (b - a > 1 * 60 * 1000 && flag) { //關(guān)門(mén) flag = false; CustomerQuene.getCustomerQuene().close(); System.out.println("關(guān)門(mén)不接客啦！"); } System.out.println("系統(tǒng)運(yùn)行時(shí)間：" + (b -a) + "ms"); System.out.println("系統(tǒng)空閑時(shí)間：" + ((b -a) * servantNum - ServantThread.getSumServeTime())); ServantThread.print(); try { TimeUnit.SECONDS.sleep(2); } catch (Exception e) { e.printStackTrace(); } } } } |
運(yùn)行結(jié)果
1）運(yùn)行開(kāi)始
2）顧客產(chǎn)生線程關(guān)閉
3）最后服務(wù)水平
通過(guò)修改服務(wù)臺(tái)的個(gè)數(shù)就可以評(píng)估在當(dāng)前的顧客情況下應(yīng)該設(shè)置幾個(gè)服務(wù)臺(tái)。
完整代碼
1）顧客類(lèi)
|
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 { //最小服務(wù)時(shí)間 private static int minServeTime = 3 * 1000; //最大服務(wù)時(shí)間 private static int maxServeTime = 15 * 1000; //顧客達(dá)到時(shí)間 private long arriveTime; //顧客需要服務(wù)耗時(shí) private int serveTime; public CustomerBean() { //設(shè)置到達(dá)時(shí)間 arriveTime = System.currentTimeMillis(); //隨機(jī)設(shè)置顧客的服務(wù)時(shí)間 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ì)列
|
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 { //等待顧客隊(duì)列 private LinkedList<CustomerBean> customers = new LinkedList<CustomerBean>(); //下一個(gè)顧客過(guò)來(lái)最短時(shí)間 private int minTime = 0; //下一個(gè)顧客過(guò)來(lái)最大時(shí)間 private int maxTime = 1 * 1000; //來(lái)顧客的概率 private double rate = 0.9; //標(biāo)識(shí)是否繼續(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ì)尾添加一個(gè)新顧客 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(); } } } } //單例模式開(kāi)始 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ù)臺(tái)線程
|
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{ //服務(wù)顧客數(shù)目 private static int customerNum = 0; //總等待時(shí)間 private static int sumWaitTime = 0; //總服務(wù)時(shí)間 private static int sumServeTime = 0; //最大等待時(shí)間 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ì)列中沒(méi)有顧客，服務(wù)臺(tái)線程關(guān)閉釋放 if (customer == null) { if (!CustomerQuene.getCustomerQuene().isFlag()) { flag = false; print(); } continue; } long now = System.currentTimeMillis(); int waitTime = (int) (now - customer.getArriveTime()); //保存最大的等待時(shí)間 if (waitTime > maxWaitTime) { maxWaitTime = waitTime; } //睡眠時(shí)間為顧客的服務(wù)時(shí)間，代表這段時(shí)間在服務(wù)顧客 try { TimeUnit.MILLISECONDS.sleep(customer.getServeTime()); } catch (Exception e) { e.printStackTrace(); } System.err.println(name + " 服務(wù)顧客耗時(shí)：" + 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("最大等待時(shí)間：" + maxWaitTime); System.out.println("等待顧客數(shù)目：" + CustomerQuene.getCustomerQuene().getWaitCustomerNum()); System.out.println("最大等待顧客數(shù)目：" + CustomerQuene.getCustomerQuene().getMaxWaitNum()); //輸出顧客平均等待時(shí)間，保留兩位小數(shù) System.out.println("顧客平均等待時(shí)間：" + ParseUtil.parseDoubleToDouble((sumWaitTime * 1.0 / customerNum), 2) + "ms"); System.out.println("顧客平均服務(wù)時(shí)間：" + ParseUtil.parseDoubleToDouble((sumServeTime * 1.0 / customerNum), 2) + "ms"); System.out.println("系統(tǒng)總服務(wù)時(shí)間：" + sumServeTime + "ms"); } } } |
4）測(cè)試模型
|
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) { //開(kāi)門(mén) System.out.println("開(kāi)門(mén)接客啦！"); boolean flag = true; CustomerQuene.getCustomerQuene(); long a = System.currentTimeMillis(); int servantNum = 10; for (int i = 0; i < servantNum; i++) { ServantThread thread = new ServantThread("服務(wù)臺(tái)" + i); thread.start(); } while (flag) { long b = System.currentTimeMillis(); if (b - a > 1 * 60 * 1000 && flag) { //關(guān)門(mén) flag = false; CustomerQuene.getCustomerQuene().close(); System.out.println("關(guān)門(mén)不接客啦！"); } System.out.println("系統(tǒng)運(yùn)行時(shí)間：" + (b -a) + "ms"); System.out.println("系統(tǒng)空閑時(shí)間：" + ((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ì)介紹，希望對(duì)大家的學(xué)習(xí)有所幫助。
