قانون لیتل

قانون یا فرمول لیتل (به انگلیسی: Little's law) قضیه‌ای است که توسط جان لیتل (john little) نوشته شده‌است و در نظریه صف کاربرد دارد و بیان می‌کند که:

تعداد میانگین مشتری‌ها در درازمدت در یک سیستم پایدار L برابر است با میانگین نرخ ورود مؤثر در درازمدت λ ضربدر میانگین زمان حضور مشتری در سیستم W یا به زبان جبری : L = λW. بسیار قابل توجه است که این رابطه تحت تأثیر توزیع فرایند ورودی یا توزیع فرایند خدمت یا سفارش خدمت و عملاً هیچ عامل دیگری نیست. نتیجه به تمامی سیستم‌ها به ویژه سیستم‌های داخلی سیستم‌ها (زیرسیستم‌ها) قابل اعمال است. بنابراین در یک بانک خط مشتری‌ها می‌تواند یک زیرسیستم باشد و خود بانک هم می‌تواند یک زیرسیستم باشد و قانون لیتل می‌تواند به هر یک از آن‌ها همانند کل سیستم اعمال شود. تنها شرط برای اعمال این قانون پایدار و غیر پیشگیرانه بودن سیستم است که از حالت‌گذار مانند مقداردهی اولیه در موقع روشن یا خاموش شدن جلوگیری می‌کند. در برخی موارد به‌طور ریاضی وار ممکن است که نه تنها میانگین تعداد در یک سیستم به میانگین انتظار مربوط باشد بلکه توزیع احتمال کل تعداد نیز در یک سیستم به انتظار مربوط شود.

تاریخچه

در سال ۱۹۸۴ قانون لیتل به‌طور فرضی درست در نظر گرفته شده بود و بدون اثبات از آن استفاده می‌شد. فرمL = λW نخست توسط فیلیپ ام. مورس انتشار یافت؛ در هنگامی که او خوانندگان را برای یافتن موقعیتی که در آن این رابطه صدق نکند به چالش کشیده بود. در سال ۱۹۶۱ لیتل اثبات خود را برای این رابطه منتشر کرد که نشان می‌داد هیچ موقعیتی وجود ندارد که این رابطه در آن صدق نکند. اثبات لیتل با نوع ساده‌تری توسط jewell ادامه یافت و بعداً نسخه ساده‌تری نیز توسط Eilon منتشر شد. Shaler Stidham یک نسخه با درکی بهتر و مستقیم تر از اثبات را در سال ۱۹۷۲ منتشر کرد.

مثال

یک فروشگاه کوچک با یک باجه و یک محل برای جستجو را در نظر بگیرید که تنها یک فرد در هر زمان واحد می‌تواند باجه را در اختیار داشته باشد و هیچ کس بدون خرید جنس خارج نمی‌شود پس تقریباً در این سیستم روند زیر را داریم:

ورود ← جستجو ← باجه ← خروج

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

قانون لیتل به ما می‌گوید که تعداد میانگین مشتری‌ها در فروشگاه L همان نرخ ورود مؤثر λ ضرب در میانگین زمانی است که هر مشتری در سیستم صرف می‌کند یعنی W یعنی به عبارت ساده‌تر: L = λW

فرض کنید مشتری‌ها با نرخ ۱۰ مشتری در ساعت به فروشگاه وارد می‌شوند و به‌طور میانگین ۰٫۵ ساعت در سیستم می‌مانند. این به آن معنی است که تعداد میانگین مشتریان حاضر در فروشگاه در هر زمان برابر ۵ است.

حال فرض کنید که این فروشگاه با افزایش تبلیغات قصد افزایش نرخ ورودی به ۲۰ مشتری در ساعت را دارد. فروشگاه همچنین باید آماده میزبانی ۱۰ ساکن را داشته باشد یا زمان حضور هر مشتری در فروشگاه را به ۰٫۲۵ ساعت کاهش دهد. فروشگاه می‌تواند برای رسیدن به مورد دوم بیشتر صدای زنگ فروشگاه را به صدا در آورد یا تعداد باجه‌ها را افزایش دهد.

ما می‌توانیم قانون لیتل را به سیستم داخلی فروشگاه اعمال کنیم. برای مثال این کار را برای باجه و صف انجام دهیم. فرض کنید ما می‌دانیم به‌طور متوسط ۲مشتری در صف و باجه وجود دارد. ما می‌دانیم نرخ ورودی ۱۰ مشتری در ساعت است پس مشتری‌ها باید به‌طور میانگین ۰٫۲ ساعت باجه را به امانت بگیرند.

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

برنامه‌های کاربردی

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

Software Infrastructure Bottlenecks in J2EE by Deepak Goel

Benchmarking Blunders and Things That Go Bump in the Night by Neil Gunther

برنامه‌های دیگری نیز شامل نیروی انسانی در بخش اورژانس در بیمارستان‌ها وجود دارد.

منابع

• ویکی‌پدیا انگلیسی