Graph multi-coloring for a job scheduling application

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