Testing and scheduling applications under uncertainty

Abstract

In this thesis, we consider two different optimization problems under uncertainty. The first problem is identifying defective components in failed k-out-of-n systems. In the second part, we study the parallel machine scheduling problem under uncertainty. In the first part of the thesis, we propose four exact and two heuristic solution meth ods for identifying defective parts in failed k-out-of-n systems with the minimum expected cost. We observe that Markov decision-based approaches perform better among the exact solutions where we consider the deterioration rates of all parts in the system based on historical knowledge. Additionally, we determine that dynamic programming for the proposed Markov Decision Process model performs better than linear programming. Since the number of states in the MDP increases exponentially due to the problem’s nature, we show that this approach cannot be used on large scale problems. Thus, we propose two heuristic methods and two lower-bound approaches to determine the solution quality of these methods. In the second part, we study parallel machine scheduling on plastic injection machines at Vestel factory, mimicking a real-life manufacturing problem. We propose two sepa rate robust optimization reformulations and a branch-and-price algorithm that solve real-life instances in a reasonable time, which cannot be achieved with a commer cial solver. Additionally, we demonstrate that the scheduling problems may have alternative optimal solutions for a worst-case (nominal) tardiness objective, whose performance under nominal (worst-case) processing times are remarkably different. Therefore, we propose Pareto efficient extensions to consider alternative solutions.Bu tez ¸calı¸smasında belirsizlik altında iki farklı optimizasyon sorunu ele alınmı¸stır. Bu sorunlardan ilki ¸calı¸smayan n’in k’lısı karma¸sık sistemlerindeki bozuk par¸caların en d¨u¸s¨uk maliyet ile belirlenme sorunudur. ˙Ikinci kısımda ise paralel makinalardaki belirsiz ¨uretim zamanı altında ¸cizelgeleme sorunu ¸c¨oz¨umlenmi¸stir. Tezin ilk kısmında, ¸calı¸smayan n’in k’lısı karma¸sık sistemlerindeki bozuk par¸caların en d¨u¸s¨uk maliyetli tespiti i¸cin d¨ort adet kesin, iki adet de sezgisel ¸c¨oz¨um metodu ¨onerilmi¸stir. Sistemdeki t¨um par¸caların ge¸cmi¸sten gelen bilgilerine dayanan bozulma oranları g¨oz ¨on¨unde bulunduruldu˘gunda kesin ¸c¨oz¨umler i¸cinden Markov karar s¨ureci temelli yakla¸sımların daha iyi performans g¨osterdi˘gi g¨or¨ulm¨u¸st¨ur. Ayrıca ¸c¨oz¨um metodu olarak dinamik programlama do˘grusal programlamaya g¨ore daha iyi perfor mans g¨ostermi¸stir. Markov karar s¨urecindeki durum sayısının, sorunun do˘gasından kaynaklanan bir ¸sekilde ¨ussel olarak artmasından dolayı, bu yakla¸sımın b¨uy¨uk boyut larda kullanılamayaca˘gı g¨osterilmi¸stir. Bu sebepten dolayı iki adet sezgisel metot ve bu metotların ¸c¨oz¨um kalitesini belirleyebilmek i¸cin de iki adet alt sınır de˘geri bulma yakla¸sımı ¨onerilmi¸stir. Tezin ikinci kısmında, ger¸cek d¨unyada var olan bir ¨uretim sorunu olan Vestel fab rikasındaki plastik enjeksiyon makinalarının paralel ¸cizelgelemesi ¨ust¨unde ¸calı¸sılmı¸stır. Ticari bir ¸c¨oz¨uc¨u ile makul bir s¨urede elde edilemeyen ger¸cek d¨unya problemlerini ¸c¨ozen iki g¨urb¨uz optimizasyon form¨ulasyonu ve ¸c¨oz¨um metodu olarak dal-ve-fiyat al goritması ¨onerilmi¸stir. Ek olarak, ¸cizelgeleme problemlerinin en k¨ot¨u (nominal) i¸slem s¨urelerinin altındaki performanslarının ortalama (en k¨ot¨u) gecikme de˘geri farklı olan v durumları i¸cin alternatif en iyi ¸c¨oz¨umleri olabilece˘gi g¨osterilmi¸s ve bunları bulmak i¸cin Pareto verimli uzantıları ¨onerilmi¸stir.