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

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

• Dynamic programming
• Deteriorating jobs
• Rate-modifying activities
• Scheduling

References

1. 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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

9. 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
10. 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
11. 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
12. 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
13. 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
14. 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