alphanumeric journal
The Journal of Operations Research, Statistics, Econometrics and Management Information Systems
A Proposed New Approach for The Single Machine Scheduling Problem: Dynamic Programming
bib
Abstract
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.
Keywords: Deteriorating Jobs, Dynamic Programming, Rate-modifying Activities, Scheduling
Jel Classification: C61, C72, G11
Suggested citation
(). 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
References
- 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
2024.12.01.OR.02
alphanumeric journal
Pages 13-20
Received: Nov. 10, 2022
Accepted: March 21, 2024
Published: July 20, 2024
2024 Özkan Özen, YD., Öztürkoğlu, Ö., Öztürkoğlu, Y.
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence, which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
scan QR code to access this article from your mobile device
Contact Us
Faculty of Transportation and Logistics, Istanbul University
Beyazit Campus 34452 Fatih/Istanbul/TURKEY
Bahadır Fatih Yıldırım, Ph.D.
editor@alphanumericjournal.com
+ 90 (212) 440 00 00 - 13219
alphanumeric journal
alphanumeric journal has been publishing as "International Peer-Reviewed Journal" every six months since 2013. alphanumeric serves as a vehicle for researchers and practitioners in the field of quantitative methods, and is enabling a process of sharing in all fields related to the operations research, statistics, econometrics and management informations systems in order to enhance the quality on a globe scale.