Premium
A knowledge‐based approach for task allocation in heterogeneous distributed computer systems
Author(s) -
Lee Anita,
Cheng Chun Hung
Publication year - 1995
Publication title -
expert systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.365
H-Index - 38
eISSN - 1468-0394
pISSN - 0266-4720
DOI - 10.1111/j.1468-0394.1995.tb00267.x
Subject(s) - computer science , scheduling (production processes) , lisp , computational complexity theory , task (project management) , common lisp , knowledge base , distributed computing , limit (mathematics) , artificial intelligence , mathematical optimization , algorithm , mathematical analysis , mathematics , management , economics , programming language
This paper presents a knowledge‐based system for task allocation in a network of processors. Since the problem is NP‐complete, optimisation techniques are computationally prohibitive and impractical. Our approach reduces computational burden by using (1) a two‐level hierarchical scheduling model to alleviate the problem complexity, and (2) a search strategy that uses knowledge from the knowledge base to limit the search space to a manageable size. The major goal of our approach is to generate good but not necessarily optimal solutions quickly. The system is implemented on a Sun SPARCstation 1 + using Common Lisp. Our computational experience in using this system for task allocation indicates that the two‐level hierarchical approach generates better schedules in shorter computational time than a non‐hierarchical approach.