Single machine scheduling with sequence dependent setup times

Bu tezde, işlerin sabit uzunluğa sahip vardiyalarda yapıldığı, sıraya bağlı hazırlık sürelerine sahip tekli makine çizelgeleme problemini inceliyoruz. Her ardışık vardiya çifti arasında periyodik bakıma ayrılmış belirli bir süre vardır, makine bu süre içerisinde çalışmaz ancak bu süre hazırlık süresi olarak kullanılabilir. Amacımız tüm işleri minimum sürede tamamlamaktır. Bu tezde ele alınan ortam, içecek ve kimya endüstrileri dahil olmak üzere farklı endüstrilerde uygulamalara sahiptir. Problem az sayıda iş için bilgisayar ortamında bazı matematiksel modeller kullanılarak çözülebilir. Ancak iş sayısı arttıkça problemi çözme zorluğu da katlanarak artmaktadır. Biz bu problemin üstesinden gelmek için bazı sezgisel algoritmalar önerdik, ve önerdiğimiz algoritmalar probleme iyi çözümler bulmamızı sağladı. Yeni sezgisel algoritmalar, kutulama problemlerinin çözümü için kullanılan İlk Sığan Algoritmasına dayanmaktadır. Öncelikle probleme İlk Sığan Azalan Algoritması uygulandı ve işler vardiyalara atandı. İlk sığan azalan algoritmasının sonuçlarındaki her vardiya için, vardiyadaki işlerin sıraları değiştirilerek kullanılan hazırlık süreleri azaltıldı. Kullanılan hazırlık sürelerinin azalmasıyla birlikte vardiyada boşluklar oluştu. Boşlukları doldurmak için tüm vardiyalar birleştirildi ve ilk sığan algoritması çalıştırıldı. Bu süreç, son işin tamamlanma süresi için daha fazla iyileşme sağlanmayana kadar tekrar edildi. Bu algoritma, Geliştirilmiş İlk Sığan Sezgisel algoritması olarak adlandırıldı. Daha sonra, Geliştirilmiş İlk Sığan Sezgisel algoritmasının sonucuna göre, son vardiya hariç vardiyaların ikili kombinasyonları ile son vardiya birleştirildi. Geliştirilmiş İlk Sığan Sezgisel Algoritması, üçlü vardiya kombinasyonları için üç kez tekrarlandı. Minimum tamamlanma süresi çözüm olarak kabul edildi. Bu algoritma, Geliştirilmiş İlk Sığan Sezgisel Algoritması-2 olarak adlandırıldı. Önerilen algoritmalar literatürdeki benzer örneklerle karşılaştırıldı.