PARALEL MAKİNELERDE İŞLERİN VE MAKİNE OPERATÖRLERİNİN BİRLİKTE ÇİZELGELENMESİ PROBLEMİNE ÇÖZÜM YAKLAŞIMLARI

Öz

Literatürde ele alınan paralel makine çizelgeleme problemlerinin çoğunluğu, işlerin ihtiyaç duyduğu tekkaynağın makine olduğu varsayımına dayanır ve yalnızca iş-makine çizelgeleme problemi ile ilgilenir. Oysagerçek yaşam problemlerinde işler, makineler dışındaki ek kaynaklara da gereksinim duymaktadır. Ekkaynakların en çok karşılaşılan örneği, farklı makinelerde farklı işlerle çalışabilme yeteneğine sahip olan makineoperatörleridir. Bu çalışmada işlerin ve operatörlerin paralel makineler boyunca çizelgelenmesini gerektiren birgerçek yaşam problemi ele alınmıştır. Operatörler, makineleri izlemek, ürünleri çıkarmak, ürün üzerindekifazlalıkları almak vb. işlemlerle sorumludur. Bu işlemler, herhangi bir ürünün işlenme süresinin tamamı boyuncabir operatörün makine başında durmasını gerektirmeyebilir. Bu kapsamda, ele alınan problemin yazındaki benzerçalışmalardan önemli bir farkı; bir operatörün belli zaman dilimleri boyunca birden fazla makineye atanabilmesiözelliğidir. Operatörün aynı zaman diliminde ilgileneceği makineler belirlenirken, makinelerin fizikselyakınlıkları da dikkate alınmalıdır. Ele alınan problem için en son işin bitiş süresini en küçükleme amaçlıtamsayı ve kısıt programlama modelleri geliştirilmiştir. Geliştirilen modeller, farklı parametreler içeren testproblemlerine uygulanmış ve performansları değerlendirilmiştir. Son olarak, kısıt programlama modeliningerçek yaşam problemine uygulanabilirliği gösterilmiştir.

Anahtar Kelimeler

• paralel makineler, iş ve operatör çizelgeleme, tamsayı programlama, kısıt programlama

Kaynakça

1. Pinedo M., Scheduling: Theory, Algorithms,
2. and Systems, 2. basım, Prentice-Hall,
3. Englewood-Cliffs, NJ, A.B.D., 2002.
4. Ventura, J.A. ve Kim, D., “Parallel machine
5. scheduling with earliness-tardiness penalties and
6. additional resource constraints”, Computers &
7. Operations Research, Cilt 30, 1945–1958, 2003.
8. Daniels, R.L., Hua, S.Y., ve Webster, S.,

9. “Heuristics for Parallel-Machine Flexible-
10. Resource Scheduling Problems with Unspecified
11. Job Assignment”, Computers & Operations
12. Research, Cilt 26, 143-155, 1999.
13. Edis, E.B., Oğuz, C. ve Özkarahan, İ., “Paralel
14. Makinelerde İşlerin ve Makine Operatörlerinin
15. Birlikte Çizelgelenmesi Problemine Çözüm
16. Yaklaşımları”, Yöneylem Araştırması ve
17. Endüstri Mühendisliği 30. Ulusal Kongresi
18. Bildiri Özetleri Kitabı, Sabancı Üniversitesi,
19. İstanbul, 338, 30 Haziran-2 Temmuz 2010.
20. Edis, E.B., “Resource Constrained Parallel
21. Machine Scheduling Problems with Machine
22. Eligibility Restrictions: Mathematical and
23. Constraint Programming Based Approaches”,
24. Doktora Tezi, Dokuz Eylül Üniversitesi, Fen
25. Bilimleri Enstitüsü, Ocak 2010.
26. Daniels, R.L., Hoopes, B.J. ve Mazzola J.B.,
27. “Scheduling Parallel Manufacturing Cells with
28. Resource Flexibility”, Management Science,
29. Cilt 42, No 9, 1260-1276, 1996.
30. Chen, Z., “Simultaneous Job Scheduling and
31. Resource Allocation on Parallel Machines”,
32. Annals of Operations Research, Cilt 129, 135–
33. , 1999.
34. Grigoriev, A., Sviridenko, M. ve Uetz, M., “LP
35. rounding and an almost harmonic algorithm for
36. scheduling with resource dependent processing
37. times”, Lecture Notes in Computer Science,
38. Cilt 4110, Editörler: Diaz, J., Jansen, K., Rolim,
39. J. ve Zwick, U., Springer-Verlag, Berlin,
40. Almanya, 140-151, 2006.
41. Grigoriev, A., Sviridenko, M. ve Uetz, M.,
42. “Machine scheduling with resource dependent
43. processing times”, Mathematical Programming
44. Series B, Cilt 110, 209-228, 2007.
45. Grigoriev, A., Sviridenko, M. ve Uetz, M.,
46. “Unrelated parallel machine scheduling with
47. resource dependent processing times”, Lecture
48. Notes in Computer Science, Cilt 3509,
49. Editörler: Jünger, M. ve Kaibel V., Springer-
50. Verlag, Berlin, Almanya, 182-195, 2005.
51. Hu, P.C., “Minimising Total Tardiness for the
52. Worker Assignment Scheduling Problem in
53. Identical Parallel-Machine Models”,
54. International Journal of Advanced
55. Manufacturing Technology, Cilt 23, No 5–6,
56. –388, 2004.
57. Hu, P.C., “Minimizing Total Flow Time for the
58. Worker Assignment Scheduling Problem in the
59. Identical Parallel-Machine Models”,
60. International Journal of Advanced
61. Manufacturing Technology, Cilt 25, No 9–10,
62. –1052, 2005.
63. Chaudry, I.A. ve Drake, P.R., “Minimizing total
64. tardiness for the machine scheduling and worker
65. assignment problems in identical paralel
66. machines using genetic algorithms”,
67. International Journal of Advanced
68. Manufacturing Technology, Cilt 42, 581–594,
69. -
70. Chaudry, I.A., “Minimizing flow time for the
71. worker assignment problem in identical parallel
72. machine models using GA”, International
73. Journal of Advanced Manufacturing
74. Technology, Cilt 48, 747–760, 2010.
75. Edis, E.B, Araz, C. ve Ozkarahan, I.
76. "Lagrangian-Based Solution Approaches for a
77. Resource-Constrained Parallel Machine
78. Scheduling Problem with Machine Eligibility
79. Restrictions", Lecture Notes in Computer
80. Science, Cilt 5027, Editörler: Nguyen, N.T. vd.,
81. Springer-Verlag, Berlin, Almanya, 337-346,
82. -
83. Edis, E. B. ve Ozkarahan, I. “A combined
84. integer/constraint programming approach to a
85. resource-constrained parallel machine scheduling
86. problem with machine eligibility restrictions”,
87. Engineering Optimization, Cilt 43, No 2, 135-
88. , 2011.
89. Edis, E.B. ve Ozkarahan, I. "Solution Approaches
90. for a Real Life Resource Constrained Parallel
91. Machine Scheduling Problem", International
92. Journal of Advanced Manufacturing
93. Technology, Cilt 58, No 9-12, 1141-1153, 2012.
94. Bourland, K.E. ve Carl, L.K., “Parallel machine
95. scheduling with fractional operator
96. requirements”, IIE Transactions, Cilt 26, No 5,
97. -65, 1994.
98. Zouba, M, Baptiste, P. ve Rebaine, D.,
99. “Scheduling identical parallel machines and
100. operators within a period based changing mode”,
101. Computers & Operations Research, Cilt 36,
102. -3239, 2009.
103. Garey, M.R. ve Johnson, D.S., Computers and
104. Intractability: A Guide to the Theory of NPCompleteness,
105. W. H. Freeman and Company,
106. A.B.D., 1979.
107. Darbi-Dowman, K.D., Little, J., Mitra, G. ve
108. Zaffalon, M., “Constraint Logic Programming
109. and Integer Programming Approaches and Their
110. Collaboration in Solving an Assignment
111. Scheduling Problem”, Constraints, Cilt 1, 245-
112. , 1997.
113. Smith, B.M., Brailsford, S.C., Hubbard, P.M. ve
114. Williams, H.P., “The Progressive Party Problem:
115. Integer Linear Programming and Constraint
116. Programming Compared”, Constraints, Cilt 1,
117. -138, 1997.
118. Darbi-Dowman, K.D. ve Little, J., “Properties of
119. Some Combinatorial Optimization Problems and
120. Their Effect on the Performance of Integer
121. Programming and Constraint Logic
122. Programming”, Informs Journal on
123. Computing, Cilt 10, No 3, 276-286, 1998.
124. Lustig, I.J. ve Puget J.F., “Program Does Not
125. Equal Program: Constraint Programming and Its
126. Relationship to Mathematical Programming”,
127. Interfaces, Cilt 31, No 6, 29-53, 2001.
128. IBM, ILOG OPL IDE 6.3., User’s Manual,
129. IBM Corp., 2009.
130. McNaughton, R., “Scheduling with deadlines and
131. loss functions”, Management Science, Cilt 6, No
132. , 1-12, 1959.
133. Li, Y., Wang, F. ve Lim A., “Resource
134. constraints machine scheduling: A genetic
135. algorithm approach”, CEC: 2003 Congress on
136. Evolutionary Computation, Cilt 1-4, 1080-
137. , 2003.