Geri Dön

Single machine scheduling problemsi early-tardy penalties

Tek makina çizelgeleme problemleri erken- geç penaltıları

  1. Tez No: 29292
  2. Yazar: CEYDA OĞUZ
  3. Danışmanlar: DOÇ. DR. CEMAL DİNÇER
  4. Tez Türü: Doktora
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Deterministik Tek Makina Çizelgelemesi, Toplam Erken-Geç Enazlanması, Hesap Karmaşıklığı Teorisi, Kesin Çözüm Al goritmaları, Dinamik Programlama, Sezgisel Yordamlar, Alt Sınırlar. iv, Deterministic Single Machine Scheduling, Minimizing Total Earliness and Tardiness, Computational Complexity Theory, Dynamic Programming, Heuristic Algorithms, Lower Bounds. 11
  7. Yıl: 1993
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 142

Özet

Özet TEK MAKİNA ÇİZELGELEME PROBLEMLERİ: ERKEN-GEÇ PENALTILARI Ceyda Oğuz Endüstri Mühendisliği Doktora Tez Yöneticisi: Doç. Dr. Cemal Dinçer Mart 1993 Tek makinalı farklı teslim tarihli toplam erken-geç çizelgeleme problemlerini analiz etmek ve problemin hem kesin çözümü için bir dinamik programlama formülasyonu hem de yaklaşık çözümü için kabul edilebilir sınırlar içinde sezgisel yordamlar geliştirmek bu çalışmanın ana içeriğini oluşturmaktadır. Tek makinalı erken-geç çizelgeleme problemleri üzerine daha önce yapılmış çalışmaların incelenmesi, araştırmaların başlıca, çizelgede boş zaman ilave edilmesine izin verilmeyen, kısıtlı bir problem üzerine yoğunlaştığını göstermektedir. Bu çalışma, gerekli olduğu zamanlarda boş zaman ilavesine izin veren genel modelle ilgilenmektedir. Tek makinalı erken-geç çizelgeleme problemleri için, ftfV-zox olmalarına rağmen, dinamik programlama formülasyonu yoluyla eniyi çözüm veren algoritmalara ihtiyaç vardır. Böyle bir algoritma, problem için bir yaklaşık yöntem tanımlayabilmek için gereklidir ki bu erken-geç çizelgeleme kuramında hemen hiç dokunulmamış bir alandır. Bundan başka, geliştirilen dinamik pro gramlama formülasyonu, önerilen sezgisel yöntemlerden birinin özünü oluşturan kısıtlandırılmış durum uzaylı bir dinamik programlama şekline dönüştürülmüştür. iiiBu çalışmanın ikinci bir safhası farklı teslim tarihleri için iki özel yapının, Eşit-Boşluk ve Toplam-İş-İçeriği kurallarının, incelenmesi ve bu özel yapılarla problemin hesap karmaşıklığının tartışılmasıdır. Bu problemler için, özel teslim tarih yapılarının özelliklerine dayanan çözüm yöntemleri önerilmiştir. Eşit-Boşluk kurallı toplam erken-geç çizelgeleme probleminin J\fV-zoı olduğu ispatlanırken, problemin belirli durumlarda polinom zamanda çözülebildiği de gösterilmiştir. Bundan başka, ikinci teslim tarihi yapısı ile problem için çok etkin bir sezgisel yordam önerilmiş ve bu problemden elde edilen sonuçlar, genel teslim tarihli problem için bir başka sezgisel yordamın geliştirilmesine öncülük etmiştir. Son olarak, problemin eniyi çözümünün yapısından kaynaklanan bir alt sınır yöntemi sunulmuştur. Bu alt sınır, literatürden bir başka alt sınır ile kıyaslanmış ve geliştirilen bu alt sınırın rassal yaratılan problemler üzerinde iyi performans gösterdiği gözlemlenmiştir.

Özet (Çeviri)

Abstract SINGLE MACHINE SCHEDULING PROBLEMS: EARLY-TARDY PENALTIES Ceyda Oğuz Ph. D. in Industrial Engineering Supervisor: Assoc. Prof. Dr. Cemal Dinger March 1993 The primary concern of this dissertation is to analyze single machine total earli- ness and tardiness scheduling problems with different due dates and to develop both a dynamic programming formulation for its exact solution and heuristic algorithms for its approximate solution within acceptable limits. The analyses of previous works on the single machine earliness and tardiness scheduling problems reveal that the research mainly focused on a restricted problem type in which no idle time insertion is allowed in the schedule. This study deals with the general case where idle time insertion is allowed whenever necessary. Even though this problem is known to be jV"P-hard in the ordinary sense, there is still a need to develop an optimizing algorithm through dynamic programming formulation. Development of such an algorithm is necessary for further identifying an approximation scheme for the problem which is an untouched issue in the earliness and tardiness scheduling theory. Furthermore, the developed dynamic programming formulation is extended to an incomplete dynamic programming which forms the core of one of the heuristic procedure proposed.A second aspect of this study is to investigate two special structures for the different due dates, namely Equal-Slack and Total- Work-Content rules, and to discuss computational complexity of the problem with these special structures. Consequently, solution procedures which bear on the characteristics of the special due date structures are proposed. This research shows that the total earliness and tardiness scheduling problem with Equal-Slack rule is MV-haxa. but can be solvable in polynomial time in certain cases. Moreover, a very efficient heuristic algorithm is proposed for the problem with the other due date structure and the results of this part leads to another heuristic algorithm for the general due date structure. Finally, a lower bound procedure is presented which is motivated from the structure of the optimal solution of the problem. This lower bound is compared with another lower bound from the literature and it is shown that it performs well on randomly generated problems.

Benzer Tezler

  1. Tez No

    472965

    Ağırlıklı toplam erken/geç bitirme süresi minimizasyonu amaçlı tek makine çizelgeleme problemi için boş zaman ilaveli dal sınır algoritması yaklaşımı

    Single machine earliness-tardiness scheduling problem by branch and bound with insertion idle time

    SEBRINA DAWD

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    Endüstri ve Endüstri Mühendisliğiİstanbul Ticaret Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. BERK AYVAZ

  2. Tez No

    170810

    Auction based scheduling for distributed systems

    Dağınık sistemler için ihale tabanlı çizelgeleme

    EMRAH ZARİFOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2005

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Bölümü

    PROF.DR. İHSAN SABUNCUOĞLU

  3. Tez No

    143347

    Scheduling with discounted revenues

    İskonto edilmiş gelirlerle çizelgeleme

    AHMET KICIROĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2003

    İstatistikOrta Doğu Teknik Üniversitesi

    Yöneylem Araştırması Ana Bilim Dalı

    PROF. DR. MERAL AZİZOĞLU

    YRD. DOÇ. DR. HALDUN SÜRAL

  4. Tez No

    335632

    Common due date early/tardy scheduling on a single machine with deteriorating jobs and deteriorating maintenance

    Ortak teslim tarihli pozisyona bağlı bozulan işler ile bakım faaliyetinin, tek makinede erken/geç tamamlanma maliyetlerinin en küçüklenerek çizelgelenmesi

    FATMA ŞİRVAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2013

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Bölümü

    PROF. DR. ÜLKÜ GÜRLER

    DOÇ. DR. MEHMET RÜŞTÜ TANER

  5. Tez No

    39859

    Tam zamanında üretim sistemi ve imalat kaynak planlaması (MRP II) sistemi ile ilişkileri

    Just-in-time productıon system and its relatıons with MRP II (Material Resource Plannıng)

    BAYBARS ELİÇİN

    Yüksek Lisans

    Türkçe

    Türkçe

    1993

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. MEHMET TANYAŞ

Geri Dön