Melez akış tipi çizelgeleme problemi için tepkisel bir algoritma

Abstract

Üretim sistemlerinin performansını artırmak yöneylem araştırmasının başlıca araştırma alanları içerisindedir. Gelişmiş üretim sistemlerinde birçok farklı ürün, müşterilerin istekleri doğrultusunda farklı zamanlarda ve farklı miktarlarda üretilebilmekte ve farklı tarihlerde teslim edilebilmektedir. Bu kadar karmaşık bir üretim sisteminin başarılı bir şekilde işletilebilmesi için, kaynakların etkin kullanılması gerekmektedir. Bu doğrultuda kompleks üretim sistemlerinin planlanması ve etkin bir şekilde işletilmesi için çeşitli modeller ve yaklaşımlar geliştirilmiştir. Artan rekabet ortamı, müşteri isteklerinin farklılaşması ve beklentilerin yükselmesi, işletmeleri üretim sistemlerini daha etkin yönetmeye mecbur kılmaktadır. Sürekli değişen koşullar ve ortamdaki belirsizlikler dinamik karar verme mekanizmalarının geliştirilmesini gerektirmektedir. Birçok üretim ve hizmet sistemi incelendiğinde yapılan işlerin bir dizi seri operasyondan geçirilerek hazır hale getirildiği görülmektedir. Sıklıkla bu operasyonlar her iş için aynı sırayı izlemek zorundadır. Makinelerin seri olarak sıralandığı ve işlerin de bu sırayı izlediği üretim ortamı, akış tipi olarak adlandırılır. Bir m- akış tipi üretim ortamında, m işlem aşaması vardır. Eğer her aşamada sadece bir işlem birimi var ise akış tipi üretim sistemi, birden fazla işlem birimi var ise melez akış tipi üretim sistemi olarak adlandırılır. Çizelgeleme sınırlı kaynakların etkin bir şekilde tahsis edilmesine yönelik bir karar verme sürecidir. Melez akış tipi çizelgeleme problemine yönelik olarak mevcut literatür incelendiğinde araştırmacıların çoğunlukla problemin en genel hali ile ilgilendikleri ve bu durum için optimum çizelgeyi üretmeye çalıştıkları görülmektedir. Standart melez akış tipi çizelgeleme probleminde bütün işler ve makineler sıfır anında mevcuttur. Seçilen bir aşama için o aşamada işlem yapan makineler özdeştir. Sistemde herhangi bir stokastik unsur yoktur. Bununla birlikte, gerçek hayatta önceden ön görülemeyen birçok belirsizlik kaynağı vardır. Makine bozulmaları, yeni gelen siparişler, sipariş iptalleri, teslim tarihi değişiklikleri, işlem zamanı dalgalanmaları, malzeme eksikliği gibi beklenmedik durumlarla her an karşılaşılabilir. Üretim sisteminde meydana gelen değişiklikler ve belirsizlikler önceden planlanmış üretim çizelgesini bozarak değişiklik yapmayı gerektirebilir. Bu gibi durumlar karşısında, üretim çizelgesi tepkisel algoritmalarla değişen koşullara göre dinamik olarak adapte edilebilir. Bu çalışmada rassal olarak yeni iş gelişlerinin olduğu melez akış tipi bir üretim sisteminin dinamik olarak çizelgelenmesi hedeflenmiştir. Ele alınan dinamik melez akış tipi çizelgeleme problemine yönelik olarak tepkisel bir algoritma geliştirilmesi amaçlanmıştır. Bu doğrultuda ilk olarak kapsamlı bir literatür araştırması gerçekleştirilerek, sürekli olarak çalışan dinamik bir üretim sistemi için efektif bir çizelgeleme/yeniden çizelgeleme sisteminin nasıl tasarlanabileceği incelenmiştir. Basit liste çizelgeleme kurallarından daha kompleks algoritmalara kadar pek çok alternatif dinamik çizelgeleme yaklaşımı olduğu görülmüştür. Bu yaklaşımların pek çoğunda çizelge üretimi için harcanan süre göz ardı edilmekte, dinamik çizelgeleme problemi statik alt problemlere bölünerek çözülmektedir. Bu tez çalışması kapsamında önerilen yaklaşım, literatürdeki çalışmalardan çizelgeleme sürecini bir bütün olarak ele alma ve bu sürece yönelik olarak önerdiği dinamik çizelgeleme sistemi ile ayrılmaktadır. Çizelgeleme süreci, çizelge üretme ve üretilen iş emirlerinin gerçeklendiği atölye olmak üzere bir bütün olarak ele alınmıştır. Önerilen yaklaşım çözüm üretilmesi için geçen zamanı da çizelgeleme sürecine yansıtarak çalışan, tamamlanma zamanını temel alan bir yapıdadır. Bu tez çalışması kapsamında dinamik stokastik ortamda melez akış tipi çizelgeleme problemine tepkisel olarak çözüm üretebilecek bir algoritma geliştirilmesi hedeflenmiştir. Ele alınan probleme yönelik olarak algoritma geliştirilirken problemin dinamik bir problem olduğu, algoritmanın çalışırken sistemin her an değişebileceği, çözüm süresi ve çözümlerin kalitesi göz önüne alınmıştır. Bu doğrultuda öncelikle melez akış tipi çizelgeleme probleminin statik deterministik durumu için alternatif çözüm algoritmaları incelenmiştir. Daha sonra dinamik durumda büyük problem boyutlarında da iyi çözümleri kabul edilebilir sürede üretebilecek çözüm yaklaşımları analiz edilmiştir. Dinamik melez akış tipi çizelgeleme problemine yönelik olarak evrimsel algoritmaların değişen ortamlara uyum sağlayabilme yeteneğinden yararlanılmaya çalışılmıştır. Bu kapsamda dinamik melez akış tipi çizelgeleme problemine yönelik olarak çizelgeleme ortamını anlık olarak ele alabilen değişken kromozom yapısına sahip ve hızlı bir şekilde çözüm üretebilen bir genetik algoritma (GA) geliştirilmiştir. GA'nın çeşitli problem boyutları için statik durumdaki çözüm kalitesi test edildikten sonra genetik algoritma popülasyonlarının nasıl değişen problem koşullarına entegre edilebileceği araştırılmıştır. Değişkenliğin olduğu ana kadar ki arama süreci kazanımlarını değişkenlik sonrası ortama aktarabilen değişken kromozom yapılı bir yaklaşımla algoritmanın çok hızlı bir şekilde yeni durum için çizelge üretebildiği görülmüştür. Geliştirilen GA, tasarlanan çizelgeleme sistemine uyarlanmıştır. Olay tabanlı bir yeniden çizelgeleme politikası tercih edilmiştir. Sisteme yeni iş gelişi ya da herhangi bir üretim aşamasından bir işin ayrılışı yeniden çizelgeleme noktası olarak kabul edilmiştir. Sürekli olarak çalışan bir üretim sistemine dinamik olarak çizelge üretebilmek için GA dinamik çizelgeleme sürecine entegre edilmiştir. Bu doğrultuda klasik GA yaklaşımından bağımsız olarak problem değişimi sonrası o anki mevcut popülasyon yeni probleme değişken kromozom yaklaşımı ile uyarlanmış ayrıca GA'nın evrilmesi için beklenmemiştir. Bunun yerine arama süreci kazanımlarını değişkenlik sonrası güncellenen ortama aktarabilen küçük ama sürekli iyileştirmelere güvenen bir yaklaşım benimsenmiştir. Dinamik çizelgeleme sistemi tasarlandıktan sonra, stokastik ortamın çizelgeleme sürecine nasıl yansıtılabileceği üzerinde durulmuştur. Önerilen genetik algoritmanın çözüm (çizelge) değerlendirme aşamasının simülasyon tabanlı sonuç üretmesi durumu incelenmiştir. Genetik algoritmanın çözüm değerlendirme modülü, simülasyon entegrasyonu ile stokastik bir yapıya getirilerek çizelgeleme sürecine stokastik ortam yansıtılmaya çalışılmıştır. Ele alınan dinamik melez akış tipi çizelgeleme problemine yönelik olarak GA strateji seçimi ve parametre optimizasyonu gerçekleştirilerek algoritmanın çözüm kalitesi iyileştirilmiştir. Dinamik deterministik ortamda geliştirilen GA'nın performansını analiz edebilmek için tavlama benzetim (TB) ve en kısa işlem zamanı önce (EKÖ) algoritmaları kıyaslama algoritması olarak kullanılmıştır. Öncelikle TB algoritmasında parametre optimizasyonu gerçekleştirilmiştir. Daha sonra hem TB algoritmasının hem de EKÖ algoritmasının GA için tasarlanan çözüm üretme ve çizelge gerçekleme sistemine entegrasyonu gerçekleştirilmiştir. Aynı çizelgeleme ortamında üç algoritma çözüm kalitesi ve çözüm süresi açısından kıyaslanmıştır. Önerilen GA yaklaşımı TB ve EKÖ algoritmalarına göre daha iyi sonuç vermiştir. Dinamik stokastik ortam içi önerilen GA'nın, uygunluk hesaplama simülasyon modülü koşum sayısı incelenmiştir. Çeşitli boyutlardaki test problemlerinde seçilen koşum sayıları için yarı güven aralığı değerleri incelenmiştir. Daha sonra dinamik stokastik ortamdaki GA'nın performansını analiz edebilmek için bir analiz prosedürü öne sürülmüştür. Buna göre dinamik deterministik ortam için iyi bir çözüm adayının dinamik stokastik ortam için de iyi bir çözüm adayı olabileceği varsayımında bulunulmuştur. Dinamik stokastik durum ile dinamik deterministik durum için önerilen GA çözümleri arasındaki fark performans kriteri olarak kabul edilmiştir. Alternatif test problemleri üzerinden dinamik stokastik durum ve dinamik deterministik durum kıyaslanmıştır. Dinamik stokastik durumda GA tarafından önerilen çözümlerin kalitesini artırabilmek için herhangi bir nesildeki toplam uygunluk hesaplama bütçesini değiştirmeden alternatif popülasyon büyüklükleri ve koşum sayıları için elde edilen sonuçlar analiz edilmiştir. Koşum sayısının mümkün olduğunca küçük tutulduğu büyük popülasyonlu bir GA, ele alınan dinamik stokastik melez akış tipi çizelgeleme problemine yönelik olarak daha iyi çözümler üretmiştir. Ayrıca iş geliş hızının daha düşük olduğu, sistemdeki dinamikliğin kabul edilebilir bir seviyede bulunduğu çizelgeleme ortamları için dinamik deterministik durumdaki bir çözüm adayının dinamik stokastik durum için iyi bir çözüm olabileceği varsayımı doğrulanmıştır.

Increasing the performance of manufacturing systems is one of the major application areas of operational research. Developed manufacturing systems can produce different products according to the different customer requirements at different times and deliver them with different quantities at different due dates. It is necessary to use resources effectively to run such a complex production system successfully. To plan and operate complex production systems effectively various models and approaches have been developed. Increasing competition, differentiation of customer demands and rising of expectations oblige companies to manage production systems more effectively. Continuously changing conditions and uncertainties in the environment requires developing dynamic decision-making mechanisms. In many production and service systems, operations are made ready after a series of processing units. Often these operations follow the same sequence. The processing environment which the processing units are ordered in series and the operations follow this sequence called as flow shop. m stages flow shop production system is composed of m processing units. If there are more than one processor units at least one stage, then this processing environment is called as a hybrid flow shop production system. Scheduling is a decision-making process which deals with allocation of limited resources. Researchers are usually interested in the standard hybrid flow shop scheduling problem and try to produce the optimum schedule for the generic case of the problem. In the standard form of the hybrid flow shop scheduling problem all jobs and machines are available at time zero. Machines at a given stage are identical. There is no stochasticity in the system, problem data is deterministic and known in advance. However, there are so many sources of uncertainty in real life. Unexpected situations such as machine breakdowns, new incoming orders, order cancellations, due date changes, fluctuations in processing time, material shortage can be encountered at any time. Occurred changes in the production and uncertainty in the system disrupt the planned schedule and may require making changes. In those circumstances, production schedule can be adapted changing conditions dynamically by using reactive algorithms. In this study, a hybrid flow shop production system where jobs arrive randomly is investigated. It is aimed to develop a reactive algorithm to schedule dynamically the hybrid flow shop scheduling problem. Firstly, an extensive literature review is conducted to design an effective scheduling/rescheduling system for a continuously running production environment. It has been seen that there are so many alternative dynamic scheduling approaches such as dispatching rules, exact algorithms, and heuristics in the literature. In many cases the time needed for schedule generation is neglected and the dynamic scheduling problem is solved by dividing the problem static sub-problems. However, in real life, the schedule generation takes time. Depending on the size of the scheduling data, the scheduling method which is applied, the time it takes to perform the scheduling process may be very significant. Our study differs from the ones in the literature in terms of the taking the scheduling process as a whole and the proposed dynamic scheduling system. Scheduling process is considered as a schedule generation and job order realization on shop floor. The proposed approach works completion time based and reflects the elapsed time while schedule generation to the shop floor. In this study, we aimed to develop a reactive algorithm that can produce solutions to the dynamic stochastic hybrid flow shop scheduling problem. It is considered that the scheduling environment is stochastic, and while the algorithm is running, the production system and also the solution quality can be changed at any moment. Alternative solution algorithms for the hybrid flow shop problem in the static and deterministic environment are analyzed. After that, the solution approaches which are generate feasible solutions in a reasonable time for the bigger problem sizes and dynamic environment are investigated. The conducted extensive review revealed that the fact that genetic algorithms (GA) used in dynamic scheduling mostly because of their adaptation skill to the changing environments. So we decided to use a GA to generate schedules for the considered hybrid flow shop scheduling problem. It is aimed to develop a GA to cover the changing production environment instantaneously by using changeable chromosome structure in its population. Firstly the GA solution quality is checked in static environment by using alternative test problems in different sizes. It is investigated that how the GA population is integrated the changing conditions. It is found that using an approach that considers the search process gains which already done before the dynamic situation happened improve the efficiency. In other words, instead of restarting the GA when the dynamic situation happened, the population of the newly started GA is obtained from the final population of the previous GA by adjusting it to the requirements of the new problem. The developed GA is adapted to the designed scheduling system by using an event driven rescheduling policy. New job arrivals or job completions at any stage are chosen to the rescheduling point. To generate schedules dynamically on a continuously running environment the GA is integrated the scheduling process. Separate from the classical GA approaches after the problem changed, it is not needed to wait until the algorithm evolved. Instead of this, the algorithm trusts little but continuous improvements and transfer of search process gains to the new problem after the dynamic situation happened. After the dynamic scheduling system is designed, we focused on how the stochastic environment can be reflected in the scheduling process. Integration of simulation to the solution evaluation module of the proposed GA is investigated. The stochasticity in the environment is reflected to the GA by using random variables as jobs processing times. And fitness calculation of solutions is done by using simulation. To increase the solution quality of the proposed GA, strategy selection and parameter optimization is performed. The performance of the proposed GA in the static environment is compared with CPLEX optimum solutions for small size problems. To analyze the performance of the proposed GA in the deterministic and dynamic environment, simulated annealing (SA) and shortest processing time (SPT) algorithms are used as a benchmark. Parameter optimization is also performed for SA. Both SA and SPT algorithm is integrated to the designed solution generation and schedule realization process. In the same conditions, the three algorithm is compared according to the solution quality and run time. The proposed GA approach yielded better results than others. Replication number of the simulation module while evaluating fitness of solutions in the dynamic stochastic environment is investigated. By using various test problems at different sizes, confidence interval is analyzed for chosen replication numbers. To analyze the proposed GA performance in the dynamic stochastic environment an analysis procedure is proposed. In this procedure a good solution in the dynamic deterministic environment is assumed to be also a good solution for the dynamic stochastic environment. By using alternative test problems, the proposed algorithm performance in the dynamic stochastic environment and in the dynamic deterministic environment is compared. To increase solution quality in the dynamic stochastic environment, replication number and population size are analyzed together without changing total evaluation budget in the algorithm. Increasing the population size and decreasing the replication number strategy gives better solutions. Test results revealed that a good solution in the dynamic deterministic environment is also good solution for the dynamic stochastic environment assumption is verified especially when there is low level stochasticity in the system.