Çizelgeleme, üretim ve hizmet sektörlerinde yaygın olarak kullanılan kritik bir karar verme sürecidir. Belirli bir zaman dilimi içinde sınırlı kaynakların çeşitli görevlere tahsis edilmesini içerir ve temel amacı, belirlenen hedefleri en iyi şekilde optimize etmektir. Kaynaklar; makineler, insan gücü, pistler, bilişim sistemleri veya inşaat ekipleri gibi farklı formlarda olabilirken, görevler ise üretim operasyonları, uçuş planlamaları, proje aşamaları veya bilgisayar işlemleri gibi çeşitli süreçleri kapsayabilir.

Günümüzün rekabetçi iş dünyasında, işletmelerin hız, esneklik ve verimlilik odaklı çözümler geliştirmesi kaçınılmaz hale gelmiştir. Müşteri taleplerini zamanında, kaliteli ve maliyet etkin şekilde karşılamak, sürdürülebilir büyüme ve rekabet avantajı açısından büyük önem taşımaktadır. Teknolojik gelişmeler ve değişen piyasa koşulları, kaynakların etkin kullanımını ve üretim süreçlerinin verimli yönetilmesini zorunlu kılmaktadır.

Üretim Çizelgeleme

Üretim çizelgeleme problemleri genellikle α|β|γ gösterimi ile ifade edilir. Burada, α üretim ortamını, β işlem özelliklerini ve kısıtlarını, γ ise optimize edilmesi gereken hedefi temsil eder. Üretim ortamı, genellikle tek makineli ve çok makineli ortamlara göre sınıflandırılır. Çok makineli çizelgeleme problemleri, çeşitli üretim süreçlerini kapsar ve bunlar arasında akış tipi atölye (flow shop), esnek akış tipi atölye (flexible flow shop), iş atölyesi (job shop) ve paralel makine sistemleri (parallel machine systems) gibi farklı üretim ortamları bulunur.

Her bir üretim süreci, kendine özgü karakteristikler ve kısıtlamalar içerir. İşlem özellikleri ve kısıtlar, üretim sürecindeki çeşitli kısıtlamaları tanımlar. Bu kısıtlar arasında kurulum süresi (setup time), işlerin bölünebilmesi (preemption), aşamalar arası beklemenin yapılamaması (no-wait) ve permütasyon gibi kısıtlamalar yer alır. Bu kısıtlar, üretim sürecinde her bir işin ne zaman ve hangi koşullar altında işleme alındığını belirler. Optimize edilmesi gereken hedefler ise, genellikle en son işin sistemden ayrılma zamanı (makespan) ve toplam gecikme süresi (total tardiness) gibi performans ölçütleridir. 

Çizelgeleme problemleri, problemin büyüklüğü ve karmaşıklığına bağlı olarak P problemleri (Polinomial) veya NP problemleri (Nondeterministic Polynomial) olabilir. P problemleri, matematiksel algoritmalarla makul bir sürede kesin sonuca ulaşılabilirken, NP problemleri için aynı şey söylenemez. Bu nedenle, çeşitli sezgisel ve meta-sezgisel yöntemler geliştirilmiştir. Bu yöntemler kesin çözüm vaat etmez, ancak doğruya en yakın çözümün makul bir sürede bulunmasına olanak tanır.

^{Gantt Şeması - Medium.com}

Makine Ortamları

Tek Makine

Tek makineli problem, çeşitli çizelgeleme konularını ele almak için kullanılabilen yönetilebilir bir model sunar. Farklı performans ölçütlerini ve çeşitli çözüm tekniklerini incelemek için bir bağlam sağlar. Bu nedenle, çizelgeleme kavramlarını kapsamlı bir şekilde anlamanın temel taşlarından biridir. Karmaşık bir sistemin davranışını tam olarak anlayabilmek için önce onun parçalarını kavramak önemlidir ve tek makineli problem genellikle daha büyük bir çizelgeleme probleminin bir parçası olarak karşımıza çıkar. Bazen, tek makineli problem bağımsız olarak çözülebilir ve elde edilen sonuç daha büyük probleme entegre edilebilir. Örneğin, çok aşamalı üretim süreçlerinde bir darboğaz aşaması bulunabilir ve bu darboğazı tek makineli analiz ile ele almak, tüm çizelgenin özelliklerini belirleyebilir.

Paralel Makine

Klasik paralel makineli çizelgeleme probleminde, n adet iş ve m adet makine bulunur. Her işin belirli bir işlem süresi boyunca bir makinede işlenmesi gerekir. Burada amaç, belirli bir performans ölçütünü optimize eden bir çizelge oluşturmaktır. Çizelgeleme sürecinde iki temel karar alınır: sıralama (işlerin hangi sırayla işleneceği) ve iş-makine ataması (hangi işin hangi makinede işleneceği). Tek makineli problemler yalnızca optimal iş sıralamasını belirlemeyi gerektirirken, çok makineli problemlerde aynı zamanda optimal iş-makine atamasını da bulmak gerekir.

^{Paralel Makine Tipi Üretim - Kaabi, J., & Harrath, Y. (2014)}

Akış Tipi Atölye

Akış tipi atölye düzenleri, makinelerin sıralı bir şekilde dizildiği ve işlerin belirli bir rota boyunca işlendiği üretim ortamlarını ifade eder. İşler, ilk makinede başlar, ara makinelerden geçer ve son makinede tamamlanır. Bu düzen genellikle akış tipi atölye olarak adlandırılsa da, gerçek üretim sistemleri genellikle daha karmaşık yapılara sahiptir. Akış tipi atölye çizelgelemesi, makinelerden belirli bir sıra ile geçmesi gereken işlere yönelik optimal bir çizelge oluşturmayı içerir. İşler, her makinede farklı işlem sürelerine sahip olabilir. Bu problem, iki temel bileşenden oluşur: m adet makine ve her biri aynı sırayla işlenecek ancak farklı işlem sürelerine sahip n adet iş.

^{Akış Tipi Atölye - Aslan, E. (2017)}

Esnek Akış Tipi Atölye

Temel akış tipi atölye problemlerinde her işlem merkezi yalnızca bir makine içerir. Ancak, en az bir işlem merkezi birden fazla makine içeriyorsa, problem esnek akış tipi atölye problemi haline gelir. Esnek akış tipi atölyeler, basit akış tipi atölyelerin genelleştirilmiş bir versiyonudur. Esnek akış tipi atölye çizelgeleme problemleri, hem akış tipi atölye hem de paralel makineli çizelgeleme özelliklerini bir araya getiren bir yapıya sahiptir. Proses esnekliği, farklı türde işlemleri gerçekleştirebilme yeteneği olarak tanımlanabilir.

Operasyonel esneklik ise, farklı parça türleri için işlem sırasını yeniden düzenleyebilme kapasitesini ifade eder. Bu iki esneklik türü sayesinde, herhangi bir operasyon belirli bir aşamadaki herhangi bir paralel makineye atanabilir. Bu atamalar değiştikçe, makinelerdeki işlem süreleri de buna bağlı olarak farklılık gösterebilir.

^{Esnek Akış Tipi Atölye - Aslan, E. (2017)}

İş Atölyesi

Klasik iş atölyesi çizelgeleme problemi, akış tipi atölye çizelgeleme probleminden önemli bir noktada farklılık gösterir, İş akışı tek yönlü değildir. Problemin temel bileşenleri, m adet makine ve çizelgelenecek n adet işten oluşur. Her iş, akış tipi atölye modelindeki gibi doğrusal bir öncelik ilişkisine sahip bir dizi operasyondan meydana gelir.

Bir işin herhangi bir sayıda operasyon içermesi mümkün olsa da, iş atölyesi çizelgeleme problemlerinin en yaygın formülasyonu, her işin tam olarak m operasyon içermesini ve her operasyonun farklı bir makinede gerçekleştirilmesini varsayar. Ancak, ana fikirleri uyarlayarak, bir işin aynı makineyi birden fazla kez ziyaret edebildiği veya bazı makineleri atlayabildiği daha genel durumlara uygulamak mümkündür. Akış tipi atölye modelinden farklı olarak, sadece ilk operasyonu gerçekleştiren bir başlangıç makinesi veya sadece son operasyonu gerçekleştiren bir bitiş makinesi bulunmaz.

İşlem Özellikleri ve Kısıtlar

Kurulum Süresi

Kurulum süresi (Setup time), bir makinenin bir işin işlenmesine başlamadan önce yapılan hazırlık süresidir. Bu hazırlık süresi, makinenin önceki işten sonraki işe geçiş yapabilmesi için gerekli olan işlemleri içerir. Bu işlemler arasında makine ayarlarının değiştirilmesi, gerekli ekipman ve malzemelerin yerleştirilmesi, yazılım güncellemeleri veya özel kalıpların takılması gibi adımlar bulunabilir.

Bölünebilme

Bölünebilme (Preemption), bir makinede işlemekte olan bir işin, o işin tamamlanmadan önce başka bir özdeş makineye veya aynı makinede farklı bir zaman dilimine kaydırılabilmesini ifade eder. Bu, bir işin tamamlanmadan önce geçici olarak durdurulması ve daha sonra başka bir işin önceliklendirilmesi için yeniden başlatılması anlamına gelir.

Aşamalar Arası Beklemenin Yapılamaması

No-wait kısıtı, bir üretim sisteminde, işlerin bir işlemden diğerine geçerken beklememesi gerektiğini ifade eden bir kısıttır. Bu kısıt, bir işin bir makinede işlem yapmayı bitirdikten sonra, hemen sonraki makinede işlem yapmaya başlaması gerektiği anlamına gelir. Yani, işler, her makinede işlem bitiminden sonra hiç beklemeden, doğrudan bir sonraki işlemi başlatacak şekilde sıralanmalıdır.

Permütasyon

Permütasyon çizelgeleme, işlerin sıralanmasının yalnızca işlerin birbirine göre sırasının değiştirilmesine dayandığı bir çizelgeleme türüdür. Yani, bu tür bir çizelgeleme probleminde, belirli bir dizi işin belirli makinelerde veya işleme istasyonlarında belirli bir sırayla yapılması gerekmektedir ve işlerin sırasını değiştirmek dışında herhangi bir başka değişiklik yapılmaz.

Amaç Fonksiyonu

En Son İşin Sistemden Ayrılma Zamanı

En son işin sistemden ayrılma zamanı (makespan), bir dizi işin tamamlanması için geçen toplam süredir. Matematiksel olarak, makespan, son işin bitiş zamanı ile ilk işin başlangıç zamanı arasındaki farktır. Yani, tüm işlerin tamamlanmasının en son zamanıdır ve üretim sürecinin verimliliğini ölçmede önemli bir performans göstergesidir.

Toplam Gecikme Süresi

Toplam gecikme süresi (total tardiness), bir üretim çizelgeleme probleminde, her bir işin teslim tarihine göre ne kadar geciktiğini ölçen bir performans göstergesidir. Yani, bir işin teslim tarihi ile gerçek tamamlanma tarihi arasındaki farkın toplamını ifade eder. Matematiksel olarak, bir işin gecikmesi, tamamlanma zamanı ile teslimat zamanı arasındaki farktır. Eğer tamamlanma zamanı teslimat zamanından önceyse, o işin gecikmesi sıfırdır (yani zamanında tamamlanmıştır). Ancak, tamamlanma zamanı teslimat zamanından sonra ise, gecikme süresi pozitif olur ve bu fark toplam gecikmeye eklenir.

Çözüm Yolları

Kesin Çözüm

Kesin algoritma, bir optimizasyon probleminin her zaman optimal çözümünü bulan bir algoritma olarak tanımlanır. Bu, bazen yakın optimal çözüm elde edebilen sezgisel yaklaşımlardan farklıdır. Bunların bir alt kümesi de yakınsama algoritmalarıdır. Bunlar, optimal çözüm ile algoritma tarafından üretilen çözüm arasındaki oran için garanti edilmiş bir sınırın kanıtlanabileceği algoritmalardır. NP-zor gibi zor optimizasyon problemleri için, genellikle bazı polinomal süreli yakınsama algoritmaları bulunurken, en iyi bilinen kesin algoritmalar üstel zaman gerektirir.

Dal-Sınır algoritması, çizelgeleme problemlerini çözmek için doğrudan bir yaklaşım olarak kabul edilebilir. Bu algoritma, ayrık ve kombinatoriyel optimizasyon problemleri için bir algoritma tasarım paradigması olarak tanımlanır. Dal-Sınır algoritmasında, aday çözümler kümesi, köklü ağacın kökü olarak tanımlanırken, çözüm kümesinin alt kümeleri bu ağacın dallarıyla temsil edilir. Algoritma, dalları keşfeder ve optimal çözüm için üst ve alt sınırları belirler. Algoritma, optimal çözüm elde edilene kadar çözümleri iteratif olarak elemek suretiyle çalışır.

Sezgisel Yöntemler

Sezgisel yöntemler, verilen bir hedef için tatmin edici bir çözüm arama sürecidir ve bu çözümün optimal olacağı garanti edilmez. Sezgisel yöntemler, problem çözme, öğrenme sistemleri ve optimizasyon için kullanılabilir. Sezgisel yöntemler grubu, yapıcı prosedürler ve iyileştirme prosedürleri olarak ikiye ayrılmıştır. Yapıcı prosedürler, çözümün iş bazlı veya aşama bazlı olarak inşa edilerek oluşturulmasına yönelik yöntemlerdir. İyileştirme prosedürleri kategorisi ise verilen bir başlangıç veya inşa edilmiş çözümü iyileştiren yöntemleri ifade eder. Sezgisel yöntemler için NEH, CDS ve Palmer algoritmaları örnek olarak verilebilir.

Meta Sezgisel Yöntemler

Meta-sezgisel yöntemler, potansiyel çözümleri iteratif bir şekilde iyileştiren süreçlerdir. Diğer bir deyişle, meta-sezgisel yaklaşım, geniş bir problem setine uygun sezgisel algoritmaları tanımlamak için kullanılabilecek matematiksel fikirlerin bir koleksiyonudur. Tabu Arama, Genetik Algortimalar, Simüle Tavlama, Parçacık Sürü Optimizasyonu ve Karınca Kolonisi Optimizasyonu, meta sezgisel yöntemlere örnek olarak verilebilir.