Geri Dön

Rescheduling parallel machines with controllable processing times

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

  1. Tez No: 307567
  2. Yazar: MÜGE MUHAFIZ
  3. Danışmanlar: PROF. DR. M. SELİM AKTÜRK
  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: 2012
  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ı: 118

Özet

İmalat sistemlerinde, üretim her zaman planlandığı gibi uygulanamaz. Çoğu zaman, makine bozulması, elektrik kesintisi gibi nedenlerden dolayı üretim aksamak zorunda kalır. Bu çalışmada, özdeş olmayan paralel makinelerin bulunduğu bir imalat ortamında, önceden planlanmış bir üretim çizelgesinde,makinelerden birinde herhangi bir t anında aksama meydana geldiği varsayımında bulunduk ve makinelerde yeniden çizelgeleme üzerine çalıştık.Bu çalışmada önceden planlanmış çizelgeyi aksaklık sonrasında mümkün olduğunca çabuk yakalamayı ve aksaklıktan dolayı meydana gelen zaman kaybını telafi etmeyi amaçladık. Ancak yeniden çizelge oluştururken dikkat etmemiz gereken bazı kısıtlamalar bulunmaktadır. Aksaklık sona erene kadar, aksamameydana gelen makine durur ve hiçbir iş işleyemez. Diğer bir yandan, yeni çizelgede makinelerin kapasite kısıtına dikkat edilmelidir. Bununla birlikte, yeni çizelgede işlerin başlangıç zamanları önceden planlanan çizelgeki başlangıç zamanlarından daha erken olmamalıdır.Makinede meydana gelen aksaklığın negatif etkilerini yumuşatmak için alternatif bir çözüm bulmamız gerekmektedir. Bunun bir yolu aksayan bir işi başka bir makineye taşımak ya da aksayan işi başlangıçtaki makinesinde bırakmak ancak aksamanın bitişinden sonra işlemektir. Ancak makinelerin kapasitesi tamamen dolu olabileceği göz önünde bulundurulursa, bir makineye yeni bir iş taşıyabilmek ya da aksayan makinede işleri aksama bittikten sonra işleyebilmek için işlerin işlem sürelerini sıkıştırmak zorunda kalınabilir. Sonuç olarak, bu çalışmada işlerin işlem sürelerinin en az ve en yüksek sınırlar dahilinde kontrol edilebilir olduğu varsaymını kullandık.Öncelikli amacımız, işlem sürelerinin sıkıştırılma miktarının doğrusal olmayan bir fonksiyonu olan sıkıştırma maliyeti ile taşıma maliyetini enazlamaktır. Bunun yanı sıra, çizelgede aksaklık olsa bile işlerin mümkün olan en kısa zamanda tamamlanması çok önemlidir. Bu yüzden işlerin ilk çizelgedeki bitis sürelerini mümkün olduğunca yakalamaya calışmayı amaçlamaktayız. Dolayısıyla, ikinci amacımız, yeniden oluşturulan çizelge ile ilk çizelgedeki işlerin bitiş zamanlarıarasındaki mutlak farkların toplamını enazlamaktır.Bu problemi çözebilmek için çift hedefli doğrusal olmayan bir matematiksel model geliştirdik. Çift hedefimiz olduğu için ikinci hedefimiz olan bitiş zamanları mutlak farklarının toplamına bir üst sınır vererek bu sınırı matematiksel modelekısıt olarak ekledik. İkinci derece konik programlama tekniğinden faydalanarak, bu modeli CPLEX ile karmaşık tam sayılı matematiksel modele çevirerek çözdük. Problemin zorluğundan dolayı, çok uzun hesaplama sürelerinde mutlak çözüm bulunamadığı durumlar için etkin çözümler üreten hızlı sezgisel tarama algoritmaları geliştirdik. Saysal deneylerimize göre, önerdiğimiz sezgisel yöntemler ikinci amaçfonksiyonu için verilen üst sınır kısıtı altında, birinci amaç fonksiyonu açısından matematiksel modelle yakın sonuçlara ulaşmaktadır.

Özet (Çeviri)

In many manufacturing environments, the production does not always endure as it is planned. Many times, it is interrupted by a disruption such as machine breakdown, power loss, etc. In our problem, we are given an original production schedule in a non-identical parallel machine environment and we assume that one of the machines is disrupted at time t.Our aim is to revise the schedule, although there are some restrictions that should be considered while creating the revised schedule. Disrupted machine is unavailable for a certain time. New schedule has to satisfy the maximum completion time constraint of each machine. Furthermore, when we revise the schedule we have to satisfy the constraint that the revised start time of a job cannot be earlier than its original start time. Because, we assume that jobs arenot ready before their original start times in the revised schedule.Therefore, we have to find an alternative solution to decrease the negative impacts of this disruption as much as possible. One way to process a disrupted job in the revised schedule is to reallocate the job to another machine. The other way is to keep the disrupted job at its original machine, but to delay its start time after the end time of the disruption. Since the machines might be fully utilized originally, we may have to compress some of the processing times in order to add a new job to a machine or to reallocate the jobs after the disruption ends.Consequently, we assume that the processing times are controllable within the given lower and upper bounds.Our first objective is to minimize the sum of reallocation and nonlinear compression costs. Besides, it is important to deliver the orders on time, not earlier or later than they are promised. Therefore, we try to maintain the original completiontimes as much as possible. So, the second objective is to minimize the total absolute deviations of the completion times in the revised schedule from the original completion times.We developed a bi-criteria non-linear mathematical model to solve this nonidentical parallel machine rescheduling problem. Since we have two objectives, we handled the second objective by giving it an upper bound and adding this bound as a constraint to the problem. By utilizing the second order cone programming, we solved this mixed-integer nonlinear mathematical model using a commercial MIP solver such as CPLEX. We also propose a decision tree based heuristic algorithm. Our algorithm generates a set of solutions for a problem instance and we test the solution quality of the algorithm solving same problem instances by the mathematical model. According to our computational experiments, theproposed heuristic approach could obtain close solutions for the first objective for a given upper bound on the second objective.

Benzer Tezler

  1. 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

    DERYA CİNCİOĞLU

    Yüksek Lisans

    İngilizce

    İngilizce

    2011

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

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

    YRD. DOÇ. DR. SİNAN GÜREL

  2. 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

  3. Simulation based optimization using simulated annealing for dynamic scheduling of parallel machines with a common server

    Ortak sunuculu paralel makinelerin dinamik çizelgelemesi için tavlama benzetimi tabanlı simülasyon optimizasyonu

    ALPER HAMZADAYI

    Doktora

    İngilizce

    İngilizce

    2014

    Endüstri ve Endüstri MühendisliğiDokuz Eylül Üniversitesi

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

    YRD. DOÇ. DR. GÖKALP YILDIZ

  4. 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

  5. Hipotetik bir tekstil atölyesinin dinamik çizelgelenmesinde yollama kurallarının benzetim tekniğiyle analizi

    Dynamic scheduling in hypothetic textile shop for analyzing dispatching rules via simulation technique

    MURAT ELHÜSEYNİ

    Yüksek Lisans

    Türkçe

    Türkçe

    2012

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

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

    YRD. DOÇ. DR. CAFER ERHAN BOZDAĞ