مرتضی رجب زاده - استادیار، دانشکده مهندسی، مرکز آموزش عالی محالت، محالت، ایران.
امین محمدنژاد - محقق، دانشکده مهندسی، مرکز آموزش عالی محالت، محالت، ایران.
کوروش عشقی - استاد، دانشکده مهندسی صنایع، دانشگاه صنعتی شریف، تهران، ایران

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

رنگ آمیزی جمعی گراف، مجموعه مستقل رئوس گراف ، الگوریتم فراابتکاری