חוק ליטל

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

חוק ליטל (Little's law) הוא חוק יסודי בתורת התורים הסטטיסטית, הקובע שבמערכת יציבה, המספר הממוצע של הלקוחות (\ E(N)) שווה לקצב ההגעה הממוצע שלהם (\ \lambda ), כשהוא מוכפל בזמן הממוצע שהלקוחות מבלים במערכת (\ E(T)), דהיינו \, E(N)= \lambda E(T). בפרט, גורמים אחרים אינם יכולים להשפיע על המערכת.

את החוק, הידוע גם כמשפט ליטל, או התוצאה של ליטל, הוכיח ג'ון ליטל בשנת 1961.

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

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

דוגמה[עריכת קוד מקור | עריכה]

בחנות קטנה יש אזור מדפים לעיון במוצרים, ודלפק מכירה שיש בו מקום לאדם אחד בלבד. כל לקוח עובר את אותו מסלול:

כניסה ← עיון ← דלפק ← יציאה

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

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

דוגמאות נוספות ניתן למצוא בפתרון מודלים שונים לתורים, ובפרט בפשוט ביותר מביניהם, תור M/M/1 ותור M/M/c.