Flowshop problem

These four goals are addressed sequentially in the next four sections. The flowshop problem will be used as an illustration throughout, because of its practical relevance, difficulty of solution, and yet relative simplicity of its mathematical formulation. 

The flowshop problem has been widely studied in the fields of both operations research (Lagweg et al., 1978 Baker, 1975) and chemical engineering (Rajagopalan and Karimi, 1989 Wiede and Reklaitis, 1987). Since the purpose of this chapter is to illustrate a novel technique to synthesize new control knowledge for branch-and-bound algorithms, we... 

To generate a specific instance of a flowshop problem we will assume that the plant produces a fixed set of products. In addition to allowing the type of product to vary, we will also allow the size of the batch to be one of a fixed set of sizes. Further details of the formulation are given in Section III, A. 

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. 

For the flowshop problem, one choice of X is an alphabet with as many symbols as the number of distinct batches to be scheduled, i.e., one symbol for each batch, then, each discrete schedule of batches is represented by a... 

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. 

We can thus think of our predicates as falling into two classes (1) the formulation-specific, and (2) the problem-specific. The implications fall into three classes (1) those that interconnect the general concepts of the formulation, (2) those that connect the general concepts of the formulation to the specific details of the problem, and finally (3) those that enable reasoning about the specific details of the problem. We have already described the predicates necessary for reasoning within the flowshop problem thus the rest of this section will focus on the general predicates and their interconnection with the specific problem details. 

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. 

The flowshop problem is the simplest structure that resembles a simple supply chain structure. The problem is extensively studied in the literature with various models of different types and efficiencies developed and examined for different objective functions and constraints. Integer programming was one of the first models developed for optimizing flow shops. 

---