Scheduling in Manufacturing Systems: The Ant Colony Approach

Read this section. It makes the case that production systems are similar to ant colonies because ants continue to learn from one another and find ways to become more efficient at their task at hand. As you read, pay special attention to some of the scheduling problems.

3. Adaptation of neural method to solve the problems of scheduling

3.1. Neural network model

The starting point for defining the neural network model for solving the problems of task scheduling and resource allocation are the assumptions for the constraint satisfaction problem (CSP). CSP is the optimization problem which contains a certain set of variables, sets of their possible values, and constraints forced on the values of these variables. On the basis of this problem assumption a network model of the following features is suggested:

  • A neural network consists of components; each of them corresponds to another variable.
  • Each component contains such number of neurons which equals the number of possible values of each variable.
  • Assigning a specified value to a variable is the process of switching on a relevant neuron (neurons) and switching off the remaining ones in the component corresponding to this variable.
  • Switching on a neuron means assigning the value "1" to its output.
  • Switching off a neuron means assigning the "0" to its output.
  • Constraints to the network are introduced by adding a negative weight connection between neurons (‘-1’), symbolizing the variable values that cannot occur simultaneously.
  • In the network there are additional neurons "the ones" that are switched on.

Each neuron has its own table of connections and each connection contains its weight and the indicator for the connected neuron. A characteristic feature of the network is the diversity of connections between neurons, but these never applied to all neurons. It is a consequence of the fact that connections between neurons exist only when some constraints are imposed. The constraints existing in the discussed network model may be of the following types: resources, time, order.

The method of constraints implementation shall be discussed upon examples.

Example 1:

Such net (Fig. 1.) blocks solution, in which Z1 = 1 as well as Z2 = 2 or Z3 = 3 as well as Z4 = 2.

Example 2:

Let us have two operations with unit execution times. The operation Z1 arrives at the system in time t = 1 and it is to be executed before the expiry of time t = 4. The operation Z2 arrives in time t = 1 and may be executed after the completion of operation Z1. A fragment of the net for his case including all the connections is shown by Fig. 2.

Neuron „one" (‘1’) – a special neuron switched on permanently – is responsible for time constraints. Introducing connections between such neuron and the relevant network neurons excludes a possibility of switching them on when searching for the solution. Task Z 1 cannot be scheduled in moment 0 and moment 4, which corresponds to the assumption that this task arrives at the system at moment 1 and must be performed before moment 4. Analogical process applies to operation Z 2 . The sequence constraints are executed by the connections between the network neurons. The figure shows (with dotted line) all the connections making the performance of task Z 2 before task Z 1 impossible.


Figure 1.

The example 1 of constraints.


Figure 2.

The example 2 of constraints.