A Hybrid Ant Colony Optimization For The Job Shop Scheduling Problem

With the increasing keen market competition, each enterprise looks for better solutions to production and operation management aiming at improve the core competitive advantage. The key to the management of production and operation management is to achieve the optimal solutions. Therefore, the study of Job Shop Schedule problem is the great significance.Job Shop problem is to solve the problem that making prearrange is optimization by assigning resources to finish different manufacture tasks according to time early or late. Job Shop problem is the concentrate model of many actual job shop schedule problems, and it is a typical Nondeterministic Polynomial-time hard problem. The problem has many complex characteristics, such as constraints, nonlinearity, uncertainty and large scale, so it is reported that it can't get the best outcome through polynomial. In recent years, meta-heuristics algorithm can get strong lift-force answer in much shorter time, but there is rare better answer.In this paper, we present a hybrid algorithm combining ant colony optimization algorithm with the taboo search algorithm for the classical job shop scheduling problem. Instead of using the conventional construction approach to construct feasible schedules, the proposed ant colony optimization algorithm employs a novel decomposition method inspired by the shifting bottleneck procedure, and a mechanism of occasional reoptimizaitons of partial schedules. Besides, a tabu search algorithm is embedded to improve the solution quality. We run the proposed algorithm on some benchmark instances and the outcome indicate the hybrid algorithm has better constringency and better whole constringency.