DESIGN OF EXPERT SYSTEMS FOR JOB SHOP SCHEDULING: A CONCEPTUAL FRAMEWORK

This paper investigates the currertt expert scheduling approaches to determine the research areas for the encouragement of the use of expert systems in production scheduling. A framevvork is presented to clarify the state-of-the-art for the expert scheduling systems. The rule-based representatioıı of the knowledge base, Üıe rule generation scheme for it, and fovvard backvvard chaining procedures for the inference engine are explaİned to shovv hovv an expert system functions in ajob-shop environment.Scheduling of n jobs through m machines results in (n!) possible schedules among which exİst one or more optimal schedules according to a performance criterion employed (French, 1982). These optimal schedules can theoretically be found in a finite number of computations indicating direct search by complete enumeration vvhich is impractical even vvith the use o f computers. For example, a simple problem having 5 jobs and 5 machines requvres (5!) possible alternatives to be evaluated. İn addition, Rinnooy Kan (1976) reports that most o f the scheduling problems are NP-Hard İncluding n-job m-machine problems. These problems have exponential time complexity function meaning that the maximum number of operations required to solve the problem exhibit an exponential behaviour. For this reason, it is impractical to solve these problems by not only complete enumeration methods but also implicit enumeration methods such as branch and bound or dynamic programming reducing the number o f alternatives to be searched. Due to the fact that realistic size and complexity o f scheduling problems have caused the efforts to fai! in finding an optimal solution baved on traditional optimisation techniques, research in schduling theory has been directed tovvards using heuritic algorithms vvhich produce near optimal schedules and reduce computational time, because they avoid searhing for ali alternatives by applying priority rules for j o b assignment. In these approaches, priority rules are compared vvith each other under a performance criterion to measure the effectiveness of schedules in meeting a specified scheduling objective. Hovvever, these appoaches usually aim at optimizing a single goal function vvith a single parameter and find it diffîcult to achieve multiple objectives (Charalambous and Hindi, 1991, Noronho and Sarma, 1991). In addition, scheduling environment is generalfy surrounded by accumulated 'knovvledge' that vvill affect scheduling decisions as to vvhich j ob should be selected as the next action according to the current state o f system(Cheng, 1985, Chovv and Huang, 1990). Traditional optimisation tecniques and heuristic approaches deal vvith only a portion o f knovvledge accumulated and cannot respond to the actual state o f system İn dynamic schduling environment. Construction o f a schedule based on ali the relevant scheduling information can be achieved by the use of expert systems infervıng solutions from structured knovvledge.