Optimisation of Job Shop Scheduling Using Genetic Algorithm

In the current trend of Job Shop Scheduling in modern industries is still relying on the expert’s skill sets, although the computation enrolls almost all the fields. Application of the biological principal of natural selection to the artificial systems such as evolutionary algorithm was introduced more than three decades ago which has an inspiring evolution in the past few years. In this project, inspiring evolution of one such evolutionary algorithm called Genetic Algorithm (GA) is applied to Static Job Shop Scheduling Problem (JSSP) based on the raw data such as number of jobs to be machined on certain numbers of machines with operation time for each job on each machine to search out the optimal make-span of the problem. This project explains various operational parameters of genetic algorithm, which is one of the optimisation technique based on the mechanics of natural selection and genetics in combination with survival of fitness among the chromosomes structures in heuristic manner. In which each chromosome is encoded as a string of job sequence in integer or real value encoding fashion and the set of chromosomes called population is evaluated using various genetic operations such as one point crossover, swap mutation and linear ranking selection to search in multi direction to find the optimal solutions in the vast search space.

Many prevailing industrial production environments still rely on pure professional knowledge for production planning and scheduling purposes. Optimization in an algorithmic sense is mostly not performed at all. This may seem amazing at first glance since computation have invaded almost all fields of modern industries. In particular, systems such as Production, Planning and Control Systems serve as a support tool for production related management activities. Such systems are designed in a highly generic and versatile way in order to be applied in many different companies no matter what products they actually manufacture. In general, the objectives of optimization may be different from company to company such as minimization of make-span, maximizing machine occupation or both. Therefore, the concept of Production, Planning and Control Systems is not applicable for the optimization of production planning and scheduling in most of the cases. Due to its increasing significance, the optimization of production planning and scheduling attracted the attention of academic research. The Job Shop Scheduling Problem (JSSP) and similar scheduling problems are combinatorial optimization problems and commonly classified as NP-hard ordering problems which makes almost impossible to solve these problems exactly, even for relatively small problem instances. Exact methods exist, like the branch and bound method which are only of theoretical relevance due to their exponential runtime complexity. In reality compute results close to the optimum but in a reasonable amount of time is highly enough rather optimality. In such a case heuristic methods such as Local Search, Tabu Search, Simulated annealing and Evolutionary Algorithms, especially Genetic Algorithms (GA), are dominating in the field of JSSP. Among the three kinds of JSSP such as static, dynamic and non-deterministic, In this project, the static JSSP is used to evaluate the sequence using GA. JSSP description in terms of GA is initial phase challenge and machine side scheduling also challenged at final phase using the result of job side sequence. This report briefly describes the GA and its parameter along with the JSS parameters.

A PROJECT BY - KUMARAVEL.S, MOHAMMED ISHAQ.I, SANKARALINGAM.B,VENKATESH.G

Table of Contents