Skip to content

🤖 基于排队论的时序控制系统及自动目标测试

License

Notifications You must be signed in to change notification settings

NekoSilverFox/CMO

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

44 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

silverfox

CMO

时序控制系统及自动目标测试

silverfox
Санкт-Петербургский государственный политехнический университет
Институт компьютерных наук и технологий

License

分析

所有的文件都应该有一根时间线(TimeLine)来贯穿,同时请求(request)应作为事件(event)的最小单位,CMO 系统中的所有事务都应该是对于请求而言

需要一下的功能模块:

  • 事件(Event)
  • 时间线(TimeLine)同时带有日志功能
  • 请求(Request)
  • 源(Source)
  • 缓冲区(Buffer)
  • 处理机(Device)

各模块类型的简要概述:

原文:

  • ИБ - бесконечный (источники)
  • ИЗ2 - равномерный (законы распределения)
  • ПЗ1 – экспоненциальный (законы распределения времени прибор)
  • Д10З3 - на свободное место (записи в буфер, если есть место)
  • Д10О5 – вновь пришедшая (дисциплины отказа)
  • Д2П1 - приоритет по номеру прибора (выбор прибора)
  • Д2Б4 - приоритет по номеру источника, по одной заявке (выбор заявки из буфера)
  • ОД1 - календарь событий, буфер и текущее состояние (отображение динамики функционирования модели)
  • ОР1 - сводная таблица результатов (отображение результатов)

中文:

  • ИБ:源的类型为无限源(一直生成请求)
  • ИЗ2:每个源生成请求的间隔为等长
  • ПЗ1:对于每个处理机处理请求的时长为负指数增长
  • Д10З3:对于请求插入缓冲区的规则为,按照顺序选择缓冲区,插入空闲的缓冲区。不存在转移队列
  • Д10О5:如果没有空闲的处理机及缓冲区,请求应直接离开系统,并且不得改变缓冲区的任何状态
  • Д2П1:处理机的优先级和源的优先级都由其编号决定,选择优先级最大的处理机进行处理请求
  • Д2Б4:从缓冲区中选择请求的规则为,选择优先级最高的请求(请求的优先级就是源的编号),如果缓冲区中有多个同优先级的请求,优先选择最后进入缓冲区的
  • ОД1:手动测试模式,输出日志、缓冲区及当前的事件
  • ОР1:自动测试模式,输出测试结果

架构

img.png

模拟时序图

timecxema.png

程序框图

cxema.png

文件职责

时间线(TimeLine)

时间线应该作为穿插各功能模块的线,带有日志功能以方便后续的统计及图表生成

开发说明:

  • 使用单例模式,每次程序运行应该只有一条时间线
  • 从 0 开始计时(计数),每次增加一个时间单位。每单位的时间是多长应在初始化时进行确定
  • 程序运行后应通过时间线中的时间对 buffer/device/source 进行判断,看里面是否记录有需要执行的任务
  • 包含一个日志,记录发生了的事件,并将其写入文件(使用列表存储)

属性:

  • 当前时间 (只允许递增!)
  • 记录事件的列表(日志)
  • 时间的步长(每单位时间是多久)
  • 是否开启调试模式

事件(Event)

记录系统中发生的单个事件,作为时间线(程序)的最小单位

属性:

  • 当前时间
  • 事件类型
    • 生成请求
    • 请求进入缓冲区
    • 请求离开缓冲区
    • 请求进入处理机
    • 请求离开处理机
    • 请求被取消
  • 本 CMO 生成的第几个请求
  • 生成这个请求的源ID
  • 请求在他的生成源的ID
  • 缓冲区ID
  • 处理机ID
  • 系统中当前空闲缓冲区的数量
  • 系统中当前空闲处理机的数量

请求(Request)

由源生成,作为一个对象可以在源、缓冲区、处理机之间相互传递

包含的属性:

  • [Static] 整个系统累计生成的请求的数量
  • [Static] 整个系统累计取消的请求的数量
  • 产生这个请求的源
  • 这个请求在它源中的ID
  • 在整个 CMO 中的唯一 ID

源(Source)

用于生成请求

  • static 当前 CMO 中的源的总数
  • 源 ID
  • 源的优先级
  • 下一个请求发生的时间
  • 本源的服务时间(各请求在源的停留时间总和
  • 时间线(用户传入)

缓冲区(Buffer)

  • static 当前 CMO 中的缓冲区总数
  • 缓冲区 ID
  • 缓冲区优先级
  • 当前在缓冲区中的请求
  • 上一个/当前 请求进入缓冲区的时间
  • 本缓冲区中存留过的请求总数
  • 本缓冲区的服务时间(各请求在缓冲区的停留时间总和
  • 时间线(用户传入)

处理机(Device)

用于处理请求

  • static 当前 CMO 中的处理机总数
  • 处理机 ID
  • 处理机优先级
  • 当前在处理机中的请求
  • 上一个/当前 请求进入处理机的时间
  • 当前请求处理结束的时间(未来)
  • 本处理机中处理过的请求总数
  • 本处理机的服务时间(各请求在处理机中的停留时间总和
  • 时间线(用户传入)

处理机的处理时间应该为负指数增长,即越往后的请求,处理越快

​ 公式:

$$ 处理时间 = MaxTime \cdot X^{-LAMBDA} $$

  • MaxTime - 最大的处理时间,即第一个请求所需的时间($MaxTime > 0$
  • X - 第几个请求($X > 0, X∈Z $)
  • LAMBDA - 参数,越接近 1,函数递减的就越快($0 < LAMBDA < 1$)

示例:

  • $$ 处理时间 = 100 \cdot X^{-0.1} $$

    img.png

  • $$ 处理时间 = 100 \cdot X^{-0.2} $$

    img_1.png

  • $$ 处理时间 = 100 \cdot X^{-0.3} $$

    img_2.png

  • $$ 处理时间 = 100 \cdot X^{-0.4} $$

    img_3.png

  • $$ 处理时间 = 100 \cdot X^{-0.5} $$

    img_4.png

应用系统解决实际问题

需求场景:每天会到来300位客户,如何在客户的离开率不大于5%,用户的等待时长不超过30分钟的情况下花费最小的钱建设银行

Из них: 500 000 рублей на каждый новый зал ожидания, 2 000 000 на каждое новое окно и персонал

Техническая система Система обслуживания клиентов банка
Источник Клиенты, которые занимаются различными видами бизнеса. Например, банковские карты, интернет-банкинг, вклады, снятие наличных и консультационные услуги. Каждый источник представляет клиента, который занимается одним видом бизнеса, и эти клиенты имеют разные приоритеты, например, те, кто занимается банковскими картами, имеют более высокий приоритет, чем те, кто консультирует бизнес. Всего существует 5 тип клиента в нашем случае.
Буфер Буфер - это зона ожидания в банке, считайте, что это место (диван). Если один из диванов занят, то никакой другой клиент не может занять его
Прибор Прибор - это окно в банке, используемые для обработки бизнеса клиентов, причем время обработки бизнеса увеличивается в геометрической прогрессии по мере приближения времени закрытия.
Дисциплина постановки в буфер 如果一个客户到达银行,此时等候室有空位,那么他就会占用这个等候室。Если клиент прибыл, а комната ожидания (диван) оказалась свободной, то клиент займет эту комнату ожидания (диван)
Дисциплина выбора из буфера 优先选择优先级大的,也就是业务比较重要的客户。Приоритетом для клиента является тип бизнеса, которым он хочет заниматься. Приоритет отдается клиентам, чей тип бизнеса важен для обработки бизнеса.
Дисциплина отказа 如果一个到达的客户发现银行中所有的窗口都被占用了,而且等候室(沙发)也没有空位,说明整个银行现在非常的繁忙。那么这个客户就会离开。Если прибывший клиент обнаруживает, что все окна в банке заняты, а в зале ожидания нет свободных мест (дивана), это означает, что весь банк сейчас очень занят. Тогда этот клиент уйдет
Дисциплина постановки на обслуживание 如果银行中有多个空闲的窗口,那么优先选择优先级大的窗口。通常窗口的优先级是由银行的经理指定的。Если в банке имеется более одного свободного окна, то предпочтение отдается окну с наивысшим приоритетом. Обычно приоритет окна назначается менеджером банка

对应到 CMO 系统中:

CMO 系统模块 实际问题中的模块 描述
请求(Request) 客户 到达银行的客户
源(Device) 客户的来源 办理不同业务的客户。比如办理银行卡、办理网上银行、存款、取款、咨询业务。每一个源就代表办理一种业务的客户,这些客户的优先级是不一样的,比如办理银行卡的优先级就要大于咨询业务的。
缓冲区(Buffer) 银行中的等待室 缓冲就是银行中的等待区,可以考虑成这是一个位置(沙发)。如果其中一个沙发被占用了,那么其他客户就不能再占用
处理机(Device) 银行中的柜台和工作人员 处理机就是银行中的窗口,用于处理客户的业务,业务处理时间随着下班时间的临近成负指数增长

发生的情况:

CMO 系统描述 实际问题
请求产生 客户到达银行
请求进入缓冲区 客户通过取号机区号,进行排队(进入等候室)
请求离开缓冲区,进入处理机 此时有空闲的柜台,客户离开等候室,进入柜台处理业务
请求离开处理机 客户的业务完成,客户离开银行
请求被取消 银行此时处于繁忙状态,即所有的柜台都繁忙,并且等候室也没有空位

其中:

  • 建设一个等候室需要花费 500 000卢布
  • 建设一个柜台及聘用相关人员需要 2 000 000 卢布
  • 模拟银行每天需要处理 300 位客户
  • 客户的离开率不得高于1%

经过建模模拟后取得结果,得到最优解:

<style> </style> <script language="JavaScript"> </script>
源的数量 等候区数量 服务窗口数量 请求被取消概率 总花费
5 1 1 0.54485 2500000
5 2 1 0.34437 3000000
5 3 1 0.25166 3500000
5 4 1 0.21262 4000000
5 1 2 0.51827 4500000
5 5 1 0.20598 4500000
5 2 2 0.27243 5000000
5 6 1 0.20266 5000000
5 3 2 0.14618 5500000
5 7 1 0.19934 5500000
5 4 2 0.08306 6000000
5 8 1 0.19601 6000000
5 1 3 0.50831 6500000
5 5 2 0.06977 6500000
5 9 1 0.19269 6500000
5 2 3 0.25249 7000000
5 6 2 0.06645 7000000
5 10 1 0.18937 7000000
5 3 3 0.11296 7500000
5 7 2 0.06312 7500000
5 4 3 0.04651 8000000
5 8 2 0.0598 8000000
5 1 4 0.50498 8500000
5 5 3 0.03322 8500000
5 9 2 0.05648 8500000
5 2 4 0.24252 9500000
5 6 3 0.0299 9500000
5 10 2 0.05316 9500000
5 3 4 0.09967 9500000
5 7 3 0.02658 9500000
5 4 4 0.02658 10000000
5 8 3 0.02326 10000000
5 1 5 0.50498 10500000
5 5 4 0.01329 10500000
5 9 3 0.01993 10500000
5 2 5 0.2392 11000000
5 6 4 0.00997 11000000
5 10 3 0.01661 11000000
5 3 5 0.09302 11500000
5 7 4 0.00664 11500000
5 4 5 0.01993 12000000
5 8 4 0.00332 12000000
5 1 6 0.50498 12500000
5 5 5 0.00664 12500000
5 9 4 0 12500000
5 2 6 0.23588 13000000
5 6 5 0.00332 13000000
5 10 4 0 13000000
5 3 6 0.0897 13500000
5 7 5 0 13500000
5 4 6 0.01661 14000000
5 8 5 0 14000000
5 1 7 0.50498 14500000
5 5 6 0.00332 14500000
5 9 5 0 14500000
5 2 7 0.23256 15000000
5 6 6 0 15000000
5 10 5 0 15000000
5 3 7 0.08638 15500000
5 7 6 0 15500000
5 4 7 0.01329 16000000
5 8 6 0 16000000
5 1 8 0.50498 16500000
5 5 7 0 16500000
5 9 6 0 16500000
5 2 8 0.23256 17000000
5 6 7 0 17000000
5 10 6 0 17000000
5 3 8 0.08306 17500000
5 7 7 0 17500000
5 4 8 0.00997 18000000
5 8 7 0 18000000
5 1 9 0.50498 18500000
5 5 8 0 18500000
5 9 7 0 18500000
5 2 9 0.23256 19500000
5 6 8 0 19500000
5 10 7 0 19500000
5 3 9 0.08306 19500000
5 7 8 0 19500000
5 4 9 0.00997 20000000
5 8 8 0 20000000
5 1 10 0.50498 20500000
5 5 9 0 20500000
5 9 8 0 20500000
5 2 10 0.23256 21000000
5 6 9 0 21000000
5 10 8 0 21000000
5 3 10 0.08306 21500000
5 7 9 0 21500000
5 4 10 0.00997 22000000
5 8 9 0 22000000
5 5 10 0 22500000
5 9 9 0 22500000
5 6 10 0 23000000
5 10 9 0 23000000
5 7 10 0 23500000
5 8 10 0 24000000
5 9 10 0 24500000
5 10 10 0 25000000

俄-中

中文 俄语
此刻生成了一个请求 В этот момент создается заявка
请求进入缓冲区 Заявка на буфер
请求离开缓冲区 Заявка на выход из буфера
请求进入处理机 Заявка на прибора
请求离开处理机 Заявка на выход из прибора
请求被取消 Заявка отказан