Optimal Software Reliability and Optimal Multiprocessor Scheduling Problems

Abstract

The scheduling and mapping of the precedence-constrained task graph to processors is considered to be the most crucial NP-complete problem in parallel and distributed computing systems. Several algorithms including genetic algorithms have been developed to solve this problem [18], [47], [124], [136]. A common feature in most of these has been the use of chromosomal representation for a schedule. However, these algorithms are monolithic, as they attempt to scan the entire solution space without considering how to reduce the complexity of the optimization process. In the case of multiprocessor scheduling problems there is still no optimum scheduling algorithm available in literature that can be applied to every type of problems that can be represented using Directed-Acyclic-Graphs of job pool. There is still a need for an efficient algorithm that can results in minimum execution time and at the same time making maximum utilization of the resources. Keeping this in view, in the present thesis we have focused on developing a genetic based approach for minimizing the schedule length (makespan) of tasks as well as maximizing the utilization of the resources. Estimating the reliability of a software under development can help managers to make release decisions during the testing stage itself. Several methods have been proposed in literature to estimate the defect content using a vast variety of software reliability growth models (SRGMs) [3], [53], [60], [107], [113]. SRGMs have certain underlying assumptions which are usually not met fully in practice. However, empirical evidence has shown that many SRGMs are quite robust despite these assumption violations. The problem is that, because of assumption violations in practice, it is often difficult to decide in a given situation which model to apply in practice. Keeping this in mind we propose in the present thesis a method for selecting an appropriate SRGM to make release decisions.