Flowshop

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. 

Many chemical batch production facilities are dedicated to producing a set of products that require for their manufacturing a common set of unit operations. The unit operations are performed in the same sequence for each product. This type of production problem is often solved by configuring the available equipment so that each unit operation is carried out by a fixed set of equipment items that are disjoint from those used in any other operation. If one unit is assigned to each step, this is called a flowshop (Baker, 1974). 

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... 

With these simplifications, we can now formulate the mathematical model, which describes the flowshop. Let... 

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. 

To solve the flowshop scheduling problem, or indeed most problems with significant discrete structure, we are forced to adopt some form of... 

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. 

The next section will highlight these features of the branch-and-bound framework, within the context of the flowshop scheduling problem. Then we will give an abstract description of the algorithm, followed by the... 

The first step in solving a combinatorial optimization problem is to model the solution space itself. Such a model should be declarative in character, if it is to be independent of the characteristics of the specific algorithm that will be used to find the solution within the solution space. The model we have adopted for the scheduling of flowshop operations is the discrete decision process (DDP) introduced originally by Karp and Held (1967). As defined by Ibaraki (1978) a DDP, Y, is a triple (.S,S,/) with its elements defined as follows ... 

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... 

In the flowshop example, the subsets of the solution space consists of subsets of feasible schedules. We can organize these subsets in a variety of ways for example, fixing any one position of the N available positions in the schedule to be a particular batch creates N subsets of size iN - 1) . Subsequently, as we fix more and more of the positions, the sets will include fewer and fewer possibilities, until all the positions are fixed, and we have a single element in the set corresponding to a single, feasible schedule. 

The intuitive notion behind a dominance condition, D, is that by comparing certain properties of partial solutions x and y, we will be able to determine that for every solution to the problem y(y) we will be able to find a solution to Yix) which has a better objective function value (Ibaraki, 1977). In the flowshop scheduling problem several dominance conditions, sometimes called elimination criteria, have been developed (Baker, 1975 Szwarc, 1971). We will state only the simplest ... 

In the case of the flowshop example, we have the following equivalence condition... 

In addition to having to assign state variables to the strings of the DDF, we also have to assign properties to the alphabet symbols. In our flowshop example, the alphabet symbols can be interpreted as batches to be executed with a series of processing times. Thus, if we use the notation, (jc), to denote the state of partial solution, x, then... 

The purpose of defining these classes of constraints and variables is that this will enable us to conveniently express general notions of equivalence and dominance, without explicit reference to the flowshop domain, but at a more abstract level. 

To define the lower-bound function for flowshop scheduling, we will use the lower-bounding schemes proposed in Lagweg et al. (1978). The lower bound schemes are organized into a hierarchy that reflects the strength o] the lower-bounding scheme. 

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. 

Consider the flowshop in Fig. 2. The unit operations being performed are mixing, reaction, distillation, cooling, and filtration. We have made the following assumptions about the way the flowshop operates ... 

Fig. 2. Example configuration of unit operations in flowshop production.

The last step in the preceding argument, the use of our knowledge about flowshop scheduling, turns what had been a mainly syntactic criterion over the tree structure of the example, into a criterion based on state variables of (jc, y). The state variable values, the completion times of the various flowshop machines, are accessible before the subtrees beneath jc and y have been generated. Indeed, they determine the relationships between the respective elements of the subtrees (jcm, yu). If we can formalize the process of showing that the pair (jc, y) identified with our syntactic criterion, satisfies the eonditions for equivalence or dominance, wc will in the process have generated a new equivalence rule. 

Thus, the next step in the problem-solving analysis is to use information about the domain of the problem, in this case flowshop scheduling, and information about dominance and equivalence conditions that is pertinent to the overall problem formulation, in this case as a state space, to convert the experience into a form that can be used in the future problem-solving activity. 

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. 

In these cases there is no well defined notion of a looser constraint, the choice is then either to force those variables to be equal in x and y, or to find some path from their value to a constraint on another inter- or intrasituational variable and thus be able to show that their values in jc, y should obey some ordering based on these other constraints. This topic is the subject of current research, but is not limiting in the flowshop example, since no such constraints exist. Lastly, it is not enough to assert conditions on the state variables in x and y, since we have made no reference to the discrete space of alternatives that the two solutions admit. Our definition of equivalence and dominance constrains us to have the same set of possible completions. For equivalence relationships the previous statement requires that the partial solutions, x and y, contain the same set of alphabet symbols, and for dominance relations the symbols of JC have to be equal to, or a subset of those of y. Thus our sufficient theory can be informally stated as follows ... 

This section details the different aspects of the representation we have adopted to describe the problem solutions and the new control knowledge generated by the learning mechanism. Throughout the section we will continue to use the flowshop scheduling problem as an illustration. The section starts by discussing the motives for selecting the horn clause form of first-order predicate calculus, and then proceeds to show how the representation supports both the synthesis of problem solutions and their analysis. The section concludes with a description of how the sufficient... 

In Section II, we presented the computational model involved in branching from a node, cr, to a node aa,. In this model, it was necessary to interpret the alphabet symbol a, and ascribe it to a set of properties. In the same way, we have to interpret o- as a state of the flowshop, and for convenience, we assigned a set of state variables to tr that facilitated the calculation of the lower-bound value and any existing dominance or equivalence conditions. Thus, we must be able to manipulate the variable values associated with state and alphabet symbols. To do this, we can use the distinguishing feature of first-order predicates, i.e., the ability to parameterize over their arguments. We can use two place predicates, or binary predicates, where the first place introduces a variable to hold the value of the property and the second holds the element of the language, or the string of which we require the value. Thus, if we want to extract the lower bound of a state o-, we can use the predicate Lower-bound Ig [cr]) to bind Ig to the value of the lower bound of cr. This idea extends easily to properties, which are indexed by more than just the state itself, for example, unit-completion-times, v, which are functions of both the state and a unit... 

In the flowshop example, when we branch, we have to calculate the start-times of the new batch to be scheduled. Here are the rules that can accomplish this ... 

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. 

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. 

To support the analysis of the solutions we will introduce several new predicate types. We have already described the basic state model in Section II, E. Explicitly manipulating parts of this model is an important component of the reasoning required to derive new control conditions. We will introduce the predicate, form , which will enable us to analyze the form of the state update rules, or constraints between variables. Thus, for our flowshop example we have two basic types of constraints ... 

---