مسئله تنظیم الگوریتم ژنتیک برای طراحی انعطاف پذیر

Many present markets for goods and services have highly volatile demand due to short life cycles and strong competition in saturated environments. Determination of capacity levels is difficult because capacities often need to be set long before demand realizes. In order to avoid capacity-demand mismatches, operations managers employ mix-flexible resources which allow them to shift excess demands to unused capacities. The Flexibility Design Problem (FDP) models the decision on the optimal configuration of a flexible (manufacturing) network. FDP is a difficult stochastic optimization problem, for which traditional exact approaches are not able to solve but the smallest instances in reasonable time. We develop a Flexibility Design Genetic Algorithm (FGA) that exploits qualitative insights into the structure of good solutions, such as the well-established chaining principle, to enhance its performance. FGA is compared to a commercial solver, a simple GA, and a Simulated Annealing local search on instances of up to 15 demand types and resources. Experimental evidence shows that the proposed approach outperforms the competing methods with respect to both computing time and solution quality.

Demand-capacity mismatches occur in a wide range of operations like workforce planning, strategic network planning or the design of queueing systems. They are mainly triggered by uncertainty about the demand for workforce, goods and services. Demand uncertainty is driven by shortening product and service life cycles, high competition on saturated markets and the increase of product and service variety. Resource capacity levels are usually fixed for a significant time period and must therefore be set long before demand realizes. Capacity levels should match demand closely to avoid capacity shortage (when demand exceeds capacity) or idle time (when capacity exceeds demand). The use of flexible resources is an important means to counter such mismatches. Bertrand (2003) discusses several types of flexibility that have been introduced in science and practice. We consider mix flexibility, which is the ability of a resource to process several demand types without incurring high transition penalties (Koste and Malhorta, 1999). The core idea of using mix-flexible resources is to assign several demand types to a single resource, so that the capacity of the resource can be used for more than one demand type. Flexibility decisions can be formalized by means of a bipartite graph, where one set of nodes represents the demand types and the other set the resources. An arc between a demand type and a resource is called a link and indicates the capability of the resource to process the demand type. If a resource is only connected to a single demand type, it is inflexible, whereas if it has more than one linked demand type, it is mix-flexible. Fig. 1 shows a simple example with two resources A and B and two demand types 1 and 2. Both resources have a capacity of 100 units and demand is 150 units for demand type 1 and 50 units for demand type 2. If both resources are inflexible and resource A can only process demand type 1 and B demand type 2 (as indicated by the solid links), we have a capacity shortage of 50 units at resource A and 50 units of unused capacity at resource B. Now, if resource B is mix-flexible and can process both demand types (by adding the dashed link), demand types 1 and 2 are linked by resource B. In this way, the 50 units of excess demand at resource A can be shifted to resource B. We end up with no capacity shortage and two completely utilized resources. Note also that, as illustrated in Fig. 1, in the mix-flexible case one demand type may link more than one resource in the sense that the resources are both able to process the demand type.Originally, this generic principle has been proposed by Jordan and Graves (1995) in the context of designing flexible production networks. Since then, it has been successfully applied in several practical applications in the same domain (see, e.g., Hallgren and Olhager, 2009 and Kauder and Meyr, 2009) or in other industrial areas like the cross-training of workers at production lines and call centers (see, e.g., Brusco and Johns, 1998, Hopp et al., 2004, Wallace and Whitt, 2005 and Nembhard, 2007) and the design of queueing systems (see, e.g., Gurumurthi and Benjaafar, 2004 and Andradóttir et al., 2007). Fig. 1 lists the appropriate domain-specific terms for the two major application areas. However, as the contributions of our paper are not restricted to an application domain, we stick to the generic terms for the remainder of the text. The challenge common to the different application areas is to find the most profitable assignment of demand types to resources when confronted with stochastic demands. This decision is modeled by the Flexibility Design Problem (FDP). The FDP determines the optimal assignment of demand types to resources such that the total expected profit is maximized. We formulate the FDP as a two-stage stochastic program, however, the FDP is NP-hard even for deterministic demands (Garey and Johnson, 1979). In our numerical studies, we observe the inability of standard solvers to solve all but the smallest FDP instances to optimality in a reasonable amount of time. Motivated by this, we develop a Genetic Algorithm (GA) specifically tailored to FDP, denoted as Flexibility Design GA (FGA). FGA incorporates problem-specific knowledge on the structure of high-quality FDP solutions to guide the search. Specifically, it uses the flexibility principles of Jordan and Graves (1995), which have proven to be a reasonable and robust strategy for designing flexible networks. We thus demonstrate how qualitative principles can be incorporated into a quantitative solution approach to increase computational efficiency. We present a computational study on FDPs with up to 15 demand types, 15 resources and 500 demand scenarios. To the best of our knowledge, no benchmark instances for the FDP or a closely related problem are available and no efficient metaheuristic solution method for the FDP has been proposed. Therefore, we generate several sets of random test instances. As comparison methods for our approach, we use the commercial solver Xpress-Optimizer (see Fico Xpress Optimization Suite, 2011), a Simple GA (SGA) and a Simulated Annealing (SA) approach. FGA demonstrates superior performance, consistently finding flexibility configurations with higher expected profits in a fraction of the time required by the comparison methods. The paper is organized as follows. Section 2 reviews the literature and describes the flexibility principles developed by Jordan and Graves (1995). A formulation of the FDP as a two-stage stochastic program is given in Section 3. Section 4 describes in detail the FGA for solving this problem. Experimental results are presented in Section 5. The experiments evaluate the run-time and solution quality of the FGA and the three comparison methods. Moreover, we study the effectiveness of each problem-specific extension that we integrate into FGA. Section 6 concludes the paper and gives a brief outlook on future research.

This paper presents a problem-adjusted genetic algorithm, called Flexibility Design GA (FGA), for solving the Flexibility Design Problem (FDP). FGA successfully integrates expert knowledge on the FDP to guide its search. FGA uses a problem-adjusted technique to generate its initial population, which is based on the estimation and replication of good flexibility structures. The problem-adjusted crossover operator avoids the disruption of good partial solutions, while mutation randomly opens or closes links only when appropriate. We conducted experiments on a base set with 180 small and medium-sized instances and a set of nine large-scale instances and compared the solution quality and run-time of FGA and three comparison methods: a simple GA, a Simulated Annealing approach and a commercial solver. Moreover, the effectiveness of the problem-specific adaptions in FGA is studied. The results show clearly that the customization of FGA is beneficial as run-time and solution quality improve with the problem-specific adaptions. In detail, FGA dominates all comparison methods with respect to both run-time and solution quality for all but the smallest problem instances. For the larger problem instances, which are of primary interest in practice, the gap between FGA and comparison methods widens. Future research is to integrate FGA into larger planning models which include resource capacity choices. The crux is to gain qualitative insights into the interplay between the assignment and capacity decisions and to examine how this knowledge can be used in a solution approach. Furthermore, we noted in the experiments that FGA spends most of its time evaluating the second stage production program. It shall be investigated how its resolution can be sped up, e.g., by using sampling techniques or iterated dual reoptimization.