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
- Tez No: 305698
- Danışmanlar: YRD. DOÇ. DR. SİNAN GÜREL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2011
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2008
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. DR. M. SELİM AKTÜRK
- Rescheduling parallel machines with controllable processing times
Kontrol edilebilir işlem süreleriyle paralel makinalarda yeniden çizelgeleme
MÜGE MUHAFIZ
Yüksek Lisans
İngilizce
2012
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. M. SELİM AKTÜRK
- 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
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
DOÇ. VEYSEL MURAT İSTEMİHAN GENÇ
- Planning of train movements in single track railways
Tek hatlı demiryollarında tren hareketlerinin planlanması
GÖKÇE AYDIN
Doktora
İngilizce
2015
UlaşımYıldız Teknik Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
DOÇ. DR. İSMAİL ŞAHİN
- 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
2006
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MERAL AZİZOĞLU