مدل سازي و حل تحليلي مساله برنامه ريزي ظرفيت و زمانبنـدي توليد يكپارچه: استخراج كران پايين و طراحي يك الگوريتم شاخه و كران كارا

Modeling and Analytical Solution of Integrated Scheduling and Capacity Planning Problem: Lower Bounds and Efficient Branch and Bound Algorithm

برنامه ريزي ظرفيت توليد و زمانبندي توليد جزيي از فرآيند تصميم گيري در زنجيره تامين بسياري از صنايع ساخت و خدماتي محسوب مي شوند كه نقش مهمي را در برآورده سازي نيازهاي مشتريان و ارتقاي سطح خدمت دهي به مشتريان ايفا مي نمايند. از آنجاييكه اين دو فرآيند در دو سطح متفاوت از زنجيره تامين عمل مي نمايند (برنامه ريزي ظرفيت در سطح تاكتيكي و زمانبندي توليد در سطح عملياتي)، لذا معمولاً تصميمات مربوط به اين دو حيطه نيز مستقلاً و جداي از هم اتخاذ مي شود. در چنين شرايطي شدني بودن تخصيص ظرفيت انجام شده در سطح تاكتيكي، زمانيكه برنامه بصورت عملياتي وارد كارگاه مي شود، به عنوان يكي از چالش هاي اصلي اين رويكرد تصميم گيري مجزا، مطرح است. لذا در اين تحقيق، پس از مدلسازي يكپارچه مساله برنامه ريزي ظرفيت توليد و مساله زمانبندي توليد دو ماشينه، به ارايه يك رويكرد حل تحليلي پرداخته مي شود. در راستاي كمينه سازي حداكثر زمان تكميل سفارشات، مفهومي تحت عنوان «زوج سفارش» تعريف، و الگوريتمي جهت تعيين زوج سفارشاتِ بهينه بر مبناي مساله تخصيص متقارن ارايه مي شود. سپس در راستاي تعيين توالي بهينه ي زوج سفارشات، الگوريتم شاخه و كراني بر مبناي سه كران پايين پيشنهادي و همچنين دو استراتژي جستجوي عمق اول و سطح اول، طراحي و در راستاي افزايش كارآيي آن تعدادي ويژگي رياضي اثبات، و بر اساس آن ها تعدادي قاعده چيرگي جهت مساله استخراج شده است. همچنين جهت تعيين مقادير تخصيص ظرفيت به عمليات، يك الگوريتم جستجوي همسايگي طراحي و بر اساس ويژگي هاي ساختاري مساله بهبود داده شد.

Production capacity planning and scheduling are parts of decision process in supply chain of many manufacturing and service industries, which have important role in satisfying customer requirements and enhancing customer service level. Since these two processes performs in two different levels of supply chain (capacity planning in tactical level and scheduling in operational one), usually their decision are made independently. In such circumstances, the feasibility of capacity decisions in tactical level, when plan imports into the shop floor, is one of the critical challenges in this decision making approach. Hence in this paper, after formulating the capacity planning and two-machine scheduling problems integrately, an analytical solution approach will be presented. In order to minimize the maximum completion time of orders, concept of order pairs is defined and the optimal orders pairs are established based on the optimal solution of symmetric assignment problem. Afterwards, to determine the optimal sequence of order pairs, a branch and bound procedure is designed which is based on three proposed lower bounds, depth first and best first strategies. To improve the efficiency of algorithm, some mathematical properties are proved and some corresponding dominance rules are derived. Furthermore, to delineate the quantity of resource allocation to the operations, a neighborhood search algorithm is designed and improved based on some structural properties of problem.