LOGARİTMİK TOPLAM İŞLEM ZAMAN TABANLI ÖĞRENME ETKİLİ TEK MAKİNELİ ÇİZELGELEME: TOPLAM ERKEN BİTİRME VE TOPLAM GECİKME MİNİMİZASYONU

Öz

Üretim ortamında aynı veya benzer işlerin sürekli tekrar etmesiyle işlem zamanlarında bir gelişme olduğu görülmüştür. Bu olgu literatürde öğrenme etkisi olarak bilinmektedir. Bu çalışmada da logaritmik işlem zamanlı tek makineli çizelgeleme problemi ele alınmıştır. Problemin amacı toplam erken bitirme ile toplam tamamlanma zamanlarının ağırlıkları toplamını minimize etmektir. Problemin çözmek için n iş sayısı göstermek üzere n2 + 5n değişkenli ve 7n kısıtlı doğrusal olmayan programlama modeli önerilmiştir. Geliştirilen model bir örnek üzerinde uygulanmıştır.

Anahtar Kelimeler

• Tek makineli çizelgeleme, öğrenme etkisi, erken bitirme, geç bitirme, doğrusal-olmayan programlama modeli

SINGLE MACHINE SCHEDULING WITH SUM OF LOGARITHM PROCESSING TIMES LEARNING EFFECT: MINIMIZATION OF TOTAL EARLINESS AND TOTAL TARDINESS

Abstract

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a single machine scheduling problem. The objective is to find a sequence that minimizes a weighted sum of total earliness and total tardiness. To solve this scheduling problem, a non-linear programming model with n2 + 5n variables and 7n constraints where n is the number of jobs is formulated. Also the model is tested on an example.

Keywords

• Single machine scheduling, learning effect, earliness, tardiness, non-linear programming model

Kaynakça

1. [1] BAKER, K.R., SCUDDER, G.D., “Sequencing with earliness and tardiness penalties: a review”, Operations Research, 38, 22–36, 1990.
2. [2] EREN, T., GÜNER, E., “Tek ve paralel makinalı problemlerde çok ölçütlü çizelgeleme problemleri için bir literatür taraması”, Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 17 (4), 37-69, 2002.
3. [3] EREN, T., GÜNER, E., “Çok ölçütlü akış tipi çizelgeleme problemleri için bir literatür taraması”, Pamukkale Üniversitesi Mühendislik Fakültesi Mühendislik Bilimleri Dergisi, 10 (1), 19-30, 2004.
4. [4] FRY, T.D., ARMSTRONG, R., BLACKSTONE, J., “Minimizing weighted absolute deviation in single machine scheduling”, IIE Transactions, 19, 445–450, 1987.
5. [5] OW, P.S., MORTON, E.T., “The single machine early/tardy problem”, Management Science, 35, 177–191, 1989.
6. [6] HALL, N.G., KUBIAK, W., SETHI, S.P., “Earliness–tardiness scheduling problems, II: deviation of completion times about a restrictive common due date”, Operations Research, 39, 847–56, 1991.
7. [7] AZIZOGLU, M., KONDAKCI, S., KIRCA, O., “Bicriteria scheduling problem involving total tardiness and total earliness penalties”, International Journal of Production Economics, 23, 17–24, 1991.
8. [8] YANO, C.A., KIM, Y.D., “Algorithms for a class of single machine weighted tardiness and earliness scheduling problems”, European Journal of Operational Research, 52, 167–178, 1991.

9. [9] DAVIS, J.S., KANET, J.J., “Single machine scheduling with early and tardy completion costs”, Naval Research Logistics, 40, 85–101, 1993.
10. [10] KIM, Y., YANO, C.A., “Minimizing mean tardiness and earliness in single machine scheduling with unequal due dates”, Naval Research Logistics, 41, 913–933, 1994.
11. [11] SZWARC, W., “The weighted common due date single machine scheduling problem revisited”, Computers & Operations Research, 23 (3), 255–262, 1996.
12. [12] WENG, X., VENTURA, J.A., “Scheduling about a given common due date to minimize mean squared deviation of completion times”, European Journal of Operational Research, 88, 328–335, 1996.
13. [13] ALIDAEE, B., DRAGAN, I., “A note on minimizing the weighted sum of tardy and early completion penalties in a single machine: a case of small common due date”, European Journal of Operational Research, 96, 559–63, 1997.
14. [14] LI, G., “Single machine earliness and tardiness scheduling”, European Journal of Operational Research, 96, 546–558, 1997.
15. [15] ALMEIDA, M.T., CENTENO, M., “A composite heuristic for the single machine early–tardy job scheduling problem”, Computers & Operations Research, 25, 625–635, 1998.
16. [16] LIAW C.F., “A branch and bound algorithm for the single machine earliness and tardiness scheduling problem”, Computers & Operations Research, 26, 679–693, 1999.
17. [17] CHANG, P.C., “A branch and bound approach for single machine scheduling with earliness and tardiness penalties”, Computers and Mathematics with Applications, 37, 133–144, 1999.
18. [18] MONDAL, S.A., SEN, A.K., “Single machine weighted earliness–tardiness penalty problem with a common due date” Computers&Operations Research, 28 (7), 649–669, 2001.
19. [19] MONDAL, S.A., “Minimization of squared deviation of completion times about a common due date”, Computers & Operations Research, 29, 2073–2085, 2002.
20. [20] FELDMANN, M., BISKUP, D., “Single machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches”, Computers & Industrial Engineering, 44, 307–323, 2003.
21. [21] SOURD, F., SIDHOUM, S.K., “The one machine problem with earliness and tardiness penalties”, Journal of Scheduling, 6, 533–549, 2003.
22. [22] SOURD, F., SIDHOUM, S.K., “A faster branch-and-bound algorithm for the earliness–tardiness scheduling problem”, Journal of Scheduling, 11, 49–58, 2008.
23. [23] VENTURA, J.A., RADHAKRISHNAN, S., “Single machine scheduling with symmetric earliness and tardiness penalties”, European Journal of Operational Research, 144, 598–612, 2003.
24. [24] HINO, C.M., RONCONI, D.P., MENDES, A.B., “Miniimizing earliness and tardiness penalties in a single machine problem with a common due date”, European Journal of Operational Research, 160, 190–201, 2005.
25. [25] SOURD, F., “Optimal timing of a sequence of tasks with general completion costs”, European Journal of Operational Research, 165, 82–96, 2005.
26. [26] SOURD, F., “New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling”, INFORMS Journal of Computing, 21, 167–175, 2009
27. [27] VALENTE, J.M.S., ALVES, R., “Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time”, Computers & Industrial Engineering 48 (2), 363–375, 2005.
28. [28] VALENTE, J.M.S., ALVES, R., “Improved heuristics for the early/tardy scheduling problem with no idle time”, Computers & Operations Research, 32 (3), 557–569, 2005.
29. [29] HENDEL, Y., SOURD, F., “Efficient neighborhood search for the one-machine earliness–tardiness scheduling problem”, European Journal of Operational Research, 173 (1), 108-119, 2006.
30. [30] M’HALLAH, R., “Minimizing total earliness and tardiness on a single machine using a hybrid heuristic”, Computers & Operations Research, 34, 3126–3142, 2007.
31. [31] WODECKI, M., “A block approach to earliness–tardiness scheduling problem”, International Journal of Advanced Manufacturing Technology, 40,797–807, 2009.
32. [32] SIDHOUM, S.K., SOURD, F., “Fast neighborhood search for the single machine earliness-tardiness scheduling problem”, Computers & Operations Research, 37 (8), 1464-1471, 2010.
33. [33] RONCONI D.P.; KAWAMURA M.S., “The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm”, Computatıonal & Applıed Mathematıcs, 29 (2), 107- 124, 2010.
34. [34] CHEN, S.H., CHEN, M.C., CHANG, P.C., CHEN Y.M., “EA/G-GA for Single Machine Scheduling Problems with Earliness/Tardiness Costs”, Entropy, 13 (6), 1152-1169, 2011.
35. [35] BISKUP, D., “Single-machine scheduling with learning considerations”, European Journal of Operational Research, 115, 173–178, 1999.
36. [36] MOSHEIOV, G., Scheduling problems with a learning effect European Journal of Operational Research, 132 (3) 2001, 687-693
37. [37] MOSHEIOV, G., SIDNEY, J.B., “Scheduling with general job-dependent learning curves”, European Journal of Operational Research, 147, Issue 3, 16 June 2003, Pages 665-670
38. [38] KUO, W.H., YANG D.L., “Minimizing the makespan in a single machine scheduling problem with a timebased learning effect” Information Processing Letters, 97 (2), 64-67, 2006.
39. [39] KOULAMAS, C., KYPARISIS G.J., “Single-machine and two-machine flowshop scheduling with general learning functions”, European Journal of Operational Research, 178 (2), 402-407, 2007.
40. [40] YANG, D.L., KUO, W.H., “Single-machine scheduling with an actual time-dependent learning effect”, Journal of the Operational Research Society, 58, 1348–1353, 2007.
41. [41] EREN T., GÜNER E., “Hazırlık ve taşıma zamanlarının öğrenme etkili olduğu çizelgeleme problemleri”, Trakya Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 8 (1), 7-13, 2007.
42. [42] CHENG, T.C.E., WU, CC, LEE WC, “Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects” Information Sciences, 178 (11), 2476-2487, 2008.
43. [43] WU, C.C., LEE, W.C., “Single-machine scheduling problems with a learning effect”, Applied Mathematical Modelling, 32 (7), 1191-1197, 2008.
44. [44] WU, CC, LEE WC, “Single-machine and flowshop scheduling with a general learning effect model”, Computers & Industrial Engineering, 56 (4), 1553-1558, 2009.
45. [45] WANG JB, “Single-machine scheduling with general learning functions”, Computers & Mathematics with Applications, 56 (8), 1941-1947, 2008.
46. [46] WANG J-B, “Single-machine scheduling with a sum-of-actual-processing-time-based learning effect”, Journal of the Operational Research Society 61, 172–177, 2010.
47. [47] YIN, Y., XU, D., SUN, K., LI, H., “Some scheduling problems with general position-dependent and dependent learning effects”, Information Sciences, 179 (14), 2416-2425, 2009.
48. [48] SUN, K.B., LI, H.X., “Some single-machine scheduling problems with actual time and position dependent learning effects”, Fuzzy Information and Engineering, 1 (2), 161-177, 2009.
49. [49] CHENG, T.C.E. LAI, PJ, WU, CC, LEE WC, “Single-machine scheduling with sum-of-logarithmprocessing-times-based learning considerations”, Information Sciences, 179 (18), 3127-3135, 2009.
50. [50] LEE, W.C., WU, C.C., “Some single-machine and m-machine flowshop scheduling problems with learning considerations”, Information Sciences, 179 (22), 3885-3892, 2009.
51. [51] ZHANG, X., YAN, G., “Machine scheduling problems with a general learning effect”, Mathematical and Computer Modelling, 51 (1–2), 84-90, 2010.
52. [52] LEE, W.C., WU, C.C., HSU, P.H., “A single-machine learning effect scheduling problem with release times”, Omega, 38 (1–2), 3-11, 2010.
53. [53] WU, C.C., LIU, C.L., “Minimizing the makespan on a single machine with learning and unequal release times”, Computers & Industrial Engineering, 59 (3), 419-424, 2010.
54. [54] WANG, J.B., WANG, D., ZHANG, G.D., “Single-machine scheduling with learning functions”, Applied Mathematics and Computation, 216 (4), 1280-1286, 2010,
55. [55] WANG, J.B., SUN, L., SUN, L., “Single machine scheduling with exponential sum-of-logarithmprocessing-times based learning effect”, Applied Mathematical Modelling, 34 (10), 2813-2819, 2010.
56. [56] WANG, J.B., SUN, L.H., SUN, L.Y., “Scheduling jobs with an exponential sum-of-actual-processing-timebased learning effect”, Computers & Mathematics with Applications, 60 (9), 2673-2678, 2010.
57. [57] WANG, L.Y, WANG, J.J., WANG, J.B., FENG, E.M., “Scheduling jobs with general learning functions”, Journal of Systems Science and Systems Engineering, 20 (1), 119-125, 2011.
58. [58] KOULAMAS, C., “A note on single-machine scheduling with job-dependent learning effects”, European Journal of Operational Research, 207 (2), 1142-1143, 2010.
59. [59] WANG, J.B., WANG, J.J., “Single-machine scheduling jobs with exponential learning functions”, Computers & Industrial Engineering, 60 (4), 755-759, 2011.
60. [60] WANG, J.B., WANG, J.J., “Scheduling jobs with a general learning effect model”, Applied Mathematical Modelling, basımda, 2012.
61. [61] LAI, P.J., LEE, W.C, “Single-machine scheduling with general sum-of-processing-time-based and positionbased learning effects”, Omega, 39 (5), 467-471, 2011.
62. [62] LEE, W.C., “Scheduling with general position-based learning curves”, Information Sciences, 181 (24), 5515-5522, 2011.
63. [63] BAI, J., WANG, M.Z., WANG, J.B., “Single machine scheduling with a general exponential learning effect”, Applied Mathematical Modelling, 36 (2), 829-835, 2012.
64. [64] ZHANG, X., YAN, G., HUANG, W., TANG G., “A note on machine scheduling with sum-of-logarithmprocessing-time-based and position-based learning effects”, Information Sciences, 187, 298-304, 2012.
65. [65] DOLGUI, A., GORDON, V., STRUSEVICH, V., “Single machine scheduling with precedence constraints and positionally dependent processing times”, Computers & Operations Research, 39 (6), 1218-1224, 2012.
66. [66] RUDEK, R., “Scheduling problems with position dependent job processing times: computational complexity results”, Annals of Operations Research, 196 (1), 491-516, 2012.
67. [67] LU, Y.Y., WEI, C.M., WANG, J.B., “Several single-machine scheduling problems with general learning effects”, Applied Mathematical Modelling, basımda, 2012.
68. [68] KUO, W.H., YANG D.L., “Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect”, European Journal of Operational Research, 174 (2), 1184-1190, 2006.
69. [69] YIN, Y., XU, D., WANG, J., “Single-machine scheduling with a general sum-of-actual-processing-timesbased and job-position-based learning effect”, Applied Mathematical Modelling, 34 (11), 3623-3630, 2010.
70. [70] WU, C.C., HSU, P.H., LAI, K., “Simulated-annealing heuristics for the single-machine scheduling problem with learning and unequal job release times”, Journal of Manufacturing Systems, 30 (1) 54-62, 2011.
71. [71] WU, C.C., HSU, P.H., CHEN, J.C., WANG, N.S., WU, W.H., “Branch-and-bound and simulated annealing algorithms for a total weighted completion timescheduling with ready times and learning effect, The International Journal of Advanced Manufacturing Technology, 55 (1-4), 341-353, 2011.
72. [72] WU, C.C., HSU, P.H., CHEN, J.C., WANG, N.S., “Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times”, Computers & Operations Research, 38 (7), 1025-1034, 2011.
73. [73] WU, CC., YIN, Y., CHENG, S.R., “Some single-machine scheduling problems with a truncation learning effect”, Computers & Industrial Engineering, 60 (4), 790-795, 2011.
74. [74] LOW, C., LIN W.Y., “Minimizing the total completion time in a single-machine scheduling problem with a learning effect”, Applied Mathematical Modelling, 35 (4), 1946-1951, 2011.
75. [75] KUO, W.H., YANG, D.L., “Single-machine scheduling problems with the time-dependent learning effect”, Computers & Mathematics with Applications, 53, 1733-1739, 2007.
76. [76] WANG, J.B., NG, C.T., CHENG, T.C.E., LIU, L.L., “Single-machine scheduling with a time-dependent learning effect, International Journal of Production Economics 111 (2), 802-811, 2008.
77. [77] XU, Z., SUN, L., GONG J., “Worst-case analysis for flow shop scheduling with a learning effect”, International Journal of Production Economics, 113 (2), 748-753, 2008.
78. [78] EREN, T., “Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect”, Applied Mathematics and Computation, 208 (2), 355-358, 2009.
79. [79] EREN, T., “Tek Makineli Çizelgelemede Genel Öğrenme Fonksiyonları: Optimal Çözümler”, Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, basımda, 2012
80. [80] WANG, J.B., WANG, J.J., “Single machine scheduling with sum-of-logarithm-processing-times based and position based learning effects”, Optimization Letters, basımda, 2012.
81. [81] EREN T., “Zamana-bağımlı öğrenme etkili çizelgeleme probleminde maksimum gecikme minimizasyonu: Doğrusal-olmayan programlama modeli”, Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 23 (2), 459-465, 2008.
82. [82] EREN T., “Zamana-bağımlı öğrenme etkili tek makineli çizelgeleme problemleri”, Sigma Mühendislik ve Fen Bilimleri Dergisi, basımda, 2012.
83. [83] CHENG, T.C.E., WANG, G., “Single machine scheduling with learning effect considerations”, Annals of Operations Research, 98 (1-4), 273-290, 2000.
84. [84] WU, C.C., LEE, W.C., CHEN, T., “Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations”, Computers & Industrial Engineering, 52 (1), 124-132, 2007.
85. [85] JIANG, Z., CHEN, F., WU C., “Minimizing the maximum lateness in a single-machine scheduling problem with the normal time-dependent and job-dependent learning effect”, Applied Mathematics and Computation, 218 (18), 9438-9441, 2012.
86. [86] EREN, T., “Hazırlık ve taşıma zamanlarının öğrenme etkili olduğu tek makineli çizelgeleme problemi: Geciken iş sayısı minimizasyonu”, International Journal of Engineering Research and Development, 6 (6), 34-36, 2011.
87. [87] EREN, T., “Logaritmik toplam işlem zaman tabanlı öğrenme etkili tek makineli çizelgeleme: geciken iş sayısı minimizasyonu”, Nevşehir Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 1, 83-88, 2012.
88. [88] EREN, T., “Öğrenme etkili çizelgeleme problemi: Geciken iş sayısı minimizasyonu”, Teknoloji Dergisi, 10 (4), 235-238, 2007.
89. [89] EREN, T., GÜNER, E., “Minimizing total tardiness in a scheduling problem with a learning effect”, Applied Mathematical Modelling, 31 (7), 1351-1361, 2007.
90. [90] YIN, Y., WU, C.C., WU, W.H., CHENG, S.R., “The single-machine total weighted tardiness scheduling problem with position-based learning effects”, Computers & Operations Research, 39 (5), 1109-1116, 2012.
91. [91] GAREY, M.R., TARJAN, R.E., WILFONG, G.T., “One-processor scheduling with symmetric earliness and tardiness penalties”, Mathematics of Operations Research, 13, 330–348, 1988.
92. [92] LEE, C.Y., KIM, S.J., “Parallel genetic algorithms for the earliness—tardiness job scheduling problem with general penalty weights”, Computers &Industrial Engineering, 28, 231–243, 1995.
93. [93] LEE, C.Y., CHOI, J.Y., “A genetic algorithm for job sequencing problems with distinct due dates and general early–tardy penalty weights”, Computers & Operations Research, 22 (8), 857–869, 1995.