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.