Single machine scheduling with sequence dependent setup times
Sıra bağımlı hazırlık süreleriyle tekli makina çizelgeleme
- Tez No: 697275
- Danışmanlar: DOÇ. DR. ALİ EKİCİ, DOÇ. DR. OKAN ÖRSAN ÖZENER, PROF. DR. SERHAN DURAN
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: Özyeğin Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 40
Özet
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ı.
Özet (Çeviri)
In this thesis, we study a single machine scheduling problem with sequence dependent-setup times where the jobs are processed in shifts with constant length. There is a certain amount of time between each pair of consecutive shifts for periodic maintenance, the machine does not work in maintenance but this time can also be used for the setup. Our goal is to complete the jobs in minimum amount of time. The setting considered in this thesis has applications in different industries including beverage and chemical industries. The problem can be solved with a small number of jobs by using some mathematical models in computer environment. However, as the number of jobs increases, the difficulty of solving the problem increases exponentially. In order to overcome the problem, we proposed heuristic algorithms, and they provided us to find good solutions for the problem. The new heuristic algorithm is based on the First Fit Algorithm (FF) that is used for solution of bin packing problems. Firstly, First Fit Decreasing (FFD) Algorithm has been applied to the problem, and jobs were assigned to shifts. For each shift in the result of FFD algorithm, used setup times were reduced by changing the orders of jobs in shift. The gaps occurred in some shifts with decrease in setup time used. All shifts were combined to fill in the gaps and FF algorithm was run. This process was repeated until there is no more improvement to be achieved for completion time of last job. This algorithm was named as Improved First Fit Heuristic (IFFH) algorithm. Then, according the result of IFFH algorithm, binary combinations of shifts and last shift were concatenated. The IFFH algorithm was repeated three times for the triple combinations of shifts. The minimum completion time was accepted as a solution. This algorithm was named as Improved First Fit Heuristic-2 (IFFH-2) algorithm. Consequently, the algorithms were compared with benchmarks in the literature.
Benzer Tezler
- Sıra bağımlı ayar zamanı ve fazla mesai ile makine çizelgeleme
Machine scheduling with sequence dependent setup time and over time
ZEYNEP BÜLBÜL
Yüksek Lisans
Türkçe
2017
Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. HAKAN GÜLTEKİN
- Ameliyathane sistemlerinde sıra bağımlı hazırlık süreli çizelgeleme yaklaşımı
Scheduling with sequence dependent setup times approach in surgery systems
ESRA YILDIRIM
- Single machine scheduling with overtime in multiproduct assembly environment
Çok ürünlü bir montaj ortamında fazla mesai ile tek makine çizelgeleme
MUSTAFA ÜSTÜNÇELİK
Yüksek Lisans
İngilizce
2023
İşletmeAnkara Sosyal Bilimler Üniversitesiİşletme Ana Bilim Dalı
DOÇ. DR. ÇAĞRI KOÇ
DOÇ. DR. HÜSEYİN TUNÇ
- A genetic algorithm for the resource constrained project scheduling problem having a single machine with sequence dependent setup times
Sıra bağımlı kurulum zamanlı tek bir makineye sahip kaynak kısıtlı proje çizelgeleme problemi için bir genetik algoritma
SÜLEYMAN KAYA
Yüksek Lisans
İngilizce
2013
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. SEDEF MERAL
- Sıra bağımlı hazırlık zamanlı tek makineli çizelgeleme problemleri: Gıda sektöründe bir uygulama
Single machine scheduling problems with sequence dependent setup times: An application in food industry
SENA KIR
Yüksek Lisans
Türkçe
2011
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET MUTLU YENİSEY