Knowledge base planning

1. Knowledge base system description

Knowledge-based systems are systems based on the methods and techniques of Artificial Intelligence. Their core components are the knowledge base and the inference mechanisms. The holonic architecture who runs the system is composed of an algorithm base, which schedules the operation with respect to an heuristic algorithm, and an inference engine which takes over the scheduling when the operating resources(eg: robots) are un available.
The KBSS(Knowledge Base System for Scheduling)has the following features:

1. It uses knowledge elicted from different sources including human experts, a designer, and the literature.
2. It is based on the tandem architecture which integrates the optimization and knowledge-based approach.
3. It has been developed for an automated manufacturing environment. The job scheduling problem which is beeing solved can be clasified as a job shop problem with a number of different resources, such as machines, tools, fixtures, grippers, material handling carriers and constraints such as precedences, due dates and so on.

If the heuristic algorithm is activated, it attempts to find a sollution, but if it has trouble it relinquishes control to the production rules, which seek a solution through interfacing.

Structure of the KBSS

2. Algoritm base

Based on tested performances (Kusiak, 1990), six priority scheduling rules have been incorporated into the heuristic assembly scheduling algorithm (SA):

• Initialize:
• Set current time t=0 and resource status sr_lq=1, q∈Q_l , l∈L
• Set the four sets S₀ - S₃ respectively of non executable (empty), executable, non schedulable (empty) and schedulable operations  os_i = 0, ...,3
• From the set of schedulable operations, select an operation o_α based on the priority rules below:
• PR1: ns_αp = max{ns_ip}, p∈P, i∈S₃
• PR2: no_αp = min{no_ip}, p∈P, i∈S₃
• PR3: ni_αp = max{ni_ip}, p∈P, i∈S₃
• PR4: nu_αp = max{nu_ip}, p∈P, i∈S₃
• PR5: t_i = min{t_i⁽⁰⁾}, i∈S₃
• PR6: select an arbitrary operation o_α (break a tie arbitrarily)
• Schedule the operation selected in step 2:
• Operation status os_α=2 for o_α selected
• Operation status os_i=0 for all the unprocessed operations of the assembly corresponding to o_α.Delete operation o_α from s₃. If S₃∪S₃ = ∅, stop (there are no unprocessed operations); otherwise set:

• Remaining processing time rt_α = t_α⁽⁰⁾
• Resource status sr_lq=0 for r_lq∈R_α⁽⁰⁾, q∈Q_l, l∈L.Update S₃ and S₂. If S₃ ≠ ∅, go to step 2. If S₃ = ∅ and there are available resources, go to step 4; otherwise, update set S₆, enter the inference engine (rules ALT_PLAN generate an alternate OH triplet), and return.

• Calculate the completion time of each operation scheduled but not completed at the current time. Set the current time equal to the completion time of the operation with the last remaining time. Add this operation (or operations in case of a tie) to the set of completed operations:  

  • f_i = rt_i + t, i∈S₄
  • 
  • Set operation status  and delete  from S₄.
  • Set resource status    and remaining time rt_i = f_i - t, i∈S₄.

Update S₃ and S₂.

• If S₃∪S₂ = ∅(if there are no unprocessed operations), stop; otherwise, go to step 6.  
• If S₃ ≠ ∅, go to step 2. If S₃ = ∅ and there are available resources go to step 4; otherwise update set S₆, enter the inference engine for alternate resource allocation, and return.

3. Inference engine

The inference engine in the KBSS controls the procedure of triggering rules in the knowledge base and the procedure of schedule generation of an algorithm. One of the greatest advantages of the tandem system architecture is the simplicity of its inference engine. The inference engine in KBSS employs a forward chaining control strategy. In a given class of rules it attempts to fire all the rules that are related to the context considered. If a rule is triggered, i.e., the conditions are true, then the actions of the rule triggered are carried out. Some rules stop the search of the inference engine and switch the control process to the algorithm.
In the process of schedule generation, an operation might not be processed according to the basic process plan due to the unavailability of the resources specified in the basic process plan. The heuristic scheduling presented in this section exits from step 3 and step 6 and enters the inference engine of the knowledge-based system. As mentioned above, the inference engine in the GAS triggers in steps 3 and 6 of the algorithm a rule in one of the following rule sets:

• SEL_ALG: selection of the appropriate SA
• ALT_PLAN: starts and controls the mechanism of selecting alternative OHs for a job, triggered by resource unavailability
• VAL_RES: evaluates the computed assembly plans and decides upon rescheduling to improve the global quality of solution at batch level. The makespan performance function is used for this: C_max =max{C_i}, with C_i = completion time of operation o_i∈OA_p, 1≤i≤f_p, p∈P.

Last updated 29.05.2008