Robust optimization of a class of queuing and inventory control problems

Abstract

Bu tezde bir dizi klasik stokastik dinamik problemin dayanıklı versiyonları ele alınmıştır.Klasik stokastik dinamik programlamada, Markov Zinciri olasılık parametreleri veya diğerproblem parametrelerinin kesin olarak bilindiği varsayılır. Çalışmamızda, tarihsel veridenveya diğer kaynaklardan tahmin edilmek durumunda olan bu parametreler bir belirsizlikkümesi olarak ele alınmaktadır. Dayanıklı dinamik programlamada, Doğa ve kontrolörarasında tanımlanan bir max-min oyunu ¸çözülmesi ile söz konusu belirsizlik kümesininproblem içerisinde modellenmesi sağlanır ve Doğa bu belirsizlik kümesi içerisinden probleminhedef fonksiyonunu minimize edecek argümanı seçer. Bu sayede elde edilen problemklasik problemin dayanıklı eşleniğidir. Tezde, envanter ve kuyruk teorisi problemlerindengeniş bir küme ¸calışılarak, elde edilen bu dayanıklı eşlenik problemlerin ve bu problemlerinoptimal ¸çözümlerinin yapısal özellikleri incelenmiştir. Söz konusu özelliklerin belirlenmesiöncelikle olay tabanlı yaklaşımın sistematik olarak kullanılması ile olmuştur. Kurulanbu sistematik yaklaşım sayesinde, olabilecek en genel seviyede klasik problemde veilişkili optimal çözümünde varolan matematiksel özelliklerin dayanıklı eşlenikte de varolduğugösterilmektedir. Bunun yanında dayanıklı eşleniğin mÜkemmel ikilik Özellik Özelliğine sahipolması ile optimal politikasının ve bu politikanın hesaplanabilirliğine yönelik ilişkiler incelenmektedir.Bu inceleme sayesinde, max-min yaklaşıma göre daha esnek olup bunun yanındagerek hesaplanabilirlik açısından gerekse de problem parametrelerindeki değişikliklere duyarlılıkaçısından etkili olan dayanıklı çözümler önerilmektedir.

In this thesis, we study the robust counterparts of some classical stochastic dynamicprogramming problems. In classical stochastic dynamic programming, the transition probabilitiesof the underlying Markov Chain or other problem parameters are assumed to beknown with certainty. We focus on the case where the transition probabilities or otherinput parameters have to be estimated from data and therefore are defined as an uncertaintyset. Robust dynamic programming addresses this problem by defining a max-mingame between Nature and the controller such that Nature?s solution is incorporated to theproblem as the minimizing argument whose feasible set is the uncertainty set. We considerrobust counterparts of classical problem using this approach. For a wide set of examplesfrom inventory and queueing control, we examine the structure of such robust counterpartsand the structure of their optimal policies. Constructing a systematic approach for exploitingthe usefulness of the event-based method is the primary tool in order to identify theseproperties. This systematic approach enables us to show that the structure that governs theoptimal policy of the classical problem is retained for its robust counterpart for a wide set ofcases at the highest level of generality. In addition to this, we elaborate on the relationshipbetween the perfect duality property of a robust counterpart and its optimal policy andan associated computationally efficient solution. Based on this latter approach, we proposeless conservative robust approaches that are both computationally tractable and responsiveto changes in the problem parameters.