Buradasınız

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

TO SOLVE THE OPEN SHOP SCHEDULING PROBLEMS WITH THE PARALLEL KANGAROO ALGORITHM

Journal Name:

Publication Year:

Abstract (2. Language): 
The open shop scheduling problem is essentially a sort of scheduling problem that each job has only one operation to be processed on each machine and the processing order is not significant. It has been mainly encountered in a facility that is manufacturing similar types of products groups. In this study, open shop scheduling problems were solved in order to minimize the total make-span with Parallel Kangaroo algorithm which runs by the random jumping method. Parallel Kangaroo Algorithm is a meta-heuristic algorithm which continuously tries to reach the better solutions. The open shop scheduling instances for the benchmarking in the literature were solved with a Kangaroo Algorithm in which the wild and the tame kangaroo operators are operated in a parallel manner. The yielded results were compared with the best results in the literature. It has been found the performance of the Parallel Kangaroo Algorithm for solving the open shop scheduling problems was efficient.
Abstract (Original Language): 
Açık Atölye Tipi Çizelgeleme (AATÇ) problemi temelde, her bir işin her makinede işlem görmesi gereken sadece bir işleminin bulunduğu ve işlem sırasının önemli olmadığı bir çizelgeleme problemidir. Çoğunlukla benzer ürün gruplarının üretildiği tesislerde görülmektedir. Bu çalışmada, AATÇ problemleri toplam tamamlanma zamanının minimizasyonuna yönelik, rassal zıplama tekniği ile işleyen Paralel Kanguru Algoritması (PKA) ile çözülmüştür. PKA, sürekli daha iyi çözümlere ulaşmaya çalışan meta-sezgisel bir yö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 en iyi sonuçlar ile karşılaştırılmıştır. PKA’nın AATÇ problemlerinin çözümünde etkin bir yöntem olduğu belirlenmiştir.
855
864

REFERENCES

References: 

1. 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.
2. 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.
3. Gonzalez, T., Sahni, S., “Open shop scheduling
to minimize finish time”, Journal of the ACM,
23(4):665–79, 1976.
4. 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-
319, 2010.
5. 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-
894, 2010
6. Liaw, C.F., “An efficient tabu search approach
for the two-machine preemptive open shop
scheduling problem”, Computers &
Operations Research, 30, 2081–2095 2003.
7. 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.
8. Blum, C., “Beam-ACO—hybridizing ant colony
optimization with beam search: an application
to open shop scheduling”, Computers &
Operations Research, 32, 1565–1591, 2005.
9. Shabtay, D., Kaspi, M., “Minimizing the
Makespan in Open-Shop Scheduling Problems
with a Convex Resource Consumption
Function,” Wiley InterScience (2 February
2006).
10. Senthilkumar, P., Shahabudeen, P., “GA based
heuristic for the open job shop scheduling
problem”, Int J Adv Manuf Technol, 30, 297–
301, 2006.
11. Sedeno-Noda, A., Alcaide, D., Gonzalez-
Martin, C., “Network flow approaches to preemptive
open-shop scheduling problems with
M.E. Baysal ve Ark. Açık Atölye Çizelgeleme Problemlerinin Paralel Kanguru Algoritması ile Çözümü
864 Gazi Üniv. Müh. Mim. Fak. Der. Cilt 27, No 4, 2012
time-windows”, European Journal of
Operational Research, 174, 1501–1518, 2006.
12. 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,
2006.
13. Sha, D.Y., Hsu, C.Y., “A new particle swarm
optimization for the open shop scheduling
problem”, Computers & Operations
Research, 35 3243 – 3261, 2008.
14. 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,
189, 856–870, 2008.
15. 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.
16. Mosheiov, G., Oron, D., “Open-shop batch
scheduling with identical jobs”, European
Journal of Operational Research, 187, 1282–
1292, 2008.
17. Werra, D., Kis, T., Kubiak, W., “Preemptive
open shop scheduling with multiprocessors:
polynomial cases and applications”, J Sched 11,
75–83, 2008.
18. 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,
196, 140–154, 2009.
19. 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,
2009.
20. 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-
16 Ekim Dicle Üniversitesi Kongre Merkezi,
122-130, 2010.
21. 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.
22. Zhang, X. ve Velde, S., “On-line two-machine
open shop scheduling with time lags”,
European Journal of Operational Research,
204 14–19, 2010.
23. 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.
24. 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.
25. 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-
24, 2007.
26. Teske, E., “Computing discrete logarithms with
the parallelized kangaroo method”, Discrete
Applied Mathematics, 130, 61-82, 2003.
27. Pollard, J.M., “Kruskal's Card Trick”, The
Mathematical Gazette, 84, 500 (Jul.), 265-267,
2000.
28. 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.
29. Stein, A. ve Teske, E., “The Parallelized Pollard
Kangaroo Method in Real Quadratic Function
Fields”, Mathematics of Computation, 71/238
793-814, 2001.
30. Minzu, V. ve Beldiman, L., “Some aspects
concerning the implementation of a parallel
hybrid metaheuristic”, Engineering
Applications of Artificial Intelligence, 20,
993–999, 2007.
31. 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.
32. 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.
33. 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,
3, 2, 2010.
34. Guéret, C., Prins, C., “A new lower bound for
the open-shop problem”, Annals of Operations
Research, 92:165–83, 1999.
35. 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
2011].

Thank you for copying data from http://www.arastirmax.com