METHOD AND DEVICE FOR SCHEDULING JOB SHOP

摘要

PURPOSE: To quickly obtain a quasi optimum solution capable of minimizing total working time by generating a new individual by genetic algorithm using critical block neighborhood for two individuals selected from an individual group and searching local neighborhoold. CONSTITUTION: When an initial individual group generating means 102 generates the initial value of a group being the set of individuals to be used for genetic algorithm, a two-individual selecting means 103 selects two individuals by biasing so as to easily select individuals more excellent than the initial individual group or an individual group on the way of processing. A multi-stage crossing means 104 applies multi-stage crossing to the two selected individuals to generate a new individual. A local neighborhood searching means 104 calculates critical block neighborhood for the individual group generated by the means 102 and the individual generated by the means 104 and substitutes the most excellent individual in the critical block neighborhood for the original individual. Consequently an excellent solution for a large-scale problem can be quickly found out.