BibTex RIS Cite

AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ

Year 2012, Volume: 27 Issue: 4, 0 - , 19.02.2013

M. Emin Baysal Taha Durmaz Ahmet Sarucan Orhan Engin

Abstract

Açık Atölye Tipi Çizelgeleme (AATÇ) problemi temelde, her bir işin her makinede işlem görmesi gerekensadece bir işleminin bulunduğu ve işlem sırasının önemli olmadığı bir çizelgeleme problemidir. Çoğunluklabenzer ürün gruplarının üretildiği tesislerde görülmektedir. Bu çalışmada, AATÇ problemleri toplamtamamlanma zamanının minimizasyonuna yönelik, rassal zıplama tekniği ile işleyen Paralel KanguruAlgoritması (PKA) ile çözülmüştür. PKA, sürekli daha iyi çözümlere ulaşmaya çalışan meta-sezgisel biryöntemdir. Literatürde yer alan AATÇ; kıyas problemleri, vahşi ve evcil iki kanguru operatörünün paralelçalıştırıldığı, Kanguru Algoritması (KA) ile çözülmüştür. Elde edilen değerler, literatürde daha önce ulaşılan eniyi sonuçlar ile karşılaştırılmıştır. PKA’nın AATÇ problemlerinin çözümünde etkin bir yöntem olduğubelirlenmiştir.

Keywords

Açık atölye tipi çizelgeleme paralel kanguru algoritması tamamlanma zamanı.

References

  • Liaw, C.F., Cheng, C.Y., Chen, M., “The total
  • completion time open shop scheduling problem
  • with a given sequence of jobs on one machine”,
  • Computers & Operations Research, 29, 1251
  • – 1266, 2002.
  • Durmaz, T., Açık Atölye Çizelgeleme
  • Problemlerinin Paralel Kanguru Algoritması
  • ile Çözümü, Yüksek Lisans Tezi, Selçuk
  • Üniversitesi, Fen Bilimleri Enstitüsü, 2011.
  • Gonzalez, T., Sahni, S., “Open shop scheduling
  • to minimize finish time”, Journal of the ACM,
  • (4):665–79, 1976.
  • Arıkan, M., Erol, S., “A long term memory tabu
  • search algorithm for part selection and machine
  • loading in flexible manufacturing systems”,
  • Journal of The Faculty of Engineering and
  • Architecture of Gazi University, 25, 2, 311-
  • , 2010.
  • Dereli, T., Daş, G. S., “Ant colony optimization
  • approach for container loading problems”,
  • Journal of The Faculty of Engineering and
  • Architecture of Gazi University, 25, 4, 881-
  • , 2010
  • Liaw, C.F., “An efficient tabu search approach
  • for the two-machine preemptive open shop
  • scheduling problem”, Computers &
  • Operations Research, 30, 2081–2095 2003.
  • NG, C.T., Cheng, T.C.E., Yuan, J.J., “Concurrent
  • Open Shop Scheduling to Minimize the
  • Weighted Number of Tardy Jobs”, Journal of
  • Scheduling, 6, 405 – 412, 2003.
  • Blum, C., “Beam-ACO—hybridizing ant colony
  • optimization with beam search: an application
  • to open shop scheduling”, Computers &
  • Operations Research, 32, 1565–1591, 2005.
  • Shabtay, D., Kaspi, M., “Minimizing the
  • Makespan in Open-Shop Scheduling Problems
  • with a Convex Resource Consumption
  • Function,” Wiley InterScience (2 February
  • .
  • Senthilkumar, P., Shahabudeen, P., “GA based
  • heuristic for the open job shop scheduling
  • problem”, Int J Adv Manuf Technol, 30, 297–
  • , 2006.
  • Sedeno-Noda, A., Alcaide, D., Gonzalez-
  • Martin, C., “Network flow approaches to preemptive
  • open-shop scheduling problems with time-windows”, European Journal of
  • Operational Research, 174, 1501–1518, 2006.
  • Gribkovskaia, I.V., Lee, C.Y., Strusevich, V.A.,
  • Werra, D., “Three is easy, two is hard: open
  • shop sum-batch scheduling problem refined”,
  • Operations Research Letters, 34, 459 – 464,
  • -
  • Sha, D.Y., Hsu, C.Y., “A new particle swarm
  • optimization for the open shop scheduling
  • problem”, Computers & Operations
  • Research, 35 3243 – 3261, 2008.
  • Brasel, H., Herms, A., Mörig, M., Tautenhahn,
  • T., Tusch, J., Werner, F., “Heuristic
  • constructive algorithms for open shop
  • scheduling to minimize mean flow time”,
  • European Journal of Operational Research,
  • , 856–870, 2008.
  • Lin, H.T., Lee, H.T., Pan, W.J., “Heuristics for
  • scheduling in a no-wait open shop with movable
  • dedicated machines”, Int. J. Production
  • Economics, 111, 368–377, 2008.
  • Mosheiov, G., Oron, D., “Open-shop batch
  • scheduling with identical jobs”, European
  • Journal of Operational Research, 187, 1282–
  • , 2008.
  • Werra, D., Kis, T., Kubiak, W., “Preemptive
  • open shop scheduling with multiprocessors:
  • polynomial cases and applications”, J Sched 11,
  • –83, 2008.
  • Sedeño-Noda, A., Pablo, D.A.L., González-
  • Martín, C., “A network flow-based method to
  • solve performance cost and makespan openshop
  • scheduling problems with time-windows”,
  • European Journal of Operational Research,
  • , 140–154, 2009.
  • Low, C. ve Yeh, Y., “Genetic algorithm-based
  • heuristics for an open shop scheduling problem
  • with setup, processing, and removal times
  • separated”, Robotics and Computer-
  • Integrated Manufacturing, 25, 314–322,
  • -
  • Akgöbek, Ö., Kaya, S., Değirmenci, Ü., Engin,
  • O., “Açık Atölye Tipi Çizelgeleme
  • Problemlerinin Paralel Doyumsuz Metasezgisel
  • Algoritma ile Çözümü”, Bilimde Modern
  • Yöntemler Sempozyumu – BMYS 2010, 14-
  • Ekim Dicle Üniversitesi Kongre Merkezi,
  • -130, 2010.
  • Naderi, B., Ghomi, S.M.T.F., Aminnayeri, M.,
  • Zandieh, M., “A contributon and new heuristics
  • for open shop scheduling”, Computers &
  • Operations Research, 37, 213-221, 2010.
  • Zhang, X. ve Velde, S., “On-line two-machine
  • open shop scheduling with time lags”,
  • European Journal of Operational Research,
  • 14–19, 2010.
  • Türkeli, B., “Solution of Bicriteria Open Shop
  • Scheduling Problem with Genetic Algorithm
  • and Tabu Search and Detailed Analysis of
  • Results”, Yüksek Lisans Tezi, Marmara
  • University Institute For Graduate Studies In
  • Pure And Applied Sciences, İstanbul, 2010.
  • Kökçam, A.H. ve Engin, O., “Bulanık Proje
  • Çizelgeleme Problemlerinin Meta Sezgisel
  • Yöntemlerle Çözümü”, Mühendislik ve Fen
  • Bilimleri Dergisi (Sigma), 28, 86-101, 2010.
  • Serbencu, A., Minzu, V., Serbencu, A., “An Ant
  • Colony System Based Metaheurıstic for Solving
  • Single Machine Scheduling Problem”, The
  • Annals of “Dunarea De Jos” Unıversity Of
  • Galati Fascicle III, Electrotechnıcs,
  • Electronıcs, Automatıc Control, Informatıcs, 19-
  • , 2007.
  • Teske, E., “Computing discrete logarithms with
  • the parallelized kangaroo method”, Discrete
  • Applied Mathematics, 130, 61-82, 2003.
  • Pollard, J.M., “Kruskal's Card Trick”, The
  • Mathematical Gazette, 84, 500 (Jul.), 265-267,
  • -
  • Jellouli, O., Chatelet, E., “Monte Carlo
  • Simulation And Stochastich Algorithms For
  • Optimising Supply Chain Management in an
  • Uncertain Environment”, Systems, Man, and
  • Cybernetics, 2001 IEEE International
  • Conference, 3 1840-1844. 2001.
  • Stein, A. ve Teske, E., “The Parallelized Pollard
  • Kangaroo Method in Real Quadratic Function
  • Fields”, Mathematics of Computation, 71/238
  • -814, 2001.
  • Minzu, V. ve Beldiman, L., “Some aspects
  • concerning the implementation of a parallel
  • hybrid metaheuristic”, Engineering
  • Applications of Artificial Intelligence, 20,
  • –999, 2007.
  • Yılmaz, M.K., Kökçam, A.H., Duvarcı, V.,
  • Fığlalı, A., Ayöz, M., Engin, O., “Paralel
  • Kanguru Algoritması Yardımıyla Beklemesiz
  • Akış Tipi Çizelgeleme Problemlerinin
  • Çözümü”, Yöneylem Araştırması ve Endüstri
  • Mühendisliği 29. Ulusal Kongresi, 2010.
  • Yılmaz, M.K., Engin, O., Fığlalı, A., Yavuz,
  • M., “Parallel Kangaroo Algorithm For Biobjective
  • Flow Shop Scheduling with a New
  • Weight Combining Approach”, 1st
  • International Symposium on Computing in
  • Science & Engineering, ISCSE-2010, Gediz
  • University (İzmir), June 3-5, Kuşadası Aydın
  • Turkey, 823-827, 2010.
  • Yılmaz, M.K., Fığlalı, A., Terzi, U., Yavuz, M.,
  • Engin, O., “A Hybrid Parallel Kangaroo a
  • &Simulated Annealing Algorithm for Multi-
  • Objective Flow Shop Scheduling” The Journal
  • of Management and Engineering Integration,
  • , 2, 2010.
  • Guéret, C., Prins, C., “A new lower bound for
  • the open-shop problem”, Annals of Operations
  • Research, 92:165–83, 1999.
  • Guéret, C., Ecole des mines de Nantes – Open
  • shop problems [online], Nantes, Ecole des
  • mines de Nantes, http://www.minesnantes.
  • fr/en/Media/ Elements-Sites-
  • Persos/Christelle-Gueret/Openshop/
  • HardOSInstances [Ziyaret Tarihi: 3 Ocak
  • .

Year 2012, Volume: 27 Issue: 4, 0 - , 19.02.2013

M. Emin Baysal Taha Durmaz Ahmet Sarucan Orhan Engin

Abstract

References

  • Liaw, C.F., Cheng, C.Y., Chen, M., “The total
  • completion time open shop scheduling problem
  • with a given sequence of jobs on one machine”,
  • Computers & Operations Research, 29, 1251
  • – 1266, 2002.
  • Durmaz, T., Açık Atölye Çizelgeleme
  • Problemlerinin Paralel Kanguru Algoritması
  • ile Çözümü, Yüksek Lisans Tezi, Selçuk
  • Üniversitesi, Fen Bilimleri Enstitüsü, 2011.
  • Gonzalez, T., Sahni, S., “Open shop scheduling
  • to minimize finish time”, Journal of the ACM,
  • (4):665–79, 1976.
  • Arıkan, M., Erol, S., “A long term memory tabu
  • search algorithm for part selection and machine
  • loading in flexible manufacturing systems”,
  • Journal of The Faculty of Engineering and
  • Architecture of Gazi University, 25, 2, 311-
  • , 2010.
  • Dereli, T., Daş, G. S., “Ant colony optimization
  • approach for container loading problems”,
  • Journal of The Faculty of Engineering and
  • Architecture of Gazi University, 25, 4, 881-
  • , 2010
  • Liaw, C.F., “An efficient tabu search approach
  • for the two-machine preemptive open shop
  • scheduling problem”, Computers &
  • Operations Research, 30, 2081–2095 2003.
  • NG, C.T., Cheng, T.C.E., Yuan, J.J., “Concurrent
  • Open Shop Scheduling to Minimize the
  • Weighted Number of Tardy Jobs”, Journal of
  • Scheduling, 6, 405 – 412, 2003.
  • Blum, C., “Beam-ACO—hybridizing ant colony
  • optimization with beam search: an application
  • to open shop scheduling”, Computers &
  • Operations Research, 32, 1565–1591, 2005.
  • Shabtay, D., Kaspi, M., “Minimizing the
  • Makespan in Open-Shop Scheduling Problems
  • with a Convex Resource Consumption
  • Function,” Wiley InterScience (2 February
  • .
  • Senthilkumar, P., Shahabudeen, P., “GA based
  • heuristic for the open job shop scheduling
  • problem”, Int J Adv Manuf Technol, 30, 297–
  • , 2006.
  • Sedeno-Noda, A., Alcaide, D., Gonzalez-
  • Martin, C., “Network flow approaches to preemptive
  • open-shop scheduling problems with time-windows”, European Journal of
  • Operational Research, 174, 1501–1518, 2006.
  • Gribkovskaia, I.V., Lee, C.Y., Strusevich, V.A.,
  • Werra, D., “Three is easy, two is hard: open
  • shop sum-batch scheduling problem refined”,
  • Operations Research Letters, 34, 459 – 464,
  • -
  • Sha, D.Y., Hsu, C.Y., “A new particle swarm
  • optimization for the open shop scheduling
  • problem”, Computers & Operations
  • Research, 35 3243 – 3261, 2008.
  • Brasel, H., Herms, A., Mörig, M., Tautenhahn,
  • T., Tusch, J., Werner, F., “Heuristic
  • constructive algorithms for open shop
  • scheduling to minimize mean flow time”,
  • European Journal of Operational Research,
  • , 856–870, 2008.
  • Lin, H.T., Lee, H.T., Pan, W.J., “Heuristics for
  • scheduling in a no-wait open shop with movable
  • dedicated machines”, Int. J. Production
  • Economics, 111, 368–377, 2008.
  • Mosheiov, G., Oron, D., “Open-shop batch
  • scheduling with identical jobs”, European
  • Journal of Operational Research, 187, 1282–
  • , 2008.
  • Werra, D., Kis, T., Kubiak, W., “Preemptive
  • open shop scheduling with multiprocessors:
  • polynomial cases and applications”, J Sched 11,
  • –83, 2008.
  • Sedeño-Noda, A., Pablo, D.A.L., González-
  • Martín, C., “A network flow-based method to
  • solve performance cost and makespan openshop
  • scheduling problems with time-windows”,
  • European Journal of Operational Research,
  • , 140–154, 2009.
  • Low, C. ve Yeh, Y., “Genetic algorithm-based
  • heuristics for an open shop scheduling problem
  • with setup, processing, and removal times
  • separated”, Robotics and Computer-
  • Integrated Manufacturing, 25, 314–322,
  • -
  • Akgöbek, Ö., Kaya, S., Değirmenci, Ü., Engin,
  • O., “Açık Atölye Tipi Çizelgeleme
  • Problemlerinin Paralel Doyumsuz Metasezgisel
  • Algoritma ile Çözümü”, Bilimde Modern
  • Yöntemler Sempozyumu – BMYS 2010, 14-
  • Ekim Dicle Üniversitesi Kongre Merkezi,
  • -130, 2010.
  • Naderi, B., Ghomi, S.M.T.F., Aminnayeri, M.,
  • Zandieh, M., “A contributon and new heuristics
  • for open shop scheduling”, Computers &
  • Operations Research, 37, 213-221, 2010.
  • Zhang, X. ve Velde, S., “On-line two-machine
  • open shop scheduling with time lags”,
  • European Journal of Operational Research,
  • 14–19, 2010.
  • Türkeli, B., “Solution of Bicriteria Open Shop
  • Scheduling Problem with Genetic Algorithm
  • and Tabu Search and Detailed Analysis of
  • Results”, Yüksek Lisans Tezi, Marmara
  • University Institute For Graduate Studies In
  • Pure And Applied Sciences, İstanbul, 2010.
  • Kökçam, A.H. ve Engin, O., “Bulanık Proje
  • Çizelgeleme Problemlerinin Meta Sezgisel
  • Yöntemlerle Çözümü”, Mühendislik ve Fen
  • Bilimleri Dergisi (Sigma), 28, 86-101, 2010.
  • Serbencu, A., Minzu, V., Serbencu, A., “An Ant
  • Colony System Based Metaheurıstic for Solving
  • Single Machine Scheduling Problem”, The
  • Annals of “Dunarea De Jos” Unıversity Of
  • Galati Fascicle III, Electrotechnıcs,
  • Electronıcs, Automatıc Control, Informatıcs, 19-
  • , 2007.
  • Teske, E., “Computing discrete logarithms with
  • the parallelized kangaroo method”, Discrete
  • Applied Mathematics, 130, 61-82, 2003.
  • Pollard, J.M., “Kruskal's Card Trick”, The
  • Mathematical Gazette, 84, 500 (Jul.), 265-267,
  • -
  • Jellouli, O., Chatelet, E., “Monte Carlo
  • Simulation And Stochastich Algorithms For
  • Optimising Supply Chain Management in an
  • Uncertain Environment”, Systems, Man, and
  • Cybernetics, 2001 IEEE International
  • Conference, 3 1840-1844. 2001.
  • Stein, A. ve Teske, E., “The Parallelized Pollard
  • Kangaroo Method in Real Quadratic Function
  • Fields”, Mathematics of Computation, 71/238
  • -814, 2001.
  • Minzu, V. ve Beldiman, L., “Some aspects
  • concerning the implementation of a parallel
  • hybrid metaheuristic”, Engineering
  • Applications of Artificial Intelligence, 20,
  • –999, 2007.
  • Yılmaz, M.K., Kökçam, A.H., Duvarcı, V.,
  • Fığlalı, A., Ayöz, M., Engin, O., “Paralel
  • Kanguru Algoritması Yardımıyla Beklemesiz
  • Akış Tipi Çizelgeleme Problemlerinin
  • Çözümü”, Yöneylem Araştırması ve Endüstri
  • Mühendisliği 29. Ulusal Kongresi, 2010.
  • Yılmaz, M.K., Engin, O., Fığlalı, A., Yavuz,
  • M., “Parallel Kangaroo Algorithm For Biobjective
  • Flow Shop Scheduling with a New
  • Weight Combining Approach”, 1st
  • International Symposium on Computing in
  • Science & Engineering, ISCSE-2010, Gediz
  • University (İzmir), June 3-5, Kuşadası Aydın
  • Turkey, 823-827, 2010.
  • Yılmaz, M.K., Fığlalı, A., Terzi, U., Yavuz, M.,
  • Engin, O., “A Hybrid Parallel Kangaroo a
  • &Simulated Annealing Algorithm for Multi-
  • Objective Flow Shop Scheduling” The Journal
  • of Management and Engineering Integration,
  • , 2, 2010.
  • Guéret, C., Prins, C., “A new lower bound for
  • the open-shop problem”, Annals of Operations
  • Research, 92:165–83, 1999.
  • Guéret, C., Ecole des mines de Nantes – Open
  • shop problems [online], Nantes, Ecole des
  • mines de Nantes, http://www.minesnantes.
  • fr/en/Media/ Elements-Sites-
  • Persos/Christelle-Gueret/Openshop/
  • HardOSInstances [Ziyaret Tarihi: 3 Ocak
  • .
There are 170 citations in total.

Details

Primary Language Turkish
Journal Section Makaleler
Authors

M. Emin Baysal This is me

Taha Durmaz This is me

Ahmet Sarucan This is me

Orhan Engin

Publication Date February 19, 2013
Submission Date February 19, 2013
Published in Issue Year 2012 Volume: 27 Issue: 4

Cite

APA Baysal, M. E., Durmaz, T., Sarucan, A., Engin, O. (2013). AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 27(4).
AMA Baysal ME, Durmaz T, Sarucan A, Engin O. AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ. GUMMFD. March 2013;27(4).
Chicago Baysal, M. Emin, Taha Durmaz, Ahmet Sarucan, and Orhan Engin. “AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 27, no. 4 (March 2013).
EndNote Baysal ME, Durmaz T, Sarucan A, Engin O (March 1, 2013) AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 27 4
IEEE M. E. Baysal, T. Durmaz, A. Sarucan, and O. Engin, “AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ”, GUMMFD, vol. 27, no. 4, 2013.
ISNAD Baysal, M. Emin et al. “AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 27/4 (March 2013).
JAMA Baysal ME, Durmaz T, Sarucan A, Engin O. AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ. GUMMFD. 2013;27.
MLA Baysal, M. Emin et al. “AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ”. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol. 27, no. 4, 2013.
Vancouver Baysal ME, Durmaz T, Sarucan A, Engin O. AÇIK ATÖLYE TİPİ ÇİZELGELEME PROBLEMLERİNİN PARALEL KANGURU ALGORİTMASI İLE ÇÖZÜMÜ. GUMMFD. 2013;27(4).