A hybrid solution for makespan minimization in identical parallel machines with release time constraint
Paralel makinelerde hazır olma zamanı kısıtı altında yayılma alanını en küçükleme problemine melez bir çözüm
- Tez No: 343455
- Danışmanlar: YRD. DOÇ. DR. SEROL BULKAN
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 96
Özet
Çizelgeleme, üretim ve hizmet endüstrilerinde çok önemli bir karar verme süreci olup matematiksel teknikler ve/veya sezgisel yöntemler kullanılarak, işletmenin kıt kaynaklarının gereken görevlere atanmasını sağlar. Çizelgeleme problemlerinin çoğu NP-zor problemlerdir. Bu gibi problemlerde en iyi sonucu polinom zamanda bulmak imkansız olduğundan bir takım sezgisel yöntemler kullanılmaktadır. Bu yöntemler, her ne kadar en iyiyi bulmaya çalışsa da bunu garanti edemezler. İste bu sebeple de sezgisel olarak tanımlanırlar. Çizelgeleme teorisindeki en temel problemlerden biri“n”tane işi“m”tane makineye yayılma alanını en aza indirmeyi amaçlayarak atama problemidir. Bu problem 3 alanlı gösterim tipi temel alınacak olursa Pm||Cmax şeklinde gösterilebilir. Bu tipteki çizelgeleme problemlerine çözüm olarak sunulan en eski ve en etkili metot ise LPT (Longest Processing Time) yöntemidir. Problem bu haldeyken bile NP-zor bir problemdir ve polinom zamanda en iyi sonucu bulmak garanti edilemez. Bu problem tipine hazır olma zamanı kısıtı da eklenecek olursa problemin çözümü gittikçe zorlaşmaktadır. Hazır olma zamanı, bir işin işlenmeye hazır olduğu zamanı göstermektedir. Bu yeni haliyle problem Pm|rj|Cmax olarak ifade edilebilir. Bir ürünün parçalarının birbirinden farklı zamanlarda üreticiye ulaşması, yani işlerin farklı hazır olma zamanlarının olması, üretimin tamamlanma zamanını belirleyen en önemli faktörlerden biridir. Bu durum parçaların yanlış sıralarda üretime sokulması ile alıcıya teslim zamanını geciktirebileceği gibi bazı parçaların uzun süre depolarda bekletilmesi gibi problemlere sebep olabilir. Bu nedenle farklı zamanlarda üreticiye gelen işlerin doğru sıralarda işleme sokulması sadece üretici değil iş sahibi herkes açısından önem arz etmektedir. Bu tezde farklı hazırlık ve işlem süreleri olan işlerin paralel ve özdeş makinelere en etkin şekilde atanması ve böylece yayılma alanının minimize edilmesi hedeflenmiştir. Bunun için, önce bir sezgisel yöntem önerilmiş, ardından üç farklı çarprazlama metodu olan genetik algoritma geliştirilmiştir. Daha sonra, genetik algoritma parametreleri üzerinde deney tasarımı yapılmıştır. Son olarak, sezgisel yöntemle genetik algoritma birleştirilerek melez bir metot geliştirilmiştir.
Özet (Çeviri)
Scheduling is an important decision concern especially in production and service sector. It deals with the assignment of limited resources to tasks by using mathematical techniques and/or heuristics. Mostly, scheduling problems are NP-hard and since it is practically impossible to find the optimum solution in polynomial time, heuristic methods are proposed. Although those methods try to find the optimum solution, they do not guarantee optimality and because of that they are called heuristic. One of the fundamental problems in scheduling theory is to assign“n”jobs to“m”machines by considering the minimization of makespan as the objective function. If the 3-field notation is used, this problem can be denoted as Pm||Cmax. One of the earliest approaches to such scheduling problems is the Longest Processing Time (LPT) priority rule. Even in this way, the problem is NP-hard and the method cannot guarantee to find the optimum solution in a polynomial time. If we also add release time constraint, which shows the time that the job is ready for processing, the problem even gets harder to be solved. In this way, the problem is denoted as Pm|rj|Cmax in which rj stands for release time for Job j Different release times of the components of a product is one of the most important factors determining the makespan of a production process. If the components are scheduled in an ineffective order, it can cause some problems like late delivery to the customer or keeping the components in stocks for a long time. Because of that correct scheduling of components of a product is an essential task for producers. In this thesis, jobs, having different processing and release time, are assigned to identical parallel machines with the objective of minimizing makespan. To do so; first, a new heuristic is proposed. Next, a genetic algorithm with three different crossover methods is given. Later, a design of experiments part is done on genetic algorithm and finally, a hybrid method combining the heuristic and the genetic algorithm with the selected crossover is proposed.
Benzer Tezler
- Bir dinamik hibrid esnek akış atölyesi çizelgeleme problemi
A realistic dynamic hybrid flexible flowshop shceduling problem
SİMAY SEZGİ UZEL
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. GÜLTEKİN KUYZU
- Development of a structured methodolgy for flexible manufacturing management systems (FMMS)
Esnek imalat yönetim sistemi için yapısal bir yöntem geliştirilmesi
CAN SAYGIN
Doktora
İngilizce
1997
Makine MühendisliğiOrta Doğu Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. S. ENGİN KILIÇ
- Tabu search based solution approaches for lot streaming problems in flow shops
Akış tipi sistemlerde, kafile bölme ve kaydırma problemleri için tabu arama tabanlı çözüm yaklaşımları
RAHİME SANCAR EDİS
Doktora
İngilizce
2009
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ARSLAN ÖRNEK
- Solving single and parallel machine scheduling problems with sequence dependent setup times using differential evolution based algorithms
Sıra bağımlı hazırlık süreleri içeren tek ve paralel makinalı çizelgeleme problemlerini diferensiyel evrim algoritması tabanlı algoritmalar kullanarak çözmek
ÖĞÜNÇ ÖZDEMİR
Yüksek Lisans
İngilizce
2010
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞEYDA TOPALOĞLU
- Çok amaçlı enerji verimli atölye çizelgeleme problemi için yeni bir çözüm yaklaşımı: WASPAS tabanlı NSGA-2
A new solution approach for multi-objective energy efficient job shop scheduling problem: WASPAS based NSGA-2
MİNE BÜŞRA GELEN MERT
Doktora
Türkçe
2024
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALPARSLAN SERHAT DEMİR