İşlerin bölünebildiği ilişkisiz paralel makine çizelgeleme problemi için iki amaçlı bir matematiksel model

Year 2022, Volume: 37 Issue: 4, 2293 - 2308, 28.02.2022

Tuğba Saraç , Büşra Tutumlu

https://doi.org/10.17341/gazimmfd.967343

Abstract

Paralel makine çizelgeleme problemlerini ele alan çalışmalarda genellikle işlerin bölünmediği ve atandığı makinede tamamlandığı varsayılmaktadır. Ancak pek çok işletme işlerini en kısa sürede tamamlayabilmek için işleri bölerek farklı makinelerde üretmeyi tercih edebilmektedir. İşlerin bölünmesi işlerin zamanında teslim edilebilmesi ya da işlerin makinelere dengeli dağıtılabilmesi gibi fırsatlar sunabilmesi açısından önemlidir. Ayrıca pek çok işletme için bir diğer önemli konu, işleri mümkün olduğunca az sayıda makine kullanarak gerçekleştirmektir. İşletmelerin genellikle makine sayıları sabit olduğu için ilk bakışta kullanılacak makine sayısının azaltılmasının herhangi bir avantaj sağlayamayacağı düşünülebilir ancak aynı işlerin daha az makine kullanılarak yapılması enerji tasarrufu sağlanabilmesi, kullanılmayan makinelerin başka bir işletmeye kiralanabilmesi veya boş kalan makinelerin kapasitesi kadar ek iş kabul edebilmesi gibi çok ciddi fırsatlar yaratabilme potansiyeline sahiptir. Bu çalışmada, işlerin bölünemediği ve bölünebildiği ilişkisiz paralel makine çizelgeleme problemi için iki farklı çok amaçlı matematiksel model önerilmiştir. İlk model, işlerin bölünemediği ilişkisiz paralel makine çizelgeleme problemi içindir. Saraç ve Tutumlu [1] tarafından önerilen model iyileştirilerek daha hızlı çözüme ulaşabilen bir matematiksel model elde edilmiştir. İkinci modelde ise işlerin bölünemeyeceği varsayımı kaldırılmıştır. Bu modelde, işlerin hangi makinelere atanacağının ve sıralarının yanı sıra işlerin kaça bölüneceği ve hangi oranlarda hangi makinelerde işleneceği de belirlemektedir. Önerilen modellerin amaçları, son işin tamamlanma zamanının ve kullanılacak makine sayısının enküçüklenmesidir. Önerilen çok amaçlı modeller ve Saraç ve Tutumlu [1] tarafından önerilen model epsilon kısıt yöntemi (EKY) kullanılarak tek amaçlı yapıya dönüştürülmüştür. Rassal türetilen test problemleri, EKY ile tek amaçlı yapıya dönüştürülen modeller ve GAMS/CPLEX ile çözülmüş, elde edilen sonuçlar karşılaştırılmıştır. Yapılan testler, işlerin bölünemediği durum için önerilen modelin literatürde yer alan modelden [1] ortalama %85 daha kısa sürede çözüm bulabildiğini, işlerin bölünemez olduğu varsayımının kaldırılmasının ise aynı makine sayısı için son işin tamamlanma zamanını ortalama %13 kısalttığını ortaya koymuştur.

Keywords

İlişkisiz Paralel Makine Çizelgeleme, İşlerin Bölünmesi, Çok amaçlı matematiksel model

References

• Saraç T., Tutumlu B., A mix integer programming model and solution approaches to determine the optimum machine number in the unrelated parallel machine scheduling problem, Journal of the Faculty of Engineering and Architecture of Gazi University, (kabul edilmiş makale).
• Akyol Özer E., Saraç T., MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints, An Official Journal of the Spanish Society of Statistics and Operations Research, 27:94–124, 2019. DOI: 10.1007/s11750-018-00494-x.
• Saraç T., Sipahioglu A., Akyol Ozer E. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial & Management Optimization, 17(3): 1289-1314, 2021. DOI: 10.3934/jimo.2020022.
• Furugi A., A tabu search algorithm for the unrelated parallel machine scheduling problem with machine availability constraint and sequence-dependent setup time. Journal of the Faculty of Engineering and Architecture of Gazi University, 36(3): 1539-1549, 2021. DOI: 10.17341/gazimmfd.806641
• Tirkolaee EB., Aydın NS., Ranjbar-Bourani M., Weber GW., A robust bi-objective mathematical model for disaster rescue units allocation and scheduling with learning effect, Computers & Industrial Engineering, 149, 2020. DOI: 10.1016/j.cie.2020.106790
• Sarıçiçek İ., Çelik C., Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness, Applied Mathematical Modelling, 35, 4117-4126, 2011.
• Wang C., Liu C., Zhang ZH., Zheng L., Minimizing the total completion time for parallel machine scheduling with job splitting and learning, Computers & Industrial Engineering, 97, 170-182, 2016.
• Liu C., Wang C., Zhang ZH., Zheng L., Scheduling with job-splitting considering learning and the vital-few law, Computers and Operations Research, 90, 264-274, 2018.
• Salimifard K., Li J., Mohammadi D., Moghdani R., A multi objective volleyball premier league algorithm for green scheduling identical parallel machines with splitting jobs, Applied Intelligence, 2020.
• Kim JG., Song S., Jeong BJ., Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times, International Journal of Production Research, 58(6), 1628-1643, 2020.
• Kim YH., Kim RS., Insertion of new idle time for unrelated parallel machine scheduling with job splitting and machine breakdowns, Computers & Industrial Engineering, 147, 2020.
• Xing W., Zhang J., Parallel machine scheduling with splitting jobs, Discrete Applied Mathematics, 103, 259-269, 2000.
• Wang WL., Wang HY., Zhao YW., Zhang LP., Xu XL., Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm, Computers and Operations Research, 40, 1196-1206, 2013.
• Lee JH., Jang H., Uniform Parallel machine scheduling with dedicated machines, Sustainability, 11(24), 2019.
• Kim HJ., Lee JH., Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers, Computers and Operations Research, 126, 2021.
• Lee JH., Kim HJ., A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence‑dependent setup times, and limited setup operators, Flexible Services and Manufacturing Journal, 2020.
• Lee JH., Jang H., Kim HJ., Iterative job splitting algorithms for parallel machine scheduling with job splitting and setup resource constraints, Journal of the Operational Research Society, 2020.
• Kim J., Kim HJ., Parallel machine scheduling with multiple processing alternatives and sequence-dependent setup times, International Journal of Production Research, 2020.
• Rosales O. A., Bello F. A., Alvarez A., Efficient metaheuristic algorithm and re- formulations for the unrelated parallel machine scheduling problem with sequence and machine dependent setup times, International Journal of Advanced Manufacturing Technology, 76, 1705- 1718, 2015.
• Meng R., Rao Y., Luo Q., Modeling and solving for bi-objective cutting parallel machine scheduling problem, Annals of Operatıons Research, 285(1-2), 223-245, 2020.
• Tosarkani BM, Amin SH., A possibilistic solution to configure a battery closed-loop supply chain: Multi-objective approach, Expert Systems with Applications, 92, 12-26, 2018.