Article Preview
Top1. Introduction
In our exposition, we will discuss the Generalized Assignment Problem and the Mixed Model Sequencing Problem. Through these, we will show the variety of ways in which AEGIS can be employed, as well as provide some concrete examples of how the solution process is improved as a result.
The AEGIS system is intended to be a metaheuristic environment for solving combinatorial optimization problems. The name itself indicates the three major aspects of the system:
- •
Attribute Experimentation: Experimentation is key, and can be done either prior to any formal decision-making, or incidental to it. By collecting data on historical and in-process solutions, we expect to identify relationships between non-objective attributes and the objective itself.
- •
Guiding: The purpose of the experimentation is to provide tools/measures that will lead the analyst in solving a problem.
- •
Improvement Searches: The process is implemented within an iterative construction environment. (However, as we shall show later, the framework is intended to suggest that one using this framework also consider rational mechanisms for decomposing an incumbent solution.)
The goal of this paper is to provide a framework in which historical information is combined with intermediate solution attributes (ISA’s), and decisions are made while the problem is being solved.
The remainder of the paper is organized as follows. The second section identifies other research that has a relationship with AEGISi. Section three discusses the dynamics of AEGISi, developing the framework for the metaheuristic used in immediate conjunction with a suite of solvers. The fourth section expands on the general discussion, focusing on two of the key components in AEGISi. In the next two sections, we show how two AEGISi systems were developed. A detailed case review is done for the Mixed Model Sequencing with Due Dates (MMSDD) Problem, along with an abbreviated look at the Generalized Assignment Problem (GAP). We then conclude with a brief review of our findings, and some ideas for follow-up research.
Top2. Literature Review
In the companion paper to this one (Racer & Lovgren, 2009), we presented a fairly comprehensive review of literature that relates to the AEGIS framework; the entire reference list is included here as well. In this paper, our review focuses primarily on other studies that are multi-algorithmic in nature.
In general, what we propose for the in-line AEGIS is a construct of the following form: Given the current solution state of some instance of a problem, (where the state can be a function of objective, status of constraints, current solver, solver parameters, etc.) determine the next step in the solution process (e.g., change solver, change parameters, terminate).
Hybrid algorithms, (e.g. Amini & Racer, 1995; Lovgren, 1996; many others) are degenerate forms of this construct, wherein there is not a formal consideration of the state. The work by Cramer, Dennis, Frank, Lewis, & Shubin, (1994) on non-linear problems is also typical of this form. The multi-disciplinary optimization (MDO) framework of theirs suggests sequencing through different solvers, each focusing on a different objective function element. For instance, their solution methodology for wing design iterates between an algorithm for designing the wing with respect to static conditions, and then re-evaluating that design with respect to dynamic, in-flight, performance.
A second area of interest to us, for reasons that we’ll explore in the next section, is that of axiomatic design (AD). Several good references are: Cochran & Reynal (1996); Lindholm, Tate, & Harutunian, (1999); and Gu, Hashemian, & Nee, (2004). The basic structure is shown in Figure 1.
Figure 1. Axiomatic design environment