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

Öz

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.

Anahtar Kelimeler

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

Kaynakça

1. Liaw, C.F., Cheng, C.Y., Chen, M., “The total
2. completion time open shop scheduling problem
3. with a given sequence of jobs on one machine”,
4. Computers & Operations Research, 29, 1251
5. – 1266, 2002.
6. Durmaz, T., Açık Atölye Çizelgeleme
7. Problemlerinin Paralel Kanguru Algoritması
8. ile Çözümü, Yüksek Lisans Tezi, Selçuk

9. Üniversitesi, Fen Bilimleri Enstitüsü, 2011.
10. Gonzalez, T., Sahni, S., “Open shop scheduling
11. to minimize finish time”, Journal of the ACM,
12. (4):665–79, 1976.
13. Arıkan, M., Erol, S., “A long term memory tabu
14. search algorithm for part selection and machine
15. loading in flexible manufacturing systems”,
16. Journal of The Faculty of Engineering and
17. Architecture of Gazi University, 25, 2, 311-
18. , 2010.
19. Dereli, T., Daş, G. S., “Ant colony optimization
20. approach for container loading problems”,
21. Journal of The Faculty of Engineering and
22. Architecture of Gazi University, 25, 4, 881-
23. , 2010
24. Liaw, C.F., “An efficient tabu search approach
25. for the two-machine preemptive open shop
26. scheduling problem”, Computers &
27. Operations Research, 30, 2081–2095 2003.
28. NG, C.T., Cheng, T.C.E., Yuan, J.J., “Concurrent
29. Open Shop Scheduling to Minimize the
30. Weighted Number of Tardy Jobs”, Journal of
31. Scheduling, 6, 405 – 412, 2003.
32. Blum, C., “Beam-ACO—hybridizing ant colony
33. optimization with beam search: an application
34. to open shop scheduling”, Computers &
35. Operations Research, 32, 1565–1591, 2005.
36. Shabtay, D., Kaspi, M., “Minimizing the
37. Makespan in Open-Shop Scheduling Problems
38. with a Convex Resource Consumption
39. Function,” Wiley InterScience (2 February
40. .
41. Senthilkumar, P., Shahabudeen, P., “GA based
42. heuristic for the open job shop scheduling
43. problem”, Int J Adv Manuf Technol, 30, 297–
44. , 2006.
45. Sedeno-Noda, A., Alcaide, D., Gonzalez-
46. Martin, C., “Network flow approaches to preemptive
47. open-shop scheduling problems with time-windows”, European Journal of
48. Operational Research, 174, 1501–1518, 2006.
49. Gribkovskaia, I.V., Lee, C.Y., Strusevich, V.A.,
50. Werra, D., “Three is easy, two is hard: open
51. shop sum-batch scheduling problem refined”,
52. Operations Research Letters, 34, 459 – 464,
53. -
54. Sha, D.Y., Hsu, C.Y., “A new particle swarm
55. optimization for the open shop scheduling
56. problem”, Computers & Operations
57. Research, 35 3243 – 3261, 2008.
58. Brasel, H., Herms, A., Mörig, M., Tautenhahn,
59. T., Tusch, J., Werner, F., “Heuristic
60. constructive algorithms for open shop
61. scheduling to minimize mean flow time”,
62. European Journal of Operational Research,
63. , 856–870, 2008.
64. Lin, H.T., Lee, H.T., Pan, W.J., “Heuristics for
65. scheduling in a no-wait open shop with movable
66. dedicated machines”, Int. J. Production
67. Economics, 111, 368–377, 2008.
68. Mosheiov, G., Oron, D., “Open-shop batch
69. scheduling with identical jobs”, European
70. Journal of Operational Research, 187, 1282–
71. , 2008.
72. Werra, D., Kis, T., Kubiak, W., “Preemptive
73. open shop scheduling with multiprocessors:
74. polynomial cases and applications”, J Sched 11,
75. –83, 2008.
76. Sedeño-Noda, A., Pablo, D.A.L., González-
77. Martín, C., “A network flow-based method to
78. solve performance cost and makespan openshop
79. scheduling problems with time-windows”,
80. European Journal of Operational Research,
81. , 140–154, 2009.
82. Low, C. ve Yeh, Y., “Genetic algorithm-based
83. heuristics for an open shop scheduling problem
84. with setup, processing, and removal times
85. separated”, Robotics and Computer-
86. Integrated Manufacturing, 25, 314–322,
87. -
88. Akgöbek, Ö., Kaya, S., Değirmenci, Ü., Engin,
89. O., “Açık Atölye Tipi Çizelgeleme
90. Problemlerinin Paralel Doyumsuz Metasezgisel
91. Algoritma ile Çözümü”, Bilimde Modern
92. Yöntemler Sempozyumu – BMYS 2010, 14-
93. Ekim Dicle Üniversitesi Kongre Merkezi,
94. -130, 2010.
95. Naderi, B., Ghomi, S.M.T.F., Aminnayeri, M.,
96. Zandieh, M., “A contributon and new heuristics
97. for open shop scheduling”, Computers &
98. Operations Research, 37, 213-221, 2010.
99. Zhang, X. ve Velde, S., “On-line two-machine
100. open shop scheduling with time lags”,
101. European Journal of Operational Research,
102. 14–19, 2010.
103. Türkeli, B., “Solution of Bicriteria Open Shop
104. Scheduling Problem with Genetic Algorithm
105. and Tabu Search and Detailed Analysis of
106. Results”, Yüksek Lisans Tezi, Marmara
107. University Institute For Graduate Studies In
108. Pure And Applied Sciences, İstanbul, 2010.
109. Kökçam, A.H. ve Engin, O., “Bulanık Proje
110. Çizelgeleme Problemlerinin Meta Sezgisel
111. Yöntemlerle Çözümü”, Mühendislik ve Fen
112. Bilimleri Dergisi (Sigma), 28, 86-101, 2010.
113. Serbencu, A., Minzu, V., Serbencu, A., “An Ant
114. Colony System Based Metaheurıstic for Solving
115. Single Machine Scheduling Problem”, The
116. Annals of “Dunarea De Jos” Unıversity Of
117. Galati Fascicle III, Electrotechnıcs,
118. Electronıcs, Automatıc Control, Informatıcs, 19-
119. , 2007.
120. Teske, E., “Computing discrete logarithms with
121. the parallelized kangaroo method”, Discrete
122. Applied Mathematics, 130, 61-82, 2003.
123. Pollard, J.M., “Kruskal's Card Trick”, The
124. Mathematical Gazette, 84, 500 (Jul.), 265-267,
125. -
126. Jellouli, O., Chatelet, E., “Monte Carlo
127. Simulation And Stochastich Algorithms For
128. Optimising Supply Chain Management in an
129. Uncertain Environment”, Systems, Man, and
130. Cybernetics, 2001 IEEE International
131. Conference, 3 1840-1844. 2001.
132. Stein, A. ve Teske, E., “The Parallelized Pollard
133. Kangaroo Method in Real Quadratic Function
134. Fields”, Mathematics of Computation, 71/238
135. -814, 2001.
136. Minzu, V. ve Beldiman, L., “Some aspects
137. concerning the implementation of a parallel
138. hybrid metaheuristic”, Engineering
139. Applications of Artificial Intelligence, 20,
140. –999, 2007.
141. Yılmaz, M.K., Kökçam, A.H., Duvarcı, V.,
142. Fığlalı, A., Ayöz, M., Engin, O., “Paralel
143. Kanguru Algoritması Yardımıyla Beklemesiz
144. Akış Tipi Çizelgeleme Problemlerinin
145. Çözümü”, Yöneylem Araştırması ve Endüstri
146. Mühendisliği 29. Ulusal Kongresi, 2010.
147. Yılmaz, M.K., Engin, O., Fığlalı, A., Yavuz,
148. M., “Parallel Kangaroo Algorithm For Biobjective
149. Flow Shop Scheduling with a New
150. Weight Combining Approach”, 1st
151. International Symposium on Computing in
152. Science & Engineering, ISCSE-2010, Gediz
153. University (İzmir), June 3-5, Kuşadası Aydın
154. Turkey, 823-827, 2010.
155. Yılmaz, M.K., Fığlalı, A., Terzi, U., Yavuz, M.,
156. Engin, O., “A Hybrid Parallel Kangaroo a
157. &Simulated Annealing Algorithm for Multi-
158. Objective Flow Shop Scheduling” The Journal
159. of Management and Engineering Integration,
160. , 2, 2010.
161. Guéret, C., Prins, C., “A new lower bound for
162. the open-shop problem”, Annals of Operations
163. Research, 92:165–83, 1999.
164. Guéret, C., Ecole des mines de Nantes – Open
165. shop problems [online], Nantes, Ecole des
166. mines de Nantes, http://www.minesnantes.
167. fr/en/Media/ Elements-Sites-
168. Persos/Christelle-Gueret/Openshop/
169. HardOSInstances [Ziyaret Tarihi: 3 Ocak
170. .