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ı: Belirtilmemiş.
Ö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Ç
- Paralel makineli sıra bağımlı hazırlık süreli çok kademeli makine çizelgeleme problemlerinin çözümü için kümeleme tabanlı ve sınırlı sayımlama temelli bir çözüm yaklaşımı
A clustering and restricted enumeration based solution approach for scheduling multi-stage parallel machines with sequence dependent setup times
HACER DEFNE OKUL
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri MühendisliğiEskişehir Osmangazi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MÜJGAN SAĞIR
- Methods for hybrid flow shop scheduling and a case study in an aerospace company
Melez akış tipi atölye çizelgelemesi için yöntemler ve bir havacılık firmasında vaka analizi
YİĞİTALP ÖZMEN
Yüksek Lisans
İngilizce
2019
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. FATMA SEDEF MERAL
- Esnek atölye tipi çizelgeleme problemi için bir hibrid genetik algoritma yaklaşımı
A hybrid problem perturbation and genetic algorithm for the flexible job-shop scheduling problem
BİLAL METO
Yüksek Lisans
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTobb Ekonomi ve Teknoloji ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. KADİR ERTOĞRAL
DOÇ. DR. ERDOĞAN DOĞDU