TY - JOUR

T1 - A strategy for evolution of algorithms to increase the computational effectiveness of NP-hard scheduling problems

AU - Li, Der Chiang

AU - Lin, Han Kun

AU - Torng, Kuan Yueh

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 1996/1/20

Y1 - 1996/1/20

N2 - We explored a method of applying techniques of inductive learning from artificial intelligence to partition a full problem space into smaller exclusive problem spaces, and developed an evolving algorithm for each problem space. In this approach we first create attributes to define a problem, and use them to cluster the problem space into classes. To each class of problems, a 'suitable' evolved algorithm is developed to apply. By suitable here we mean that its level of complexity fits the level of difficulty of a problem of a particular type. The purpose is to increase efficiency and effectiveness. In this work we selected a developed algorithm as the parent algorithm to generate an evolved algorithm. The methods used include the technique of maximum decreasing of impurity to construct a classification tree that provides systematic class descriptions. A problem of sequencing jobs of unequal importance in a set on a single processor in order to minimize total tardiness is provided to illustrate the problem-solving procedures.

AB - We explored a method of applying techniques of inductive learning from artificial intelligence to partition a full problem space into smaller exclusive problem spaces, and developed an evolving algorithm for each problem space. In this approach we first create attributes to define a problem, and use them to cluster the problem space into classes. To each class of problems, a 'suitable' evolved algorithm is developed to apply. By suitable here we mean that its level of complexity fits the level of difficulty of a problem of a particular type. The purpose is to increase efficiency and effectiveness. In this work we selected a developed algorithm as the parent algorithm to generate an evolved algorithm. The methods used include the technique of maximum decreasing of impurity to construct a classification tree that provides systematic class descriptions. A problem of sequencing jobs of unequal importance in a set on a single processor in order to minimize total tardiness is provided to illustrate the problem-solving procedures.

UR - http://www.scopus.com/inward/record.url?scp=0029755591&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029755591&partnerID=8YFLogxK

U2 - 10.1016/0377-2217(94)00196-0

DO - 10.1016/0377-2217(94)00196-0

M3 - Article

AN - SCOPUS:0029755591

VL - 88

SP - 404

EP - 412

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -