مدل های ریاضی ساده ترین سیستم های صف. توابع p0(t) و p1(t) فرآیند گذرا را در یک QS تک کانالی تعیین می‌کنند و روند نزدیک شدن نمایی QS به حالت حدی خود را با ثابت زمانی مشخصه d توصیف می‌کنند.

اکتبر 23, 2013 در 02:22 ب.ظ

Squeak: مدل سازی سیستم های صف

• برنامه نويسي،
• اوپ،
• برنامه نویسی موازی

اطلاعات بسیار کمی در مورد Habré در مورد زبان برنامه نویسی مانند Squeak وجود دارد. من سعی خواهم کرد در مورد آن در زمینه مدل سازی سیستم های صف صحبت کنم. من نشان خواهم داد که چگونه یک کلاس ساده بنویسیم، ساختار آن را توصیف کنم و از آن در برنامه ای استفاده کنم که درخواست ها را از طریق چندین کانال ارائه می دهد.

چند کلمه در مورد Squeak

Squeak یک پیاده سازی باز و چند پلتفرمی از زبان برنامه نویسی Smalltalk-80 با تایپ پویا و جمع کننده زباله است. رابط کاملاً خاص است، اما برای اشکال زدایی و تجزیه و تحلیل بسیار راحت است. Squeak به طور کامل با مفهوم OOP مطابقت دارد. همه چیز از اشیا تشکیل شده است، حتی ساختارها اگر-پس-دیگر، برای، در حالی کهبا کمک آنها اجرا شد. کل نحو به ارسال پیام به شی به شکل زیر خلاصه می شود:

<объект> <сообщение>

هر متدی همیشه یک شی را برمی گرداند و می توان پیام جدیدی به آن ارسال کرد.
Squeak اغلب برای مدل سازی فرآیند استفاده می شود، اما می تواند به عنوان ابزاری برای ایجاد برنامه های چند رسانه ای و انواع پلت فرم های آموزشی نیز استفاده شود.

سیستم های نوبت دهی

سیستم های صف (QS) شامل یک یا چند کانال هستند که برنامه های کاربردی را از چندین منبع پردازش می کنند. زمان سرویس دهی به هر درخواست می تواند ثابت یا دلخواه و همچنین فواصل بین رسیدن آنها باشد. این می تواند یک مرکز تلفن، یک لباسشویی، صندوقدار در یک فروشگاه، یک دفتر تایپ و غیره باشد. چیزی شبیه به این است:

QS شامل چندین منبع است که وارد صف مشترک می شوند و با آزاد شدن کانال های پردازش برای سرویس فرستاده می شوند. بسته به ویژگی‌های خاص سیستم‌های واقعی، مدل ممکن است حاوی تعداد متفاوتی از منابع درخواست و کانال‌های خدمات باشد و محدودیت‌های متفاوتی در طول صف و احتمال از دست دادن درخواست‌ها (شکست) داشته باشد.

هنگام مدل سازی یک QS، وظایف تخمین میانگین و حداکثر طول صف، فرکانس انکار سرویس، میانگین بار کانال و تعیین تعداد آنها معمولاً حل می شود. بسته به وظیفه، مدل شامل بلوک های نرم افزاری برای جمع آوری، انباشت و پردازش داده های آماری لازم در مورد رفتار فرآیندها است. متداول‌ترین مدل‌های جریان رویداد در تحلیل QS معمولی و پواسون هستند. مشخصه های معمولی با زمان یکسانی بین وقوع رویدادها مشخص می شود، در حالی که موارد پواسون تصادفی هستند.

کمی ریاضی

برای یک جریان پواسون، تعداد رویدادها ایکسقرار گرفتن در فاصله طولی τ (تاو) مجاور نقطه تی، طبق قانون پواسون توزیع شده است:
جایی که a (t، τ)- میانگین تعداد رویدادهای رخ داده در بازه زمانی τ .
میانگین تعداد رویدادهای رخ داده در واحد زمان برابر است با λ(t). بنابراین، میانگین تعداد رویدادها در بازه زمانی τ ، مجاور لحظه زمان تی، برابر خواهد بود با:

زمان تیبین دو رویداد λ(t) = const = λطبق قانون توزیع می شود:
چگالی توزیع یک متغیر تصادفی تیبه نظر می رسد:
برای به دست آوردن دنباله های پواسون شبه تصادفی از فواصل زمانی تی منحل معادله:
جایی که r iیک عدد تصادفی است که به طور یکنواخت در بازه توزیع شده است.
در مورد ما، این عبارت را می دهد:

با تولید اعداد تصادفی می توانید مجلدات کامل را بنویسید. در اینجا، برای تولید اعداد صحیح که به طور یکنواخت در بازه توزیع شده اند، از الگوریتم زیر استفاده می کنیم:
جایی که R i- یک عدد صحیح تصادفی دیگر؛
آر- تعدادی عدد اول بزرگ (مثلا 2311)؛
س- عدد صحیح - حد بالای بازه، به عنوان مثال، 2 21 = 2097152؛
رم- عملیات به دست آوردن باقیمانده از تقسیم اعداد صحیح.

مقدار اولیه R0معمولاً به طور دلخواه تنظیم می شود، به عنوان مثال، با استفاده از قرائت های تایمر:
زمان مجموع ثانیه
برای بدست آوردن اعدادی که به طور مساوی در بازه توزیع شده اند، از عملگر زبان استفاده می کنیم:

کلاس رند

برای بدست آوردن اعداد تصادفی که به طور یکنواخت در بازه توزیع شده اند، یک کلاس ایجاد می کنیم - مولد اعداد واقعی:

متغیر floatWordSubclass: #Rand "class name" instanceVariableNames: "" "instance variables" classVariableNames: "R" "class variables" poolDictionaries: "" "لغت نامه های رایج" دسته: "نمونه" "نام دسته"
مواد و روش ها:

"Initialization" init R:= Time totalSeconds.next "Next شبه تصادفی" بعدی R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
برای تنظیم وضعیت اولیه سنسور، یک پیام ارسال کنید رند اینیت.
برای دریافت یک عدد تصادفی دیگر ارسال کنید رند بعدی.

برنامه پردازش برنامه

بنابراین، به عنوان یک مثال ساده، بیایید موارد زیر را انجام دهیم. فرض کنید باید حفظ جریان منظم درخواست‌ها را از یک منبع با فاصله زمانی تصادفی بین درخواست‌ها شبیه‌سازی کنیم. دو کانال با عملکرد متفاوت وجود دارد که امکان سرویس دهی به برنامه ها را به ترتیب در 2 و 7 واحد زمان می دهد. لازم است تعداد درخواست های ارائه شده توسط هر کانال در بازه 100 واحد زمانی ثبت شود.

کد جیر جیر

"اعلام متغیرهای موقت" | proc1 proc2 t1 t2 s1 s2 sys صف اولویت ادامه r | "Initial variable settings" Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2: = -1. ادامه: = درست است. sysPriority:= Processor activeProcess اولویت. صف "اولویت فعلی": = سمافور جدید. "Claim Queue Model" "Creating Process - Channel Model 1" s1:= s1 + 1. proc1 suspend."Suspend process pending service endination" ].proc1:= nil."Remove reference to process 1" ]priority: (sysPriority + 1)) رزومه. "اولویت جدید بیشتر از پس زمینه است" "ایجاد فرآیند - مدل کانال 2" .proc2:= nil.] اولویت: (sysPriority + 1)) رزومه. "توضیحات ادامه فرآیند اصلی و مدل منبع" در حالی که True: [ r:= (رند بعدی * 10) گرد شد. (r = 0) ifTrue: . ((SysTime rem: r) = 0) ifTrue: . "Send request" "Service process switch" (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. "Model time is ticking" ]. "نمایش وضعیت شمارنده درخواست" PopUpMenu اطلاع رسانی: "proc1: ",(s1 printString)," proc2: ",(s2 printString). ادامه:= نادرست.

در هنگام راه اندازی، می بینیم که فرآیند 1 موفق به پردازش 31 درخواست شد و 2 فقط 11 درخواست را پردازش کرد:

طبقه بندی، مفاهیم اساسی، عناصر مدل، محاسبه ویژگی های اصلی.

هنگام حل مشکلات سازماندهی منطقی تجارت، خدمات مصرف کننده، انبارداری و غیره. تفسیر فعالیت های ساختار تولید بسیار مفید است سیستم های نوبت دهی، یعنی سیستمی که در آن از یک سو درخواست های انجام هر کاری مدام مطرح می شود و از سوی دیگر این درخواست ها دائماً برآورده می شود.

هر SMO شامل چهار عنصر: جریان ورودی، صف، سرور، جریان خروجی.

نیاز(مشتری، برنامه کاربردی) در QS هر درخواست فردی برای انجام هر کاری است.

سرویساجرای کار برای ارضای تقاضای ورودی است. شیئی که تعمیر و نگهداری نیازمندی ها را انجام می دهد دستگاه سرویس (دستگاه) یا کانال سرویس نامیده می شود.

زمان سرویس دوره ای است که در طی آن نیاز خدمات برآورده می شود، یعنی. مدت زمان شروع خدمت تا اتمام آن. از لحظه ورود درخواست به سیستم تا شروع سرویس، زمان انتظار سرویس نامیده می شود. زمان انتظار برای سرویس به همراه زمان سرویس، زمان اقامت مورد نیاز در سیستم است.

SMO ها بر اساس معیارهای مختلف طبقه بندی می شوند..

1. با توجه به تعداد کانال های سرویس، QS به تک کانال و چند کانال تقسیم می شوند.

2. بسته به شرایط انتظار، نیازمندی شروع سرویس QS را با ضرر (شکست) و QS را با انتظار متمایز می کند.

AT QS با از دست دادن تقاضا، دریافت شده در لحظه ای که تمام دستگاه ها مشغول تعمیر و نگهداری هستند، رد می شوند، برای این سیستم گم می شوند و هیچ تاثیری در روند نگهداری بعدی ندارند. مثال کلاسیک یک سیستم خراب، سانترال تلفن است - در صورتی که طرف تماس گرفته شده مشغول باشد، درخواست اتصال رد می شود.

برای یک سیستم با خرابی، مشخصه اصلی کارایی عملکرد، احتمال شکست یا نسبت متوسط ​​درخواست‌هایی است که ارائه نشده باقی می‌مانند.

AT CMO با انتظار تقاضا، دریافت شده در لحظه ای که همه دستگاه ها مشغول سرویس هستند، از سیستم خارج نمی شود، اما در صف می ماند و منتظر می ماند تا یکی از کانال ها آزاد شود. هنگامی که دستگاه بعدی منتشر می شود، یکی از برنامه های موجود در صف بلافاصله برای سرویس پذیرفته می شود.

برای QS با انتظار، ویژگی های اصلی انتظارات ریاضی طول صف و زمان انتظار است.

نمونه ای از سیستم انتظار و دیدن، فرآیند بازیابی تلویزیون ها در تعمیرگاه است.

سیستم هایی وجود دارند که بین این دو گروه قرار دارند ( CMO های مختلط). آنها با وجود برخی شرایط میانی مشخص می شوند: محدودیت ها می توانند محدودیت هایی در زمان انتظار برای شروع خدمات، طول صف و غیره باشند.

به عنوان ویژگی های عملکرد، احتمال شکست را می توان هم در سیستم هایی با تلفات (یا ویژگی های زمان انتظار) و هم در سیستم های دارای انتظار استفاده کرد.

3. با توجه به رشته خدمات، QS ها به سیستم های با اولویت سرویس و سیستم های بدون اولویت خدمات تقسیم می شوند.

درخواست ها می توانند به ترتیبی که دریافت می شوند، به صورت تصادفی یا بر اساس اولویت های تعیین شده، سرویس دهی شوند.

4. QS می تواند تک فاز و چند فاز باشد.

AT تک فازسیستم‌ها، نیازمندی‌ها توسط کانال‌هایی از همان نوع (به عنوان مثال، کارگران همان حرفه) بدون انتقال آنها از یک کانال به کانال دیگر، ارائه می‌شوند. چند فازیسیستم های چنین انتقالی امکان پذیر است.

5. با توجه به محل منبع نیازمندی ها، QS ها به باز (زمانی که منبع نیاز خارج از سیستم است) و بسته (زمانی که منبع در خود سیستم باشد) تقسیم می شوند.

به بستهشامل سیستم هایی است که در آنها جریان ورودی نیازمندی ها محدود است. به عنوان مثال، یک سرکارگر که وظیفه اش راه اندازی ماشین آلات در کارگاه است، باید به صورت دوره ای آنها را سرویس کند. هر دستگاه راه اندازی به منبع بالقوه ای از الزامات راه اندازی در آینده تبدیل می شود. در چنین سیستم هایی، تعداد کل ادعاهای در گردش محدود و اغلب ثابت است.

اگر منبع تامین بی نهایت نیاز داشته باشد، سیستم ها فراخوانی می شوند باز کن. نمونه هایی از این سیستم ها عبارتند از فروشگاه ها، باجه های فروش بلیط ایستگاه ها، بنادر و غیره. برای این سیستم ها، جریان ورودی درخواست ها را می توان نامحدود در نظر گرفت.

روش ها و مدل های مطالعه QS را می توان به صورت مشروط به تحلیلی و آماری (مدل سازی شبیه سازی فرآیندهای صف) تقسیم کرد.

روش های تحلیلی به دست آوردن ویژگی های سیستم به عنوان برخی از توابع پارامترهای عملکرد آن امکان پذیر است. این امکان انجام یک تحلیل کیفی از تأثیر عوامل فردی بر کارایی QS را فراهم می کند.

متأسفانه، تنها طیف نسبتاً محدودی از مسائل در تئوری صف را می توان به صورت تحلیلی حل کرد. با وجود توسعه مداوم روش‌های تحلیلی، در بسیاری از موارد واقعی، دستیابی به یک راه‌حل تحلیلی یا غیرممکن است، یا وابستگی‌های حاصل آنقدر پیچیده می‌شوند که تجزیه و تحلیل آنها به یک کار دشوار مستقل تبدیل می‌شود. بنابراین، برای اینکه بتوان روش‌های تحلیلی حل را به کار برد، باید به فرضیات ساده‌سازی مختلفی متوسل شد که تا حدودی با امکان اعمال تحلیل کیفی وابستگی‌های نهایی جبران می‌شود (البته در این مورد، ضروری است که مفروضات انجام شده تصویر واقعی فرآیند را مخدوش نکنند).

در حال حاضر، از نظر تئوری، توسعه یافته ترین و راحت ترین در کاربردهای عملی، روش هایی برای حل چنین مسائل صف بندی هستند که در آن جریان نیازمندی ها ساده ترین است ( پواسون).

برای ساده‌ترین جریان، فرکانس دریافت نیازمندی‌ها به سیستم از قانون پواسون تبعیت می‌کند، یعنی احتمال رسیدن در زمان t برابر با k مورد نیاز با فرمول داده می‌شود:

که در آن λ پارامتر جریان است (به زیر مراجعه کنید).

ساده ترین جریان دارای سه ویژگی اصلی است: معمولی، ثابت و بدون اثر.

معمولی بودنجریان به معنای عدم امکان عملی دریافت همزمان دو یا چند نیاز است. به عنوان مثال، احتمال خرابی همزمان چندین ماشین از گروهی از ماشین آلات که توسط یک تیم تعمیرکار سرویس می شوند، بسیار کم است.

ثابتتماس گرفت جریان، که برای آن انتظار ریاضی تعداد ادعاهای وارد شده به سیستم در واحد زمان (که با λ نشان داده می شود) در زمان تغییر نمی کند. بنابراین، احتمال ورود تعداد معینی از ادعاها به سیستم در طول یک بازه زمانی معین Δt به مقدار آن بستگی دارد و به مبدأ آن در محور زمانی بستگی ندارد.

بدون عواقببه این معنی که تعداد مشتریانی که قبل از زمان t وارد سیستم می شوند تعیین نمی کند که در زمان t + Δt چه تعداد مشتری وارد سیستم می شوند.

به عنوان مثال، اگر در لحظه در یک ماشین بافندگی نخی شکسته شود و توسط بافنده حذف شود، این امر تعیین نمی کند که آیا در لحظه بعد در این ماشین بافندگی گسست جدیدی رخ می دهد یا خیر، بلکه بیشتر از این اتفاق می افتد. بر احتمال شکست در سایر ماشین ها تأثیر نمی گذارد.

یکی از مشخصه های مهم QS زمان سرویس دهی نیازمندی ها در سیستم است. زمان سرویس، به عنوان یک قاعده، یک متغیر تصادفی است و بنابراین، می تواند توسط قانون توزیع توصیف شود. قانون نمایی بیشترین توزیع را در تئوری و به ویژه در کاربردهای عملی داشته است. برای این قانون، تابع توزیع احتمال به شکل زیر است:

F(t) \u003d 1 - e -μt،

آن ها احتمال اینکه زمان سرویس از مقدار معین t تجاوز نکند با فرمول (1 - e -μt) تعیین می شود، که μ پارامتر قانون نمایی زمان خدمات مورد نیاز در سیستم است - متقابل میانگین زمان سرویس، یعنی .

مدل های تحلیلی QS را با انتظار در نظر بگیرید(متداول ترین QS که در آن درخواست های دریافت شده در لحظه ای که همه واحدهای خدماتی مشغول هستند در صف قرار می گیرند و با رایگان شدن واحدهای خدماتی سرویس می شوند).

وظایف با صف در شرایط تولید معمول است، به عنوان مثال، هنگام سازماندهی کار تنظیم و تعمیر، در طول تعمیر و نگهداری چند ماشین و غیره.

بیان مشکل کلی به شرح زیر است.

این سیستم از n کانال سرویس دهی تشکیل شده است. هر یک از آنها می تواند تنها یک درخواست را در یک زمان ارائه دهد. سیستم ساده ترین (پواسون) جریان الزامات را با پارامتر λ دریافت می کند. اگر در لحظه ورود درخواست بعدی در سیستم حداقل n درخواست در سرویس وجود داشته باشد (یعنی همه کانال ها مشغول هستند)، این درخواست وارد صف می شود و منتظر شروع سرویس می ماند.

زمان سرویس هر نیاز t about یک متغیر تصادفی است که از قانون توزیع نمایی با پارامتر μ پیروی می کند.

همانطور که در بالا ذکر شد، QS با انتظار را می توان به دو گروه بزرگ تقسیم کرد: بسته و باز.

ویژگی های عملکرد هر یک از این دو نوع سیستم، سایه خود را بر دستگاه ریاضی مورد استفاده تحمیل می کند. محاسبه ویژگی های عملیات QS در انواع مختلف را می توان بر اساس محاسبه احتمالات حالت های QS (فرمول های Erlang) انجام داد.

از آنجایی که سیستم بسته است، یک شرط باید به بیانیه مشکل اضافه شود: جریان درخواست های دریافتی محدود است، به عنوان مثال. سیستم صف نمی تواند همزمان بیش از m درخواست داشته باشد (m تعداد اشیاء سرویس شده است).

به عنوان معیارهای اصلی مشخص کننده کیفیت عملکرد سیستم مورد بررسی، ما انتخاب می کنیم: 1) نسبت میانگین طول صف به بیشترین تعداد نیازهایی که به طور همزمان در سیستم سرویس دهی وجود دارد - ضریب خرابی شی سرویس شده؛ 2) نسبت میانگین تعداد کانال‌های سرویس‌دهی بی‌حرکت به تعداد کل آنها، نسبت بی‌کاری کانال ارائه‌شده است.

محاسبه ویژگی های احتمالی لازم (شاخص های عملکرد) یک QS بسته را در نظر بگیرید.

1. احتمال وجود k الزامات در سیستم، مشروط بر اینکه تعداد آنها از تعداد دستگاه های سرویس n تجاوز نکند:

P k = α k P 0، (1 ≤ k ≤ n)،

جایی که

λ فرکانس (شدت) دریافت الزامات به سیستم از یک منبع است.

میانگین مدت خدمت یک نیاز؛

m - بیشترین تعداد ممکن نیازهایی که همزمان در سیستم خدمت رسانی وجود دارد.

n تعداد دستگاه های خدماتی است.

P 0 - احتمال رایگان بودن تمام دستگاه های خدماتی.

2. احتمال وجود k الزامات در سیستم، مشروط بر اینکه تعداد آنها بیشتر از تعداد دستگاه های سرویس دهنده باشد:

P k = α k P 0 ، (n ≤ k ≤ m)،

جایی که

3. احتمال رایگان بودن همه سرورها از روی شرط مشخص می شود

در نتیجه،

4. میانگین تعداد درخواست‌های منتظر شروع سرویس (متوسط ​​طول صف):

5. نسبت زمان توقف تقاضا در انتظار خدمات:

6. احتمال اینکه همه دستگاه های سرویس مشغول هستند:

7. میانگین تعداد نیازمندی ها در سیستم خدمات (خدمات و در انتظار خدمت):

8. نسبت کل خرابی مورد نیاز برای سرویس و انتظار برای سرویس:

9. میانگین زمان بیکاری ادعا در صف خدمات:

10. میانگین تعداد مهمانداران رایگان:

11. نسبت خرابی وسایل نقلیه خدماتی:

12. احتمال اینکه تعداد مشتریانی که منتظر سرویس دهی هستند بیشتر از تعداد B باشد (احتمال وجود بیش از B مشتریان در صف خدمات):

در بسیاری از حوزه های اقتصاد، امور مالی، تولید و زندگی روزمره، سیستم هایی که اجرای مکرر وظایفی از یک نوع را اجرا می کنند، نقش مهمی ایفا می کنند. چنین سیستم هایی نامیده می شوند سیستم های نوبت دهی ( CMO ). نمونه هایی از SMO ها عبارتند از: بانک ها در انواع مختلف، سازمان های بیمه، بازرسی های مالیاتی، خدمات حسابرسی، سیستم های ارتباطی مختلف، مجتمع های تخلیه و بارگیری، پمپ بنزین ها، شرکت ها و سازمان های مختلف در بخش خدمات.

3.1.1 اطلاعات کلی در مورد سیستم های صف

هر QS برای ارائه (اجرا) جریان خاصی از برنامه ها (نیازمندی ها) طراحی شده است که در بیشتر موارد نه به طور منظم، بلکه در زمان های تصادفی به ورودی سیستم می رسند. سرویس برنامه ها نیز نه برای یک زمان ثابت و از پیش تعیین شده، بلکه تصادفی است که به دلایل تصادفی زیادی بستگی دارد که گاهی اوقات برای ما ناشناخته است. پس از انجام سرویس درخواست، کانال آزاد شده و آماده دریافت درخواست بعدی می باشد. ماهیت تصادفی جریان برنامه ها و زمان سرویس دهی آنها منجر به بار کاری ناهموار QS می شود. در برخی بازه‌های زمانی، درخواست‌ها می‌توانند در ورودی QS جمع شوند که منجر به اضافه بار QS می‌شود، در حالی که در برخی بازه‌های زمانی دیگر، با کانال‌های رایگان (دستگاه‌های سرویس)، هیچ درخواستی در ورودی QS وجود نخواهد داشت که منجر به زیربار QS می‌شود. یعنی کانال هایش را بیکار کند. برنامه هایی که در ورودی QS انباشته می شوند یا در صف قرار می گیرند یا به دلایلی عدم امکان ماندن بیشتر در صف، QS را بدون سرویس رها می کنند.

شکل 3.1 نمودار QS را نشان می دهد.

عناصر اصلی (ویژگی های) سیستم های صف عبارتند از:

گره خدمات (بلوک)،

جریان برنامه،

دور زدندر انتظار خدمت (انضباط صف).

بلوک خدماتطراحی شده برای انجام اقدامات مطابق با الزامات سیستم ورودی برنامه های کاربردی.

برنج. 3.1 طرح سیستم صف

دومین جزء سیستم های صف، ورودی است جریان برنامهبرنامه ها به صورت تصادفی وارد سیستم می شوند. معمولاً فرض بر این است که جریان ورودی از قانون احتمال مشخصی برای مدت زمان فواصل بین دو درخواست متوالی دریافت شده پیروی می کند و قانون توزیع برای مدتی به اندازه کافی طولانی بدون تغییر در نظر گرفته می شود. منبع برنامه ها نامحدود است.

جزء سوم است نظم صف. این مشخصه ترتیب سرویس درخواست هایی را که به ورودی سیستم می رسند را توصیف می کند. از آنجایی که بلوک سرویس معمولاً ظرفیت محدودی دارد و درخواست‌ها به‌طور نامنظم می‌رسند، به‌طور دوره‌ای صفی از درخواست‌ها در انتظار سرویس ایجاد می‌شود و گاهی اوقات سیستم ارائه‌دهنده در انتظار درخواست‌ها بیکار است.

ویژگی اصلی فرآیندهای صف، تصادفی بودن است. در این مورد، دو طرف تعامل وجود دارد: خدمت و خدمت. رفتار تصادفی حداقل یکی از طرفین منجر به ماهیت تصادفی جریان فرآیند خدمات به عنوان یک کل می شود. منابع تصادفی در تعامل این دو طرف، رویدادهای تصادفی دو نوع هستند.

1. ظاهر یک برنامه کاربردی (نیاز) برای خدمات. دلیل تصادفی بودن این رویداد اغلب ماهیت عظیم نیاز به خدمات است.

2. پایان خدمت درخواست بعدی. دلایل تصادفی بودن این رویداد هم تصادفی بودن شروع سرویس و هم مدت زمان تصادفی خود سرویس است.

این رویدادهای تصادفی یک سیستم از دو جریان را در QS تشکیل می دهند: جریان ورودی درخواست های سرویس و جریان خروجی درخواست های سرویس شده.

نتیجه تعامل این جریان های تصادفی تعداد برنامه های کاربردی در QS در لحظه است که معمولاً به آن می گویند. وضعیت سیستم

هر QS بسته به پارامترهای خود از ماهیت جریان برنامه ها، تعداد کانال های خدمات و عملکرد آنها، بر اساس قوانین سازماندهی کار، دارای کارایی خاصی از عملکرد (ظرفیت) است که به آن اجازه می دهد با موفقیت با جریان برنامه های کاربردی

حوزه ویژه ریاضیات کاربردی نظریه جرمسرویس (TMO)- به تجزیه و تحلیل فرآیندها در سیستم های صف می پردازد. موضوع مطالعه تئوری صف بندی QS می باشد.

هدف از تئوری صف ایجاد توصیه هایی برای ساخت منطقی QS، سازماندهی منطقی کار آنها و تنظیم جریان برنامه ها برای اطمینان از کارایی بالای QS است. برای دستیابی به این هدف، وظایف تئوری صف تعیین می شود که شامل ایجاد وابستگی های کارایی عملکرد QS به سازمان آن است.

وظایف تئوری صف ماهیت بهینه سازی دارند و در نهایت با هدف تعیین چنین گونه ای از سیستم هستند که حداقل هزینه های کل را از انتظار برای سرویس، از دست دادن زمان و منابع برای سرویس، و از واحد خدمات بیکار ارائه می کند. . آگاهی از این ویژگی ها اطلاعاتی را در اختیار مدیر قرار می دهد تا تأثیر مستقیمی بر این ویژگی ها ایجاد کند تا اثربخشی فرآیندهای صف را مدیریت کند.

سه گروه اصلی شاخص های زیر (معمولاً متوسط) معمولاً به عنوان ویژگی های اثربخشی عملکرد QS انتخاب می شوند:

شاخص های اثربخشی استفاده از QS:

توان عملیاتی مطلق QS میانگین تعداد درخواست هایی است که QS می تواند در واحد زمان ارائه دهد.

توان عملیاتی نسبی QS نسبت میانگین تعداد برنامه های ارائه شده توسط QS در واحد زمان به میانگین تعداد برنامه های دریافت شده در همان زمان است.

میانگین مدت دوره استخدام SMO.

نرخ استفاده از QS - میانگین زمان زمانی که QS مشغول سرویس دهی به برنامه ها و غیره است.

شاخص های کیفیت خدمات برنامه:

میانگین زمان انتظار برای یک برنامه در صف.

میانگین زمان اقامت یک درخواست در CMO.

احتمال رد شدن درخواست سرویس بدون انتظار

احتمال اینکه یک درخواست دریافتی بلافاصله برای سرویس پذیرفته شود.

قانون توزیع زمانی که برنامه در صف می ماند.

قانون توزیع زمان صرف شده توسط یک برنامه کاربردی در QS.

میانگین تعداد برنامه های موجود در صف.

میانگین تعداد برنامه های کاربردی در QS و غیره

شاخص های عملکرد جفت "QS - مصرف کننده"، که در آن "مصرف کننده" به معنای کل مجموعه برنامه ها یا برخی از آنها است.

عملکرد یا کارایی سیستم نوبت دهی به شرح زیر است.

برای CMO با شکست:

برای CMO با انتظار نامحدودهر دو خروجی مطلق و نسبی معنای خود را از دست می دهند، زیرا هر درخواست دریافتی دیر یا زود ارائه می شود. برای چنین QS، شاخص های مهم عبارتند از:

برای نوع مختلط CMOهر دو گروه از شاخص ها استفاده می شود: هر دو نسبی و پهنای باند مطلقو ویژگی های انتظار

بسته به هدف عملیات صف بندی، هر یک از شاخص های فوق (یا مجموعه ای از شاخص ها) را می توان به عنوان معیار عملکرد انتخاب کرد.

مدل تحلیلی QS مجموعه ای از معادلات یا فرمول هایی است که امکان تعیین احتمالات حالت های سیستم را در جریان عملکرد آن و محاسبه شاخص های عملکرد بر اساس ویژگی های شناخته شده جریان ورودی و کانال های خدماتی را ممکن می سازد.

هیچ مدل تحلیلی کلی برای QS دلخواه وجود ندارد. مدل های تحلیلی برای تعداد محدودی از موارد خاص QS توسعه یافته است. مدل‌های تحلیلی که کم و بیش دقیق سیستم‌های واقعی را نشان می‌دهند، معمولاً پیچیده و به سختی دیده می‌شوند.

مدل‌سازی تحلیلی QS بسیار تسهیل می‌شود اگر فرآیندهایی که در QS رخ می‌دهند مارکوین باشند (جریان درخواست‌ها ساده است، زمان‌های سرویس به صورت نمایی توزیع شده است). در این حالت، تمام فرآیندها در QS را می توان با معادلات دیفرانسیل معمولی و در حالت محدود، برای حالت های ثابت، با معادلات جبری خطی توصیف کرد و با حل آنها، شاخص های عملکرد انتخاب شده را تعیین کرد.

بیایید نمونه هایی از QS را در نظر بگیریم.

2.5.1. QS چند کاناله با خرابی

مثال 2.5. سه بازرس راهنمایی و رانندگی بارنامه رانندگان کامیون را بررسی می کنند. اگر حداقل یک بازرس آزاد باشد، کامیون عبوری متوقف می شود. اگر همه بازرسان مشغول باشند، کامیون بدون توقف عبور می کند. جریان کامیون ها ساده ترین است، زمان بررسی تصادفی با توزیع نمایی است.

چنین وضعیتی را می توان با یک QS سه کاناله با خرابی (بدون صف) شبیه سازی کرد. سیستم باز، با برنامه های همگن، تک فاز، با کانال های کاملا قابل اعتماد است.

شرح حالات:

همه بازرسان آزاد هستند.

یک بازرس مشغول است.

دو بازرس مشغول هستند.

سه بازرس مشغول هستند.

نمودار وضعیت سیستم در شکل نشان داده شده است. 2.11.

برنج. 2.11.

در نمودار: - شدت جریان کامیون ها. - شدت بررسی اسناد توسط یک بازرس راهنمایی و رانندگی.

شبیه سازی به منظور تعیین بخشی از خودروها انجام شده است که آزمایش نمی شود.

راه حل

قسمت مورد نظر احتمال، احتمال استخدام هر سه بازرس است. از آنجایی که نمودار حالت یک طرح معمولی از "مرگ و تولید مثل" را نشان می دهد، ما با استفاده از وابستگی ها (2.2) خواهیم یافت.

توان عملیاتی این پست بازرسان ترافیک را می توان مشخص کرد توان نسبی:

مثال 2.6. برای دریافت و رسیدگی به گزارشات گروه شناسایی، یک گروه سه نفره از افسران به بخش شناسایی انجمن اعزام شدند. نرخ مورد انتظار گزارش 15 گزارش در ساعت است. میانگین زمان پردازش یک گزارش توسط یک افسر است. هر افسر می تواند از هر گروه شناسایی گزارش دریافت کند. افسر آزاد شده آخرین گزارش های دریافتی را پردازش می کند. گزارش های دریافتی باید با احتمال حداقل 95 درصد پردازش شوند.

تعیین کنید که آیا گروه سه افسر تعیین شده برای انجام وظیفه محول شده کافی است یا خیر.

راه حل

گروهی از افسران به عنوان CMO با شکست، متشکل از سه کانال کار می کنند.

جریان گزارش ها با شدت را می توان ساده ترین در نظر گرفت، زیرا مجموع چندین گروه شناسایی است. شدت نگهداری . قانون توزیع ناشناخته است، اما این ضروری نیست، زیرا نشان داده شده است که برای سیستم های دارای خرابی می تواند دلخواه باشد.

شرح حالات و نمودار وضعیت QS مشابه موارد ارائه شده در مثال 2.5 خواهد بود.

از آنجایی که نمودار حالت یک طرح "مرگ و بازتولید" است، عبارات آماده ای برای احتمالات حالت محدود برای آن وجود دارد:

رابطه نامیده می شود کاهش شدت جریان برنامه ها. معنای فیزیکی آن به شرح زیر است: مقدار میانگین تعداد درخواست‌هایی است که برای میانگین زمان سرویس یک درخواست به QS می‌آیند.

در مثال .

در QS در نظر گرفته شده، شکست زمانی رخ می دهد که هر سه کانال مشغول باشند، یعنی . سپس:

زیرا احتمال شکستدر پردازش گزارش ها بیش از 34٪ () است، پس باید پرسنل گروه را افزایش داد. اجازه دهید ترکیب گروه را دو برابر کنیم، یعنی QS اکنون شش کانال خواهد داشت و محاسبه می کنیم:

بنابراین، تنها یک گروه شش نفره از افسران قادر به پردازش گزارش های دریافتی با احتمال 95٪ خواهند بود.

2.5.2. QS چند کاناله با انتظار

مثال 2.7. 15 گذرگاه از همین نوع در بخش اجباری رودخانه وجود دارد. جریان وسایل نقلیه وارد شده به گذرگاه به طور متوسط ​​1 واحد در دقیقه است، میانگین زمان عبور از یک واحد تجهیزات 10 دقیقه است (با در نظر گرفتن بازگشت تسهیلات عبور).

ویژگی های اصلی گذرگاه، از جمله احتمال عبور فوری بلافاصله پس از رسیدن یک قطعه تجهیزات را ارزیابی کنید.

راه حل

پهنای باند مطلق، یعنی هر چیزی که به گذرگاه می رسد تقریباً بلافاصله عبور می کند.

میانگین تعداد گذرگاه های عملیاتی:

نسبت های استفاده متقاطع و خرابی:

برنامه ای نیز برای حل مثال ایجاد شد. فواصل زمانی برای رسیدن تجهیزات به گذرگاه، زمان عبور طبق قانون نمایی توزیع می شود.

نرخ استفاده از کشتی پس از 50 بار در عمل یکسان است: .

مقدمه

فصل اول. شکل‌گیری مشکلات خدمات صف

1.1 مفهوم کلی تئوری صف

1.2 مدل سازی سیستم های صف

1.3 نمودارهای وضعیت QS

1.4 فرآیندهای تصادفی

فصل دوم. معادلات توصیف سیستم های صف

2.1 معادلات کولموگروف

2.2 فرآیندهای "تولد - مرگ"

2.3 فرمول بندی اقتصادی و ریاضی مسائل صف

فصل سوم. مدل های سیستم های نوبت دهی

3.1 QS تک کاناله با انکار سرویس

3.2 QS چند کاناله با انکار سرویس

3.3 مدل سیستم خدمات گردشگری چند فازی

3.4 QS تک کاناله با طول صف محدود

3.5 QS تک کاناله با صف نامحدود

3.6 QS چند کاناله با طول صف محدود

3.7 QS چند کاناله با صف نامحدود

3.8 تجزیه و تحلیل سیستم صف سوپرمارکت

نتیجه

مقدمه

در حال حاضر، حجم زیادی از ادبیات ظاهر شده است که به طور مستقیم به تئوری صف، توسعه جنبه های ریاضی آن، و همچنین زمینه های مختلف کاربرد آن - نظامی، پزشکی، حمل و نقل، تجارت، هوانوردی و غیره اختصاص دارد.

نظریه صف بر اساس نظریه احتمال و آمار ریاضی است. توسعه اولیه تئوری صف با نام دانشمند دانمارکی A.K. ارلنگ (1878-1929) با آثار خود در زمینه طراحی و راه اندازی مبادلات تلفنی.

تئوری صف رشته ای از ریاضیات کاربردی است که به تجزیه و تحلیل فرآیندها در سیستم های تولید، خدمات و کنترل می پردازد که در آن رویدادهای همگن بارها تکرار می شوند، به عنوان مثال، در شرکت های خدمات مصرف کننده. در سیستم های دریافت، پردازش و انتقال اطلاعات؛ خطوط تولید اتوماتیک و غیره کمک بزرگی به توسعه این نظریه توسط ریاضیدانان روسی A.Ya. خینچین، بی.وی. گندنکو، A.N. کولموگروف، E.S. ونتزل و دیگران.

موضوع تئوری صف ایجاد روابط بین ماهیت جریان درخواست ها، تعداد کانال های سرویس، عملکرد یک کانال واحد و سرویس کارآمد به منظور یافتن بهترین راه ها برای کنترل این فرآیندها است. وظایف تئوری صف ماهیت بهینه سازی دارند و در نهایت جنبه اقتصادی تعیین چنین گونه ای از سیستم را شامل می شوند که حداقل هزینه کل را از انتظار برای سرویس، از دست دادن زمان و منابع برای سرویس و از کار افتادن فراهم می کند. از کانال های خدماتی

در فعالیت های تجاری، کاربرد تئوری صف هنوز توزیع مطلوبی را پیدا نکرده است.

این عمدتاً به دلیل دشواری تعیین اهداف، نیاز به درک عمیق محتوای فعالیت های تجاری و همچنین ابزارهای قابل اعتماد و دقیق است که امکان محاسبه گزینه های مختلف برای پیامدهای تصمیمات مدیریتی در فعالیت های تجاری را فراهم می کند.

فصل من . تنظیم وظایف صف

1.1 مفهوم کلی تئوری صف

ماهیت صف بندی در زمینه های مختلف بسیار ظریف و پیچیده است. فعالیت تجاری با انجام بسیاری از عملیات در مراحل حرکت همراه است، به عنوان مثال، انبوهی از کالاها از حوزه تولید تا حوزه مصرف. چنین عملیاتی عبارتند از بارگیری کالا، حمل و نقل، تخلیه، ذخیره سازی، پردازش، بسته بندی، فروش. علاوه بر این گونه عملیات اساسی، فرآیند جابجایی کالا با تعداد زیادی عملیات مقدماتی، مقدماتی، همراه، موازی و بعدی با اسناد پرداخت، کانتینر، پول، خودرو، مشتریان و ... همراه است.

بخش های ذکر شده از فعالیت تجاری با دریافت انبوه کالاها، پول، بازدیدکنندگان در زمان های تصادفی، سپس خدمات ثابت آنها (اجرای نیازها، درخواست ها، درخواست ها) با انجام عملیات مناسب مشخص می شود که زمان اجرای آن نیز تصادفی است. همه اینها باعث ایجاد ناهمواری در کار، ایجاد بارهای کم، خرابی و اضافه بار در عملیات تجاری می شود. صف‌ها دردسرهای زیادی را ایجاد می‌کنند، به عنوان مثال، بازدیدکنندگان در کافه‌ها، غذاخوری‌ها، رستوران‌ها یا رانندگان خودرو در انبارهای کالا، منتظر تخلیه، بارگیری یا کاغذبازی هستند. در این راستا، وظایف تجزیه و تحلیل گزینه های موجود برای انجام کل مجموعه عملیات، به عنوان مثال، طبقه تجاری یک سوپرمارکت، یک رستوران، یا در کارگاه های تولید محصولات خود به منظور ارزیابی کار آنها، شناسایی وجود دارد. پیوندهای ضعیف و ذخایر، و در نهایت توسعه توصیه هایی با هدف افزایش کارایی عملیات تجاری.

علاوه بر این، وظایف دیگری مربوط به ایجاد، سازماندهی و برنامه ریزی یک گزینه اقتصادی و منطقی جدید برای انجام بسیاری از عملیات در طبقه تجاری، شیرینی فروشی، کلیه سطوح خدمات یک رستوران، کافه، غذاخوری، بخش برنامه ریزی، بخش حسابداری، بخش پرسنل و غیره

وظایف سازمان صف تقریباً در تمام حوزه های فعالیت انسانی مطرح می شود، به عنوان مثال، خدمات رسانی به خریداران در فروشگاه ها توسط فروشندگان، خدمات رسانی به بازدیدکنندگان در موسسات پذیرایی عمومی، خدمات رسانی به مشتریان در شرکت های خدمات مصرف کننده، ارائه مکالمات تلفنی در یک مرکز تلفن، ارائه مراقبت های پزشکی بیماران در یک کلینیک و غیره. در تمام مثال های فوق نیاز به ارضای نیازهای تعداد زیادی از مصرف کنندگان وجود دارد.

وظایف فهرست شده را می توان با استفاده از روش ها و مدل های تئوری صف (QMT) که مخصوص این اهداف ایجاد شده است، با موفقیت حل کرد. این تئوری توضیح می‌دهد که لازم است به کسی یا چیزی خدمات داده شود، که با مفهوم «درخواست (نیاز) برای سرویس» تعریف می‌شود، و عملیات سرویس توسط شخص یا چیزی به نام کانال‌های سرویس (گره‌ها) انجام می‌شود. نقش اپلیکیشن ها در فعالیت های تجاری را کالاها، بازدیدکنندگان، پول، حسابرسان، اسناد و مدارک و نقش کانال های خدماتی را فروشندگان، مدیران، آشپزها، قنادی ها، پیشخدمت ها، صندوقداران، بازرگانان، لودرها، تجهیزات تجاری و غیره ایفا می کنند. توجه به این نکته حائز اهمیت است که در یک نوع، به عنوان مثال، آشپز در فرآیند تهیه ظروف، یک کانال خدماتی است و در نوع دیگر، به عنوان درخواست خدمات، به عنوان مثال، به مدیر تولید برای دریافت کالا عمل می کند.

به دلیل ماهیت انبوه دریافت خدمات، برنامه‌ها جریان‌هایی را تشکیل می‌دهند که قبل از انجام عملیات سرویس‌دهی، ورودی نامیده می‌شوند و پس از انتظار احتمالی برای شروع سرویس، یعنی. خرابی در صف، سرویس فرم در کانال ها جریان می یابد و سپس یک جریان خروجی از درخواست ها تشکیل می شود. به طور کلی، مجموعه ای از عناصر جریان ورودی برنامه ها، صف، کانال های خدمات و جریان خروجی برنامه ها ساده ترین سیستم صف بندی تک کانالی - QS را تشکیل می دهد.

یک سیستم مجموعه ای از به هم پیوسته و. قطعات (عناصر) که به طور هدفمند در تعامل هستند. نمونه هایی از چنین QS ساده در فعالیت های تجاری، مکان های دریافت و پردازش کالا، مراکز تسویه حساب با مشتریان در مغازه ها، کافه ها، غذاخوری ها، مشاغل یک اقتصاددان، حسابدار، تاجر، آشپز در هنگام توزیع و غیره است.

هنگامی که درخواست سرویس از سیستم خارج می شود، روال سرویس تکمیل شده در نظر گرفته می شود. مدت زمان فاصله زمانی لازم برای اجرای رویه سرویس عمدتاً به ماهیت درخواست خدمات، وضعیت خود سیستم خدمات و کانال سرویس بستگی دارد.

در واقع، مدت اقامت خریدار در سوپرمارکت از یک طرف به ویژگی های شخصی خریدار، درخواست های او، به محدوده کالایی که قصد خرید دارد و از طرف دیگر به فرم بستگی دارد. سازمان خدمات و متصدیان، که می تواند به طور قابل توجهی بر زمان صرف شده توسط خریدار در سوپرمارکت و شدت خدمات تأثیر بگذارد. به عنوان مثال، صندوقدار-کنترل کننده هایی که به روش "کور" کار بر روی صندوق پول تسلط داشتند، این امکان را فراهم کردند که توان عملیاتی گره های تسویه را 1.3 برابر افزایش دهند و در زمان صرف شده برای تسویه حساب با مشتریان در هر صندوق بیش از 1.5 ساعت در روز صرفه جویی کنند. . معرفی یک گره تسویه حساب در سوپرمارکت مزایای ملموسی به خریدار می دهد. بنابراین، اگر با شکل سنتی شهرک ها، زمان خدمات برای یک مشتری به طور متوسط ​​1.5 دقیقه بود، سپس با معرفی یک گره تسویه حساب - 67 ثانیه. از این تعداد 44 ثانیه صرف خرید در قسمت و 23 ثانیه به صورت مستقیم صرف پرداخت برای خرید می شود. اگر خریدار چندین خرید در بخش های مختلف انجام دهد، با خرید دو خرید 1.4 برابر، سه - 1.9، پنج - 2.9 برابر، از دست دادن زمان کاهش می یابد.

منظور ما از خدمات دهی به درخواست، فرآیند برآوردن نیاز است. ماهیت خدمات متفاوت است. با این حال، در همه نمونه‌ها، درخواست‌های دریافت‌شده باید توسط برخی دستگاه‌ها سرویس شوند. در برخی موارد خدمات توسط یک نفر (خدمات مشتری توسط یک فروشنده، در برخی موارد توسط گروهی از افراد (خدمات بیمار توسط کمیسیون پزشکی در پلی کلینیک) و در برخی موارد توسط دستگاه های فنی (فروش آب سودا) انجام می شود. مجموعه ای از ابزارهایی که به برنامه های کاربردی سرویس می دهند، کانال سرویس نامیده می شود.

اگر کانال های سرویس قادر به برآورده کردن همان درخواست ها باشند، کانال های سرویس همگن نامیده می شوند. به مجموعه ای از کانال های خدماتی همگن، سیستم سرویس دهی می گویند.

سیستم نوبت دهی تعداد زیادی درخواست را در زمان های تصادفی دریافت می کند که مدت زمان سرویس آن نیز یک متغیر تصادفی است. ورود متوالی مشتریان به سیستم نوبت دهی، جریان ورودی مشتریان و به ترتیب خروج مشتریان از سیستم صف، جریان خروجی نامیده می شود.