一种预估业务处理时间的排队处理系统及排队机调度方法

1.一种预估业务处理时间的排队处理系统，其特征在于：所述的预估业务处理时间的排队处理系统包括：
排队机装置，用于接收客户业务单据，读取单据数据以及打印排队号码条，所述的排队机装置上安装有条码扫描装置、排队号码条打印装置；
业务处理终端，所述业务处理终端上安装有业务单识别装置、客户叫号装置，用于服务人员对客户业务进行处理，记录各类业务处理时间，呼叫下一名客户；
业务处理服务器，用于管理排队队列，调用业务处理时间数据入库，预估业务处理时间，分配排队号码，调度排队队列，业务处理服务器包括：业务处理用时数据库，用于记录一段时期内各个业务处理用时记录；
业务处理用时预估模块，用于当客户向系统提交新业务时估计处理此业务需要消耗的时间；
排队队列管理模块，用于维护和管理待处理业务队列；
业务调度模块，用于从待处理业务队列中选择一项业务交给服务窗口处理；
网络连接装置，用于提供排队机装置、业务处理终端和业务处理服务器之间的数据通信连接。
2.一种采用权利要求1所述的预估业务处理时间的排队处理系统的排队机调度方法包括如下步骤：
（1）排队机装置接收客户提交的业务单据，每张业务单据上都印刷有业务分类条码，排队机装置能够根据业务分类条码提取到此业务对应的业务分类代码，通过网络连接装置将业务代码发送到业务处理服务器；
（2）业务处理服务器将接收到的新业务放入排队队列，并产生一个排队号码返回到排队机装置；
（3）排队机装置接收到排队号码后，打印排队号码条提交给客户；
（4）业务处理服务器根据新业务的业务分类代码，查询业务处理用时数据库，使用业务处理用时预估模块根据业务用时预估算法对新业务所需的处理时间进行预测；
（5）业务处理终端向业务处理服务器发出叫号请求，业务处理服务器调用业务调度模块，使用调度算法从排队队列中选择一项业务，将其排队号码反馈到业务处理终端，通过业务叫号装置播放叫号提示；
（6）业务处理终端处理完一项业务后，将此业务处理用时发送到业务处理服务器，存入业务处理用时数据库。
3.根据权利要求2所述的一种排队机调度方法，其特征在于：所述步骤（4）的业务用时预估算法为首先对业务进行分类，给每类业务分配一个业务分类代码，当一项业务处理完成时，将此业务处理用时记入业务处理用时数据库中，当一项新业务到达时，业务处理用时预估模块首先读取其业务分类代码，然后在业务处理用时数据库中检索近期此类业务的处理用时信息，使用如下公式估算新业务的处理用时： 其中 为预估的新业务处理时间， 为上次预估的业务处理时
间， 为最近一次此类业务的处理时间，α为平滑系数取值为0.125。
4.根据权利要求2所述的一种排队机调度方法，其特征在于：所述步骤（5）的业务调度算法为同时考虑每个业务的等待时间长短和估计需要的处理时间长短，从中选出响应比最高的作业投入执行，响应比R定义如下： 其中T为该业务估计需要的执
行时间，W为业务在排队队列中的等待时间,当业务处理终端可以接受新业务时，向业务处理服务器发出请求,业务处理服务器计算每个业务的响应比，选择其中响应比最大者，将其排队号码反馈给业务处理终端进行处理。

一种预估业务处理时间的排队处理系统及排队机调度方法\n技术领域\n[0001] 本发明涉及一种排队处理系统及其调度方法，特别是一种预估业务处理时间的排队处理系统及排队机调度方法。\n背景技术\n[0002] 在日常工作和生活中，办理业务时排队是非常普遍的现象。目前银行、电信、医院、政务等各类行业服务大厅普遍设置有排队机系统。即客户到达服务大厅后，先在排队机上取一个号码单。同时排队机将此号码送入排队队列及相关柜台，工作人员按照号码顺序叫号并轮流处理客户业务。使用排队机系统后，客户等候时可以在休息区休息，无需站在柜台前等待，提高了客户排队的舒适程度，并且可以防止出现插队现象。\n[0003] 但是目前的排队机系统在调度上存在以下问题，如：\n[0004] （1）未能减少客户平均等待时间。目前的排队系统调度方法采用的是先来先服务法，即处理顺序取决于客户取号的先后顺序。在实际情况中经常出现少量客户办理的业务工作量较大，占用工作人员大量的处理时间，而其他客户要办理的业务量较小，却不得不等待较长的时间。从整体上看，所有客户的平均等待时间较长。\n[0005] （2）未针对客户业务类型预估处理时间。目前的排队机系统通常不能估计每项业务的处理时间，导致客户取号后难以预计等待时间长度。客户估计等待时间较长时常常会选择在此时间段内离开服务大厅去处理其他工作，从而导致所取号码逾期作废。申请号为\n200710027670.2，名称为“一种智能排队叫号系统”的发明专利申请根据排队论方法预测客户等待时间，但并未针对客户业务类型进一步优化其预测算法。\n发明内容\n[0006] 为解决上述问题，本发明公开了一种预估业务处理时间的排队处理系统及排队机调度方法，能够判别客户业务类型，根据历史统计数据预测各类业务处理与等待时间，自动调整队列分配与顺序，达到降低客户平均等待时间的目的。\n[0007] 本发明公开的一种预估业务处理时间的排队处理系统包括：\n[0008] 排队机装置，用于接收客户业务单据，读取单据数据以及打印排队号码条；\n[0009] 业务处理终端，用于服务人员对客户业务进行处理，记录各类业务处理时间，呼叫下一名客户；\n[0010] 业务处理服务器，用于管理排队队列，调用业务处理时间数据入库，预估业务处理时间，分配排队号码，调度排队队列；\n[0011] 网络连接装置，用于提供排队机装置、业务处理终端和业务处理服务器之间的数据通信连接。\n[0012] 本发明公开的一种预估业务处理时间的排队处理系统的一种改进，所述的排队机装置上安装有条码扫描装置、排队号码条打印装置。\n[0013] 本发明公开的一种预估业务处理时间的排队处理系统的又一种改进，所述业务处理终端上安装有业务单识别装置、客户叫号装置。\n[0014] 本发明公开的一种预估业务处理时间的排队处理系统的又一种改进，所述业务处理服务器包括：\n[0015] 业务处理用时数据库，用于记录一段时期内各个业务处理用时记录；\n[0016] 业务处理用时预估模块，用于当客户向系统提交新业务时估计处理此业务需要消耗的时间；\n[0017] 排队队列管理模块，用于维护和管理待处理业务队列；\n[0018] 业务调度模块，用于从待处理业务队列中选择一项业务交给服务窗口处理。\n[0019] 一种排队机调度方法，包括如下步骤：\n[0020] （1）排队机装置接收客户提交的业务单据，每张业务单据上都印刷有业务分类条码，排队机装置能够根据业务分类条码提取到此业务对应的业务分类代码，通过网络连接装置将业务代码发送到业务处理服务器；\n[0021] （2）业务处理服务器将接收到的新业务放入排队队列，并产生一个排队号码返回到排队机装置；\n[0022] （3）排队机装置接收到排队号码后，打印排队号码条提交给客户；\n[0023] （4）业务处理服务器根据新业务的业务分类代码，查询业务处理用时数据库，使用业务处理用时预估模块根据业务用时预估算法对新业务所需的处理时间进行预测；\n[0024] （5）业务处理终端向业务处理服务器发出叫号请求，业务处理服务器调用业务调度模块，使用调度算法从排队队列中选择一项业务，将其排队号码反馈到业务处理终端，通过业务叫号装置播放叫号提示；\n[0025] （6）业务处理终端处理完一项业务后，将此业务处理用时发送到业务处理服务器，存入业务处理用时数据库。\n[0026] 本发明公开的一种排队机调度方法的一种改进，所述步骤（4）的业务用时预估算法为首先对业务进行分类，给每类业务分配一个业务分类代码，当一项业务处理完成时，将此业务处理用时记入业务处理用时数据库中，当一项新业务到达时，业务处理用时预估模块首先读取其业务分类代码，然后在业务处理用时数据库中检索近期此类业务的处理用时信息，使用如下公式估算新业务的处理用时： \n 其中 为预估的新业务处理时间， 为上次预估的业务处理\n时间， 为最近一次此类业务的处理时间，α为平滑系数取值为0.125。\n[0027] 本发明公开的一种排队机调度方法的又一种改进，所述步骤（5）的业务调度算法为同时考虑每个业务的等待时间长短和估计需要的处理时间长短，从中选出响应比最高的作业投入执行，响应比R定义如下： 其中T为该业务估计需要的执行时\n间，W为业务在排队队列中的等待时间,当业务处理终端可以接受新业务时，向业务处理服务器发出请求。业务处理服务器计算每个业务的响应比，选择其中响应比最大者，将其排队号码反馈给业务处理终端进行处理。\n[0028] 本发明公开的预估业务处理时间的排队处理系统及排队机调度方法，能够判别客户业务类型，根据历史统计数据预测各类业务处理与等待时间，自动调整队列分配与顺序，达到降低客户平均等待时间的目的。\n附图说明\n[0029] 图1、本发明公开的预估业务处理时间的排队处理系统的系统结构示意图；\n[0030] 图2、本发明公开的排队机装置的系统结构示意图；\n[0031] 图3、本发明公开的业务处理服务器的系统结构示意图；\n[0032] 图4、本发明公开的业务处理终端的系统结构示意图；\n[0033] 附图标记列表：\n[0034] 1、排队机装置； 2、网络连接装置； 3、业务处理服务器；\n[0035] 4、业务处理终端； 11、条码扫描装置 12、排队号码条打印装置；\n[0036] 31、业务处理用时数据库； 32、业务处理用时预估模块；33、排队队列管理模块；\n[0037] 34、业务调度模块； 41、业务单识别装置； 42、客户叫号装置。\n具体实施方式\n[0038] 下面结合附图和具体实施方式，进一步阐明本发明，应理解下述具体实施方式仅用于说明本发明而不用于限制本发明的范围。\n[0039] 如图1至图4所示，本发明公开的一种预估业务处理时间的排队处理系统包括：\n[0040] 排队机装置1，用于接收客户业务单据，读取单据数据以及打印排队号码条；\n[0041] 业务处理终端4，用于服务人员对客户业务进行处理，记录各类业务处理时间，呼叫下一名客户；\n[0042] 业务处理服务器3，用于管理排队队列，调用业务处理时间数据入库31，预估业务处理时间，分配排队号码，调度排队队列；\n[0043] 网络连接装置2，用于提供排队机装置1、业务处理终端4和业务处理服务器3之间的数据通信连接。\n[0044] 作为一种优选，所述的排队机装置1上安装有条码扫描装置11、排队号码条打印装置12。\n[0045] 作为一种优选，所述业务处理终端4上安装有业务单识别装置41、客户叫号装置\n42。\n[0046] 作为一种优选，所述业务处理服务器3包括：\n[0047] 业务处理用时数据库31，用于记录一段时期内各个业务处理用时记录；\n[0048] 业务处理用时预估模块32，用于当客户向系统提交新业务时估计处理此业务需要消耗的时间；\n[0049] 排队队列管理模块33，用于维护和管理待处理业务队列；\n[0050] 业务调度模块34，用于从待处理业务队列中选择一项业务交给服务窗口处理。\n[0051] 本发明公开的一种排队机调度方法，包括如下步骤：\n[0052] （1）排队机装置1接收客户提交的业务单据，每张业务单据上都印刷有业务分类条码，排队机装置1能够根据业务分类条码提取到此业务对应的业务分类代码，通过网络连接装置2将业务代码发送到业务处理服务器3；\n[0053] （2）业务处理服务器3将接收到的新业务放入排队队列，并产生一个排队号码返回到排队机装置1；\n[0054] （3）排队机装置1接收到排队号码后，打印排队号码条提交给客户；\n[0055] （4）业务处理服务器3根据新业务的业务分类代码，查询业务处理用时数据库31，使用业务处理用时预估模块32根据业务用时预估算法对新业务所需的处理时间进行预测；\n[0056] （5）业务处理终端4向业务处理服务器3发出叫号请求，业务处理服务器3调用业务调度模块34，使用调度算法从排队队列中选择一项业务，将其排队号码反馈到业务处理终端4，通过业务叫号装置播放叫号提示；\n[0057] （6）业务处理终端4处理完一项业务后，将此业务处理用时发送到业务处理服务器3，存入业务处理用时数据库31。\n[0058] 作为一种优选，所述步骤（4）的业务用时预估算法为首先对业务进行分类，给每类业务分配一个业务分类代码，当一项业务处理完成时，将此业务处理用时记入业务处理用时数据库31中，当一项新业务到达时，业务处理用时预估模块32首先读取其业务分类代码，然后在业务处理用时数据库31中检索近期此类业务的处理用时信息，使用如下公式估算新业务的处理用时： 其中 为预估的新业务处理时间，\n为上次预估的业务处理时间， 为最近一次此类业务的处理时间，α为平滑系数取值为\n0.125。\n[0059] 作为一种优选，所述步骤（5）的业务调度算法为同时考虑每个业务的等待时间长短和估计需要的处理时间长短，从中选出响应比最高的作业投入执行，响应比R定义如下：\n 其中T为该业务估计需要的执行时间，W为业务在排队队列中的等待\n时间,当业务处理终端4可以接受新业务时，向业务处理服务器3发出请求。业务处理服务器3计算每个业务的响应比，选择其中响应比最大者，将其排队号码反馈给业务处理终端4进行处理。\n[0060] 本方法的关键是业务调度算法和新业务处理用时的预估方法，下面分别进行详细描述：\n[0061] （1）业务调度算法\n[0062] 传统排队机系统的业务调度算法为先来先服务算法（FCFS，First Come First Serve），即客户到达后进入同一个队列，叫号顺序和客户进入队列的顺序一致。传统业务调度算法存在的问题是对于需要处理简单业务的客户而言等待时间过长，常常出现为了办理仅仅耗时几分钟的业务却不得不排队数小时的情况。此外还有一种短业务优先算法（SJF，Shortest Job First），这种方法总是优先选择耗时较短的业务，可以有效地降低客户的平均等待时间。但是这种调度算法会导致耗时较长的业务总是会被耗时较短的业务插队，长时间得不到调度。\n[0063] 本发明采用最高响应比优先算法（HRN，Highest Response-ratio Next）进行业务调度。此调度策略同时考虑每个业务的等待时间长短和估计需要的处理时间长短，从中选出响应比最高的作业投入执行。响应比R定义如下：\n[0064] \n[0065] 其中T为该业务估计需要的执行时间，W为业务在排队队列中的等待时间。当业务处理终端4可以接受新业务时，向业务处理服务器3发出请求。业务处理服务器3计算每个业务的响应比，选择其中响应比最大者，将其排队号码反馈给业务处理终端4进行处理。这样耗时较长的业务的响应比也就随着等待时间的流逝而增加，从而有机会获得调度处理。这种算法是介于FCFS和SJF之间的一种折中算法，客户平均等待时间比SJF法略有延长，但是能保证各类业务调度的相对公平。\n[0066] （2）业务用时预估方法\n[0067] 为了实现最高响应比优先算法，必须要对新提交业务的处理用时进行预估。本发明对业务进行分类，给每类业务分配一个业务分类代码。当一项业务处理完成时，将此业务处理用时记入业务处理用时数据库中。当一项新业务到达时，业务处理用时预估模块首先读取其业务分类代码，然后在业务处理用时数据库中检索近期此类业务的处理用时信息，使用如下公式估算新业务的处理用时：\n[0068] \n[0069] 其中 为预估的新业务处理时间， 为上次预估的业务处理时间， 为最近一次此类业务的处理时间，α为平滑系数，根据经验可取为0.125。\n[0070] 为了计算方便，可从业务处理用时数据库中读取最近若干条业务处理用时记录，使用如下通项公式计算：\n[0071] \n[0072] 其中Ti为第i条业务处理用时记录，n为读取记录数，可取为最近一星期的业务量。\n[0073] 具体实施例 单位财务服务排队叫号系统\n[0074] 大型单位的财务报销大厅在报销高峰期经常出现排队现象，有些客户积攒的各类单据比较多，审核窗口的工作人员需要花费一个小时甚至更多时间才能办理完一位客户的业务。与此同时，还有一些客户办理的业务比较简单，可能只需要花费数分钟即可办理。若采用传统排队叫号方案，经常出现为了办理一件五分钟即可完成的业务却不得不排队数小时的情况。\n[0075] 本实施例提供了一种预估业务处理时间的排队处理系统，图1为本实施例的排队处理系统结构示意图。如图1所示，该系统主要包括：排队机装置1、网络连接装置2、业务处理服务器3和业务处理终端4。\n[0076] 其中，所述的排队机装置1主要用于：接收客户业务单据、读取业务单据数据和打印排队号码条。排队机装置通过网络连接装置2连接业务处理服务器3。\n[0077] 所述业务处理服务器3主要用于：接收业务单据信息，分配排队号码，管理排队队列，调度排队队列，历史业务处理时间数据入库，估计新业务处理时间。\n[0078] 所述业务处理终端4主要用于：服务人员对客户业务进行处理，包括接收客户业务单据后扫描单据上印刷的分类条码号、记录业务处理时间、呼叫下一位客户。\n[0079] 图2为所述排队机装置1的系统结构，包括条码扫描装置11、排队号码条打印装置\n12。\n[0080] 所述条码扫描装置11用于扫描客户提交的业务单据上的业务分类条码，读取业务分类代号。\n[0081] 所述排队号码条打印装置12用于打印客户排队号码条。排队号码条主要包含的内容有：排队号码、业务受理日期和时间、业务分类代码号。\n[0082] 图3为所述业务处理服务器3的系统结构，包括业务处理用时数据库31、业务处理用时预估模块32、排队队列管理模块33、业务调度模块34。\n[0083] 所述业务处理用时数据库31采用小型数据库管理系统（如mysql或其他小型数据库），存储历史业务处理数据。业务处理数据表主要字段有：ID号、业务分类代码、受理时间、处理用时、处理终端号、是否有效业务。每当服务人员处理完一件业务时，都会将业务处理时间发送到业务处理服务器3，存入业务处理用时数据库31。若出现过号、废号等情况，也在数据库中存入一条记录，但是“是否有效业务”字段设置为FALSE。\n[0084] 所述业务处理用时预估模块32用于估计新业务处理用时，读取业务处理用时数据库31中最近500条同类业务处理用时记录，计算新业务的处理用时。\n[0085] 所述排队队列管理模块33用于维护业务队列，每当客户提交一份新业务时，将此业务信息（包括排队号码、业务分类代码、预估处理用时）放入待调度业务池中，每隔一定时间间隔（如每分钟）更新此业务的等待时间，并计算此业务的响应比。\n[0086] 业务调度模块34用于从排队队列中按照最高响应比优先算法选择待处理的业务，将其从待调度业务池中取出，并将排队号码发送到业务处理终端4。\n[0087] 图4为所述业务处理终端4的系统结构，包括业务单识别装置41、客户叫号装置\n42。\n[0088] 所述业务单识别装置41用于在接受客户业务时扫描业务单据上的条码，读取业务分类代码。\n[0089] 所述客户叫号装置42用于在LED屏幕上显示当前可处理的排队号码，并通过扬声器播放排队号码，提醒客户前来办理业务。\n[0090] 本实施例的提供的排队机调度方法工作流程包括如下步骤：\n[0091] （1）客户从服务柜台领取业务处理单。每张业务处理单上都印刷有条形码，各种业务类型均有业务分类条码。\n[0092] （2）客户填写完业务处理单后将其放入排队机装置1安装的条码扫描装置11上，条码扫描装置11扫描业务单上的条码信息，通过网络连接装置2将条码信息发送到业务处理服务器3。\n[0093] （3）业务处理服务器3收到来自排队机装置1的业务单条码信息后，检索业务处理用时数据库31，并调用业务处理用时预估模块32，对处理这批业务需要消耗的时间进行预估。\n[0094] （4）业务处理服务器3估计出业务处理用时后，调用排队队列管理模块33，将此业务放入待处理业务池，生成排队号码并通过网络连接装置2发送到排队机装置1。\n[0095] （5）排队机装置1接收到排队号码后，打印出排队号码条。\n[0096] （6）客户领取排队号码条后进入等待区休息。\n[0097] （7）工作人员准备处理下一单业务时，操作业务处理终端4向业务处理服务器3发出请求信号。\n[0098] （8）业务处理服务器3调用业务调度模块34，从待处理业务池中取出响应比R最高的业务，将其排队号码发送到业务处理终端4。\n[0099] （9）业务处理终端4呼叫排队号码，接收客户的业务单据，并将其放入业务单识别装置41读取业务分类代码，并开始计时。业务处理完成后，将此业务实际所用时间发送到业务处理服务器3入库。\n[0100] （10） 服务完毕后，客户离开大厅。\n[0101] 本发明公开的预估业务处理时间的排队处理系统及排队机调度方法，能够判别客户业务类型，根据历史统计数据预测各类业务处理与等待时间，自动调整队列分配与顺序，达到降低客户平均等待时间的目的。\n[0102] 本发明方案所公开的技术手段不仅限于上述技术手段所公开的技术手段，还包括由以上技术特征任意组合所组成的技术方案。