Ardışık makinelerde çoklu operasyona sahip işlerin eş zamanlı çizelgelenmesi

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.