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

Der Chiang Li, Han Kun Lin, Kuan Yueh Torng

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)404-412
Number of pages9
JournalEuropean Journal of Operational Research
Volume88
Issue number2
DOIs
Publication statusPublished - 1996 Jan 20

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'A strategy for evolution of algorithms to increase the computational effectiveness of NP-hard scheduling problems'. Together they form a unique fingerprint.

Cite this