Certain investigations on scheduling problems using meta heuristics

Abstract

In manufacturing systems, the selection of the appropriate order in which waiting jobs are processed by machines is called “Job sequencing or permutation flow shop scheduling”. Typically, the number of machines available is limited. Each job consists of a certain number of operations and a machine can process a single operation at a time. Although theoretically it is possible to find the optimum sequence by testing each one, in practice, it is difficult to check each sequence because of the large number of computations involved. Hence any technique to arrive at optimum sequence at least approximately will be quite valuable. In the first part of the thesis, three genetic algorithm operators and a model for job sequence are proposed. These modified operators and the model can be used in the Genetic Algorithm (GA) procedure to get the optimum or sub-optimum sequences based on makespan i.e., minimum elapsed time.The second part of the thesis deals with the multiprocessor scheduling problem. Given a parallel program, and multiprocessors, the multiprocessor-scheduling problem has to find out the assignmentand execution order of tasks in the processors such that the given criterion is minimized. In this thesis, total execution time is considered the criterion to be ivminimized. A Hybrid Genetic Algorithm (HGA) is proposed in this thesis for the multiprocessorscheduling problem. In HGA, the GA part performs the exploration of the solutions and the exploitation is done by one of the two local search procedures, namely, Simulated annealing or Hill climbing. In hybridGA, hill climbing genetic algorithm is compared with the simulated annealing genetic algorithm. A novel Ant Colony algorithm (ACO) procedure for multiprocessor is also proposed. ACO is compared with the HGA and GA procedures for the standard benchmark task graphs. GA, Hybrid GA, and ACO procedures are compared for 2,4,8, and 16 processors.