Please use this identifier to cite or link to this item: http://hdl.handle.net/11452/5842
Title: Ardışık makinelerde çoklu operasyona sahip işlerin eş zamanlı çizelgelenmesi
Other Titles: Simultaneously scheduling of jobs with multiple operations in consecutive machines
Authors: Özmutlu, H. Cenk
Beğen, Mehmet A.
Gençosman, Burcu Çağlar
Uludağ Üniversitesi/Fen Bilimleri Enstitüsü/Endüstri Mühendisliği Anabilim Dalı.
Keywords: Bağımsız paralel makine çizelgeleme
Makine elverişlilik ve kaynak kısıtları
Karışık tamsayılı programlama
Tamsayılı programlama
Kısıt programlama
Mantık-tabanlı Benders ayrıştırma
Unrelated parallel machine scheduling
Machine eligibility and resource restrictions
Mixed integer programming
Integer programming
Constraint programming
Logic-based Benders decomposition
Issue Date: 10-Jun-2014
Publisher: Uludağ Üniversitesi
Citation: Genşosman, B. Ç. (2014). Ardışık makinelerde çoklu operasyona sahip işlerin eş zamanlı çizelgelenmesi. Yayınlanmamış doktora tezi. Uludağ Üniversitesi Fen Bilimleri Enstitüsü.
Abstract: Bu doktora çalışmasının amacı; makine elverişlilik ve kaynak kısıtları altında ardışık makinelerde işlenmesi gereken farklı sayıda operasyona sahip işlerin bağımsız paralel makine ortamında eş zamanlı olarak çizelgelenmesi problemi için etkili çözüm yöntemleri geliştirmektir. Problemin çözümü için ilk olarak karışık tamsayılı programlama modeli (KTP1) geliştirilmiştir. Bu model teorik olarak problemi temsil etmekle birlikte, gerçek boyutlu problemlerin çözümünde yetersiz kalmıştır. Sonrasında, kısıt programlamanın özel kısıt tanımlamaları kullanılarak kısıt programlama modeli (KP1) geliştirilmiştir. KTP1 ve KP1 çözümleri karşılaştırılmış ve çeşitli iyileştirme çalışmaları gerçekleştirilmiştir. KP1 modelinin atama prosedürleri incelenerek blok atama yapabilen bir tamsayılı programlama modeli (TP1) geliştirilmiştir. Bu model de gerçek boyutlu problemlerle test edilmiş ve diğer yöntemlerden iyi olmasına rağmen optimal çözümlere istenen hızda ulaşamadığı görülmüştür. Bu problemi basitleştirmek amacıyla mantık-tabanlı Benders ayrıştırma tekniği (MTBA) kullanılmış ve MTBA1 ve MTBA2 olarak adlandırılan iki farklı algoritma geliştirilmiştir. Algoritmalarda kullanılan kesimler çeşitlendirilerek iyileştirme çalışmaları gerçekleştirilmiştir. Son olarak, MTBA algoritmasından esinlenilerek TP2/TP1 algoritması geliştirilmiş ve yöntemin optimum sonucu garantilediği ispatlanmıştır. Yapılan karşılaştırmalar sonucunda, TP2/TP1 algoritması ile dakikalar içinde gerçek boyutlu problemlerin optimal çözümlerine ulaşılabildiği görülmüştür.
The aim of this PhD study is to develop effective solution approaches for a scheduling problem which have jobs with different number of operations that must be processed on consecutive machines regarding to the machine eligibility and resource restrictions in an unrelated parallel machine environment. Firstly, a mixed integer programming (MIP1) model is proposed for the solution of problem. Although MIP1 represents the problem in a theoretic way, it is insufficient to solve the real-world problems. Therefore, a constraint programming (CP1) model is developed by using special constraint definitions of constraint programming. MIP1 and CP1 results are compared with randomly generated data, and some improvement studies are performed. Considering the block scheduling behavior of the CP1 model, an integer programming (IP1) model is developed. The comparison results prove that IP1 generates better schedules than previous models, but it is not an efficient method to reach the optimal solutions of real-world problems. In order to simplify the complex scheduling problem, the logic-based Benders decomposition (LBBD) technique is used, two different algorithms are proposed: LBBD1 and LBBD2. To improve the solutions, the cuts in the algorithms are diversified. Finally, a new algorithm as IP2/IP1 is developed by inspiring from LBBD, and it is proved that IP2/IP1 guarantees the optimal solution of problems. The comparison results show that the IP2/IP1 algorithm reaches the optimal solution of real-world problems within minutes.
URI: http://hdl.handle.net/11452/5842
Appears in Collections:Doktora Tezleri / PhD Dissertations

Files in This Item:
File Description SizeFormat 
373732.pdf1.3 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons