Improved dynamic programming approach for the response time

Abstract

Fair sequences are useful in a variety of manufacturing and computer systems. The concept of fair sequence has emerged independently from scheduling problems of diverse environments, principally from manufacturing, hard real-time systems, operating systems and network environments. There has been a growing interest in scheduling problems where fair sequence is needed. There are various applications where jobs, clients, or products need to be scheduled in such a way that they get their necessary resources at a constant interval, without being too early or too late. The concept of variation in response time has been recently appeared in literature and a lot of research is being carried out in this area.

The problem of variation in the response time is known as Response Time Variability Problem (RTVP). This dissertation includes recent researches regarding the response time variability problem. RTVP is very hard to solve optimally. It has been proved to be NP-hard. Our concern in this dissertation is to find out the optimal sequence of jobs with objective of minimizing the response time variability. Various solutions based on heuristics exist in the literature to fulfill this objective. One of the approaches is the dynamic programming approach. This dissertation work focuses on the dynamic programming approach. Dynamic programming approach is a complete enumeration scheme that minimizes the amount of computation to be done by dividing the problem into series of subproblems. It solves the subproblems until it finds the solution of the original problem. This approach is not supposed to be a practical solution because of the exponential time and space complexity. The main objective of this dissertation is to improve the dynamic programming approach to RTVP to obtain an efficient solution. The dynamic programming approach will be practically improved by applying some heuristic methods. The basic idea behind the improvement is that we need not search the whole state space if we can find that some states do not lead to an optimal solution. Heuristics will be applied to prune the nonoptimal states. Since, the problem is NP-hard, we cannot theoretically reduce exponential complexity to polynomial complexity. But practically, we can apply heuristic methods to modify the algorithm that can solve the larger instances of the problem.