Efficient method for designing slabs for production from an order book

An efficient computer implemented method is used to design slabs for production from an order book. This method minimizes the number of slabs designed to fulfill an order book. This method is based on a heuristic algorithm which is a variant of the greedy approach for the set covering method. The variations are novel in three ways. First, designing slabs using the flexibility in the order size; second, using weight for choosing large slabs; and third, controlling the exponential nature of enumeration of the set of all subsets by constructing only the largest slab at each step.

DESCRIPTION
 BACKGROUND OF TIE INVENTION
 1. Field of the Invention
 The present invention generally relates to operations planning in a process
 industry and, more particularly, to a method of designing a set of slabs
 from target orders in a near-optimal manner while satisfying design
 restrictions.
 2. Background Description
 General background information may be had by reference to the following two
 books:
 1. Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993), Network Flows,
 Prentice Hall, N.J.
 2. Horowitz, E. and Sahni, S. (1978), Fundamentals of Data Structures,
 Computer Science Press, Inc.
 Operations planning in a process industry typically begins with a order
 book which contains a list of orders that need to be satisfied. The
 initial two steps in an operations planning exercise involves (1) first
 trying to satisfy orders from the order book using leftover stock from the
 inventory and (2) subsequently designing productions units for manufacture
 from the remaining orders. Two important characteristics of a process
 industry are that the products are all manufactured based on the orders
 instead of being based on a forecast of the expected demand (as in retail
 or semiconductor manufacturing) and, as a consequence, the inventory is
 merely the stock of previously produced units which for reasons of quality
 could not be shipped to the customer.
 The subject invention is a novel and fast computer-implemented method for
 the second of these problems from an optimization perspective. The second
 problem, i.e., designing production units, involves using the order book
 to design the size and number of production units that need to be
 manufactured. The goal of this design is to minimize the number of units
 that need to be manufactured, which for a given order book is equivalent
 to maximizing the average size of the production unit. This problem has a
 strong flavor of a grouping exercise where different orders are grouped
 together to form a slab (the manufacturing unit in a steel industry)--we
 call this the slab design problem. There are, once again, several
 constraints regarding which orders can be grouped together, based on grade
 and surface quality and weight considerations, which give rise to
 integrality constraints. The maximum allowable size of a slab for a
 potential group of orders is constrained based on manufacturing
 considerations. Additionally, each designed slab needs to be of a minimum
 size, and any group of orders weighing less than this minimum introduces a
 designed slab with some partial surplus. The partial surplus is clearly
 undesirable and needs to be minimized. This problem can be formulated as a
 variation of the variable size bin packaging problem.
 Characteristics of Orders and Slabs
 In application Ser. No. 09/047,275, we introduced the inventory matching
 problem in terms of an order book which contains a list of orders and
 their specifications, and an inventory of existing slabs. Here, we provide
 a description of the order book which is similar to the one described in
 Ser. No. 09/047,275. We will also describe constraints that arise in
 designing virtual slabs. The specification of orders and the use of
 inventory (or slabs) has some unique attributes which are important in
 understanding the integer formulations that arise while modeling these
 problems.
 The order book contains a list of orders from various customers. Each order
 has a target weight (O.sub.t) that needs to be delivered. However, there
 are allowances with respect to this target weight which specify the
 minimum (O.sub.min) and maximum weight (O.sub.max) that are accepted at
 delivery. Over and above the total weight (per order) that needs to be
 delivered, there are additional restrictions regarding the size and number
 of units into which this order can be factorized at delivery. For example,
 with each order is associated a range for the weight of units which are
 delivered. We call the units to be delivered "Deliverable Production
 Units" or DPUs. Let us assume that the minimum weight for the deliverable
 production unit is DPU.sub.min and the maximum is DPU.sub.max. Then, for
 each order we need to deliver an integral number of deliverable production
 units (DPU.sub.mumber) of size in the interval [DPU.sub.min, DPU.sub.max ]
 so that the total order weight delivered is in the range [O.sub.min,
 O.sub.max ]. In order to fulfill an order, we need to choose a size for
 the deliverable production unit (DPU.sub.size) and the number of
 deliverable production units (DPU.sub.number) to be produced such that
 O.sub.min.ltoreq.DPU.sub.size.times.DPU.sub.number.ltoreq.O.sub.max
EQU DPU.sub.min.ltoreq.DPU.sub.size.ltoreq.DPU.sub.max
EQU DPU.sub.number.di-elect cons.{0,1,2, . . . } (1)
 Notice that the DPU.sub.number is a general integer variable. Additionally,
 the constraint represented by Equation (1) is a bilinear constraint.
 In addition to the weight requirements, each order has four other classes
 of attributes, wherein (1) the first pertains to the quality requirements
 such as grade, surface anti internal properties of the material to be
 delivered; (2) the second set are physical attributes such as the width
 and thickness of the product delivered; and (3) the third set of
 attributes refer to the finishing process that needs to be applied to the
 deliverable production units. For example, car manufacturers often require
 the steel sheets to be galvanized. Finally, (4), the fourth set of
 attributes provides the maximum and the minimum slab size that can be used
 to produce this order. At first this may appear undesirable since the
 decision of how to manufacture slabs to fulfill an order should, in
 general, be left to a manufacturer. It turns out, however, that the
 maximum and minimum allowable slab size is in fact determined by the
 manufacturer based on the current technological limitations of process
 technologies. For example, in a steel mill, all slabs need to be hot
 rolled to produce units of desired physical dimensions. However, based on
 the width and thickness required and the quality requirements, the maximum
 size of the slab that can be hot rolled is constrained, and this
 determines the allowable maximum allowable slab size. Similar
 considerations are used to prescribe the minimum allowable slab size.
 For the slab design problem, the dimensions of the slab are unknown. The
 objective of the slab design problem is to optimally design the dimensions
 of the slab, subject to various processing constraints which are described
 below.
 The Slab Design Problem
 The slab design problem requires that we design a minimal number of slabs
 to satisfy the order book, subject to constraints on the maximum allowable
 size for each of the designed slabs. It is possible to group multiple
 orders on the same designed slab. There are two considerations that arise
 in grouping multiple orders to the same slab:
 1. Orders need to compatible in terms of physical dimensions in order to be
 grouped together. Orders that have similar width and thickness
 requirements can be packed together. As we had mentioned before for
 inventory matching according to Ser. No. 09/047,275, it is possible to
 alter the thickness and width (within a range) by rolling. Therefore,
 orders with thickness and width close to each other can be grouped on the
 same slab.
 2. The second set of grouping constraints arise from process considerations
 in the hot/cold mill and the finishing line. These constraints can be
 represented using color constraints. More explicitly, we can associate
 with each order a color which represents the finishing operations that are
 required. As before, we can specify color constraints which limit the
 number of colors that can be grouped on each designed slab.
 Orders that are grouped on the same slab might have different maximum
 allowable slab weights. However, when grouped as such, the allowable
 maximum slab weight is actually determined by the largest of all the
 allowable slab weights.
 We therefore have a representation of the slab design problem in terms of
 multiple groups of orders, where each group can be packed on the same slab
 of a maximum allowable size. The maximum allowable slab size for each
 group can be different. Consider the (unlikely) case where all orders can
 be grouped together and we derive a corresponding allowable slab size.
 Ignoring the color constraints and decomposing all the orders into
 constituent production units, the slab design problem (of minimizing the
 number of slabs used to fulfill the order book) is exactly the same as a
 bin packing problem. We can now describe two variations to the simple bin
 packing problem that arise from our considerations:
 1. In the first variation, we continue to assume a single group with a
 single allowable slab; however, we invoke the color constraints. This
 leads to a bin packing problem with colors constraints.
 2. In the second variation, we relax our earlier assumption of having a
 single group. In place of that assumption we allow multiple groups with
 multiple corresponding allowable slab weights. We can represent this
 problem with a bipartite graph with a node for each order and a
 corresponding slab node for each group that multiple orders can be packed
 into. We use arcs from orders to slabs to indicate the assignment
 restrictions. This is a variable bin packing problem with color
 constraints. Note that if the bipartite graph is complete, then the
 problem degenerates to a single bin packing problem with the bin
 representing the slab of the largest allowable weight. However, with
 sparse assignment restrictions, the variable bin packing problem with
 color constraints constitutes an interesting variation of the original
 problem.
 Notice that the variable size bin packing problem with color constraints is
 still an incomplete representation of the slab design problem where we
 have assumed the deliverable production unit size to decompose the orders.
 Simplified Problem Formulation
 TABLE 1
 List of Notations
 N= Total number of orders.
 M= Total number of slabs.
 N.sub.i = Set of slabs incident to order i.
 N.sub.j = Set of orders incident to slab j.
 P.sub.i = Maximum number of production units of order i
 required.
 L.sub.i = Maximum number of units of slab j required.
 O.sub.jl.sup.ip = The weight of the p.sup.th DPU for order i obtained from
 the l.sup.th unit of slab j.
 z.sub.jl.sup.ip = 1 if the p.sup.th DPU for order i is obtained from
 the l.sup.th unit of slab j; 0 otherwise.
 C.sub.jl = Set of colors incident on the l.sup.th unit of slab j.
 y.sub.jl.sup.c = 1 if an order(s) ofcolor c obtains material from
 the l.sup.th unit of slab j; 0 otherwise.
 W.sub.jl = Weight of the l.sup.th unit of slab j.
 PU.sub.min.sup.i,DPU.sub.ma.sup.i = Minimum and maximum production unit
 sizes,
 respectively, for order i.
 O.sub.min.sup.i,O.sub.max.sup.i = Minimum and maximum order weight,
 respectively,
 for order i.
 s.sub.jl = 1 if the l.sup.th unit of slab j is used to supply some
 order(s); 0 otherwise.
 Problem Constraints
 ##EQU1##
 Problem Objectives
 Minimize number of slabs:
 ##EQU2##
 Minimize surplus weight: A surplus is accounted for the l.sup.th slab of
 slab j only if we use the slab.
 ##EQU3##
 Description of the Prior Art
 According to one aspect of the prior art, a search for a solution to the
 slab design problem is done in the space of orders, creating a solution by
 selecting one order at a time. This search can be either a depth-first,
 breadth-first or a best-first. Therefore, the search progresses
 iteratively, expanding one node of assigning part of an order to an
 existing slab or creating a new slab at a time and then backtracking to
 cover all possibilities. Clearly, this is a naive approach to the search,
 as the computational burden relates exponentially to the problem size.
 Techniques for pruning the search tree can alleviate this problem, provided
 we have good measures for pruning the search tree. The slab design problem
 can be formulated as an integer programming problem, as shown in the
 previous pages. A branch-and-bound technique is commonly used to solve
 such integer problems by solving a sequence of relaxed solution linear
 problems which are derived from the original problem.
 The branching splits a linear program into two subproblems and bounding
 computes the upper bound for the objective function for each subproblem.
 If the upper bound for the subproblem is no better than the best integer
 solution found up to that point, then the entire subproblem is pruned from
 the search space. A branch-and-bound process can be represented by a tree,
 where every node in the tree represents a subproblem. At each stage of the
 branch-and-bound search, one active node is selected and the associated
 relaxed problem is solved. Depending on the solution one of the following
 three actions is taken: (1) if the relaxed problem has a solution that is
 worse than the current best feasible objective value, prune the node
 (pruning); (2) update the integer solution if the solution feasible and
 better than the current best feasible objective value (updating); and (3)
 branch on some edge in the bipartite graph if the relaxed solution is not
 feasible for the integer program and if its objective value is better than
 the current best feasible solution (branching).
 Shortcomings of Traditional Search Based Approaches
 The several shortcomings of this approach for the slab design problem are:
 1. Because of its incremental approach to searching the space of matches,
 the speed of this algorithm depends critically on how close the actual
 optimal solution is to the relaxed solution generated by the linear
 program. For the slab design problem, both the integrality constraints of
 the DPU.sub.number and the color constraints render the relaxed problem to
 be a rather loose approximation to the actual problem. Hence, the
 branch-and-bound algorithm is very slow (a couple of hours) for even
 moderate sized problems. Such a response time is not acceptable in real
 world situations where the entire production plan (of which the slab
 design is a small part) has to be done within a couple of hours.
 2. Finally the branch-and-bound algorithm can optimize for only one
 objective at a time. The slab design problem has two major competing
 objectives: maximize designed slab size and minimize partial surplus. In
 order to solve for both these objectives, the algorithm has to be applied
 once for each objective by constraining the other objective at some
 desirable goal. This procedure is repeated until no further improvement in
 both objectives can be achieved. Since the algorithm response for each
 objective is slow, such a goal programming approach is too slow for real
 world applications.
 Accordingly, a main objective for the invention disclosed in this document
 is a fast heuristic algorithm which can solve the multi-objective slab
 design problem described before. An additional objective is a heuristic
 algorithm that can solve for multiple objectives simultaneously and
 generate multiple non-dominating solutions.
 SUMMARY OF THE INVENTION
 It is therefore an object of the present invention to provide a means to
 create multiple slabs from orders while satisfying all given restrictions
 and achieving near-optimization.
 According to the invention, there is provided an efficient method for
 designing slabs for production from an order book. This method minimizes
 the number of slabs designed to fulfill an order book. This method is
 based on a heuristic algorithm which is a novel variant of the greedy
 approach for the set covering method. The variations are novel in three
 ways. First is designing slabs using the flexibility in the order size.
 The second is using weight for choosing large slabs. The third is
 controlling the exponential nature of enumeration of the set of all
 possible slabs by constructing only a cleverly chosen subset of slabs at
 each step. This invention has been successfully applied to a set of large
 instances for a leading steel manufacturer and has proved its performance,
 efficiency and quality of solutions.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION
 Set Covering Approach for Slab Design
 The solution method for slab design is based on a set covering approach.
 The basic idea behind set covering is as follows: Given a base set S and a
 collection, F, of subsets of S, find a collection B* of subsets from F
 such that this collection covers all members of S and that the number of
 subsets in this collection is minimum.
 In more formal terms, consider a set of items denoted by S. We denote a
 collection of subsets of S by F={S.sub.1 S.sub.2, . . . , S.sub.n) where
 S.sub.i is a subset of S. The objective is to find a minimum collection
 B.OR right.F such that every element of S is covered.
 A greedy algorithm for set covering is to start with an empty set B and
 pick the largest subset S.sub.i from F. S.sub.i is added to the cover B
 and all items of S.sub.i are then removed from the target set S. This is
 repeated until the target set is empty. This algorithm finds an
 approximation to the optimal solution that is no worse than log(d), where
 d is the size of the largest subset. We have extended this greedy
 algorithm to solve the slab design problem. For the purposes of exposition
 we will first describe a simplified version of the problem. Let us fix the
 DPU.sub.size for each order so that an integral number of these DPUs can
 be used to satisfy this order. We split the max order weight,
 O.sub.max.sup.i into several production units of equal size, O.sup.i,
 where DPU.sub.min.sup.i.ltoreq.DPU.sub.max.sup.i.ltoreq.DPU.sub.max.sup.i.
 For example, consider an order i with O.sub.max.sup.i =30 tons,
 DPU.sub.min.sup.i =4 tons and DPU.sub.max.sup.i =6 tons. We split order i
 into six production units each having weight five tons. Note that if
 O.sub.max.sup.i can be split into an integer number of production unit
 sizes between DPU.sub.min.sup.i and DPU.sub.max.sup.i, then such a
 splitting is always possible. If O.sub.max.sup.i is in the "block-out"
 region (i.e., it cannot be split into an integer number of production unit
 sizes between DPU.sub.min.sup.i and DPU.sub.max.sup.i), we follow a
 conservative strategy to make
 ##EQU4##
 production units, each of size DPU.
 Now, the target set for slab design consists all the DPUs represented by
 the list where DPU.sub.i.sup.j represents the j.sup.th of DPU for order i
EQU ={DPU.sub.1.sup.1,DPU.sup.2.sup.1, . . . ,DPU.sub.1.sup.N.sup..sub.1
 .sub.1, DPU.sub.2.sup.1,DPU.sup.2.sub.2, . . . ,DPU.sub.2.sup.N.sup..sub.2
 , . . . ,DPU.sub.N.sup.1,DPU.sub.N.sup.2, . . .
 ,DPU.sub.N.sup.N.sup..sub.m }
 The collection of all subsets is
 ##EQU5##
 where W.sub.max.sup.i is the maximum allowable slab weight for order i.
 The objective is to find the minimum size set B* of F that covers P. Note
 that F could be exponentially large since the different combinations of
 DPUs can be used to fill slabs.
 Problem Representation
 The slab design problem consists of an order book with a list of orders
 O={O.sub.1,O.sub.2, . . . ,O.sub.n }. The objective is to fulfill the
 order book by designing the minimum number of slabs. This optimization is
 constrained by a set of compatibility conditions which specify the set of
 orders that can be packed to the same slab. These compatibility conditions
 are shown in the table below.
 TABLE 2
 Compatibility Matrix
 O.sub.1 O.sub.2 O.sub.3 O.sub.4 O.sub.5 . . . O.sub.n
 O.sub.1 x x x x
 O.sub.2 x x
 O.sub.3 x x x
 O.sub.4 x
 O.sub.5 x x x x
 . x
 .
 .
 O.sub.n x x x
 Additional constraints require that at most two orders types (colors) can
 be packed on a slab. For any slab, the maximum and minimum allowable
 weight is determined by using the order with the largest maximum weight.
 If the total applied weight is less than the minimum slab weight then the
 slab is designed to the minimum weight and the extra weight is considered
 to be partial surplus.
 The slab design problem is implemented on a computer using lists or sets.
 Two sets of lists are maintained, enumerated as (3) and (4) below:
 3. The slab design problem is represented by a set of orders
 O={O.sub.1,O.sub.2, . . . ,O.sub.m } in the order book.
 4. The solution (or partial solution) is represented using a set of
 designed--slabs S={S.sub.1, S.sub.2, . . . , S.sub.m }
 A Method for Slab Design
 The set covering formulation can be modified to allow for the fact that the
 slab design has orders with variable DPU size and, additionally, the items
 (DPUs for slab design) have weights associated with them. There are three
 novel extensions that need to be made to accommodate the slab design
 problem.
 1. We allow for the variable DPU size by filling a given slab weight W
 maximally by taking advantage of a range of DPU values instead of an item
 count.
 2. Since each item has a weight, and the objective is to fulfill the total
 weight of a order book, we choose slabs having the largest weight rather
 than the maximum number of DPUs.
 3. Finally, the exponential nature of enumeration of the set of all subsets
 is contained by constructing a cleverly chosen subset of slabs that can be
 designed at any given point and adding the largest slab to the cover.
 The solution to the slab design problem is represented by a list of
 designed slabs S=(S.sub.1,S.sub.2, . . . ,S.sub.m } Each slab S.sub.i in
 the list S has associated with it a list of SO.sub.i of orders applied
 against it. Associated with each order in SO.sub.i is a DPU number and a
 DPU size, represented as DPU.sub.number and DPU.sub.size, respectively,
 which indicates the applied quantity. Therefore, the list SO.sub.i is a
 list of tuples
EQU SO.sub.i ={{Order.sub.ID, DPU.sub.size, DPU.sub.number }.sub.1,
 {Order.sub.ID, DPU.sub.size, DPU.sub.number }.sub.2, . . . ,
 {Order.sub.ID, DPU.sub.size, DPU.sub.number }.sub.m }.
 The heuristic consists of two steps:
 Modified Set Covering: A generative step where a solution of slabs is
 created using set covering based techniques, and
 Max Flow: A post processing step which creates a network flow
 representation and uses max flow analysis to minimize the unused weight on
 each slab.
 These two steps are implemented as a computer program, the logic of which
 is shown in FIG. 1.
 Modified Set Covering
 With reference to FIG. 1, the step of modified set covering is first
 described.
 Step 1 (Initialization): Let RO.sup.i denote the remaining weight for order
 i; W.sub.max.sup.i denote the maximum slab weight corresponding to order
 i, and N.sub.i the number of orders compatible with order i. Let RS.sub.j
 denote the remaining weight of slab j designed to fill order i. Set
 RO.sub.i =O.sub.max.sup.i and Rs.sub.j =W.sub.max.sup.i.
 Step 2: Evaluate all orders in the order book represented by list O based
 on any function
 ##EQU6##
 and sort order list O in ascending order of function F.
 Step 3 (inner Loop): Create a temporary slab list TS=.PHI. and temporary
 order list OL=O.
 Step 4: Choose order i which has the smallest value of F (i.e., the head of
 the sorted list O and create a slab S.sub.i for this order.
 Step 5: Fill Si using order O.sub.i. The applied order weight AW.sub.i
 =DPU.sub.size.times.DPU.sub.number where DPU.sub.size and DPU.sub.number
 is calculated as follows:
 1. Let RW.sub.j.sup.i =min{RO.sup.i, RS.sub.j }. For a order node i and a
 slab node j, if
 ##EQU7##
 Step 6: Choose the orders compatible with O.sub.i sorted in increasing
 order of F. Denote this list of compatible orders as OL.sub.i. Note that
 this list corresponds to the row of orders corresponding to O.sub.i in the
 matrix shown in Table 2.
 Step 7: Fill slab S.sub.i using orders from OL.sub.i until the slab is
 full.
 Step 8: Add slab S.sub.i to the list of temporary slabs TS. Note that
 S.sub.i is a list of tuples which indicates the orders, the DPU.sub.size
 and DPU.sub.number used to fill the slab. Update OL to reflect the applied
 order quantity.
 Step 9 (End of Inner Loop): If there exist any unfilled orders in order
 list OL go to Step 3.
 Step 10: Pick the slab SL with the largest weight in TS and add it to the
 permanent list of slab designs S and remove the corresponding weight for
 orders applied from the order list O.
 Step 11 (End of Outer Loop): If there exist any unfilled orders in O go to
 Step 3
 This algorithm is followed by a post processing step where order completion
 rules and a max flow algorithm is used to minimize the waste on each
 designed slab.
 Max Flow Analysis
 At the end of the modified set covering step there might exist some orders
 O.sub.i which are not filled to .sub.m.sup.i and some slabs S.sub.j with
 partial surplus. We call such orders minimally filled orders.
 The purpose of the max flow analysis is to improve on the result of the set
 covering step by increasing the applied weight of such minimally filled
 orders in order to decrease the partial surplus of the slabs. FIG. 2 shows
 three such applied orders and the corresponding slabs. As shown in the
 figure, we construct a network by adding a source node and a sink node.
 The source node is connected to all the partially filled orders, while all
 the partially filled slabs are connected to the sink node. The capacities
 of the arcs are determined as follows:
 Capacity of an arc from the source to an order i is:
EQU min {(DPU.sub.max.sup.i -DPU.sub.size.sup.i).times.DPU.sub.number,
 O.sub.max.sup.i -AO.sup.i }.
 We now explain the reasons for choosing this value for the capacity: First,
 we do not wish to change the DPU.sub.number since it is restricted to be
 in integer. Changing the DPU.sub.number would involve obeying the
 integrality restriction which would make this step hard to solve. So, we
 choose to change the DPU.sub.size.sup.i. Note, again, that at the end of
 Step 1, for a partially filled order, i, the applied weight AO.sub.i
 =DPU.sub.number.times.DPU.sub.size.sup.i. Also, the maximum allowable
 value for DPU.sub.size.sup.i is DPU.sub.max.sup.i. Hence, keeping
 DPU.sub.number.sup.i to be the same, the maximum additional order weight
 which can be applied for order i is (DPU.sub.max.sup.i
 -DPU.sub.size.sup.i).times.DPU.sub.number. However, O.sub.max.sup.i
 -AO.sup.i is the total order weight remaining to be applied for order i.
 The minimum of these two quantities is then the bound on the capacity of
 the arc.
 Capacity of each arc from an order to a slab is .infin..
 Capacity of an arc from a slab j to the sink is equal to the partial
 surplus PS.sub.j of that slab.
 Having constructed the network with the above capacities on its arcs, we
 then find a maximum flow, as described for example by Ahuja, et al., from
 the source to the sink. In this step, we restrict ourselves to partially
 filled orders only (and ignore orders which have not been applied at all)
 because of the color constraints. That is, the maximum flow algorithm does
 not account for the color constraints and, hence, if we allow orders which
 have not been applied at all it is possible that the algorithm assigns
 these orders such that the color constraints are violated.
 While the invention has been described in terms of a single preferred
 embodiment, those skilled in the art will recognize that the invention can
 be practiced with modification within the spirit and scope of the appended
 claims.