Deterministic and stochastic team formation problems
Deterministik ve rassal ekip kurma problemleri
- Tez No: 659121
- Danışmanlar: PROF. DR. OYA KARAŞAN, PROF. DR. HANDE YAMAN PATERNOTTE
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 138
Özet
Günümüz ürünlerinin ve servislerinin karmaşıklığı çok farklı alanlarda bilgi, beceri ve deneyim gerektirmektedir. Bu nedenle şirketler, üniversiteler, hastaneler, belediyeler gibi çok çeşitli kurumlarda ekipler halinde çalışılır. Ekip tarafından yapılan işin kalitesi üyelerin teknik bilgi ve becerilerine bağlı olduğu kadar aralarındaki iletişim kalitesine de bağlıdır. Bu tezde amacın en iyi ekibi oluşturmak olduğu çeşitli ekip kurma problemleri inceliyoruz. İlk olarak, etkili bir şekilde iletişim kurabilen ve işbirliği yapabilen gerekli yeteneklere sahip bir ekip oluşturmayı amaçlayan bir ekip oluşturma problemi üzerinde çalışıyoruz. Kişiler arası iletişim kalitesini ölçmek için, kişilerin bir sosyal ağın parçası olduğu varsayıyor, bu ağdaki yakınlıklarını kullanarak bir iletişim maliyeti tanımlıyoruz. Problemimizde iletişim maliyetlerinin toplamını en aza indirgerken ve en büyük iletişim maliyetine de bir üst sınır koyuyoruz. Bu problemi, kısıtlı karesel bir küme kapsama problemi olarak formüle ediyoruz. Sayısal analizlerimiz, genel amaçlı bir tamsayılı programlama çözücüsünün küçük ve orta ölçekli örnekleri çözebildiğini gösteriyor. Daha büyük boyutları çözmek için bir dal-sınır yöntemi geliştirildi. Bu yöntemde önce problem yeniden formüle edildi, ardından bir dizi doğrusal küme kapsama problemine ayrışacak şekilde gevşetildi. Dallanma yoluyla gevşetilmiş kısıtlamalar dayatıldı. Analizlerimiz, dal-sınır yönteminin çözücü için zor olan büyük boyutlu örnekleri çözebildiğini gösteriyor. İkinci olarak, amacın takımın beklenen iletişim maliyetini en aza indirmek olduğu iki aşamalı bir rassal takım oluşturma problemini ele alıyoruz. Bazı bireyler arasında iletişim maliyetlerinin belirsiz olduğunu, ancak bu maliyetlerin bilinen bir ayrık dağılıma sahip olduklarını varsayıyoruz. Problemin ilk aşaması, karar vericinin iletişim maliyeti rassal olan çiftler arasından sınırlı sayıda seçtiği bir deneme aşamasıdır. Seçilen çiftlerin gerçek iletişim maliyet değerleri ikinci aşamadan önce öğrenilir. İlk aşama kararlar değişkenleri, belirsizliğin hangi parametreler için ortadan kalkacağını belirlediği için bu problemdeki belirsizlik karara bağlıdır. Bu problem için iki formülasyon veriyoruz; ilki ilgili literatürdeki modeller ile benzer bir dizi beklentisizlik kısıtları içermektedir. İkincisinde, tanımladığımız karesel amaç fonksiyonu bu beklentisizlik kısıtlarına ihtiyacı ortadan kaldırıyor. Ekstra ikili karar değişkeni tanımlayarak bu karesel fonksiyonu doğrusallaştırıyoruz. Çözücü kullanarak bu formülasyonlarla çözebileceğimiz örneklerin boyutunun sınırlı olduğunu gösteriyoruz. Bu nedenle daha büyük örnekleri çözebilmek için, Benders ayrıştırma yöntemi tabanlı bir dal-kesi algoritması geliştirildi. Algoritmada güçlü kesiler elde etmek için ikinci aşama probleminin güçlendirilmiş bir doğrusal gevşetmesi kullanıldı. Ayrıca karara bağlı yapıdan yararlanılarak algoritmanın her yinelemesinde daha küçük bir senaryo seti yaratılarak çözüm zamanı azaltıldı. Rastgele oluşturulmuş örneklerle yapılan analizlerin sonuçları ile algoritmanın etkinliğini gösterildi. Son olarak bu tezde, amacın işe alım ve dış kaynak masrafları ile personel ücretlerinin en aza indirmek olduğu çok aşamalı bir ekip oluşturma problemini inceliyoruz. Bu problemde aşamalar, ardışık olarak yürütülen projelere karşılık gelir. Her proje, her biri bir insan kaynağı gerektiren birkaç görevden oluşur. Eksik bilgi nedeniyle insanların performanslarında belirsizlik olduğunu ve dolayısıyla bir kişinin bir görevi tamamlaması için ihtiyaç duyduğu sürenin bazı kişi-görev çiftleri için rassal olduğunu varsayıyoruz. Bir kişi bir göreve atandığında, bu kişinin görevi bitirmesinin ne kadar sürdüğünü öğrendiğimizi kabul ediyoruz. Dolayısıyla, belirsizlik burada yine karara bağlıdır. Bir görevin süresi bir proje için izin verilen süreyi aşarsa, yöneticinin süreci hızlandırmak için harici bir kaynak kiralaması gerekir. Bu problem için bir tamsayılı programlama formülasyonu sunuyoruz ve formülasyonun boyutunun büyük ölçüde rassal parametrelerin ve senaryoların sayısına bağlı olduğunu açıklıyoruz. Bu deterministik eşdeğer formülasyon, küçük örnekler için ticari bir çözücü ile çözülebilirken, rassal parametrelerin sayısındaki bir birim artışla çözülemez hale gelmektedir. Kesin yöntemlerin umut verici olmadığı bu tür durumlarda, sıkı sınırlar ve iyi çözümler elde etmek için sezgisel yöntemler ararız. İlgili literatürde, bu tür rassal problemler için farklı Lagrangian ayrıştırma yöntemleri geliştirilmiştir. Bu çalışmada, mevcut yöntemlerin yakınsamasının çok yavaş olduğunu gösteriyoruz ve formülasyonun gevşetmesinin ayrıştırma tabanlı bir dal-sınır algoritması ile çözüldüğü alternatif bir yöntem öneriyoruz.
Özet (Çeviri)
In various organizations, physical or virtual teams are formed to perform jobs that require different skills. The success of a team depends on the technical capabilities of the team members as well as the quality of communication among the team members. We study different variants of the team formation problem where the goal is to build the best team with respect to given criteria. First, we study a deterministic team formation problem which aims to construct a capable team that can communicate and collaborate effectively. To measure the quality of communication, we assume the candidates constitute a social network and we define a cost of communication using the proximity of people in the social network. We minimize the sum of all pairwise communication costs, and we impose an upper bound on the largest communication cost. This problem is formulated as a constrained quadratic set covering problem. Our experiments show that a general-purpose solver is capable of solving small and medium-sized instances to optimality. We propose a branch-and-bound algorithm to solve larger sizes: we reformulate the problem and relax it in such a way that it decomposes into a series of linear set covering problems, and we impose the relaxed constraints through branching. Our computational experiments show that the algorithm is capable of solving large-sized instances, which are intractable for the solver. Second, we consider a two-stage stochastic team formation problem where the objective is to minimize the expected communication cost of the team. We assume that for a subset of pairs the communication costs are uncertain but they have a known discrete distribution. The first stage is a trial stage where the decision-maker chooses a limited number of pairs from this subset. The actual cost values of the chosen pairs are realized before the second stage. Hence, the uncertainty in this problem is decision-dependent, also called endogenous, because the first stage decisions determine for which parameters the uncertainty will resolve. For this problem, we give two formulations, the first one contains a set of non-anticipativity constraints similar to the models in the related literature. In the second, we are able to eliminate these constraints by changing the objective function into a quadratic one, which is linearized by a set of extra binary variables. We show that the size of instances we can solve with these formulations using a commercial solver is limited. Therefore, we develop a Benders' decomposition-based branch-and-cut algorithm that exploits decision-dependent nature to partition scenarios and use tight linear relaxations to obtain strong cuts. We show the efficiency of the algorithm presenting results of experiments conducted with randomly generated instances. Finally, we study a multi-stage team formation problem where the objective is to minimize the monetary cost including hiring and outsourcing costs. In this problem, stages correspond to projects which are carried out consecutively. Each project consists of several tasks each of which requires a human resource. We assume that due to incomplete information there is uncertainty in people's performances and consequently the time a person needs to complete a task is random for some person-task pairs. When a person is assigned to a task, we learn how long it takes for this person to finish the task. Hence, the uncertainty is again decision-dependent. If the duration of a task exceeds the allowable time for a project then the manager must hire an external resource to speed up the process. We present an integer programming formulation to this problem and explain that the size of the formulation strongly depends on the number of random parameters and scenarios. While this deterministic equivalent formulation can be solved with a commercial solver for small-sized instances, it easily becomes intractable when the number of random parameters increases by one. For such cases where exact methods are not promising, we investigate heuristic methods to obtain tight bounds and near-optimal solutions. In the related literature, different Lagrangian decomposition methods are developed for such stochastic problems. In this study, we show that the convergence of existing methods is very slow, and we propose an alternative method where a relaxation of the formulation is solved by a decomposition-based branch-and-bound algorithm.
Benzer Tezler
- Jeoistatistiksel, statik ve kararsız basınç testi verilerine koşullandırılmış heterojen geçirgenlik ve gözeneklilik sahalarının türetilmesi
Generation of porosity and permeability fields conditioned to geostatistical, and pressure transient data
ADİL GÜRKAN CEYHAN
Yüksek Lisans
Türkçe
1997
Petrol ve Doğal Gaz Mühendisliğiİstanbul Teknik ÜniversitesiPetrol Mühendisliği Ana Bilim Dalı
PROF. DR. ABDURRAHMAN SATMAN
- Bir montaj hattının yeniden tasarımı ve tavşan kovalama yönteminin uygulaması
Redesign of an assembly line and application of rabit chasing assembly method
MEHMET TAYFUN DİKER
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET BÜLENT DURMUŞOĞLU
- Orman ürünleri endüstrisi temelli bir endüstriyel simbiyoz ağı için deterministik ve stokastik modeller
Deterministic and stochastic models for an industrial symbiosis network based on forest products industry
MURAT YEŞİLKAYA
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiKırıkkale ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. GÜLESİN SENA DAŞ
- Deterministic and stochastic models for practical scheduling problems
Uygulamalı çizelgeleme problemleri için deterministik ve stokastik modeller
ELVİN ÇOBAN GÖKTÜRK
Doktora
İngilizce
2012
Endüstri ve Endüstri MühendisliğiCarnegie Mellon Universityİşletme Yönetimi Ana Bilim Dalı
PROF. DR. ALAN SCHELLER-WOLF
- Biyokimyasal reaksiyon sistemlerinin modellenmesi için deterministik ve stokastik yaklaşım
Deterministic and stochastic approach for modelling biochemical reactions
BÜŞRANUR OĞRAŞ