A branch-and-price algorithm for the Aperiodic Multi-Period Service Scheduling Problem

در این مقاله، مسئله برنامه ریزی سرویس چند دوره ای با یک سیاست سرویس آپریدی مطرح می شود. در این مشکل، مجموعه ای از مشتریانی که به طور دوره ای نیاز به خدمات در طول افق زمانی محدود دارند، داده می شود. برای برآوردن نیازهای خدماتی، مجموعه ای از اپراتورها داده می شود، هر کدام با ظرفیت ثابت از لحاظ تعداد مشتریانی که می توانند در هر دوره خدمت کنند. با یک سیاست تقریبی، مشتریان ممکن است در خدمت قبل از دوره سرویس باشد. در این مسئله دو معیار در نظر گرفته شده است: تعداد کل اپراتورها و تعداد کل دوره های پیش از زمان. وظیفه این است که دوره سرویس را برای هر مشتری تعیین کنید تا درخواست های سرویس مشتریان انجام شود و هر دو معیار به حداقل برسد. فرمول برنامه ریزی عدد صحیح جدید پیشنهاد شده است که از یک فرمول موجود بهتر است. از آنجا که تلاش های محاسباتی مورد نیاز برای به دست آوردن راه حل ها با اندازه نمونه افزایش می یابد، ما همچنین اصلاح فرمول مناسب برای تولید ستون را ارائه می دهیم که در الگوریتم شاخه و قیمت یکپارچه شده است. آزمایش های محاسباتی، کارایی این الگوریتم را برای نمونه های بزرگ تر نشان می دهد.