Open Access Open Access  Restricted Access Subscription Access

A Hybrid Genetic Algorithm with a Knowledge-Based Operator for Solving the Job Shop Scheduling Problems


Affiliations
1 Department of Manufacturing and Industrial Engineering, Universiti Teknologi Malaysia (UTM), 81310 Skudai, Johor, Malaysia
 

Scheduling is considered as an important topic in production management and combinatorial optimization in which it ubiquitously exists in most of the real-world applications. The attempts of finding optimal or near optimal solutions for the job shop scheduling problems are deemed important, because they are characterized as highly complex and 𝑁𝑃-hard problems. This paper describes the development of a hybrid genetic algorithm for solving the nonpreemptive job shop scheduling problems with the objective of minimizing makespan. In order to solve the presented problem more effectively, an operation-based representation was used to enable the construction of feasible schedules. In addition, a new knowledge-based operator was designed based on the problem’s characteristics in order to use machines’ idle times to improve the solution quality, and it was developed in the context of function evaluation. A machine based precedence preserving order-based crossover was proposed to generate the offspring. Furthermore, a simulated annealing based neighborhood search technique was used to improve the local exploitation ability of the algorithm and to increase its population diversity. In order to prove the efficiency and effectiveness of the proposed algorithm, numerous benchmarked instances were collected from the Operations Research Library. Computational results of the proposed hybrid genetic algorithm demonstrate its effectiveness.
User
Notifications
Font Size

Abstract Views: 62

PDF Views: 1




  • A Hybrid Genetic Algorithm with a Knowledge-Based Operator for Solving the Job Shop Scheduling Problems

Abstract Views: 62  |  PDF Views: 1

Authors

Hamed Piroozfard
Department of Manufacturing and Industrial Engineering, Universiti Teknologi Malaysia (UTM), 81310 Skudai, Johor, Malaysia
Kuan Yew Wong
Department of Manufacturing and Industrial Engineering, Universiti Teknologi Malaysia (UTM), 81310 Skudai, Johor, Malaysia
Adnan Hassan
Department of Manufacturing and Industrial Engineering, Universiti Teknologi Malaysia (UTM), 81310 Skudai, Johor, Malaysia

Abstract


Scheduling is considered as an important topic in production management and combinatorial optimization in which it ubiquitously exists in most of the real-world applications. The attempts of finding optimal or near optimal solutions for the job shop scheduling problems are deemed important, because they are characterized as highly complex and 𝑁𝑃-hard problems. This paper describes the development of a hybrid genetic algorithm for solving the nonpreemptive job shop scheduling problems with the objective of minimizing makespan. In order to solve the presented problem more effectively, an operation-based representation was used to enable the construction of feasible schedules. In addition, a new knowledge-based operator was designed based on the problem’s characteristics in order to use machines’ idle times to improve the solution quality, and it was developed in the context of function evaluation. A machine based precedence preserving order-based crossover was proposed to generate the offspring. Furthermore, a simulated annealing based neighborhood search technique was used to improve the local exploitation ability of the algorithm and to increase its population diversity. In order to prove the efficiency and effectiveness of the proposed algorithm, numerous benchmarked instances were collected from the Operations Research Library. Computational results of the proposed hybrid genetic algorithm demonstrate its effectiveness.