נוסחת קינגמן

נוסחת קינגמן, בתורת התורים, היא נוסחה המספקת קירוב למודל תורים מסוג G/G/1. מודל תורים מסוג זה מציין, לפי סימון קנדל, מודל כללי בעל שרת יחיד ותור אינסופי. G/G/1 מתאר מערכת בעלת מופע לקוחות שלו התפלגות כללית כלשהי, תהליך שירות עם התפלגות כללית כלשהי, שרת יחיד ותור אינסופי, הפועל על פי מודל FCFS, נכנס ראשון יוצא ראשון. הנוסחה מאפשרת מציאת קירוב לתוחלת זמן ההמתנה בתור. כלומר, מציאת משך זמן ההמתנה הממוצע של לקוח, מרגע כניסתו לתור ועד לתחילת קבלת השירות. הנוסחה הוצגה לראשונה בשנת 1966 על ידי ג'ון קינגמן, במאמרו "On the Algebra of Queues", והיא נחשבת לקירוב טוב עבור מערכת העובדת בנצילות גבוהה.

הנוסחה

הנוסחה שהציג קינגמן הייתה זו:

$\mathbb {E} (W_{q})\approx \left({\frac {\rho }{1-\rho }}\right)\left({\frac {c_{a}^{2}+c_{s}^{2}}{2}}\right)\tau$

כאשר:

• $\tau$ הוא זמן השירות הממוצע ($\mu =1/\tau$ הוא קצב השירות הממוצע)
• $\lambda$ הוא קצב המופע של לקוחות חדשים במערכת
• $\rho =\lambda \tau =\lambda /\mu$ הוא נצילות השרת במערכת
• c_a הוא קבוע השונות של תהליך מופע הלקוחות (כלומר סטיית התקן של משך הזמן בין מופע למופע חלקי משך הזמן הממוצע בין מופע למופע)
• c_s הוא קבוע השונות למשך השירות (כלומר סטיית התקן למשך השירות חלקי משך השירות הממוצע)

הנוסחה היא מכפלתם של שלושה איברים התלויים בנצילות השרת, בשונות הזמנים במערכת ובמשך השירות בהתאמה. הנוסחה מבטאת הנחות אינטואיטיביות לגבי משך ההמתנה, שמשכו ארוך יותר ככל שנצילות השרת עולה, ככל שהשונות במשך הזמן בין המופעים או בזמן השירות עולה וככל שמשך השירות הממוצע עולה (בהתאמה לאיברים השונים במכפלה).

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

21351828נוסחת קינגמן