Buradasınız

Anasayfa » Content

SIRA BAĞIMLI HAZIRLIK OPERASYONLARI İÇİN TEK EKİPLİ PARALEL MAKİNALARDA ÇİZELGELEME PROBLEMİNE KARMA YAKLAŞIM

A HYBRIT APPROACH ON SINGLE SERVER PARALLEL MACHINES SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES

Journal Name:

  • Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi

Publication Year:

  • 2011

Key Words:

Keywords (Original Language):

Author NameUniversity of Author
Abstract (2. Language): 
In this paper, a scheduling problem on two identical parallel machines with sequence-dependent setup times and setup operations that performed by a single server is considered. The main objective is to minimize the makespan of the schedule. For solution procedure, an algorithm combining genetic algorithm and tabu search methodology is proposed. Firstly, the algorithm finds an initial solution using genetic algorithm module. Then, tabu search module is applied to the solution of genetic algorithm in order to find better solution. The performance of the algorithm is analyzed by comparing the results with the random search results. It has been seen that the proposed algorithm is effective to solve P2,S|STsd|Cmax scheduling problem in reasonable time, and the results are close to optimum solution values.
Bookmark/Search this post with
Abstract (Original Language): 
Bu çalışmada; paralel makinelerde hazırlık süresinin sıra bağımlı olduğu, bir başka ifadeyle işin hazırlık süresinin bir önceki işe bağlı olarak farklılık gösterdiği ve hazırlık operasyonlarının bir ekip tarafından gerçekleştirildiği, iş çizelgeleme probleminin tamamlanma süresini en küçükleyecek sezgisel bir yaklaşım sunulmuştur. Problem çözümü için genetik algoritma ve tabu arama yaklaşımlarını birlikte kullanan bir yaklaşım önerilmiştir. İlk olarak, genetik algoritma ile problemin başlangıç çözümü elde edilmiş ve sonrasında daha iyi çözümler elde etmek için tabu arama yöntemi kullanılmıştır. Bu yaklaşımın performansı, rastgele arama yöntemi sonuçları ile kıyaslanarak analiz edilmiştir. Sonuç olarak, önerilen yaklaşımın, P2,S|STsd|Cmax probleminde etkin olduğu görülmüştür.
FULL TEXT (PDF): 
PDF icon arastirmax-sira-bagimli-hazirlik-operasyonlari-icin-tek-ekipli-paralel-makinalarda-cizelgeleme-problemine-karma-yaklasim.pdf
  • 4
731
740
  • Turkish

REFERENCES

References: 

1. Abdekhodaee, A.H., Wirth,A., Gan,H.S.
Scheduling two paralel machines with a single
server: the general case. Computers &
Operations Research.33, 994-1009, 2006.
2. Abdekhodaee, A. H., Wirth, A. Scheduling
parallel machines with a single server: Some
solvable cases and heuristics. Computers and
Operations Research.,29, 295-315, 2002.
Tablo 6. Hesaplama süreleri ve kıyaslama sonuçları (Computational times and comparison results)
Problem
Setleri
Uygulanan Yaklaşımların Hesaplama
Süreleri
Uygulanan Yaklaşımlardan
Elde edilen Sonuçları
RS TS GA GTA RS TS GA GTA Sapma
(%)
10x2_1 13,63 2,31 13,69 13,63 72 97 72 72 0
10x2_2 15,85 2,21 12,88 15,85 62 82 61 61 1,61
10x2_3 20,37 2,86 15,73 20,37 154 181 154 154 0
10x2_4 17,58 2,46 15,99 17,58 105 138 105 105 0
10x2_5 19,51 2,9 19,93 19,51 165 197 166 166 -0,6
20x2_1 32,57 13,86 19,72 32,57 152 154 152 147 3,29
20x2_2 31,46 14,81 17,69 31,46 126 126 127 123 2,38
20x2_3 41,83 20,65 21,33 41,83 263 264 264 256 2,66
20x2_4 38,32 17,14 19,59 38,32 202 197 203 196 2,97
20x2_5 44,6 22,24 19,91 44,6 338 328 334 324 4,14
30x2_1 55,31 44,73 19,74 55,31 227 242 228 215 5,29
30x2_2 52,35 36,53 18,86 52,35 183 193 182 175 4,37
30x2_3 87,21 70,37 21,77 87,21 433 411 431 409 5,54
30x2_4 63,53 47,63 21,82 63,53 303 302 302 287 5,28
30x2_5 81,24 57,28 21,72 81,24 558 535 558 532 4,66
50x2_1 107,66 106,8 17,41 107,66 400 384 401 371 7,25
50x2_2 113,82 81,12 16,96 113,82 324 307 324 303 6,48
50x2_3 168,63 145,79 19,58 168,63 689 641 688 639 7,26
50x2_4 115,74 104,91 17,81 115,74 507 480 509 472 6,9
50x2_5 177,54 151,15 18,53 177,54 931 872 928 863 7,3
Ortalama 65,94 47,39 18,53 64,94 309,7 309,45 309,45 293,5 3,84
A.K. Türker ve Ç. Sel Sıra Bağımlı Hazırlık Operasyonları İçin Tek Ekipli Paralel Makinalarda…
740 Gazi Üniv. Müh. Mim. Fak. Der. Cilt 26, No 4, 2011
3. Allahverdi, A., Gupta, J. N., Aldowaisan, T. A
review of scheduling research involving setup
considerations. OMEGA The Int. Journal of
Management Sciences.27,219-239,1999.
4. Allahverdi, A., Mg, C. T., Cheng, T. C.,
Kovalyov, M. Y. A survey of scheduling
problems with setup times or costs. European
Journal of Operational Research.187,985-
1032,2008.
5. Armento, V. A., Yamashita, D. S. Tabu search for
scheduling on identical parallel machines to
minimize mean tardiness. Journal of Intelligent
Manufacturing. 11,453-460,2000.
6. Bilge, U., Kirac, F., Kurtulan, M., Pekgun, P.A.
Tabu search algorithm for parallel machine total
tardiness problem. Computers and Operations
Research. 31,397-414,2004.
7. Cheng, T., C., E., Gupta, J., N., D., Wang, G. A
review of flowshop scheduling research with
setup times. Production and Operations
Managament. 9,262-282,2010.
8. Gendreau, M., Laporte, G., Guimaraes, E. M. A
divide and merge heuristic for the multiprocessor
scheduling problem with sequence dependent
setup times. European Journal of Operational
Research. 133,183-189,2001.
9. Glover, F., Kochenberger, G. A. Handbook of
metaheuristics. Kluwer Academic Publishers.
New York. 2003.
10. Guinet, A.Scheduling sequence dependent jobs on
identical parallel machines to minimize
completion time criteria. Int. J. Prod. Res. 31(7),
1579-1594,1993.
11. Huang, S., Chai, L., Zhang, X. Parallel dedicated
machine scheduling problem with sequencedependent
setups and a single server.
Computers& Industrial Engineering. 58,165-
174,2009.
12. Kellegoz, T., Toklu, B., Wilson, J, Comparing
efficiencies of genetic crossover operators for one
machine total weighted tardiness problem.
Applied Mathematics and Computation.
199,590-598,2008.
13. Kellegoz, T., Toklu, B., Wilson, J. Elite guided
steady-state genetic algorithm for minimizing
total tardiness in flowshops. Computers &
Industrial Eng. 58,300-306,2010.
14. Kim, S. S., Shin, H. J., Eom, D. H., Kim, C. O. A
due date density-based categorising heuristic for
parallel machines scheduling. Int J. Adv. Manuf.
Technol. 22,753-760,2003.
15. Kim, C. O., Shin, H. J. Scheduling jobs on
parallel machines: a restricted tabu search
approach. Int. J. Adv. Manuf. Technol. 22,278-
287,2003.
16. Kurz, M. E., Askin, R. G. Heuristic scheduling of
parallel machines with sequence-dependent set-up
times. Int. J. Prod. Res. 39(16),3747-3769,2001.
17. McNaughton, R. Scheduling with deadlines and
loss functions. Management Science.,6,1-
12,1959.
18. Montoya-Torres, J.R., Soto-Ferrari, M.,
Gonzalez-Solano, F., Alfonso-Lizarazo, E.
Machine Scheduling with Sequence-dependent
Setup Times using a Randomized Search
Heuristic. Proceedings of the 39th International
Conference on Computers and Industrial
Engineering (CIE-39),28-33,2009.
19. Sel, C. Scheduling parallel machines using
genetic algorithms with sequence dependent setup
times and a single server. Masters thesis,
Kirikkale University, Kirikkale, August 2010.
20. Sivriaya, F., Ulusoy, G. Parallel machine
scheduling with earliness and tardiness penalties.
Computers & Operations Research.,26,773-
787, 1999.
21. Turker, A. K., Sel, C. Scheduling two parallel
machines with sequence- dependent setups and a
single server. G.U Journal of Science.24,1,113-
123,2011.
22. Wilson, A. D., King, R. E., Hodgson, T. J.
Scheduling non-similar groups on a flow line:
multiple group setups. Robotics and Computer-
Integrated Manufacturing,20,505-515,2004.
23. Yang, W., Liao, C. Survey of scheduling research
involving setup times. International Journal of
Systems Science,30,143-155,2010.

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