Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri

Yıl 2023, Cilt: 38 Sayı: 2, 1041 - 1054, 07.10.2022

Arda Takan Tuğba Saraç

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

Öz

Makine çizelgeleme problemleri teorik olarak ve uygulamada sıklıkla karşılaşılan problemler arasındadır. Bu konuda literatürde yer alan çalışmaların önemli bir bölümünde problemin tek amaçlı olarak ele alındığı görülmektedir. Tek amaçlı yaklaşım teorik anlamda problemlerin daha kolay çözülebilmesini sağlasa da gerçek hayat problemlerinin hemen hepsinin çok amaçlı özellik göstermesinden dolayı çoğu zaman gerçekçi çözümler sunamamaktadır. Bu çalışmada, ilişkisiz paralel makine çizelgeleme problemi çok amaçlı olarak ele alınmıştır. Ele alınan amaçlar son işin tamamlanma zamanının ve toplam gecikmenin enküçüklenmesidir. Amaçların birleştirilmesinde genişletilmiş E-kısıt ve sözlüksel ağırlıklandırılmış Tchebycheff yöntemleri kullanılmıştır. Elde edilen çözümler kullanılarak yöntemlerin performansı karşılaştırılmıştır.

Anahtar Kelimeler

Paralel makine çizelgeleme problemi, Metasezgiseller, Genetik Algoritma, Gösterim Şekli

Kaynakça

• [1] Allahverdi A., Gupta J., Aldowaisan T., A review of scheduling involving setup considerations, Omega The International Journal of Management Science, 27, 219-239, 1999.
• [2] Xi Y., Jang J., Scheduling jobs on identical parallel machines with unequal future ready time and sequence dependent setup: An experimental study, International Journal of Production Economics, 137(1), 1-10, 2012.
• [3] Yang W.H, Liao C.J., Survey of scheduling research involving setup times, International Journal of Systems Science, 30, 143-155, 1999.
• [4] Lee Y., Pinedo M., Scheduling Jobs on Parallel Machines with Sequence Dependent Setup Times, European Journal of Operational Research, 100(3), 464-474, 1997.
• [5] Min L., Cheng W., A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines, Artificial Intelligence in Engineering, 13(4), 399-403, 1999.
• [6] Tahar D.N., Yalaoui F., Chu C., Amodeo L., A Linear Programming Approach for Identical Parallel Machine Scheduling with job Splitting and Sequence-Dependent Setup Times, International Journal of Production Economics, 99 (1), 63–73, 2006.
• [7] Lee W.C., Wu C.C., Chen P., A Simulated Annealing Approach to Makespan Minimization on Identical Parallel Machines, The International Journal of Advanced Manufacturing Technology, 31(3-4), 328–334, 2006.
• [8] Biskup D., Herrmann J., Gupta J.N.D., Scheduling Identical Parallel Machines to Minimize Total Tardiness, International Journal of Production Economics, 115(1), 134–142, 2008.
• [9] Tanaka S., Araki M., A Branch-and-Bound Algorithm with Lagrangian Relaxation to Minimize Total Tardiness on Identical Parallel Machines, International Journal of Production Economics, 113(1), 446–458, 2008.
• [10] Chang P.C., Chen S.H., Integrating Dominance Properties with Genetic Algorithms for Parallel Machine Scheduling Problems with Setup Times, Applied Soft Computing, 11(1), 1263–1274, 2011.
• [11] Wang X., Cheng T.C.E., A Heuristic for Scheduling Jobs on two Identical Parallel Machines with a Machine Availability Constraint, International Journal of Production Economics, 161, 74–82, 2015.
• [12] Beezão A. C., Cordeau J.F., Laporte G. Yanasee H.H., Scheduling Identical Parallel Machines with Tooling Constraints, European Journal of Operational Research, 257 (3), 834–844, 2017.
• [13] Labbi W., Boudhar M., Oulamara A., Scheduling Two Identical Parallel Machines with Preparation Constraints, International Journal of Production Research, 55(6), 1531–1548, 2017.
• [14] Chaudhry I.A., Elbadawi I.A., Minimisation of total tardiness for identical parallel machine scheduling using genetic algorithm, Sadhana, 42(1), 11-21, 2017.
• [15] Wang S., Wang X., Yu J., Ma S., Liu M., Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan, Journal of Cleaner Production, 193, 424-440, 2018.
• [16] Lee C.H., A Dispatching Rule and a Random Iterated Greedy Metaheuristic for Identical Parallel Machine Scheduling to Minimize Total Tardiness, International Journal of Production Research, 56(6), 2292–2308, 2018.
• [17] Kim J.G., Song S., Jeong B., Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times, International Journal of Production Research, 5(6), 1628-1643, 2020.
• [18] Holland J. H., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, Ann Arbor, MIT Press Cambridge, 1992.
• [19] Goldberg D.E., Genetic algorithms in search, optimization, and machine learning, Reading, MA: Addison-Wesley, 1989.
• [20] Cheng R., Gen M., Minmax earliness/tardiness scheduling in identical parallel machine system using genetic algorithm, International Journal of Computers and Industrial Engineering, 29(1-4), 513-517, 1995.
• [21] Bean J., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6(2), 154-160, 1994.
• [22] Hoare C., Algorithm 64: Quicksort, Communications of the ACM, 4(7), 321, 1961.