Araştırma Makalesi
BibTex RIS Kaynak Göster

A Proposed New Approach for The Single Machine Scheduling Problem: Dynamic Programming

Yıl 2024, Cilt: 12 Sayı: 1, 13 - 20, 20.07.2024
https://doi.org/10.17093/alphanumeric.1202408

Öz

A traditional scheduling problem is one of the optimization problems that assign tasks to humans and machines in an optimal order. In real applications, many jobs do not have a fixed processing time. During production, some machines need to be cooled due to overheating. This activity, which takes place outside periodic maintenance, is called rate-modifying. During this time, the job times increase with each passing second as Jobs wait to be assigned. The rate of deterioration due to this increase is called deteriorating jobs. This paper considers scheduling a set of deteriorating jobs with rate-modifying activity with a single processor. During the speed change activity, the production process is halted, resulting in increased completion times of jobs. The problem arose from the problem of a machine and an automatic production line. This problem is classified as an NP-Hard problem. The problem addressed by the study has been tried to obtain optimal results with different methods by considering different factors by many authors. When a detailed literature review is made, it has been seen that no author has developed a dynamic programming model until today. The most significant advantage of dynamic programming models is that they provide solutions with the closest optimal result faster, especially in solving problems classified as Np-Hard. Therefore, a dynamic programming algorithm was developed for the first time for large job numbers of the focused problem. Therefore, this study presents a dynamic programming algorithm to calculate the optimal solution. The algorithm's efficiency is proven on an extensive randomly generated sample data set. The results prove that the proposed algorithm provides the optimal solution with much less effort than the mathematical model.

Kaynakça

  • Browne, S., & Yechiali, U. (1990). Scheduling Deteriorating Jobs on a Single Processor. Operations Research, 38(3), 495–498. https://doi.org/10.1287/opre.38.3.495
  • Cheng, B., & Cheng, L. (2014). Note on "Single-machine due-window assignment and scheduling with resource allocation, aging effect, and a deteriorating rate-modifying activity". Computers & Industrial Engineering, 78, 320–322. https://doi.org/10.1016/j.cie.2014.07.013
  • Chung, B. D., & Kim, B. S. (2016). A hybrid genetic algorithm with two-stage dispatching heuristic for a machine scheduling problem with step-deteriorating jobs and rate-modifying activities. Computers & Industrial Engineering, 98, 113–124. https://doi.org/10.1016/j.cie.2016.05.028
  • Chung, T., Gupta, J. N. D., & Qiu, M. (2018). Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities. Engineering Optimization, 51(10), 1743–1760. https://doi.org/10.1080/0305215x.2018.1552269
  • Gupta, J. N., & Gupta, S. K. (1988). Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering, 14(4), 387–393. https://doi.org/10.1016/0360-8352(88)90041-1
  • Ji, M., Ge, J., Chen, K., & Cheng, T. (2013). Single-machine due-window assignment and scheduling with resource allocation, aging effect, and a deteriorating rate-modifying activity. Computers & Industrial Engineering, 66(4), 952–961. https://doi.org/10.1016/j.cie.2013.08.020
  • Kim, B. S., & Ozturkoglu, Y. (2012). Scheduling a single machine with multiple preventive maintenance activities and position-based deteriorations using genetic algorithms. The International Journal of Advanced Manufacturing Technology, 67(5–8), 1127–1137. https://doi.org/10.1007/s00170-012-4553-x
  • Kim, H., & Kim, B.-I. (2022). Optimal sequence for single server scheduling incorporating a rate-modifying activity under job-dependent linear deterioration. European Journal of Operational Research, 298(2), 439–450. https://doi.org/10.1016/j.ejor.2021.07.023
  • Lee, C.-Y., & Leon, V. (2001). Machine scheduling with a rate-modifying activity. European Journal of Operational Research, 128(1), 119–128. https://doi.org/10.1016/s0377-2217(99)00066-1
  • MacCarthy, B. L., & Liu, J. (1993). Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling. International Journal of Production Research, 31(1), 59–79. https://doi.org/10.1080/00207549308956713
  • Ozturkoglu, Y. (2020). A Different Approach to Nurse Scheduling Problem: Lagrangian Relaxation. Alphanumeric Journal, 8(2), 237–248. https://doi.org/10.17093/alphanumeric.659121
  • Ozturkoglu, Y., & Bulfin, R. L. (2011). A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying activities on a single machine. The International Journal of Advanced Manufacturing Technology, 57(5–8), 753–762. https://doi.org/10.1007/s00170-011-3303-9
  • Renna, P. (2014). Deteriorating job scheduling problem in a job-shop manufacturing system by multi-agent system. International Journal of Computer Integrated Manufacturing, 28(9), 936–945. https://doi.org/10.1080/0951192x.2014.928747
  • Zhang, X., Wu, W.-H., Lin, W.-C., & Wu, C.-C. (2018). Machine scheduling problems under deteriorating effects and deteriorating rate-modifying activities. Journal of the Operational Research Society, 69(3), 439–448. https://doi.org/10.1057/s41274-017-0200-0
Yıl 2024, Cilt: 12 Sayı: 1, 13 - 20, 20.07.2024
https://doi.org/10.17093/alphanumeric.1202408

Öz

Kaynakça

  • Browne, S., & Yechiali, U. (1990). Scheduling Deteriorating Jobs on a Single Processor. Operations Research, 38(3), 495–498. https://doi.org/10.1287/opre.38.3.495
  • Cheng, B., & Cheng, L. (2014). Note on "Single-machine due-window assignment and scheduling with resource allocation, aging effect, and a deteriorating rate-modifying activity". Computers & Industrial Engineering, 78, 320–322. https://doi.org/10.1016/j.cie.2014.07.013
  • Chung, B. D., & Kim, B. S. (2016). A hybrid genetic algorithm with two-stage dispatching heuristic for a machine scheduling problem with step-deteriorating jobs and rate-modifying activities. Computers & Industrial Engineering, 98, 113–124. https://doi.org/10.1016/j.cie.2016.05.028
  • Chung, T., Gupta, J. N. D., & Qiu, M. (2018). Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities. Engineering Optimization, 51(10), 1743–1760. https://doi.org/10.1080/0305215x.2018.1552269
  • Gupta, J. N., & Gupta, S. K. (1988). Single facility scheduling with nonlinear processing times. Computers & Industrial Engineering, 14(4), 387–393. https://doi.org/10.1016/0360-8352(88)90041-1
  • Ji, M., Ge, J., Chen, K., & Cheng, T. (2013). Single-machine due-window assignment and scheduling with resource allocation, aging effect, and a deteriorating rate-modifying activity. Computers & Industrial Engineering, 66(4), 952–961. https://doi.org/10.1016/j.cie.2013.08.020
  • Kim, B. S., & Ozturkoglu, Y. (2012). Scheduling a single machine with multiple preventive maintenance activities and position-based deteriorations using genetic algorithms. The International Journal of Advanced Manufacturing Technology, 67(5–8), 1127–1137. https://doi.org/10.1007/s00170-012-4553-x
  • Kim, H., & Kim, B.-I. (2022). Optimal sequence for single server scheduling incorporating a rate-modifying activity under job-dependent linear deterioration. European Journal of Operational Research, 298(2), 439–450. https://doi.org/10.1016/j.ejor.2021.07.023
  • Lee, C.-Y., & Leon, V. (2001). Machine scheduling with a rate-modifying activity. European Journal of Operational Research, 128(1), 119–128. https://doi.org/10.1016/s0377-2217(99)00066-1
  • MacCarthy, B. L., & Liu, J. (1993). Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling. International Journal of Production Research, 31(1), 59–79. https://doi.org/10.1080/00207549308956713
  • Ozturkoglu, Y. (2020). A Different Approach to Nurse Scheduling Problem: Lagrangian Relaxation. Alphanumeric Journal, 8(2), 237–248. https://doi.org/10.17093/alphanumeric.659121
  • Ozturkoglu, Y., & Bulfin, R. L. (2011). A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying activities on a single machine. The International Journal of Advanced Manufacturing Technology, 57(5–8), 753–762. https://doi.org/10.1007/s00170-011-3303-9
  • Renna, P. (2014). Deteriorating job scheduling problem in a job-shop manufacturing system by multi-agent system. International Journal of Computer Integrated Manufacturing, 28(9), 936–945. https://doi.org/10.1080/0951192x.2014.928747
  • Zhang, X., Wu, W.-H., Lin, W.-C., & Wu, C.-C. (2018). Machine scheduling problems under deteriorating effects and deteriorating rate-modifying activities. Journal of the Operational Research Society, 69(3), 439–448. https://doi.org/10.1057/s41274-017-0200-0
Toplam 14 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Endüstri Mühendisliği
Bölüm Makaleler
Yazarlar

Yeşim Deniz Özkan Özen 0000-0003-4520-6590

Ömer Öztürkoğlu 0000-0003-3937-6657

Yücel Öztürkoğlu 0000-0002-9569-8178

Yayımlanma Tarihi 20 Temmuz 2024
Gönderilme Tarihi 10 Kasım 2022
Yayımlandığı Sayı Yıl 2024 Cilt: 12 Sayı: 1

Kaynak Göster

APA Özkan Özen, Y. D., Öztürkoğlu, Ö., & Öztürkoğlu, Y. (2024). A Proposed New Approach for The Single Machine Scheduling Problem: Dynamic Programming. Alphanumeric Journal, 12(1), 13-20. https://doi.org/10.17093/alphanumeric.1202408

Alphanumeric Journal is hosted on DergiPark, a web based online submission and peer review system powered by TUBİTAK ULAKBIM.

Alphanumeric Journal is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License