Kısıtlandırılmış teslim tarihli ve sıraya-bağımlı hazırlık süreli tek makine çizelgeleme problemlerinde erkenlik ve geçlik toplamının en küçüklenmesi
Minimizing the total earliness and tardiness for single machine scheduling problems with restricted due date and sequence-dependent setup times
- Tez No: 199871
- Danışmanlar: DOÇ.DR. ERTAN GÜNER
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2007
- Dil: Türkçe
- Üniversite: Gazi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 122
Özet
ivKISITLANDIRILMIŞ TESL M TAR HLVE SIRAYA-BAĞIMLI HAZIRLIK SÜRELTEK MAK NE Ç ZELGELEME PROBLEMLER NDEERKENL K VE GEÇL K TOPLAMININ EN KÜÇÜKLENMES(Yüksek Lisans Tezi)Müge Hanım ÖZDEM RGAZ ÜN VERS TESFEN B L MLER ENST TÜSÜOcak 2007ÖZETBu tezde, sıraya-bağımlı hazırlık süreleri içeren tek makineli bir çizelgelemeproblemi incelenmiştir. Problemde tüm işler ortak bir teslim tarihine sahip olupişlerin bu tarihten önce veya sonra tamamlanması arzu edilmez. Erken veya geçtamamlanmadan dolayı cezalar ortaya çıkar. Literatürde bu problemErkenlik/Geçlik (E/G) problemi olarak bilinir. Burada temel amaç, erkenlik vegeçlik toplamını en küçüklemektir. Japonların ortaya koyduğu TamZamanında (TZ) üretim felsefesinin popülerliğinin artması ile E/G problemi deyaygınlaşmıştır.Bu çalışmada, erkenlik ve geçlik eşit ağırlığa sahiptir ve teslim tarihi tüm işleriçin ortak ve kısıtlandırılmıştır. Çizelgeleme literatüründe genellikle makinehazırlık süreleri göz ardı edilir veya işlem sürelerinin içinde varsayılır. Buçalışmada, makinenin hazırlık süresi işlem süresinden ayrı ve sıraya-bağımlıolarak ele alınmıştır. Hazırlık sürelerinin dikkate alınmasıyla probleminkarmaşıklığı oldukça artmış ve NP-zor bir problem olmuştur.Çalışmada, küçük boyutlu problemlerin en iyi çözümlerini elde etmek için birKarışık Tamsayılı Programlama (KTP) modeli kullanılmıştır. Büyük boyutluproblemlerin en iyi çözümlerini KTP ile makul sürelerde bulmak mümkünvolmamıştır. Bu nedenle, daha önce kısıtlandırılmamış ortak teslim tarihliproblem için geliştirilen düzenlenmiş en küçük işlem süreli işin ilkyerleştirilmesine dayanan SAPT sezgiseli kısıtlandırılmış duruma uyarlanarakbüyük boyutlu problemler için çözümler elde edilmiştir. Bu çözümlerigeliştirmek için SAPT sezgiseliyle bulunan çözüm Tabu Arama (TA)algoritmasının başlangıç çözümü olarak kullanılmıştır. Hem SAPT sezgiselininve hem de TA algoritmasının performansı, çözümlerinin en iyi çözümlerdensapması dikkate alınarak ölçülmüştür. SAPT sezgiseliyle kabul edilebilirçözümler bulunmakla birlikte, TA algoritması pek çok örnekte iyileştirmesağlamış ve iş sayısı 180'e kadar olan problemlerin çözümlerigerçekleştirilmiştir.Bilim Kodu : 906.1.141Anahtar Kelimeler : Erkenlik, geçlik, sıraya-bağımlı, kısıtlandırılmış, tekmakineSayfa Adedi : 109Tez Yöneticisi : Doç. Dr. Ertan GÜNER
Özet (Çeviri)
viMINIMIZING THE TOTAL EARLINESS AND TARDINESS FOR SINGLEMACHINE SCHEDULING PROBLEMS WITH RESTRICTED DUE DATEAND SEQUENCE-DEPENDENT SETUP TIMES(M.Sc. Thesis)Müge Hanım ÖZDEM RGAZ UNIVERSITYINSTITUTE OF SCIENCE AND TECHNOLOGYJanuary 2007ABSTRACTIn this thesis, a single-machine scheduling problem including sequence-dependent setup times is discussed. All jobs have a common due date in thisproblem and it is not desired that the jobs complete before or after the due date.In the literature, this problem is known as the Earliness/Tardiness (E/T)problem. The main objective is minimizing the total amount of earliness andtardiness. The E/T problem became common by the popularity of the Just-In-Time (JIT) Japanese manufacturing philosophy increased.In this research, earliness and tardiness have equal weights and the due date iscommon and restricted for all jobs. In the most scheduling literature, machinesetup time was ignored or assumed to be part of the jobs? processing times. Inthis thesis, the machine setup is separated from the processing time and isconsidered to be sequence-dependent. The intricacy of the problem increasesdramatically and the problem becomes NP-hard when sequence-dependentsetup times are included. Therefore, optimal solutions cannot be obtained in apolynomial time.A Mixed Integer Programming (MIP) is used to obtain optimal solutions forsmall sized problems. For large-sized problems, obtaining optimal solutionsusing exact methods is not feasible. Therefore, the ?Shortest AdjustedviiProcessing Time First? (SAPT) heuristic developed before for unrestrictedcommon due date of this problem is also adapted to restricted version. After, aTabu Search (TS) algorithm is implemented to find better solutions using thebest solution of the SAPT heuristic as an initial solution. The performance of theSAPT heuristic and the TS algorithm are measured by considering thedeviations of their solutions from the optimal solutions. SAPT heuristic providedacceptable solutions; however, the TS algorithm outperformed the SAPTheuristic in the most cases and results for problems up to 180 jobs were found.Science Code : 906.1.141Key Words : Earliness, tardiness, sequence-dependent, restricted, singlemachinePage Number : 109Adviser : Assoc. Prof. Ertan GÜNER
Benzer Tezler
- Single machine scheduling problemsi early-tardy penalties
Tek makina çizelgeleme problemleri erken- geç penaltıları
CEYDA OĞUZ
Doktora
İngilizce
1993
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEMAL DİNÇER
- Noise enhanced detection in restricted Neyman-Pearson framework
Kısıtlandırılmış Neyman-Pearson çerçevesinde gürültü iyileştirmeli sezim
ŞAN GÜLTEKİN
Yüksek Lisans
İngilizce
2013
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
DOÇ. DR. SİNAN GEZİCİ
- A heuristic solution procedure for the constrained node routing problem and an implementation to hazardous solid waste collection
Kısıtlandırılmış nokta dolaşım problemi için bir höristik çözüm prosedürü ve tehlikeli katı atık toplanmasına yönelik bir uygulanışı
ALİ TÜMER AKYÜZ
Yüksek Lisans
İngilizce
1992
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF.DR. İLHAN OR
- Sıralı seçenek hipotezlerinde kullanılan testler
Tests used in the ordered alternatives hypothesis
HATİCE DAĞLIOĞLU
Yüksek Lisans
Türkçe
2008
İstatistikHacettepe Üniversitesiİstatistik Ana Bilim Dalı
DR. SERPİL AKTAŞ ALTUNAY
- A comparative study of quadtree decomposition and constrained delaunay triangulation using mdp and artificial potential field based path planning
Dördün ağaç ayrıştırması ve kısıtlandırılmış delaunay üçgenleştirmesinin markov karar süreci ve yapay potansiyel alan tabanlı yol planlaması kullanılarak karşılaştırmalı bir çalışması
BAŞER KANDEHİR
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. AFŞAR SARANLI