Content area
Full Text
ABSTRACT
This paper demonstrates the solution of a combinatorial optimization problem. The general problem faced is that of determining an acceptable sequence in which to provide a service to specific entities. In this specific case, the service is painting houses (the entities) and the sequence is constrained by the need to avoid painting contiguous houses within a minimum time period. Neither specialized optimization software nor a general programming language is used to perform the optimization. Instead, the authors formulated an Excel spreadsheet solution utilizing Excel add-in tools (Premium Solver Platform, Evolver, and GeneHunter). Genetic algorithms, a more efficient technique than those frequently found in Excel optimization software, were used to reduce solution time. Model development time was minimal and execution time was not a significant constraint. It is likely that genetic algorithm tools will contii to be use id more applications.
(ProQuest: ... denotes formula omitted.)
INTRODUCTION
Optimization problems have the goal of obtaining an optimal solution while meeting desired objectives. Combinatorial optimization problems are an important subset. In combinatorial optimization problems, some or all of the variable values must be integers. These problems are often referred to as integer programming problems. In an all-integer problem, the solution space is restricted to a finite, although not necessarily small, number of possible solutions. Indeed, Meredith, Shafer, and Turban (2002) describe the solution space size as "sometimes astronomical." The literature shows that such problems occur frequently; for instance, Hoffman and Padberg (n.d.) note their pervasiveness throughout most management fields. Further, combinatorial optimization problems are often of financial significance (Sensen, 2006). Postrel (2004) writes, "tweaking such mundane but strategically critical decisions as where to site plants, when to restock, andso on, can provide enormous productivity boosts."
In this paper, we demonstrate the solution of a combinatorial problem: determining an acceptable sequence in which to provide a service to specific entities. In this case, the service is painting houses(the entities) and the sequence is constrained by the need to avoid painting contiguous houses within a minimum time period. Rather than using specialized optimization software or a general programming language to perform the optimization, we formulate an Excel spreadsheet solution that utilizes Excel add-in tools.The need for a reasonable solution time necessitated the use of techniques-i.e. genetic algorithms-beyond those...