توصيفگر ها :
مسئله تعيين اندازه دسته ظرفيت دار , فسادپذيري , تخفيف كلي , فروش مجدد , تحليل پيچيدگي زماني , الگوريتم دقيق چندجمله اي
چكيده فارسي :
در اين رساله، مسئله تعيين اندازه دسته تك كالايي ظرفيت دار با درنظرگيري تخفيف كلي تك نقطه اي و امكان فروش مجدد براي كالاهاي فسادپذير با نام CLSP1DP، بررسي شده است. مفروضات مسئله به اين قرار است: قيمت خريد بدون تخفيفِ واحد كالا و هزينه ثابت سفارش دهي، وابسته به دوره و غيرافزايشي اند. هزينه نگهداري وابسته به دوره است. ظرفيت، سطح شكستِ تخفيف، نرخ تخفيف و نرخ كاهش قيمت در فروش مجدد در تمامي دوره ها ثابت در نظر گرفته شده است. زمان تدارك صفر فرض شده و هيچ نوع كمبودي مجاز نيست. همچنين، كيفيت كالا در طول عمر مفيد خود ثابت فرض شده و سيستم مصرف موجودي هم FIFO در نظر گرفته شده است. ابتدا، مسئله ي مورد بررسي، بدون درنظرگيري فسادپذيري و امكانِ فروش مجدد، مورد ارزيابي قرار گرفته است. طبيعتا، بدون در نظر گرفتنِ فسادپذيري، سياست مصرف در يافتنِ جواب بهينه تاثيرگذار نيست. اين مسئله را به اختصار CLSP1D مي ناميم. مسئله CLSP1D حالت خاصي از مسئله LS-PC است كه توسط كوجا و همكاران، در پژوهش [1]، مورد بررسي قرار گرفته و در آن، يك الگوريتم برنامه ريزي پويا، براي حل دقيق مسئله ارائه شده است. الگوريتم كوجا قادر است كه مسئله CLSP1D را به طور دقيق با پيچيدگي زماني O(T^7 ) حل كند، كه در آن، T نمايانگرِ تعداد دوره هاي افق برنامه ريزي است. در بررسي CLSP1D، ابتدا، مفهوم سفارش نامتعارف، براي اولين بار، مطرح شده و سپس با استفاده از مفهومِ مذكور، شرط تعميم يافته ي ZIO براي CLSP1D ارائه شده است.سپس، با استفاده از مفاهيم دوره هاي بازتوليد و سفارش ناقص، چندين ويژگي مفيد براي جواب بهينه ارائه شده و با استفاده از ويژگي هاي مذكور، يك الگوريتم شمارش ضمني با نام IEA1، با پيچيدگي O(T^5 )، براي حل دقيق CLSP1D طراحي شده است. در ادامه، با اثبات چند ويژگي جديد و با اصلاح IEA1، الگوريتم IEA2 با پيچيدگي زماني O(T^4 ) طراحي شده است. همچنين، يك الگوريتم ابتكاري نيز براي مسئله طراحي شده است.پس از ارائه الگوريتم ها، با توليد نمودهاي تصادفي، الگوريتم¬ها در قياس با يك ديگر و همچنين، در قياس با حل كننده CPLEX مورد ازيابي قرار گرفته اند. نتايج محاسباتي نشان مي دهد كه الگوريتم هاي ارائه شده براي مسئله CLSP1D عملكرد بسيار بهتري نسبت به الگوريتم برنامه ريزي پوياي كوجا، و همچنين حل كننده ي CPLEX داشته و در زمان بسيار كم، قادرند نمودهاي با ابعاد بالاي مسئله را حل كنند. ضمنا، الگوريتم IEA1، با وجودي كه نسبت به IEA2 كند تر است، حافظه كمتري مصرف مي كند و بنابراين، قادر است ابعاد بالاترِ مسئله را حل كند. همچنين، الگوريتم ابتكاري نيز، از IEA1 و IEA2 سريع تر بوده و قادر است با خطاي بسيار ناچيز، يك جواب نزديك به بهينه به دست آورد. نتايج نشان داد كه، در ابعاد بالا، خطاي الگوريتم ابتكاري صفر است. پس از بررسي مسئله CLSP1D، مسئله CLSP1DP مورد ارزيابي قرار گرفته است. با تعميم مفاهيمِ مطرح شده در مسئله CLSP1D و همچنين، اثبات چند قضيه و ويژگي بهينگي، الگوريتم IEA2 براي مسئله CLSP1DP گسترش داده شده و الگوريتم IEAP ارائه شده است كه قادر است با پيچيدگي زماني O(T^4 )، مسئله را به صورت دقيق حل كند. نتايج محاسباتيِ حاصل از حل نمودهاي تصادفي، نشان داد كه الگوريتم IEAP بسيار كاراتر از حل كننده CPLEX است و ابعاد بالاي مسئله را در زمان بسيار كم حل مي كند.
چكيده انگليسي :
In this thesis, the single-item capacitated lot sizing problem considering a 1-breakpoint all-units quantity discount, perishability and resale (CLSP1DP) is investigated. The fixed ordering cost and the undiscounted unit purchase price are assumed to be non-increasing over the periods. The capacity, the discount breakpoint level, the discount rate, and the price drop rate are time-invariant. Also, it is assumed that the lead time is zero, the consumption mechanism is FIFO, backlogging is not permitted, and the quality of items remains constant during their ages. Because of discount base incentives, the firm may decide to order a quantity more than what is needed during the lifetime of the order, to use the discount. In this case, the firm resells surplus items at a lower price at the ordering period. First we consider the problem by ignoring the perishability (CLSP1D). Ignoring the perishability, the lot sizing problem under study is a special case of that with piecewise concave production cost function investigated by Koca et al [1]. Koca’s DP algorithm solves CPSL1D with a time complexity of O(T7), where T denotes the number of periods. It, however, fails in the case of large-sized instances in acceptable runtimes due to its higher complexity. Hence, the present study is a response to the need for more efficient algorithms to overcome this shortcoming. First, some properties of the optimal solution are proved. Second, these properties are exploited in an implicit enumeration exact algorithm. Third, certain speed-up techniques are employed to reduce the time complexity of the proposed algorithm from O(T5) to O(T4). Then, a heuristic algorithm is presented for the problem. The proposed algorithms are compared with Koca’s DP algorithm and the commercial solver used to solve some test problems. Based on the runtimes observed, the exact algorithms proposed in this study are found to outperform both Koca’s DP one and the commercial solver. Moreover, the heuristic algorithm developed herein is found to be faster than both the exact algorithms in finding optimal solutions to most problem instances. Finaly, by extending theorems and properties proposed for CLSP1D and proving some new properties, an implicit enumeration exact algorithm is developed for CLSP1DP that solves the problem in O(T4) time complexity. The efficiency of the proposed algorithm is examined by developing an experimental design with various environments. Based on the observed runtimes, the proposed exact algorithm is found to outperform the CPLEX solver in solving the mathematical model.
