Geri Dön

A rescheduling problem with controllable processing times: Trade-off between number of disrupted jobs and rescheduling costs

Kontrol edilebilir işlem süreleriyle yeniden çizelgeleme: Arızadan etkilenen iş sayısı ve yeniden çizelgeleme maliyeti arasındaki ilişkiler

  1. Tez No: 305698
  2. Yazar: DERYA CİNCİOĞLU
  3. Danışmanlar: YRD. DOÇ. DR. SİNAN GÜREL
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2011
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 92

Özet

Bu çalışma, kontrol edilebilir işlem sürelerinin söz konusu olduğu özdeş olmayan paralel makinalarda işlerin yeniden çiizelgelenmesi problemini dikkate almaktadır. Makine arızası, hammadde eksikliği ya da arızalanan bir parça sebebiyle makinelerden birinin belli bir dönem kullanım dışı olması söz konusu olabilmektedir. Bu aksaklıklar mevcut çizelgenin verimsiz ilerlemesine, hatta bazen de tamamlanmasının mümkün olmamasına sebebiyet verebilmektedir. Yeni ve uygulanabilir bir çiizelge oluşturabilmek içinse, kararlılık ve verimlilik gibi çatışan iki ölçüm değerini aynı anda hesaba katmak gerekmektedir. Verimlilik, istenen hedef fonksiyondeğerini ölçerken, kararlılıksa arıza öncesi ve sonrası çizelgede meydana gelen sapmanın büyüklüğünü ölçmektedir. Bu çalışmada biz kararlılığı geç tamamlanan işlerin sayısı cinsinden ölçümlendirmekteyiz. Bu tezde; yeniden çizelgelenen bir iş eğer arıza oluşmadan önceki çizelgedeki planlanan tamamlanma zamanından daha geç tamamlanıyorsa, geç tamamlanan iş olarak adlandırılmaktadır. Verimlilik, işleri ek üretim maliyetleri cinsinden ölçümlendirmektedir. Geç tamamlanan işlerin azaltılması işlerin işlem sürelerinin sıkıştırılmasını gerektirmektedir, bu da işlerin ek üretim maliyetinlerinde artışa sebep olmaktadır. Bu sebeple her iki ölçüm değerini aynı anda azaltmak mümkün olmamaktadır. Bu soruna çözüm bulabilmek amacıyla epsilon-kısıt yaklaşımı uygulanan karışık tamsayılı doğrusal programlama modeli geliştirilmiştir. Bu yaklaşım tek bir ölçüm hedefine odaklanarak verimli sonuçlar elde etmeye olanak sağlamaktadır. Bu yüzden biz de ek üretim maliyetlerinin geç tamamlanan iş sayısı kısıtlanacak şekilde en aza indirilmesi problemi üzerine çalışmalar yaptık. Ayrıca her iş için konveks sıkıştırma maliyeti fonksiyonunu hesaba katıp, maliyeti en aza indirme problemini ikinci derece konik programlama kullanarak modelimiz için çözümledik. Maliyet fonksiyonlarının konvekslik özelliği optimum çözümlerin bulunmasının önündeki en büyük sorun kaynağınıoluşturmaktaydı. Fakat güçlendirilmiş konik programlama metotlarını kullanarak bu sorunun da üstesinden gelinmiştir. Ayrıca, makul CPU sürelerinde uygun çözümler bulabilmek amacıyla bir geliştirici tarama algoritması da geliştirilmiştir. Önerilen algoritmanın uygulama aşamasında kullanmak üzere, en iyileme özellikleri tek makina çizelgeleme problemi için araştırılmıştır. Küçük ve orta ölçekli test problemleri için sayısal deneyler yapılarak, matematiksel model ve geliştirici tarama algoritmasının performansları çözüm kalitesi ve süreler cinsinden karşılaştırılmıştır.

Özet (Çeviri)

In this thesis, we consider a rescheduling problem on non-identical parallel machines with controllable processing times. A period of unavailability occurs on one of the machines due to a machine failure, material shortage or broken tool. These disruptions may cause the original schedule to become inefficient and sometimes infeasible. In order to generate a new and feasible schedule, we are dealing with two conflicting measures called the efficiency and stability measures simultaneously. The efficiency measure evaluates the satisfaction of a desired objective function value and the stability measure evaluates the amount of change between the schedule before and after the disruption. In this study, we measure stability by the number of disrupted jobs. In this thesis, the job is referred as a disrupted job if it completes processing after its planned completion time in the original schedule. The efficiency is measuredby the additional manufacturing cost of jobs. Decreasing number of disrupted jobs requires compressing the processing time of a job which cause an increase in its additional manufacturing cost. For that reason we cannot minimize these objectives at the same time. In order to handle this, we developed a mixed integer programming model for the considered problem by applying the epsilon-constraint approach. This approach makes focusing on the single objective possible to get efficient solutions. Therefore, we studied the problem of minimizing additional manufacturing cost subject to a limit on the number of disrupted jobs. We also considered a convex compression cost function for each job and solved a cost minimization problem by applying conic quadratic reformulation for the model. The convexity of cost functions is amajor source of difficulty in finding optimal integer solutions in this problem, but applying strengthened conic reformulation has eliminated this difficulty. In addition, we prepare an improvement search algorithm in order to find good solution in reasonable CPU times. We use our heuristic procedure on optimality properties we showed for a single machine subproblem. We made computational experiments on small and medium scale test problems. Afterwards, we compare the performance of the improvement search algorithm and mathematical model for their solution quality and durations.

Benzer Tezler

  1. Time/cost trade-offs in machine scheduling with controllable processing times

    Kontrol edilebilir işlem süreleriyle makine çizelgelemede maliyet/zaman ilişkileri

    SİNAN GÜREL

    Doktora

    İngilizce

    İngilizce

    2008

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

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

    PROF. DR. M. SELİM AKTÜRK

  2. Rescheduling parallel machines with controllable processing times

    Kontrol edilebilir işlem süreleriyle paralel makinalarda yeniden çizelgeleme

    MÜGE MUHAFIZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2012

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

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

    PROF. DR. M. SELİM AKTÜRK

  3. Dynamic security enhancement of power systems via population based optimization methods integrated with artificial neural networks

    Yapay sinir ağlarının entegre edildiği popülasyon tabanlı optimizasyon yöntemleriyle güç sistemlerinin dinamik güvenliğinin iyileştirilmesi

    CAVİT FATİH KÜÇÜKTEZCAN

    Doktora

    İngilizce

    İngilizce

    2015

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektrik Mühendisliği Ana Bilim Dalı

    DOÇ. VEYSEL MURAT İSTEMİHAN GENÇ

  4. Planning of train movements in single track railways

    Tek hatlı demiryollarında tren hareketlerinin planlanması

    GÖKÇE AYDIN

    Doktora

    İngilizce

    İngilizce

    2015

    UlaşımYıldız Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. İSMAİL ŞAHİN

  5. A bicriteria rescheduling problem on unrelated parallel machines: Network flow and enumeration based approaches

    İlgisiz paralel makinelerde iki kriterli yeniden çizelgeleme problemi: Ağ akış ve birerleme tabanlı yaklaşımlar

    MELİH ÖZLEN

    Doktora

    İngilizce

    İngilizce

    2006

    Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik Üniversitesi

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

    PROF. DR. MERAL AZİZOĞLU