قانون لیتل

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

قانون یا فرمول لیتل (به انگلیسی: 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

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

منابع[ویرایش]

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