Структуры и алгоритмы обработки данных


Краткая теория


Формулировка задачи.

Пусть обслуживающая система состоит из конечного числа обслуживающих аппаратов. Система  относится к  числу систем с ожиданием. Каждый аппарат может обслуживать  одновременно  только   одно  требование. Если в момент поступления очередного требования  имеются  свободные  аппараты,  то один из них немедленно  приступает  к  обслуживанию, если свободных  аппаратов нет,  то   требование   ждет   обслуживания.  Естественно,   если   требований больше, чем обслуживающих аппаратов,  то образуется  очередь. Время  обслуживания одного требования есть  случайная  величина,  подчиненная  показательному закону распределения:

F(t)=1-e-nt

Поток поступающих требований ограничен, то есть одновременно в системе обслуживания не может находиться больше  m требований,  где m -  конечное число. Это дает право считать, что требования на  обслуживание поступают от m обслуживаемых объектов, которые время от времени нуждаются в  обслуживании.    Пусть вероятность того, что поступит заявка на обслуживания  на данном такте  равна  Р(А)  и  вероятность   того, что  требование  из  очереди поступит  на обслуживание равно Р(В) ( на каждом такте может поступить не  более   одной заявки  на обслуживание). Число обслуживающих аппаратов равно N.  Допустим,  требование дождалось своей очереди и оно начало обслуживаться. Обслуживание может длиться в течении не более 3-х тактов.  Заявки могут быть двух приоритетов:

 

Заявка первого приоритета:

     Это обычная заявка, она не обладает ни какими  привилегиями. Она  может покинуть систему через определенное число тактов Т. При приходе  в обслуживающую систему заявка первого  приоритета  становится в   конец очереди.

 

Заявка второго приоритета:

     Эта заявка отличается только тем, что она при поступлении в  обслуживающую систему   становится в начало очереди, то есть как только освобождается аппарат, то она поступает на обслуживание  с  вероятностью Р(В).

 

Заявка второго  приоритета , как и заявка первого  приоритета, покидает систему через Т тактов. Естественно, что появление заявок второго приоритета достаточно мало ( хотя эта вероятность задается пользователем и может быть любой ).  Теперь об обслуживании:    Количество тактов, в течение которых будет обслуживаться  та или иная заявка выбирается случайно (эта величина в  данной  задаче не должна быть больше 3).   Если заявка  обслужилась  положенное ей число тактов, то  она покидает систему. Если заявка находится в очереди больше Т тактов, то она с некоторой  вероятностью покидает систему. 

 




- Начало -  - Назад -  - Вперед -



Книжный магазин