Parallel logic programming for problem solving

We present a new model for parallel evaluation of logic programs. This mode l can exploit the main sources of parallelism that the language of logic ex presses: Independent AND parallelism and OR parallelism, together with a se condary source emerging as a consequence of the Independent AND Parallelism : the producer/consumer parallelism. The efficiency is derived from the use of ordered structures for managing the information generated throughout th e search process. The model is suitable for evaluating programs with a high degree of non-determinism because it never generates two processes for sol ving the same subgoal and hence it can exploit the same real parallelism ge nerating a lower number of processes than other models. As an application e xample, we consider the Job Shop Scheduling problem. We report experimental results showing that logic programs can be designed that exhibit paralleli sm, and that the use of heuristic information translates into speedup in ob taining answers.