Optimization of Online Job Shop Partitioning and Scheduling for Heterogeneous Systems using Genetic Algorithm

摘要

Job Shop Scheduling problem becomes more complex if heterogeneous systems are considered and algorithm is to be implemented for online schedulers. In real time, number of heterogeneous systems connected to online scheduler may vary from time to time. Also, number of different sized jobs may differ at any instant. This problem deals with optimization of job partitioning when maximum partition size is given; and to find out scheduling criteria when new jobs arrive keeping old jobs status in mind. So, partitioning size for any particular job and make span time for given jobs are optimized at any given instant for given set of jobs. This is known to be NP complete problem therefore many techniques based on different heuristics have been proposed to solve partitioning and scheduling problem efficiently and in reasonable amount of time. This paper proposes the solution to this problem using Genetic algorithm. Variation in number of jobs and systems require very flexible algorithm which can adjust its parameters accordingly; the proposed algorithm is capable and very efficient to handle such issues. This paper covers introduction to problem and various terms used, proposed solution using Genetic Algorithm (GA) with newly designed fitness function and performance comparison of proposed GA under various constraints.