Introduced:
Some time ago, I went to the bank to handle business, and there were so many people in line. It took less than 5 minutes to handle business by myself, but I waited for two hours (I believe many people have encountered this situation). I was speechless about this service level, but the problem arises again. The bank should open several windows to ensure the overall service quality and the utilization rate of resources? Next, we will simulate this problem through queue theory.
Introduction to the queue theory
Queuing theory is a mathematical theory and method that studies the phenomenon of random gathering and dispersion of systems and the working engineering of random systems. It is also known as the theory of random service systems, and is a branch of operations research. Let’s simplify the queueing theory below, and look at the following figure first:
We arrange several blue service desks on the left side of the picture, with red customers who may come over on the right, and a yellow waiting area in the middle. If a service desk is idle, customers can directly receive services, otherwise they have to wait in the yellow area. The order of customer service adopts the principle of first-come and current service. Now if we know the probability distribution of customers coming, then how can we arrange several service desks on the left to achieve a better service level and ensure the usage rate of the service desk? Next, we will build a model to simulate this problem.
Queuing theory is implemented step by step
1) For the queuing theory, we first need to determine the customer attributes, know when the customer arrives, the service time required, etc. We first create a customer class, where we specify the maximum and minimum time for customer service. Here, in order to simplify, we directly think that the service time is completely random:
public class CustomerBean { //Minimum service time private static int minServeTime = 3 * 1000; //Maximum service time private static int maxServeTime = 15 * 1000; //Customer reaches time private long arriveTime; //Customer needs service time private int serveTime; public CustomerBean() { //Set arrival time arrivalTime = System.currentTimeMillis(); //Random set customer service time serveTime = (int) (Math.random() * (maxServeTime - minServeTime) + minServeTime); } } 2) We define the customer above, and then we need to define a queue queue. Let’s first look at the attributes of the queue. Here we define an array to save the queued customers, define the minimum and maximum time intervals for the next customer to arrive and the probability of the customer coming (to be briefly explained here, if the interval time of the next customer is 3, but it is calculated through the probability and satisfied, the customer will not enter the queue. The reason for this setting is to make the customer reach a great randomness as much as possible) and the maximum number of people in the queue.
public class CustomerQuene { //Waiting for customer queue private LinkedList<CustomerBean> customers = new LinkedList<CustomerBean>(); //The shortest time for next customer to come private int minTime = 0; //The maximum time for next customer to come private int maxTime = 1 * 1000; //The probability of coming customers private double rate = 0.9; //Identify whether the customer private boolean flag = true; //The maximum number of people queuing private int maxWaitNum = 0; } 3) When there are customers and queues, we set up a thread to generate customers to continuously generate customers. Here are the time and probability distributions we mentioned above.
/** *@Description: Generate customer thread*@Version:1.1.0 */ private class CustomerThread extends Thread { private CustomerThread(String name) { super(name); } @Override public void run() { while (flag) { //Add a new customer at the end of the team 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) If there are customers in the queue queuing to cut in the free service desk, you need to get the customer in the head of the team to receive the service.
public synchronized CustomerBean getCustomerBean() { if (customers == null || customers.size() < 1) { return null; } return customers.removeFirst(); } 5) Customer-related attributes and methods are all ready. Let’s set the service desk related attributes. Here we directly set the service desk to a thread to define some service indicators, such as the number of customers served, the total waiting time, the total service time, the maximum waiting time, etc.
public class ServantThread extends Thread{ //Number of service customers private static int customerNum = 0; //Total waiting time private static int sumWaitTime = 0; //Total service time private static int sumServeTime = 0; //Maximum waiting time private static int maxWaitTime = 0; private boolean flag = false; private String name; } 6) The main job of the service desk is to serve customers. Here we write operations related to serving customers into the run method of the thread.
public void run() { flag = true; while (flag) { CustomerBean customer = CustomerQuene.getCustomerQuene().getCustomerBean(); //If the customer thread has been closed and there are no customers in the queue, the service desk thread closes and releases if (customer == null) { if (!CustomerQuene.getCustomerQuene().isFlag()) { flag = false; print(); } continue; } long now = System.currentTimeMillis(); int waitTime = (int) (now - customer.getArriveTime()); //Save the maximum waiting time if (waitTime > maxWaitTime) { maxWaitTime = waitTime; } //Sleep time is the customer's service time, which represents the service period during this period of time serving customers. Try { TimeUnit.MILLISECONDS.sleep(customer.getServeTime()); } catch (Exception e) { e.printStackTrace(); } System.err.println(name + " Time to serve customers: " + customer.getServeServeTime() + "ms/t Customer waiting: " + waitTime + "ms"); customerNum++; sumWaitTime += waitTime; sumServeTime += customer.getServeTime(); } } 7) Finally, we write a test model to verify the service level
/** *@Description: */ package com.lulei.opsearch.quene; import java.util.concurrent.TimeUnit; public class Test { public static void main(String[] args) { //Open the door System.out.println("Open the door and pick up the customers!"); boolean flag = true; CustomerQuene.getCustomerQuene(); long a = System.currentTimeMillis(); int serviceNum = 10; for (int i = 0; i < serviceNum; i++) { ServantThread thread = new ServantThread("Service Desk" + i); thread.start(); } while (flag) { long b = System.currentTimeMillis(); if (b - a > 1 * 60 * 1000 && flag) { //Close flag = false; CustomerQuene.getCustomerQuene().close(); System.out.println("Close the door and don't pick up customers!"); } System.out.println("System running time: " + (b -a) + "ms"); System.out.println("System idle time: " + ((b -a) * servantNum - ServantThread.getSumServeTime())); ServantThread.print(); try { TimeUnit.SECONDS.sleep(2); } catch (Exception e) { e.printStackTrace(); } } } } Running results
1) Start of operation
2) Customer generates thread closing
3) Final service level
By modifying the number of service desks, you can evaluate how many service desks should be set up in the current customer situation.
Complete code
1) Customer category
/** *@Description: */ package com.lulei.opsearch.quene; public class CustomerBean { //Minimum service time private static int minServeTime = 3 * 1000; //Maximum service time private static int maxServeTime = 15 * 1000; //Customer reaches time private long arriveTime; //Customer needs service time private int serveTime; public CustomerBean() { //Set arrival time arriveTime = System.currentTimeMillis(); //Randomly set customer service time 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) Customer queue
/** *@Description: */ package com.lulei.opsearch.quene; import java.util.LinkedList; import java.util.concurrent.TimeUnit; public class CustomerQuene { //Waiting for customer queue private LinkedList<CustomerBean> customers = new LinkedList<CustomerBean>(); //The shortest time for next customer to come private int minTime = 0; //The maximum time for next customer to come private int maxTime = 1 * 1000; //The probability of coming customer private double rate = 0.9; //Identify whether customers continue to generate private boolean flag = true; //Maximum number of people queued private int maxWaitNum = 0; public int getMaxWaitNum() { return maxWaitNum; } public boolean isFlag() { return flag; } /** * @return * @Author:lulei * @Description: Get the customer in the head of the queue*/ 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: Get the number of waiting customers*/ public int getWaitCustomerNum() { return customers.size(); } /** *@Description: Generate customer thread*@Version:1.1.0 */ private class CustomerThread extends Thread { private CustomerThread(String name) { super(name); } @Override public void run() { while (flag) { //Add a new customer at the end of the team 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(); } } } } } //Singleton mode start private static class CustomerQueneDao { private static CustomerQuene customerQuene = new CustomerQuene(); } private CustomerQuene() { CustomerThread customerThread = new CustomerThread("Customer Generation Thread"); customerThread.start(); } public static CustomerQuene getCustomerQuene() { return CustomerQueneDao.customerQuene; } //Singleton mode end 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) Service desk thread
/** *@Description: */ package com.lulei.opsearch.quene; import java.util.concurrent.TimeUnit; import com.lulei.util.ParseUtil; public class ServantThread extends Thread{ //Number of service customers private static int customerNum = 0; //Total waiting time private static int sumWaitTime = 0; //Total service time private static int sumServeTime = 0; //Maximum waiting time 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 the customer thread has been closed and there are no customers in the queue, the service desk thread closes and releases if (customer == null) { if (!CustomerQuene.getCustomerQuene().isFlag()) { flag = false; print(); } continue; } long now = System.currentTimeMillis(); int waitTime = (int) (now - customer.getArriveTime()); //Save the maximum waiting time if (waitTime > maxWaitTime) { maxWaitTime = waitTime; } //Sleep time is the customer's service time, which represents the customer's try { TimeUnit.MILLISECONDS.sleep(customer.getServeTime()); } catch (Exception e) { e.printStackTrace(); } System.err.println(name + " Time to serve customers: " + customer.getServeTime() + "ms/t Customer waiting: " + waitTime + "ms"); customerNum++; sumWaitTime += waitTime; sumServeTime += customer.getServeTime(); } } public static void print() { if (customerNum > 0) { System.out.println("---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- //Output the average wait time of the customer, and retain two decimal places System.out.println("Average wait time for customers: " + ParseUtil.parseDoubleToDouble((sumWaitTime * 1.0 / customerNum), 2) + "ms"); System.out.println("Average service time for customers: " + ParseUtil.parseDoubleToDouble((sumServeTime * 1.0 / customerNum), 2) + "ms"); System.out.println("Total service time for systems: " + sumServeTime + "ms"); } } } 4) Test the model
/** *@Description: */ package com.lulei.opsearch.quene; import java.util.concurrent.TimeUnit; public class Test { public static void main(String[] args) { //Open the door System.out.println("Open the door and pick up the customers!"); boolean flag = true; CustomerQuene.getCustomerQuene(); long a = System.currentTimeMillis(); int serviceNum = 10; for (int i = 0; i < serviceNum; i++) { ServantThread thread = new ServantThread("Service Desk" + i); thread.start(); } while (flag) { long b = System.currentTimeMillis(); if (b - a > 1 * 60 * 1000 && flag) { //Close flag = false; CustomerQuene.getCustomerQuene().close(); System.out.println("Close the door and don't pick up customers!"); } System.out.println("System running time: " + (b -a) + "ms"); System.out.println("System idle time: " + ((b -a) * servantNum - ServantThread.getSumServeTime())); ServantThread.print(); try { TimeUnit.SECONDS.sleep(2); } catch (Exception e) { e.printStackTrace(); } } } }The above is a detailed introduction to the principles of Java implementing queueing theory. I hope it will be helpful to everyone's learning.