چگونه یک بازی بیلیارد حل مشکل صف

"لطفا از خط نگه دارید، پاسخ شما برای ما مهم است." این یک جمله ما همه ناامید کننده با آن آشنا است. فقط به عنوان آشنا که ما با ایستادن در صف در سوپر مارکت و یا پست اداری، با صف های دیگر به نظر می رسد به حرکت بسیار سریع تر از یکی از ما اتفاق می افتد به در باشد. وشبختانه، ریاضیات کمک می کند. صف مطالعات تئوری چنین شرایطی ریاضی، و تلاش می کند تا پیدا کردن راه حل که به حداقل رساندن زمان متوسط ​​انتظار مشتری در حالی که همچنین محدود کردن زمان متوسط ​​سرور صف بیکار باقی مانده است. این محدودیت دو باعث می شود مشکل یک مشکل. یک منبع اضافی از دشواری اتفاقی درگیر است. مشتریان معمولا در فواصل منظم می رسد نیست، اما زمان ورود خود آنچه که به نام فرایند تصادفی . در آینده با یک فرمول کلی فراهم می کند که یک راه حل برای چنین مشکلاتی تصادفی به طور کلی دشوار است، و گاهی اوقات حتی غیر ممکن است. اخیرا عموی من که Arie Hordijk و من، همراه با برند Heidergott دانشگاه VU آمستردام، چنین مشکلی صف مطالعه قرار گرفت. این اغلب در مراکز تماس، که در آن تماس گیرنده ورودی باید به یکی از چندین صف انتظار که، برای مثال، توزیع بیش از مکان های مختلف اختصاص داده می شود رخ می دهد. مشکل خاصی که ما مورد مطالعه قرار هیچ راه حل تحلیلی شناخته شده ای ندارد - است که، یک فرمول کلی ریاضی برای حل آن وجود ندارد. ما بدترین حالت که در آن هیچ اطلاعات موجود در مورد وضعیت فعلی سیستم، مانند چه مدت هر مشتری قبلا از انتظار در صف های مربوطه خود را در نظر گرفته. در شرایط عملی ممکن است برخی از چنین اطلاعاتی در دسترس وجود دارد، اما اغلب این اطلاعات ناقص است، و یا یک تاخیر قابل توجه در به روز رسانی آن (به خصوص در مراکز توزیع) وجود دارد. بنابراین، با فرض عدم اطلاعات در تمام نقطه شروع مفید از نقطه نظر ریاضی است. در چنین وضعیتی ممکن به نظر می رسد که بهترین استراتژی است که به سادگی اختصاص ورود مشتریان به صف انتظار در دسترس به طور تصادفی. این در واقع راه حل استاندارد است که در این موارد استفاده می شود. آنچه که اکنون نشان داده شده است، هر چند، این است که با استفاده از یک استراتژی انتساب قطعی (که شده است، زیر یک قاعده از پیش تعیین شده)، به جای یک تصادفی، متوسط ​​و ضوابط زمان انتظار در واقع می تواند به طور قابل توجهی کاهش می یابد. این ممکن است به نظر می رسد متضاد، با توجه به اینکه سیستم خود رفتار تصادفی. با این حال، با استفاده از یک استراتژی تخصیص مشتری خاص بر اساس توالی بیلیارد به اصطلاح، آن را ممکن است برای بهبود در تکالیف تصادفی استاندارد. توپ در حال حرکت بر روی یک میز بیلیارد. دنباله بیلیارد مربوطه شروع می شود 2122. تصور کنید یک میز بیلیارد تنها با یک توپ بر روی آن و جیب. همچنین فرض کنیم که توپ هیچ اصطکاک تجربه نمی کنند. حالا ضربه زدن به توپ (در یک جهت داده)، و نوشتن در هر زمان 1 توپ بازدید یکی از دو طرف کوتاه تر از جدول و 2 هر بار از آن بازدید یکی از دو طرف دیگر از جدول. از آنجا که هیچ اصطکاک وجود دارد، توپ در حال حرکت ادامه خواهد داد، و ظهور یک توالی طولانی از 1s و 2S. دنباله ساخته شده در این (قطعی) راه باشد، توالی بیلیارد نامیده می شود. تغییر (نسبی) طول از طرف جدول، و یا به سادگی انتخاب یک مسیر مختلف برای ضربه اولیه، نتایج در یک توالی بیلیارد متفاوت است. (توجه داشته باشید که ما یک میز بیلیارد واقعی نیاز به آمده تا با یک توالی بیلیارد: ما می توانیم آن را با استفاده از موقعیت شروع و جهت توپ و محاسبه قانون بازتاب .) ریاضی همان روش را می توان برای میز بیلیارد از بیش از دو بعد است. یک میز بیلیارد سه بعدی است اساسا یک جعبه است که توپ تندرست اطراف در داخل آن. ما فرض می کنیم هیچ جاذبه وجود دارد، به طوری که توپ به سادگی سقوط، اما همچنان قوی بین دو طرف از جعبه. سه جفت از طرف مقابل وجود دارد و ما می توانیم این جفت با شماره های 1، 2 و 3. توپ در حال حرکت در حال حاضر تولید دنباله از 1S، 2S و 3S ساخته شده برچسب. اگر چه ما می توانید آن را تجسم نیست، ما ریاضی می توانید تعریف یک جعبه بعدی N، و به این ترتیب یک توالی بیلیارد از اعداد 1 تا N به. توپ در حال حرکت در یک میز بیلیارد 3D، که در این مثال اتفاق می افتد به یک مکعب. اگر شما برچسب در بالا و پایین با یک جلو 1 مواجه است و تماس با آن مواجه با 2 و دو چهره دیگر با 3، مسیر توپ دنباله بیلیارد تعریف می کند. استراتژی تخصیص مشتری بر اساس یک دنباله بیلیارد حال حاضر به سادگی اختصاص هر یک از مشتریان ورودی بعدی به صف انتظار نشان داده شده با عدد بعدی در این رشته بیلیارد. ما شبیه سازی کامپیوتری از یک سیستم (تصادفی) ورود مشتری با ده (10 نفر) صف انتظار در دسترس انجام، یا با استفاده از یک استراتژی تخصیص مشتری کاملا تصادفی، و یا یکی بر اساس یک دنباله بیلیارد. این شبیه سازی به وضوح نشان می دهد که با یک توالی بیلیارد مناسب، متوسط ​​زمان انتظار مشتری می تواند در واقع می تواند به شدت کاهش می یابد. (ما تجزیه و تحلیل آماری به مطمئن شوید که برابر بهتر انتظار فقط یک اتفاق نیست انجام می شود.) مشکل اصلی این است برای پیدا کردن چنین دنباله بیلیارد مناسب (طول نسبی یعنی مناسب از طرف میز بیلیارد). برای این کار، ما با استفاده از الگوریتم ژنتیک ، یک برنامه کامپیوتری که شبیه تکامل طبیعی، به معنای واقعی کلمه در حال تحول راه حل بهتر و بهتر برای یک مشکل داده شده است. با استفاده از این روش محاسباتی، ما قادر به پیدا کردن توالی بیلیارد که گاهی اوقات حتی قطع متوسط ​​زمان انتظار مشتری در نیمه نسبت به تکالیف تصادفی استاندارد بود. ما پس از آن نیز محدودیت های اضافی، مانند توزیع عادلانه حجم کار بیش از ده سرور صف، و یا اجازه می دهد تنها توالی بیلیارد متشکل از یک توالی نسبتا کوتاه (اما تکرار) در نظر گرفته. در این موارد آن را نیز ممکن است برای پیدا (با استفاده از الگوریتم ژنتیک) توالی بیلیارد مناسب است که در مقایسه با تکالیف تصادفی طور قابل توجهی کاهش میانگین زمان مشتری انتظار. این نتایج تعجب آور اما بسیار مفید، که رسما به نمایندگی دستاورد علمی نهایی عموی من که Arie Hordijk، در یک مقاله مشترک در مجله آسیا و اقیانوس آرام از پژوهش عملیاتی منتشر شد. با بیش از 170 انتشارات ، پنج کتاب و یک مسئله خاص از مجله علمی روش های ریاضی تحقیق در عملیات برای تولد 65 خود را به او اختصاص داده شده، عموی من یک ریاضیدان شناخته شده است. این افتخار بزرگی است که یک همکاری نویسنده در چه خواهد بود، آخرین انتشارات علمی او است. نتیجه ما به وضوح نشان میدهد که چگونه یک ایده ساده را بر اساس یک بازی محبوب، هنگامی که در یک محیط ریاضی مناسب استفاده می شود، می توانید راه حل برای مشکلات ما با به صورت روزانه مواجه فراهم می کند. علاوه بر این، یک نمونه عالی از قدرت همکاری میان رشته ای است. ترکیب دانش نظری دو ریاضیدانان با مهارت های عملی از یک دانشمند کامپیوتر است به یک راه حل قابل توجهی بهبود یافته برای یک مشکل در نظریه صف بندی شد. و نه برخی از سخت به درک راه حل نظری، اما یکی که به راحتی می توان در عمل اجرا شود. پس از همه، پاسخ خود را واقعا برای ما مهم است!مبنع:https://plus.maths.org/content/how-game-billiards-solved-queueing-problem