Bu bölümde iş sıralama algoritmaları olan Johnson, palmer, cds, gupta, neh ve rap algoritmalarının nasıl kullanıldığı ve formülasyonlarını örnekler ile bulabilirsiniz.
Çizelgeleme, belirli bir takım görevleri yerine getirmek üzere kaynakların zaman içinde tahsisi olarak tanımlanabilir. Bu tanımda görevler, içinde bulunulan ortama bağlı olarak değişik şekillerde adlandırılabilirler. Genel olarak, belirli ürün veya hizmetleri meydana getirmek için gerekli olan faaliyetlerdir.
Çizelgelemede üç unsur söz konusudur. Bunlar; üretim, kaynak ve zamandır. Bu unsurları göz önüne alarak çizelgelemeyi şöyle ifade edebiliriz:
Çizelgeleme, belirli bir takım işleri yapmak için hangi kaynakların, ne zaman ve nasıl kullanılacaklarının tespit edilmesidir. Etkin bir çizelgeleme sayesinde belirli faaliyetlerin daha az kaynak kullanımıyla ve/veya daha kısa zamanda yapılabilme olanağı ortaya çıkmaktadır.
Herhangi bir üretim sisteminde, atölye içinde kabarık sayıdaki yarı mamul yığınları ve/veya bir kısım tezgahların çalışırken diğerlerinin boş durması gibi durumların gözlenmesi çizelgeleme problemlerinin varlığını ortaya koyar. Ayrıca, üretim kayıtları incelendiğinde görülebilecek yüksek seviyede fazla mesai, gecikmiş işlerin varlığı, düşük tezgah/işgücü kullanım oranları gibi istatistikler de çizelgeleme problemlerinin işaretleridir.
Bu nedenle çizelgeleme, işletmelerin verimliliklerini arttırabilmeleri açısından çok önemli bir unsurdur.
Çizelgeleme problemlerini üç sınıfta toplamak mümkündür:
1. Atölye çizelgeleme problemi
2. Proje çizelgeleme problemi
3. Montaj hattı dengeleme problemi
Atölye çizelgeleme problemi, sıralama problemi olarak da adlandırılır. Atölyedeki m adet makinede işlenmesi gereken n adet işin, önceden belirlenmiş performans ölçütlerini en iyileyecek şekilde sıralanması problemidir.
Proje; belirli bir amaçla birden fazla faaliyetin, belirli bir öncelik sırası ile yapılmasını gerektiren faaliyetler topluluğu olarak tanımlanabilir.
Bir projenin, belirli bir zaman periyodu boyunca gerçekleştirilmesi için, tüm üretim kaynaklarının tahsis edilmesi problemine proje çizelgeleme problemi denir. Çizelgeleme ve kaynak tahsisi, projeyi oluşturan faaliyetlerin bir şebeke ile temsil edilip şebeke planlama teknikleri ile yapılmasıdır.
Montaj hattı dengeleme problemi, standart ürün üreten bir montaj hattında kaynakların tahsisi ve düzenlenmesine yönelik kararları içeren bir problemdir. Bir değerlendirme ölçütünü en iyileyecek şekilde faaliyetlerin iş istasyonlarına atanmasına ve bu istasyonların sayısını tespit etmeye yönelik çalışmalardır.
Atölye çizelgeleme hem matematiksel problem olarak hem de uygulamalardaki sorunları açısından yöneylem araştırmasının en zor alanlarından biridir. Gerçek bir çizelgeleme probleminin matematiksel modelini formüle ederken çeşitli basitleştirici varsayımlar yapmak gereklidir. Tüm parametrelerin önceden bilinmesi, makinelerde bozuklukların söz konusu olmayacağı, hazırlık zamanlarının sıfır olması, vb. gibi bir takım basitleştirici varsayımlardan sonra bile, elde edilen modelin çoğu zaman teorik tanımda zor bir problem olmaktadır.
Bu çalışmada atölye çizelgeleme problemlerinden, tüm işlerin makinelerde aynı sırada işlendiği, işlerin maksimum tamamlanma zamanını minimize edecek şekilde seri akışlı çizelgeleme problemleri incelenmiştir.
Seri akışlı çizelgeleme problemleri; makine sayısı iki, üç ve üçten büyük olmak üzere iki kısımda incelenmektedir. Makine sayısının iki olduğu durumda, problemi çözen optimal teknik S.M. Johnson tarafından 1954 yılında gerçekleştirilmiştir. Johnson geliştirdiği bu algoritmayı üç makineli probleme uygulayarak bazı şartlar sağlandığında optimal çözümün elde edilebileceği sonucuna varmıştır.
Makine sayısı üç ve üçten büyük olduğu durumlarda çizelgeleme problemlerinin çözümü zorlaşmaktadır. Dinamik programlama, tamsayılı programlama gibi yöntemleri çizelgeleme problemine uygulayarak optimal çizelgeler elde edilmiştir. Bir tamsayılı programlama tekniği olan dal-sınır algoritması tekniği çeşitli bilim adamları tarafından çizelgeleme problemlerine uygulanmış, küçük boyutlu problemlerde optimum sonucu veren bir teknik olmasına rağmen büyük boyutlu problemlerde bilgisayar hesaplama zamanının üstel olarak artmasından ötürü genel olarak uygulanmamaktadır.
Dinamik programlamanın da yukarıda belirtilen sebepten ötürü küçük boyutlu problemler dışında uygulama imkanı olmadığı sonucuna varılmıştır.
Bu nedenle büyük boyutlu problemler için sezgisel (heuristic) algoritmalar geliştirilmiştir. Sezgisel algoritmalar, optimal sonucu garanti etmeyen, yaklaşık çözümler üreten ancak uygulaması kolay ve hesaplama zamanı kısa olan algoritmalardır. Çalışmamızda bahsi geçecek olan NEH, CDS, Palmer, Gupta algoritmaları sezgisel algoritmalardandır.