محمدرضا اکبری - دانشیار دانشکده مهندسی صنایع دانشگاه صنعتی شریف
علی شجاع سنگچولی - دانشجوی کارشناسی ارشد مهندسی صنایع گرایش سیستم های اقتصادی اجتماعی
محسن قره خانی - دانشجوی کارشناسی ارشد مهندسی صنایع گرایش مهندسی صنایع دانشگاه صنعتی

یکی از مهمترین روشهای حل مساله چیدمان، روش نظریه گراف است. در این روش ما تجهیزات را با گره‌ها و مطلوبیت همسایگی بین آنها را با یال‌های وزن‌دار نشان می‌دهیم. برای اینکه بیشترین تعداد همسایگی و بیشترین وزن را داشته باشیم ما بدنبال تولید گراف ماکزیمم وزنی مسطح (MPWG) هستیم. مسئله‌ی WMPG کاربرد زیادی در سیستم‌های تولید جدید دارد. این مسئله NP-Hard می‌باشد و با توجه به عدم وجود یک الگوریتم زمان ـ چند جمله‌ای که آن را به طور دقیق حل کند این موضوع همچنان تلاش‌ها و تحقیقات زیادی را در رویکردهای تقریبی می‌طلبد. در این مقاله یک الگوریتم شاخه و کران برای حل این مساله ارائه خواهد شد.

الگوریتم شاخه و کران، مساله گراف ماکزیمم وزنی مسطح، چیدمان تجهیزات