Optimization of Makespan for Flexible Job Shop Scheduling Problems using Genetic Algorithms

Abstract

Manufacturing scheduling is one of the most researched areas since its optimality plays an important role in the operation of the shop floor. Manufacturing has a vital contribution in the overall economy of a country as it generates and attracts commercial activities. The whole framework of business has changed in view of the fluctuating global customer demands and fierce opposition from technologically advanced competitors. There is always a pressure on the manufacturer to produce the designed products in the shortest possible time to capture the market. To the challenge of changing product requirements and market demands, flexible manufacturing system is the answer. Flexible job shop is employed to produce a medium variety of products in a medium volume category. In contrast to the conventional job shop, it offers flexibility in performing operations on different machines; hence providing space for the manufacturing planner / scheduler for arranging parts as per corporate requirements. When seen in the context of optimal operation, this setting while offering such great advantage, also poses the scheduler with the decision regarding assignment of operations to available machines in addition to sequencing of operations. In this way, the complexity of the problem grows exponentially even in the small settings of the shop.The flexible job shop scheduling is a NP-hard combinatorial optimization problem with regards to complexity and its exact solution requires many lifetimes to reach. Consequently, techniques built around the concepts of artificial intelligence have been popularly used to solve the problem. Genetic Algorithm (GA) is one of the most attempted and widespread technique from this domain. GA can produce good results of the scheduling problems, however when stuck in the local minima, the algorithm normally fails to escape, and solution quality is badly affected. In this research work, problem is formulated mathematically and insights to a selected benchmark is provided. Problem complexity is then evaluated in a quantitative way through estimation of search space of the selected datasets and an understanding to the actual area of search is developed. Priority rules are then integrated with the GA (GA-PR) to solve the FJSSP. In this regard, competitive modification in the rule has been proposed in addition to the integration scheme. The algorithm is also equipped with adaptive operators which also contribute to its performance. In addition to this a standalone pure GA (GA-IDT) is also proposed to efficiently solve the target problem. An iterative diversification technique is embedded into the proposed algorithm which proficiently manages the intensification and diversification of the population.The efficacy of both algorithms is tested against standard benchmark problems and it is concluded that proposed techniques are competitive with other concepts in literature.