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
Yazar: MÜGE HANIM ÖZDEMİR
Danışman: DOÇ.DR. ERTAN GÜNER
Gazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2007
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Ö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

Abstract:
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