Article Preview
TopIntroduction
In this paper we focus on the problem of optimizing a distributed manufacturing network (DMN), in which a number of products need to be manufactured. Each product can be produced by one or more assembly node processes, where each assembly is composed of several machines working in parallel, as shown in Figure 1. For the required demand of the output products, a decision must be made on how much should be produced by each DMN assembly node, which machines should be on and their output level. Operation of each machine has associated cost, which is a function of the machine output level. Typically, the cost function has an S shape, indicating less efficient operation at the edges of its operational range, and more efficient operation in its ”sweet spot”. In turn, each DMN assembly node requires sub-products as its input, and those in turn are produced by other assemblies. Thus the overall DMN may involve multiple layers of DMN assembly nodes. An important question is how to make production decisions that minimize the total production cost.
Figure 1. Distributed manufacturing network
The state-of-art implementation of decision optimization solutions, such as the DMN problem, involves Mathematical and Constraint Programming (MP and CP), used for decision optimization, i.e., finding values for control variables that maximize or minimize an objective within given constraints. While software developers find database programming mostly intuitive, they typically do not have the mathematical expertise necessary for MP and CP. In addition, much investment has already been spent on database applications. Clearly, it is desirable to leverage this investment when building decision optimization applications.
To bridge the gap, in Brodsky, Bhot, Chandrashekar, Egge, and Wang (2009) we introduced a Decision Guidance Query Language (DGQL) and system, following the Decision Guidance Management System framework of Brodsky and Wang (2008). In Brodsky, Egge, and Wang (2011) we provided DGQL formal syntax and semantics, a reduction of DGQL to the standard mathematical programming (MP) formulation, and a proof of its soundness and completeness. DGQL makes a step toward making decision optimization easier, especially in applications where database technology has been heavily used.
DGQL provides a query-like abstraction for expressing decision optimization problems so that database programmers would be able to use it without prior experience in MP and, more importantly, they would be able to reuse the queries already built into existing applications. A decision optimization problem in DGQL is written as a “regular” database program, i.e., a sequence of SQL views and accompanying integrity constraints, together with some annotation of which database table column needs to be decided by the system (i.e., variables) and toward what goal (i.e., optimization objective). Here, existing queries in SQL can be directly used. Essentially, DGQL allows users to write an optimization problem as if writing a database program in SQL in a forward manner.
The challenge in the DGQL approach, however, is how to execute the “inverse” decision optimization based on a “forwardly” expressed code. This is done in Brodsky, Bhot, Chandrashekar, Egge, and Wang (2009) and Brodsky, Egge, and Wang (2011) by encoding the DGQL queries as an MP problem, solving it using an MP solver (such as ILOG CPLEX MILP solver) and then deriving the solution to the DGQL original problem. This approach was demonstrated to be comparable in efficiency to equivalent MP formulations that were expertly crafted and solved using a Mixed Integer Linear Programming (MILP) solver.
However, for optimization problems such as the DMN problem considered in this paper, even when only linear arithmetic constraints are used, the DGQL compiler generates a Mixed Integer Linear Programming (MILP) formulation (Schrijver, 1998), which involves a large number of binary decision variables. Thus, for this family of optimization problems, standard algorithms for MILP such as the branch and bound method are highly inefficient.