# Lisa's post on evolution -Reply

Paul Cockshott wpc at clyder.gn.apc.org
Fri Aug 4 22:19:09 MDT 1995

```Jim:

What are 'constraint satisfaction problems'?

Paul
----
It is a term applied both to a class of abstract mathematics
and to a class of practical problems that this branch of
mathematics can be used to solve.

A practical example of a constraint satisfaction problem
is job scheduling in a machine shop. Suppose we have a
machine shop with 10 machine tools of 7 different types.
Suppose that we have 8 jobs to process, and we want
to obtain the most efficient use of our machine tools.
Let us further assume that there are constraints on
the way we use them. Each job requires operations by
one or more machine tools, applied in a specific order.
Beyond this there are constraints caused by the time
to move pieces between machines. In general the
constraints are set by the number of machines, the
number of different types of operations in each job,
the total time available etc.

If we can find some ordering in which the tasks are to
be performed such that everything is completed on
schedule then we are said to have satisfied the
constraints.

When the shop is working at low capacity, job scheduling
is easy, but when the shop is busy, meeting all of
the constraints can be very hard indeed. It has been
shown that the difficulty of meeting the constraints
is an example of phase change or in Engels terminology
quantity moving into quality.

--- from list marxism at lists.village.virginia.edu ---

------------------

```