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 Sayfa Aralığı: 1041 - 1054 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.815942 İndeks Tarihi: 13-03-2023
Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri
Ö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 Kelime: New representation schemes for identical parallel machine scheduling problems with sequence dependent setup times
Öz: In this study, an identical parallel machine scheduling problem (IPMSP) with sequence-dependent setup times, which is significantly crucial in literature, is studied. There are different heuristics and metaheuristics for the problem in the literature. The representation method used in these studies is usually the permutation type representation, where each number corresponds to a job. The order of these numbers represents the order of the jobs in the machines. In this study, new solution representations are presented. A classical genetic algorithm and two new genetic algorithms using the proposed solution representations are compared by using randomly generated instances to show the success of the proposed representations. Diversification of the solution space is expanded, and the same results are eliminated with these solution representations. Specifically, the new algorithms generate better results than the classical genetic algorithm for large sized problems.
Anahtar Kelime: Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
- Allahverdi A., Gupta J., Aldowaisan T., A review of scheduling involving setup considerations, Omega The International Journal of Management Science, 27, 219-239, 1999.
- 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.
- Yang W.H, Liao C.J., Survey of scheduling research involving setup times, International Journal of Systems Science, 30, 143-155, 1999.
- Lee Y., Pinedo M., Scheduling Jobs on Parallel Machines with Sequence Dependent Setup Times, European Journal of Operational Research, 100 (3), 464-474, 1997.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Labbi W., Boudhar M., Oulamara A., Scheduling Two Identical Parallel Machines with Preparation Constraints, International Journal of Production Research, 55 (6), 1531–1548, 2017.
- Chaudhry I.A., Elbadawi I.A., Minimisation of total tardiness for identical parallel machine scheduling using genetic algorithm, Sadhana, 42 (1), 11-21, 2017.
- 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.
- 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.
- 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.
- Lee, J.H., Kim, H.J., A heuristic algorithm for identical parallel machine scheduling: splitting jobs, sequence dependent setup times, and limited setup operators, Flexible Services and Manufacturing Journal, DOI: 10.1007/s10696-020-09400-9, 2018.
- Silva, J.M.P, Teixeira, E., Subramanian, A., Exact and metaheuristic approaches for identical parallel machine scheduling with a common server and sequence-dependent setup times, Journal of The Operational Research Society, 72 (2), 444-457,2021.
- Ozer, E.A., Sarac, T., MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints, TOP, 27, 94–124, 2019.
- Izquierdo, C.E., Bello, F.A., Batista, B.M., Alvarez, A., Báez, S., A metaheuristic algorithm and simulation to study the effect of learning or tiredness on sequence-dependent setup times in a parallel machine scheduling problem, Expert Systems with Applications, 117,62- 74,2019.
- Ghalami, L., Grosu, D., Scheduling parallel identical machines to minimize makespan:A parallel approximation algorithm, Journal of Parallel and Distributed Computing, 133, 221-231, 2019.
- Laha, D., Gupta, J.N.D., An improved cuckoo search algorithm for scheduling jobs on identical parallel machines, Computers & Industrial Engineering, 126, 348-360, 2018.
- Branda, M., Distributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing times, Computers and Operations Research, 98, 231-239, 2018.
- Jager, S., Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates, Operations Research Letters, 46 (5), 505-509, 2018.
- Schwerdfeger, S., Walter, R., Improved algorithms to minimize workload balancing criteria on identical parallel machines, Computers & Operations Research, 93, 123-134, 2018.
- Ouazene, Y., Yalaoui, F., Identical parallel machine scheduling with time-dependent processing times, Theoretical Computer Science, 721, 70-77, 2018.
- 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.
- Goldberg D.E., Genetic algorithms in search, optimization, and machine learning, Reading, MA: Addison-Wesley, 1989.
- 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.
- Bean J., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6(2), 154-160, 1994.
- Hoare C., Algorithm 64: Quicksort, Communications of the ACM, 4 (7), 321, 1961.
- Saraç T., Tutumlu B., A bi-objective mathematical model for an unrelated parallel machine scheduling problem with job-splitting, Journal of the Faculty of Engineering and Architecture of Gazi University, 37 (4), 2293-2308, 2022.
- Saraç T., Tutumlu B., A mix integer programming model and solution approach to determine the optimum machine number in the unrelated parallel machine scheduling problem. Journal of the Faculty of Engineering and Architecture of Gazi University, 37 (1), 329-345, 2022.
| APA | Takan A, Saraç T (2023). Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. , 1041 - 1054. 10.17341/gazimmfd.815942 |
| Chicago | Takan Arda,Saraç Tugba Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. (2023): 1041 - 1054. 10.17341/gazimmfd.815942 |
| MLA | Takan Arda,Saraç Tugba Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. , 2023, ss.1041 - 1054. 10.17341/gazimmfd.815942 |
| AMA | Takan A,Saraç T Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. . 2023; 1041 - 1054. 10.17341/gazimmfd.815942 |
| Vancouver | Takan A,Saraç T Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. . 2023; 1041 - 1054. 10.17341/gazimmfd.815942 |
| IEEE | Takan A,Saraç T "Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri." , ss.1041 - 1054, 2023. 10.17341/gazimmfd.815942 |
| ISNAD | Takan, Arda - Saraç, Tugba. "Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri". (2023), 1041-1054. https://doi.org/10.17341/gazimmfd.815942 |
| APA | Takan A, Saraç T (2023). Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 38(2), 1041 - 1054. 10.17341/gazimmfd.815942 |
| Chicago | Takan Arda,Saraç Tugba Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38, no.2 (2023): 1041 - 1054. 10.17341/gazimmfd.815942 |
| MLA | Takan Arda,Saraç Tugba Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.38, no.2, 2023, ss.1041 - 1054. 10.17341/gazimmfd.815942 |
| AMA | Takan A,Saraç T Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2023; 38(2): 1041 - 1054. 10.17341/gazimmfd.815942 |
| Vancouver | Takan A,Saraç T Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2023; 38(2): 1041 - 1054. 10.17341/gazimmfd.815942 |
| IEEE | Takan A,Saraç T "Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 38, ss.1041 - 1054, 2023. 10.17341/gazimmfd.815942 |
| ISNAD | Takan, Arda - Saraç, Tugba. "Sıra bağımlı hazırlık süreli özdeş paralel makine çizelgeleme problemi için yeni çözüm gösterimleri". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38/2 (2023), 1041-1054. https://doi.org/10.17341/gazimmfd.815942 |
