DEĞİŞKEN MAKİNE HIZLARINA SAHİP KAPASİTELİ İLİŞKİSİZ PARALEL MAKİNE ÇİZELGELEME PROBLEMİ İÇİN ÇÖZÜM YAKLAŞIMLARI

Abstract

Bu çalışmada, değişken makine hızlarına sahip kapasiteli ilişkisiz paralel makine çizelgeleme problemi ele alınmıştır. Paralel makine çizelgeleme problemini ele alan çalışmaların çoğunda makinelerin sabit hızlarda çalıştığı varsayılmaktadır. Ancak pek çok üretim ortamında, makineler farklı hız seviyelerinde çalışabilmekte ve kapasite kısıtlarına tabi olabilmektedir. Bu nedenle bu çalışmada, makine hızlarının iş bazında değişebildiği ve kapasite kısıtlarının dikkate alındığı bir matematiksel model önerilmiştir. Önerilen model, işlerin hangi makinalara atanacağının yanı sıra hangi hızlarda üretileceklerine de karar vermektedir. Amaç enerji tüketimi ve fazla mesai maliyetlerinin toplamının enküçüklenmesidir. Modelin performansı, farklı ölçeklerdeki rassal türetilen test problemleri kullanılarak değerlendirilmiş ve değişken hızların toplam maliyet üzerindeki etkisi analiz edilmiştir. Elde edilen sonuçlar, iş bazında makine hızlarının değişebilmesine izin vermenin toplam maliyeti önemli ölçüde iyileştirebildiğini göstermiştir. Ayrıca daha büyük boyutlu problemlerin çözümü için iki aşamalı bir çözüm yaklaşımı önerilmiştir. Önerilen çözüm yaklaşımı ile matematiksel modelle süre limiti içinde çözülemeyen 100 iş 12 makineye kadar büyük boyutlu problemlere çözüm bulunmuştur.

Keywords

• İlişkisiz paralel makine çizelgeleme
• Değişken makine hızları
• Kapasite kısıtı
• Matematiksel modelleme.

SOLUTION APPROACHES FOR CAPACITATED UNRELATED PARALLEL MACHINE SCHEDULING PROBLEM WITH VARIABLE MACHINE SPEEDS

Abstract

In this study, the unrelated parallel machine scheduling problem with variable machine speeds is considered. In most studies addressing the parallel machine scheduling problem, machines are assumed to operate at fixed speeds. However, in most of the production environments, machines can usually operate at different speed levels and may be subject to capacity constraints. Therefore, in this study, a mathematical model is proposed in which machine speeds can vary on a job basis and capacity constraints are taken into account. The proposed model decides which machines to assign jobs to as well as at which speeds, they will be produced. The objective is to minimize the sum of energy consumption and overtime costs. The performance of the model is evaluated using randomly generated test problems at different sizes and the effect of variable speeds on total cost is analyzed. The results show that allowing machine speeds to vary for each individual job can significantly improve total cost. Additionally, a two-stage solution approach is proposed for large sized problems. The proposed approach addresses large sized problems with up to 100 jobs and 12 machines that cannot be solved by the proposed mathematical model.

Keywords

• Unrelated parallel machine scheduling
• Variable machine speeds
• Capacity constraint
• Mathematical modeling.

References

1. Kaynaklar (References)
2. Abedi, M., Chiong, R., Noman, N., Zhang, R., 2020. A multi-population, multi-objective memetic algorithm for energy-efficient job-shop scheduling with deteriorating machines. Expert Systems with Applications, 157, 113348.
3. Alfares, H. K. (2022). Plant shutdown maintenance workforce team assignment and job scheduling. Journal of Scheduling, 25(3), 321-338.
4. Chen, S., Pan, Q. K., Gao, L., Miao, Z. H., Peng, C., 2023. Energy-efficient distributed heterogeneous blocking flowshop scheduling problem using a knowledge-based iterated Pareto greedy algorithm. Neural Computing and Applications, 35(9), 6361-6381.
5. Cota, L. P., Coelho, V. N., Guimarães, F. G., Souza, M. J., 2021. Bi‐criteria formulation for green scheduling with unrelated parallel machines with sequence‐dependent setup times. International Transactions in Operational Research, 28(2), 996-1017.
6. Darghouth, M. N., Attia, A. M., 2026. Sustainable scheduling for job shops with joint maintenance, machine speed scaling, and uncertain processing times. Robotics and Computer-Integrated Manufacturing, 97, 103091.
7. Ebrahimi, M., Dinari, P., Samaei, M., Sohrabi, R., Sherafatianfini, S., 2022. A New Approach Based on the Learning Effect for Sequence‐Dependent Parallel Machine Scheduling Problem under Uncertainty. Discrete Dynamics in Nature and Society, 2022(1), 2648936.
8. Ertem, M., 2024. Renewable energy-aware machine scheduling under intermittent energy supply. IEEE Access, 12, 23613-23625.

9. Fang, K. T., Lin, B. M., 2013. Parallel-machine scheduling to minimize tardiness penalty and power cost. Computers & Industrial Engineering, 64(1), 224-234.
10. Guan, E., Wang, J., Duan, J., 2025. Sustainable scheduling for a flexible job shop considering batch processing and batch transportation strategies. Journal of Scheduling, 28(6), 615-637.
11. He, L., Cao, Y., Li, W., Cao, J., Zhong, L., 2022. Optimization of energy-efficient open shop scheduling with an adaptive multi-objective differential evolution algorithm. Applied Soft Computing, 118, 108459.
12. Li, D., Gao, K., Duan, P., Suganthan, P. N., Wu, N., 2025. Reinforcement Learning Assisting Artificial Bee Colony Algorithm for Scheduling Distributed Assembly Flowshops With Batch Delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems.
13. Özçelik, F., Saraç, T., Ertem, M., 2024. Makinelerde hız değişikliğinin sürdürülebilirliğe etkisinin incelenmesi: bir matematiksel model. Endüstri Mühendisliği, 35(1), 115-135.
14. Perez, C., March, C., Salido, M. A., 2025. Driving energy efficiency in scheduling manufacturing: An advanced instance generation and a metaheuristic approach. Expert Systems with Applications, 288, 128138.
15. Shao, W., Shao, Z., Pi, D., 2022. A multi-neighborhood-based multi-objective memetic algorithm for the energy-efficient distributed flexible flow shop scheduling problem. Neural Computing and Applications, 34(24), 22303-22330.
16. Wang, L., Qi, Y., 2023. Scheduling an Energy-Aware Parallel Machine System with Deteriorating and Learning Effects Considering Multiple Optimization Objectives and Stochastic Processing Time. CMES-Computer Modeling in Engineering & Sciences, 135(1), 325-339.
17. Wang, Y. C., Wang, M. J., Lin, S. C., 2017. Selection of cutting conditions for power constrained parallel machine scheduling. Robotics and Computer-Integrated Manufacturing, 43, 105-110.
18. Wang, Y. J., Li, J., Wang, G. G., 2023. Fuzzy correlation entropy-based NSGA-II for energy-efficient hybrid flow-shop scheduling problem. Knowledge-based systems, 277, 110808.
19. Wang, Y. J., Wang, G. G., Wang, L., 2025. A tree-based multiobjective evolutionary algorithm for energy-efficient hybrid flow-shop scheduling. IEEE Transactions on Evolutionary Computation, 29(6), 2313-2327.
20. Wu, X., Che, A., 2019. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega, 82, 155-165.
21. Xiao, Y., Zheng, Y., Yu, Y., Zhang, L., Lin, X., Li, B., 2021. A branch and bound algorithm for a parallel machine scheduling problem in green manufacturing industry considering time cost and power consumption. Journal of Cleaner Production, 320, 128867.
22. Yağmur, E., Kesen, S. E., 2024. Integrated production scheduling and vehicle routing problem with energy efficient strategies: Mathematical formulation and metaheuristic algorithms. Expert Systems with Applications, 237, 121586.
23. Yu, H., Gao, K., Li, Z., Duan, P., 2025. Double-learning-strategy-based evolutionary algorithm for scheduling multiobjective distributed assembly permutation flowshops with setup time. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 55(2), 925-935.
24. Yu, H., Gao, K., Li, Z., Suganthan, P. N., 2024. Energy-efficient multi-objective distributed assembly permutation flowshop scheduling by Q-learning based meta-heuristics. Applied Soft Computing, 166, 112247.
25. Yüksel, D., Taşgetiren, M. F., Kandiller, L., Gao, L., 2020. An energy-efficient bi-objective no-wait permutation flowshop scheduling problem to minimize total tardiness and total energy consumption. Computers & Industrial Engineering, 145, 106431.
26. Zhang, L., Deng, Q., Gong, G., Han, W., 2020. A new unrelated parallel machine scheduling problem with tool changes to minimise the total energy consumption. International Journal of Production Research, 58(22), 6826-6845.
27. Zhang, R., Chiong, R., 2016. Solving the energy-efficient job shop scheduling problem: a multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. Journal of Cleaner Production, 112, 3361-3375.
28. Zhang, R., 2013. A Three‐Stage Optimization Algorithm for the Stochastic Parallel Machine Scheduling Problem with Adjustable Production Rates. Discrete Dynamics in Nature and Society, 2013(1), 280560.
29. Zhang, Y., Li, J., Xu, Y., Duan, P., 2024. Multi-population cooperative multi-objective evolutionary algorithm for sequence-dependent group flow shop with consistent sublots. Expert Systems with Applications, 237, 121594.
30. Zheng, X. L., Wang, L., 2018. A collaborative multiobjective fruit fly optimization algorithm for the resource constrained unrelated parallel machine green scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 48(5), 790-800.
31. Zhuang, M., Zhang, W., Tang, H., Li, X., Wang, K., 2024. A multi-objective genetic algorithm based on two-stage reinforcement learning for green flexible shop scheduling problem considering machine speed. Expert Systems with Applications, 258, 125189.