Özdeş olmayan paralel makina çizelgeleme problemlerinin çözümü için bir karar destek sistemi

Öz

İşletmelerin üretim planlama faaliyetlerinde makina çizelgeleme kısa dönem planlamada sık tekrarlanan bir faaliyet olup kaynakların etkin kullanımı açısından çok önemlidir. Gerek darboğaz problemleri gerek kapasiteyi arttırma amaçlı aynı işi yapabilen birden fazla makina bulanan atölyelerde atölye ortamı ne olursa olsun bir paralel makina çizelgeleme probleminin de çözülmesi gereği ortaya çıkmaktadır. Özellikle özdeş olmayan paralel makinalarda işin hangi makinada işleneceği birçok faktöre bağlı olarak belirlenmek istenmektedir. Bu tür durumlara genel yazılımlar cevap verememektedir. Ayrıca plastik akıtma, fırınlama gibi paralel makina ortamlarında iş sırasına bağlı olarak hazırlık sürelerinin değişmesi durumu söz konusu olduğunda sıraya bağımlı hazırlık sürelerini de dikkate alan çizelgeler hazırlamak planlamacılar için önem arz etmektedir.  Bu kapsamda, çalışmada sıraya bağımlı hazırlık süreli özdeş olmayan paralel makina çizelgeleme problemleri için bir karar destek sistemi tasarlanmıştır. Karar verici ilgili sistemi kullanarak, durumsallık yaklaşımıyla ilgili dönemde atölyede hangi amaç için işlerin çizelgelenmesi gerekiyorsa ilgili amaca göre çizelgeyi elde edebilir. Ayrıca, işleri en kısa sürede bitirmek ve geciken iş sayısını en küçüklemek gibi farklı amaç fonksiyonları için çizelgeleri elde etme ve sonuçlarını karşılaştırma imkânı bulabilir. Karar destek sisteminin model temelinde, büyük boyutlu gerçek hayat çizelgeleme problemlerine kısa sürede çözüm üretebilen ileri sezgisel algoritmalar kullanılmıştır.

Anahtar Kelimeler

• Özdeş olmayan paralel makina çizelgeleme,Sıraya bağımlı Hazırlık Süreleri,Karar destek sistemi,Tavlama benzetimi,Yasaklı arama

A decision support system for non-identical parallel machine scheduling

Abstract

Machine scheduling in the production planning activities of enterprises is an activity that is frequently repeated in short periods and is very important in terms of efficient use of resources. It is necessary to solve a parallel machine scheduling problem regardless of the workshop environment in workshops where more than one machine that can do the same job to increase the capacity and solve the bottleneck problems. Especially in non-identical parallel machines, it is desired to determine which machine will process the job depending on many factors. A general software cannot respond to such situations. In addition, it is important for planners to prepare charts that take into account sequence dependent setup times in parallel machine environments such as plastic injection and oven scheduling problems. In this context, the study is focused on designing a decision support system for non-identical parallel machine scheduling problems with sequence dependent setup times. By using the decision support system, the decision maker can obtain the schedule for the jobs need to be scheduled for the relevant period and purpose according to situation of workshop. The system makes it possible to find and compare schedules for different objective functions such as minimizing makespan and minimizing the number of tardy jobs. On the basis of the model of the decision support system, meta-heuristic algorithms that can produce a solution to large scale real-life scheduling problems in a short time have been used.

Keywords

• Non-identical parallel machine scheduling,Sequence dependent setup Times,Decision support system,Simulated annealing,Tabu search

Kaynakça

1. Pinedo M. Scheduling Theory, Algorithms, and Systems. Second Edition, New Jersey, USA, Prentice Hall, 2002.
2. Allahverdi A, Gupta JND, Aldowaisan, T. “A review of scheduling research involving setup considerations”. Omega, 27(2), 219-239, 1999.
3. Allahverdi A, Ng CT, Cheng TCE, Kovalyov M. “A survey of scheduling problems with setup times or costs”. European Journal of Operational Research, 187(3), 985-1032, 2008.
4. Li K, Yang SL. “Non identical parallel machine scheduling research with minimizing total weighted completion times: Models, relaxations and algorithms, Applied Mathematical Modelling, 33(4), 2145-2158, 2009
5. Chen CL, Chen CL. “Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times”. International Journal of Advanced Manufacturing Technology, 43(1-2), 161-169, 2009.
6. Tavakkoli-Moghaddam R, Taheri F, Bazzazi M. “Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints”. Computers & Operations Research, 36(12), 3224-3230, 2009.
7. Arnaout JP, Rabadi G, Musa R. “A two-stage Ant Colony Optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times”. Journal of Intelligent Manufacturing, 21(6), 693-701, 2010.
8. Vallada E, Ruiz R. “A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times”. European Journal of Operational Research, 211(3), 612-622, 2011.

9. Lin SW, Lu CC, Ying KC. “Minimization of total tardiness on unrelated parallel machines with sequence- and machine-dependent setup times under due date constraints”. International Journal of Advanced Manufacturing Technology, 53(1-4), 353-361, 2011.
10. Ying KC, Lin SW. “Unrelated parallel machine scheduling with sequence and machine-dependent setup times and due date constraints”. International Journal of Innovative Computing Information and Control, 8(5A), 3279-3297, 2012.
11. Hsu CJ, Ji M, Guo JY, Yang DL. “Unrelated parallel-machine scheduling problems with aging effects and deteriorating maintenance activities”. Information Sciences, 253, 163-169, 2013.
12. Naderi-Beni M, Ghobadian E, Ebrahimnejad S, Tavakkoli Moghaddam R. “Fuzzy bi-objective formulation for a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times”. International Journal of Production Research, 52(19), 5799-5822, 2014.
13. Sarıçiçek İ, Çelik C. “Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness”. Applied Mathematical Modelling, 35(8), 4117-4126, 2011.
14. Kirkpatrick S, Gelatt CD, Vecchi MP. “Optimization by Simulated Annealing”. Science, 220(4598), 671-680, 1983.