Hazırlık Zamanlı Ortak Teslim Tarihli Özdeş Paralel Makine Çizelgeleme Problemlerinin Çok Amaçlı Çözümü

Paralel makine çizelgeleme problemi tek makine çizelgeleme probleminin genişletilmiş hâlidir. Aynı işi yapan birden fazla makinenin olduğu üretim ortamları, paralel makineli üretim ortamları olarak tanımlanır. Paralel makine çizelgeleme problemleri işlerin makinelere atanması ve sıralanması alt problemlerinden oluşmaktadır. Bu nedenle paralel makine çizelgeleme problemleri tek makine çizelgeleme problemlerine göre daha karmaşık bir yapıya sahiptir. Öncelik kuralları çizelgeleme problemlerine kolaylıkla uygulanabilmelerinden dolayı tercih edilen klasik yöntemlerdir. Yerel arama algoritmaları genellikle diğer algoritmalar tarafından bulunmuş bir başlangıç çözümü ile çalışmaya başlar ve öncekinden daha iyi bir performans değerine ulaştığında sonlanır. Bu çalışmada, sıra bağımlı hazırlık zamanlı, ortak teslim tarihli özdeş paralel makine çizelgeleme problemi ele alınmıştır. Ele alınan performans ölçütleri ortalama tamamlanma zamanı ve maksimum tamamlanma zamanıdır. Klasik öncelik kuralları ile elde edilen başlangıç çözümleri yerel arama algoritması ile geliştirilmiştir. Elde edilen pareto optimal sonuçlar literatürdeki diğer sonuçlarla karşılaştırılmıştır. Yerel arama algoritması ile elde edilen sonuçların klasik sıralama kurallarına ve karınca kolonileri algoritmasına göre daha iyi sonuçlar verdiği gösterilmiştir.

Anahtar Kelimeler:

Çok amaçlı çizelgeleme, Özdeş paralel makine, Yerel arama algoritması, öncelik kuralları

PDF

___

[1] Pinedo, M. L., Scheduling Theory, Algorithms, and Systems. Third edition, Springer, New York, A.B:D., 2008.
[2] Ruiz-Torres, A. J., Enscore, E. E. and Barton, R. R., "Simulated Annealing Heuristics for the Average Flow-Time and the Number of Tardy Jobs Bi-Criteria Identical Parallel Machine Problem", Computers and Industrial Engineering, Vol. 33, 257–260, 1997.
[3] Min, L. and Cheng, W., "A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines", Artificial Intelligence in Engineering, Vol. 13, 399-403, 1999.
[4] Silva, C.A., Sousa, J.M., Runkler, T.A., Palm, R. and Sa da Costa, J.M., "Scheduling in manufacturing systems using the ant colonies optimization algorithm", Proceedings of 5st Potuguese conference on automatic control, Portekiz, September 5-7, 2002.
[5] Rajakumar, S., Arunachalam, V.P. and Salladurai, V., "Workflow balancing strategies in parallel machine scheduling", International Journal of advanced Manufacturing Technology, Vol. 23, 366-374, 2004.
[6] Sankar, S.S., Ponnambalam, S.G., Rathinavel, V. and Viveshvaren, M.S., "Scheduling in parallel machine shop: An ant colony optimization Approach", Institute of Electrical and Electronics Engineers (IEEE), 276-280, 2005.
[7] Toksarı, M.D. and Güner, E., "Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration", Computers & Operations Research, Vol. 36, 2394-2417, 2009.
[8] Chen, J., Chen, K., Wu, C. and Chen, W., "A study of the flexible job shop scheduling problem with parallel machines and reentrant process, Journal of Advanced Manufacturing Technology, Vol. 39, 344-354, 2008.
[9] Edis, E.B. Oğuz, C. And Özkarahan, İ., "Paralel Makinelerde işlerin ve makine operatörlerinin birlikte çizelgelenmesi problemine çözüm yaklaşımları, Journal of the Faculty of Engineering and Architecture of Gazi University. Vol. 27, No 3, 527-535, 2012.
[10] Gomes, M. C., Barbosa-Povoa, A. P. and Novais, A. Q., "Optimal scheduling for flexible job shop operation", International Journal of Production Research", Vol. 43, 2323 – 2353, 2005.
[11] Shim, S. and Kim, Y., "Scheduling on parallel identical machines to minimize total tardiness", European Journal of Operation Research", Vol. 177, 135-146, 2007.
[12] Anghinolfi, D. and Paolucci, M., "Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach", Computers & Operations Research, Vol. 34, 471-3490, 2007.
[13] Kaya, S., Akgöbek, Ö. and Eren, T., "The Solution with Particle Swarm Optimization of two Criteria Identical Parallel Machine Scheduling Problems", 16th International Symposium on Econometrics Operations Research and Statistics. Edirne. Turkey. 7-12 May 2015.
[14] Kaya, S., Çok amaçlı esnek atölye tipi çizelgeleme problemlerinin geliştirilmiş parçacık sürü optimizasyonu ile çözümüne yönelik model önerileri, Doktora Tezi. Kocaeli Üniversitesi. Fen Bilimleri Enstitüsü, Endüstri Mühendisliği ABD, 2014.
[15] Eren, T., "A bicriteria parallel machine scheduling with a learning effect of setup andremoval times", Applied Mathematical Modelling , Vol. 33, No 2, 1141-1150, 2009.
[16] Driessel, R. and Moench, L., "Scheduling jobs on parallel machines with sequencedependent setup times, presedence constraints, and ready times using variable neighborhood search", Proceedings of international conference of computers and industrial engineering, 273-278, 2009.
[17] Cota, L., Haddad, M., Souza, M. and Coelho, V., "AIRP: A heuristic algorithm for solving the unrelated parallel machine scheduling problem", Proceedings of the 2014. IEEE congress on evolutionary computation, 1855-1862, 2014.
[18] Chen, J.F., "Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints", The International Journal of Advanced Manufacturing Technology, Vol. 44, 1204-1212, 2009.
[19] Yılmaz Eroğlu, D., Özmutlu, H.C. and Köksal, S.A., "A Genetic Algorithm fort he unrelated parallel machine scheduling problem with job splitting and sequence dependent setup times loom scheduling, Tekstil ve Konfeksiyon, Vol. 24, No 1, 66-73, 2014.
[20] Wang, C., Liu, C., Zhang, Z. H. and Zheng, L., "Minimizing the total completion time for parallel machine scheduling with job splitting and learning", Computers & Industrial Engineering, Vol. 97, 170-182, 2016.
[21] Yang, S. J., "Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time", Applied Mathematical Modelling, Vol. 37, No 5, 2995-3005, 2013.
[22] Eren, T. and Güner, E. "Öğrenme etkili hazırlık ve taşınma zamanlı paralel makineli çizelgeleme problemi", Havacılık ve Uzay Teknolojileri Dergisi, Vol. 2, No. 4, 67-72, 2006.
[23] Yeh, W. C., Lai, P. J., Lee, W. C. and Chuang, M. C., "Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects", Information Sciences, Vol. 269, 142-158, 2014.
[24] Aarts. E., and Lenstra, J.K., 1997. Local Search in Combinatorial Optimization, Wiley & Sons. England, 1997.
[25] Kaya, S. and Fığlalı, N. "Çok Amaçlı Optimizasyon Problemlerinde Pareto Optimal Kullanımı," Social Sciences Research Journal, Vol. 5, 9-18, 2016.
[26] Jozefowska, J. "Just-İn-Time Scheduling: Models and algorithms for computer and manufacturing systems", Springer Science. New York, 2007.
[27] Küçük, B., Özdeş Paralel Makineli Bir Üretim Sisteminin Karınca Koloni Algoritması İle Çizelgelenmesi, Doktora Tezi, İstanbul Üniversitesi, Sosyal Bilimler Enstitüsü, 2010.