Geliş Zamanlarının Farklı Olduğu Öğrenme Etkili Tek Makine Çizelgelemede Toplam Gecikmenin Çözümü

Son zamanlarda çeşitli öğrenme etkisi modelleri, çizelgeleme problemlerinde yoğun olarak uygulama alanı bulmaktadır. Bu çalışmada, zamana bağlı öğrenme modeli kullanılarak, farklı geliş zamanlarının olduğu tek makine çizelgeleme problemi için toplam gecikmenin en küçüklemesi ele alınmıştır. Öne sürülen problemin optimum çözümlerini elde etmek için matematiksel programlama modeli oluşturulmuş, makul süre ve kısıtlı işlemci hafızasından dolayı ancak küçük boyutlu problemler çözülebilmiştir. Endüstriyel faaliyetlere daha uygun olan büyük boyutlu problemleri çözmek için bu yapıdaki problemlerde oldukça seyrek kullanılan meta sezgisel yöntemlerden faydalanılmıştır. Genetik algoritma, genetik algoritma tabanlı çözüm kombinasyon metodu, kanguru algoritması ve genetik-kanguru hibrid algoritma olmak üzere 4 farklı sezgisel yöntem geliştirilmiştir. Bu sezgiseller için soru çözümleri elde edilmiş ve birbiriyle karşılaştırılarak performans değerlendirmesi yapılmıştır.

Solution of Total Tardiness in Single Machine Scheduling Contains Learning Effect and Unequal Release Dates

Recently, various learning effect models intensively find application area in scheduling problems. In this study, minimization of total tardiness is considered by using time dependent learning effect for single machine scheduling problem with unequal release dates. A mathematical model is established for obtaining optimal solutions of proposed problem, and because of the reasonable period of time and limited processor memory, only small size problems can be solved. Meta-heuristics which are quite infrequently used in the problems of this nature, are utilized to solve large scale problems which are more suitable for industrial activities. 4 heuristics that genetic algorithm, genetic algorithm based solution combination method, kangaroo algorithm and genetic-kangaroo hybrid algorithm are developed. Problem solutions are obtained by these heuristics and performance evaluation is conducted by comparing these methods with each other.

___

  • Badiru, A. B. (1992). Computational survey of univariate and multivariate learning curve models. Engineering Management, IEEE Transactions on, 39(2), 176-188. Baker, K. R., & Martin, J. B. (1974). An experimental comparison of solution algorithms for the single‐machine tardiness problem. Naval Research Logistics Quarterly, 21(1), 187- 199.
  • Baker, K. R., & Schrage, L. E. (1978). Finding an optimal sequence by dynamic programming: an extension to precedence-related tasks. Operations Research, 26(1), 111- 120.
  • Biskup, D. (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1), 173-178. Cheng, T. E., & Wang, G. (2000). Single machine scheduling with learning effect considerations. Annals of Operations Research, 98(1-4), 273-290.
  • Cheng, T. E., Lai, P. J., Wu, C. C., & Lee, W. C. (2009). Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations. Information Sciences, 179(18), 3127-3135.
  • Cheng, T.C.E., Kuo, W-H., & Yang, D-L. (2013). Scheduling with a position-weighted learning effect based on sum-of-logarithm-processing-times and job position. Information Sciences 221, 490-500.
  • Cheng, T.C.E., Kuo, W-H., & Yang, D-L. (2014). Scheduling with a position-weighted learning effect. Optimization Letters 8, 293-306. Chou, F. D. (2009). An experienced learning genetic algorithm to solve the single machine total weighted tardiness scheduling problem. Expert Systems with Applications, 36(2), 3857-3865.
  • Duta, L., Henrioud, J. M., & Caciula, I. (2007, September). A real time solution to control disassembly processes. In 4th IFAC Conference on Management and Control of Production and Logistics, MCPL'2007. (Vol. 3, pp. 789-794).
  • Eren, T. Güner, E. (2006). A bicriteria scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 179 (1), 378-385.
  • Eren, T., & Güner, E. (2007a). A Bicriteria Scheduling Problem with a Learning Effect: Total Completion Time and Total Tardiness. INFOR: Information Systems and Operational Research, 45(2), 75-81.
  • Eren, T., & Güner, E. (2007b). Minimizing total tardiness in a scheduling problem with a learning effect. Applied Mathematical Modelling, 31(7), 1351-1361.
  • Eren, T. (2008). 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.
  • Eren, T., & Güner, E. (2008). A bicriteria flowshop scheduling with a learning effect. Applied Mathematical Modelling, 32(9), 1719-1733.
  • Eren, T. (2009a). A bicriteria parallel machine scheduling with a learning effect of setup and removal times. Applied Mathematical Modelling, 33(2), 1141-1150.
  • Eren, T. (2009b). Human and machine effects in a just-in-time scheduling problem. Human Factors and Ergonomics in Manufacturing, 19 (4), 294-299.
  • Eren, T. (2009). 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.
  • Eren, T. (2012a). Geciken iş sayısı ve gecikme aralığı ölçütlü zamana-bağımlı öğrenme etkili çizelgeleme probleminin çözümü. Gazi Üniversitesi Mühendislik-Mimarlık Fakültesi Dergisi, 27 (4), 875-879.
  • Eren, T. (2012b). Logaritmik Toplam İşlem Zaman Tabanlı Öğrenme Etkili Tek Makineli Çizelgeleme: Toplam Erken Bitirme Ve Toplam Gecikme Minimizasyonu. Niğde Üniversitesi Mühendislik Fakültesi Dergisi, 1 (2), 61-68.
  • Eren, T. (2012c). 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.
  • Eren, T. (2013a). Tek Makineli Çizelgelemede Genel Öğrenme Fonksiyonları: Optimal Çözümler. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 19(2), 76-80.
  • Eren, T. (2013b). İki Ölçütlü Üssel İşlem Zaman Taban Toplamlı Öğrenme Etkili Tek Makineli Çizelgeleme Problemi. Trakya Üniversitesi Mühendislik Bilimleri Dergisi, 14 (2), 99-104
  • Eren, T. (2013c). Zamana-bağımlı öğrenme etkili tek makineli çizelgeleme problemleri. Sigma Mühendislik ve Fen Bilimleri Dergisi, 31 (2), 214-221.
  • Eren, T. (2014). Öğrenme ve bozulma etkili tek makineli çizelgeleme problemleri. International Journal of Engineering Research and Development, 6 (1).
  • Golberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addion wesley, 1989.
  • Gourgand, M., Grangeon, N., & Norre, S. (2003). A contribution to the stochastic flow shop scheduling problem. European Journal of Operational Research, 151(2), 415-433.
  • Gourgand, M., Grangeon, N., & Norre, S. (2005). Markovian analysis for performance evaluation and scheduling in m machine stochastic flow-shop with buffers of any capacity. European Journal of Operational Research, 161(1), 126-147.
  • Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.
  • Janiak, A., & Rudek, R. (2009). Experience-based approach to scheduling problems with the learning effect. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 39(2), 344-357.
  • Janiak, A., & Rudek, R. (2010). A note on a makespan minimization problem with a multiability learning effect. Omega 38, 213-217.
  • Janiak, A., Janiak, W., Rudek, R., & Wielgus, A. (2009). Solution algorithms for the makespan minimization problem with the general learning model. Computers & Industrial Engineering 56, 1301-1308.
  • Jolai, F., Rabbani, M., Amalnick, S., Dabaghi, A., Dehghan, M., & Parast, M. Y. (2007). Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs. Applied Mathematics and Computation, 194(2), 552-560.
  • Koulamas, C., & Kyparisis, G. J. (2007). Single-machine and two-machine flowshop scheduling with general learning functions. European Journal of Operational Research, 178(2), 402-407.
  • Kuo, W. H., & Yang, D. L. (2006). 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.
  • Lawler, E. L. (1977). A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Annals of discrete Mathematics, 1, 331-342.
  • M‟Hallah, R. (2007). Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Computers & Operations Research, 34(10), 3126-3142.
  • Minzu, V., & Beldiman, L. (2007). Some aspects concerning the implementation of a parallel hybrid metaheuristic. Engineering Applications of Artificial Intelligence, 20(7), 993-999.
  • Mosheiov, G. (2001). Scheduling problems with a learning effect. European Journal of Operational Research, 132(3), 687-693.
  • Mosheiov, G., & Sidney, J. B. (2003). Scheduling with general job-dependent learning curves. European Journal of Operational Research, 147(3), 665-670.
  • Niu, Y-P., Wan, L., & Wang, J-B. (2015). A note on scheduling jobs with extended sum-ofprocessing-times-based and position-based learning effect. Asia-Pacific Journal of Operational Research 32(2), 1550001 (12 pages).
  • Pollard, J. M. (1978). Monte Carlo methods for index computation ( \ ). Mathematics of computation, 32(143), 918-924. Serbencu, A., Minzu, V., & Serbencu, A. (2007). An Ant Colony System based metaheuristic for solving single machine scheduling problem. Electrotechnics Electronics Automatic Control informatics, 19-24.
  • Sioud, A., Gravel, M., & Gagné, C. (2012). A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times. Computers & Operations Research, 39(10), 2415-2424.
  • Soltani, R., Jolai, F., & Zandieh, M. (2010). Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria. Expert Systems with Applications, 37(8), 5951-5959.
  • Stein, A., & Teske, E. (2002). The parallelized Pollard kangaroo method in real quadratic function fields. Mathematics of Computation, 71(238), 793-814.
  • Wang, J-B., & Wang, M-Z. (2014). Single-machine due-window assignment and scheduling with learning effect and resource-dependent processing times. Asia-Pacific Journal of Operational Research 31(5), 1450036 (15 pages).
  • Wang, X., & Tang, L. (2009). A population-based variable neighborhood search for the single machine total weighted tardiness problem. Computers & Operations Research, 36(6), 2105-2110.
  • Wright, T. P. (1936). Factors affecting the cost of airplanes. Journal of the Aeronautical Sciences 3, 122-128.
  • Wu, C. C., Hsu, P. H., & Lai, K. (2011). Simulated-annealing heuristics for the singlemachine scheduling problem with learning and unequal job release times. Journal of Manufacturing Systems, 30(1), 54-62.
  • Wu, C-C., Hsu, P-H., Chen, J-C., & Wang, N-S. (2011). Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times. Computers And Operations Research 38, 1025-1034.
  • Yin, Y., Wu, W-H., Wu, W-H., & Wu, C-C. (2014). A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects. Information Sciences 256, 91-108.
  • Yin, Y., Xu, D., Sun, K., & Li, H. (2009). Some scheduling problems with general positiondependent and time-dependent learning effects. Information Sciences 179, 2416-2425.
  • Zhou, H., Cheung, W., & Leung, L. C. (2009). Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research, 194(3), 637-649.