Flowshop problem example

Representation. The solution space is composed of discrete combinatorial alternatives of batch production schedules. For example, in the permutation flowshop problem, where the batches are assumed to be executed in the same order on each unit, there are A number of solutions, where N is the number of batches. We must find a way to compactly represent this solution space, in such a way that significant portions of the space can be characterized with respect to our objective as either poor or good without explicitly enumerating them. 

To make the ideas of this section more concrete we will use a specific example of a flowshop problem. The problem is a small one, only five batches will be considered, since this enables us to examine the enumeration tree by hand. 

This completes the representation of the sufficient theory required for the flowshop example. It consists of about 10 different predicates listed in Table II and configured in four different implications (rules). These predicates have an intuitive appeal, and are not complex to evaluate, thus the sufficient theory could be thought of as being simple. The theory is capable of deriving the equivalence-dominance condition in flowshop problem. It is, however, expressed in terms that could be applied to any problem with that type of constraint. Thus it has generality, and since we can add new implications to deal with new constraint types, it has modularity. 

The specific explanation structure for the flowshop problem is given in Fig. 10. In the example we have assumed that the sufficient condition is satisfied by having all the end-times of x less than or equal to those of y. Thus the proof begins by selecting the appropriate variable set, and proceeds to prove that each variable is more loosely constrained in x than in y. The intersituational variables in the flowshop problem are the start-times of the next state. 

The success of the algorithm relies on the GA processing many generations solutions can only evolve if evolution is possible. Excessively large populations are especially problematic if evaluation of the fitness function is computationally expensive as it is, for example, in the chemical flowshop problem (section 5.10) in which evaluating the total time required for all chemicals to be processed by the flowshop in a defined order may take far more time than the execution of all other parts of the GA combined. 

Before showing how the logical analysis will be carried out, it is useful to describe the sufficient theory we will be using for the specific flowshop example. This theory is not restricted to flowshop scheduling, but applies to many state-space problems. 

The type of theories we will be using to prove dominance and/or equivalence of solutions will not be specific to the particular problem domain, but will rely on more general features of the problem formulation. Thus, for our flowshop example, we will not rely on the fact that we are dealing with processing times, end-times, or start-times, to formulate the general theory. The general theory will be in terms of sufficient statements about the underlying mathematical relationships, as described in Section III. 

The traveling gourmet problem is in itself not of much interest to physical and life scientists (or, more accurately, is probably of acute interest to many of us, but well beyond our means to investigate in any practical way), but problems that bear a formal resemblance to this problem do arise in science. The chemical flowshop is an example (Figure 5.29). ... 

---