Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Hybrid genetic simulated annealing algorithm for solving job shop scheduling problem

A simulated annealing algorithm and job scheduling technology, applied in genetic rules, calculations, genetic models, etc., can solve the problems of poor time performance of SA algorithm and very strict global convergence requirements, and achieve reduced calculations, convenient operation, and convenience The effect of using

Active Publication Date: 2015-05-20
中国科学院沈阳计算技术研究所有限公司
View PDF5 Cites 42 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, the SA algorithm has a strong dependence on the cooling process, and its global convergence has very strict requirements on the cooling conditions, so the time performance of the SA algorithm is not good.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Hybrid genetic simulated annealing algorithm for solving job shop scheduling problem
  • Hybrid genetic simulated annealing algorithm for solving job shop scheduling problem
  • Hybrid genetic simulated annealing algorithm for solving job shop scheduling problem

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0060] The present invention will be further described in detail below with reference to the drawings and embodiments.

[0061] In order to overcome the limitations of the traditional genetic algorithm to solve the job-shop scheduling problem, the present invention combines the simulated annealing algorithm and the genetic algorithm, and proposes a new genetic simulated annealing (GASA) hybrid algorithm. The genetic algorithm has poor local search capabilities, but has a strong ability to grasp the overall search process; while the simulated annealing algorithm has strong local search capabilities and can prevent the search process from falling into the local optimal solution, but the simulated annealing algorithm has The condition of the search space is not well understood, and it is inconvenient for the search process to enter the most promising search area, which makes the operation efficiency of the simulated annealing algorithm inefficient. However, if the genetic algorithm ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to a hybrid genetic simulated annealing algorithm for solving a job shop scheduling problem. The job shop scheduling problem is solved through the algorithm. The hybrid genetic simulated annealing algorithm aims to solve the problems that the genetic algorithm is poor in local searching capability but high in capability of overall search process grasping, the simulated annealing algorithm has high local searching capability but knows less of conditions of the entire searching space and is inconvenient for enabling the searching process to enter the most promising searching region and the like. The genetic algorithm and the simulated annealing algorithm are combined for adopting the long points while overcoming the weak points, and the hybrid GASA is proposed. According to the algorithm, genetic operations such as selection, crossing, variation and the like are performed on populations to generate new populations, then each individual in the new populations is subjected to the simulated annealing, results are taken as input of genetic operation in the next steep, and the whole operation process is subjected to repeated iteration till certain end condition is satisfied.

Description

Technical field [0001] The present invention relates to the field of manufacturing execution systems, and specifically is to solve the Job-Shop Scheduling Problem (Job-Shop Scheduling Problem) through algorithms. Background technique [0002] Job-Shop Scheduling Problem (Job-Shop Scheduling Problem) is one of the core and focus of manufacturing execution system research. Its research not only has great practical significance, but also has profound theoretical significance. Job shop scheduling problem, referred to as JSP, is to allocate product manufacturing resources reasonably according to product manufacturing requirements, and then achieve the purpose of rational use of product manufacturing resources and improve the economic benefits of enterprises. JSP is a coexistent problem in the product manufacturing industry. It is closely related to the factory management and product manufacturing levels in CIMS. It is an important subject in the CIMS field. JSP is a typical NP-hard p...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06Q10/04G06N3/12
CPCY02P90/30G06Q10/04G06N3/126
Inventor 马跃于东胡毅周鑫李霄
Owner 中国科学院沈阳计算技术研究所有限公司
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com