## 2 Materials and Methods
### Combinatorial Optimization Techniques
#### 2.3.1 Enumeration and Branch-and-Bound Approach  
Enumerating the full set of combinations for all competing operations is an exercise of exponential complexity [9]. However, as we have mentioned above the number of combinations in constraint (3) is restricted due to other constraints (2) and (1). The precedence graph constraint (1) excludes the permutations of competing operations within one order making the linear problem setting non-feasible for corresponding combinations. The way we enumerate the combinations and choose the starting point of enumeration also influences the flow of computations significantly. The common approach to reducing the number of iterations in enumeration is to detect the forbidden areas where the optimal solution problem does not exist (e.g., the constraints form a non-feasible problem or multiple solutions exist). The most widely spread variant of the technique described is branch-and-bound method [10] and its different variations. Let us choose the strategy of enumerating permutations of operations in such a way that it explicitly and easily affords to apply branch-and-bound method. The starting point of the enumeration will be the most obvious positioning of orders in a row as shown in Figure 2. We start from the point where the problem is guaranteed to be solvable--when all orders are planned in a row--which means that the first operation of the next order starts only after the last operation of the previous order is finished. If the preceding graph is correct and the resources are enough that means the single order can be placed on the resources that are totally free (the problem is solvable--we do not consider the unpractical case when the graph and/or resources are not enough to fulfill a single order). Infeasibility here can be reached only in the case when we start mixing the orders. This guarantees that the linear programming problem is solvable, however, this combination is far from being optimal/reasonable. Figure 2: Initial state: all orders are placed in a row. The enumeration is organized by shifting the operations of the last order to the left in such a way that they trade their places with previous competing operations of preceding orders (see Figure 3). As soon as the operation reaches its leftmost feasible position and the current combination corresponds to a linear programming problem with no solution we roll back to the previous combination, stop shifting operations of the last order and switch to the operations of the previous order. After the enumeration for orders on the current resource is over, we proceed the same iterations with the next resource. The formal presentation of the designed branch-and-bound algorithm is described by Procedure 1. **Procedure 1: branch-and-bound**  
1. **Find the initial solution** of the **LP problem** (1)-(3) for the combination \(c_{k}\in\{0,1\},\ k=1,\ldots,K\) that corresponds to the case when all orders are in a row (first operation of the following order starts only after the last operation of preceding order is completed). 2. **Remember** the solution and keep the value of objective function \(\Phi\) as temporarily best result \(Opt=\Phi\). 3. **Select the last** order \(f=|F|\). 4. **Select the resource \(r=|R|\)** that is used by last operation \(i=|J|\) of the precedence graph \(G\) of the manufacturing process. 5. **The branch \(<i,r,f>\)** is now formulated. 6. **Condition**: Does the selected resource \(r\) have more than one operation in the manufacturing procedure that allocates it? 6.1. **If** yes **then**  
**Begin** evaluating branch \(<i,r,f>\)  
**Shift** the operation \(i\) one competing position to the left  
**Find** the solution of the **LP problem** (1)-(3) for current combination and calculate the objective function \(\Phi\)  
**Condition**: is the solution feasible? **If** feasible **then**  
**Condition**: Is the objective function value \(\Phi\) better than temporarily best result \(Opt\)? **If** yes **then**  
**save current solution** as the new best result \(Opt=\Phi\).