3% WIHHIIIIIHIIIHIWWWHNIHIHHHIWWII THE SWAPPING HEURISTIC By Brian Zulawinski A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE Department of Computer Science 1995 ABSTRACT THE SWAPPING HEURISTIC By Brian Zulawinski In a grouping problem, a set must be partitioned subject to problem-specific constraints. The Swapping Heuristic (SH) is a family of local search heuristics for solving grouping problems. In this paper we apply the SH to two classic grouping problems: the Bin Packing Problem and the Minimum Makespan Problem. We show that the SH outperforms previously published methods for solving these two problems in a wide variety of situations. TABLE OF CONTENTS LIST OF TABLES vi LIST OF FIGURES vii 1. INTRODUCTION 1 2. THE BIN PACKING PROBLEM AND THE MINIMUM MAKESPAN PROBLEM 1 3. THEORETICAL BACKGROUND AND LIMITATIONS 2 4. KNOWN METHODS FOR THE BIN PACKING PROBLEM 4 4.1 Theoretical Results 4 4.1.1 First Fit 4 4.1.2 First Fit Descending 4 4.1.3 Best Fit 5 4.1.4 Best Fit Descending 5 4.2 Approximation Schemes 6 4.2.1 Asymptotic Polynomial Approximation Scheme 6 4.2.2 Asymptotic Fully Polynomial Approximation Scheme 6 4.2.3 Near-Absolute Approximation Scheme 7 4.3 Practical Results 8 4.3.1 Open Loop Hybrid Algorithm 8 4.3.2 The Reduction Method 11 4.3.3 The Hybrid Grouping Genetic Algorithm 13 5. THE SWAPPING HEURISTIC APPLIED TO THE BIN PACKING PROBLEM 20 5.1 Rationale for the Swapping Heuristic 20 5.1.1 Case 1: The Number Of Bins Stays The Same 21 5.1.2 Case 2: The Number Of Bins Decreases 22 5.2 Description of the Swapping Heuristic Applied to the Bin Packing Problem 23 5.3 Worst-Case Performance 26 5.4 Results: Bin Packing Problem 30 5.4.1 Comparison to Standard Methods 30 5.4.2 Comparison to Reduction Method and Hybrid Grouping Genetic Algorithm 31 5.4.3 Comparison to the Open Loop Hybrid Algorithm 37 6. KNOWN METHODS FOR MINIMUM MAKESPAN PROBLEM 38 6.1 Theoretical Results 38 6.1.1 Longest Job First 38 6.1.2 Multifit Algorithm 39 6.2 Dual Approximation Schemes 40 6.3 Practical Methods ' 41 7. THE SWAPPING HEURISTIC APPLIED TO THE MINIMUM MAKESPAN PROBLEM 43 7.1 Rationale for the Swapping Heuristic 43 7.2 Description of the Swapping Heuristic Applied to the Minimum Makespan Problem 44 7.3 Results: Minimum Makespan Problem 46 7.3.1 Comparison to Longest Job First and the Multifit Algorithm 46 7.3.2 Comparison to Simulated Annealing 49 8. CONCLUSION 51 9. REFERENCES 53 vi LIST OF TABLES TABLE ‘II EXECUTION TIMES FOR INCREASING NUMBER OF OBJECTS ................................ 29 TABLE 22 RESULTS, BIN PACKING PROBLEM, COMPARISON TO STANDARD METHODS ........ 31 TABLE 32 RESULTS, BIN PACKING PROBLEM, 'UNIFORMS' ................................................. 35 TABLE 42 RESULTS, BIN PACKING PROBLEM, TRIPLETS DISTRIBUTION .............................. 36 TABLE 52 RESULTS, BIN PACKING PROBLEM, BILCHEV INSTANCES 1 ................................. 37 TABLE 62 RESULTS, BIN PACKING PROBLEM, BILCHEV INSTANCES 2 ................................. 38 TABLE 72 RESULTS, MINIMUM MAKESPAN PROBLEM, COMPARISON TO STANDARD METHODS47 TABLE 8: RESULTS, MINIMUM MAKESPAN PROBLEM, UNIFORM DISTRIBUTION ................... 48 TABLE 9: RESULTS, MINIMUM MAKESPAN PROBLEM, DISCRETE DISTRIBUTION .................. 49 TABLE 10: RESULTS, MINIMUM MAKESPAN PROBLEM, UNIFORM DISTRIBUTION ................. 50 TABLE 112 RESULTS, MINIMUM MAKESPAN PROBLEM, NORMAL DISTRIBUTION ................... 51 vii LIST OF FIGURES FIGURE 1: THE BIN PACKING PROBLEM ............................................................................. 2 FIGURE 2: THE MINIMUM MAKESPAN PROBLEM .................................................................. 2 FIGURE 3: PERMUTATION CHROMOSOME REPRESENTATION ............................................. 11 FIGURE 4: OPEN LOOP HYBRID ALGORITHM ..................................................................... 11 FIGURE 5: DOMINANCE CRITERION .................................................................................. 13 FIGURE 6: TRADITIONAL CHROMOSOME REPRESENTATION ............................................... 14 FIGURE 7: TRADITIONAL CROSSOVER .............................................................................. 14 FIGURE 8: CHROMOSOME REPRESENTATION OF THE GROUPING GENETIC ALGORITHM ...... 15 FIGURE 9: CROSSOVER EXAMPLE .................................................................................... 17 FIGURE 10: GGA vs. FFD .............................................................................................. 18 FIGURE 11: EXAMPLE DEMONSTRATING MUTATION-LIKE BEHAVIOR OF THE GGA'S CROSSOVER ............................................................................................................ 19 FIGURE 12: CASE 1 EXCHANGES ..................................................................................... 21 FIGURE 13: CASE 2 EXCHANGES ..................................................................................... 22 FIGURE 14: BASIC DESCRIPTION OF THE SWAPPING HEURISTIC ........................................ 24 FIGURE 16: SWAPPING HEURISTIC WITH OBJECT LIMIT .................................................... 26 FIGURE 17: WORST KNOWN CASE FOR THE SH ............................................................... 27 FIGURE 18: EXECUTION TIME vs. NUMBER OF OBJECTS ................................................... 29 FIGURE 19: NUMBER OF ITERATIONS vs. NUMBER OF OBJECTS ........................................ 30 FIGURE 20: TIME PER ITERATION vs. NUMBER OF OBJECTS .............................................. 30 FIGURE 21: PROCEDURE FOR CREATING INSTANCES OF THE ‘UNIFORMS' .......................... 33 FIGURE 22: THE MULTIFIT ALGORITHM ............................................................................ 4O viii FIGURE 23: DESCRIPTION OF THE SIMULATED ANNEALING ALGORITHM ............................. 43 FIGURE 24: THE SWAPPING HEURISTIC FOR THE MINIMUM MAKESPAN PROBLEM ............... 45 1. Introduction In a grouping problem, a set must be partitioned subject to problem-specific constraints. The Swapping Heuristic (SH) is a family of local search heuristics for solving grouping problems. In this paper we discuss the SH as applied to two classic grouping problems: the Bin Packing Problem and the Minimum Makespan Problem. Research on these problems falls into two distinct categories: theoretical and practical. Theoretical research focuses on determining the computational complexity and proving bounds on the worst-case performance. These analyses are usually limited to simple deterministic algorithms and approximations schemes. The simple algorithms do not produce high quality approximations. The approximation schemes are difficult to implement and require unreasonable execution times for solutions with small error. Practical research focuses on search tools including simulated annealing, genetic algorithms, heuristics, and various combinations of these methods. These methods are difficult to analyze theoretically but produce good results with practical execution times. These methods are often complex and involve “tweaking” many parameters. The SH is a practical approximation scheme that produces high quality results in short amounts of time. The SH is also easier to implement than other complex solutions found in the literature. 2. The Bin Packing Problem and the Minimum Makespan Problem Figure 1 defines the Bin Packing Problem (BPP), a well-studied grouping problem. Figure 2 describes the Minimum Makespan Problem (MMP), the dual of the Bin Packing Problem. In the Bin Packing Problem, the size of the bins is fixed and the number of bins is minimized. In the Minimum Makespan Problem, the number of machines (bins) is fixed and the makespan (size of the bins) is minimized. Given: . Identical bins of capacity C . A set W = {1,2,...,n} of n objects with sizes s,, 1' EW such that each s, s C Constraints: . Each object in W is assigned to exactly one bin. 0 The sum of the object sizes of the objects assigned to any bin does not exceed the bin capacity C. Goal: - Find an assignment of the objects to bins such that the number of bins, m, is minimized. Figure 1: The Bin Packing Problem Given: . a set of n jobs with designated integral processing times p}. . m identical machines. A schedule of jobs is an assignment of the jobs to the machines, so that each machine is scheduled for a certain total time, 1,. The maximum time that any machine is scheduled for is called the makespan of the schedule. Therefore, Makespan = max,=,',,, {1, }. Goal: . Find a schedule that minimizes the makespan. Figure 2: The Minimum Makespan Problem 3. Theoretical Background and Limitations The time requirements of an algorithm are expressed in terms of the “size” of a problem instance [Garey and Johnson, 79]. The relative difficulty of problem instances varies with several factors, including their size. The size of an instance of the BPP is the number of objects. The size of an instance of the MMP is the number of jobs. The time complexity function for an algorithm expresses its time requirements by giving, for each possible input size, the largest amount of time needed by the algorithm to solve a problem instance of that size. A polynomial time algorithm has a polynomial time complexity function. An algorithm that cannot be bounded by a polynomial time complexity function is a superpolynomial time algorithm. The computational time required for superpolynomial time algorithms grows far more rapidly than polynomial time algorithms with respect to the input size. Therefore, superpolynomial time algorithms are impractical for large problem instances. To date there is no known polynomial time algorithm for solving the BPP or the MMP. Furthermore, these problems belong to the class of NP-Complete problems. No member of the class of N P-Complete problems has a known polynomial time algorithm. In addition, if a polynomial time algorithm is found for any member of the class of NP- Complete, every problem in NP-Complete would also be solved in polynomial time. Currently, all algorithms which produce optimal solutions for any NP-complete problem are superpolynomial time algorithms. Since superpolynomial time algorithms are impractical for large problem instances, the focus turns to finding near-optimal solutions that require less time. There are simple, practical algorithms which achieve small constant approximation ratios. However, we often require optimal or extremely close to optimal solutions. Another approach is polynomial approximation schemes. For any bounded error, there is a polynomial time algorithm which can guarantee solutions within that error bound. These schemes have a high-order polynomial complexity for small error and are often not feasible for practical problems. These algorithms are also complex and difficult to implement. Thus, practitioners have often turned to other methods which do not have provable worst-case guarantees, which do not have provable running times, but which empirically produce good results quickly. Our work presents a newer algorithm along these lines which is simpler, often runs faster, and often produces better solutions than these previously used practical algorithms. 4. Known Methods for the Bin Packing Problem 4. 1 Theoretical Results 4.1.1 First Fit First Fit is arguably the simplest approach for the BPP. First Fit (FF): For each object, place the object in the first bin it fits. If no such bin exists, start a new bin and place the object in the new bin. FF has a time complexity function 0(n2). For any instance I , the number of bins used by FF is upper bounded by Equation 1 [Garey and Johnson, 79]. Equation 1 FF(I) s (%) 0pt(l) + 2 FF (1 ): Number of bins used by First Fit on Instance I 0pt(1): Minimum number of bins required for Instance 1 4.1.2 First Fit Descending First Fit Descending improves on FF by sorting the objects in descending order before they are assigned to the bins. First Fit Descending (FFD): Sort the objects in descending order. For each object, place the object in the first bin into which it fits. If no such bin exists, start a new bin and place the object in the new bin. FFD also has a time complexity function 0(n2). For any Instance I , the number of bins used by FFD is upper bounded by Equation 2 [Garey and Johnson, 79]. Equation 2 FFD(I) s gown) + 4 FFD(I): Number of bins used by First Fit Descending on Instance I 0pt(l): Minimum number of bins required for Instance I 4.1.3 Best Fit Best Fit tries to improve on FF by placing each object into the bin with the minimum available space that can still accommodate the object. The bin meeting this criterion is said to have the “best” fit for the object. Best Fit (BF): For each object, place the object in the bin that has current contents closest to, but not exceeding C — 3,. If no such bin exists, start a new bin and place the object in the new bin. BF has a time complexity function 0(n2). BF's worst-case performance is identical to FF. 4.1.4 Best Fit Descending Best Fit Descending improves on BF by sorting the objects before they are assigned to the bins. Best Fit Descending (BFD): Sort the objects in descending order. For each object, place the object in the bin that has current contents closest to, but not exceeding C — 3,. If no such bin exists, start a new bin and place the object in the new bin. BFD also has a time complexity 0(n2). Surprisingly, BFD’s worst case performance is identical to F F D. 4.2 Approximation Schemes For any relative bounded error a, polynomial approximation schemes provide an algorithm with a polynomial time complexity function. The time complexity functions for small I»: are high order polynomials, making these schemes computationally infeasible for practical problems. 4.2.1 Asymptotic Polynomial Approximation Scheme An asymptotic polynomial approximation scheme (APAS) is a family of algorithms {A€|e> 0} such that each A, runs in polynomial time with respect to the length of the input and A‘(I) S(1+£)°Opt(I) as the length of the input goes to infinity. [Vega and Lueker, 81] identify an APAS which runs in linear time but is severely exponential in 3. Their method produces solutions that are upper bounded by Equation 3. Equation 3 A£(I) s(1+g)-0pt(1)+1 AU) 3 (1+ 5) as n goes to infinity n: Number of objects A; (I): Number of bins used by A: on instance I 0pl(I): Minimum number of bins required for Instance I 4.2.2 Asymptotic Fully Polynomial Approximation Scheme An asymptotic fully polynomial approximation scheme (AFPAS) is a family of algorithms {Aslg > 0} such that each A; runs in polynomial time relative to the length of the input and %. while A£(I) 3 (1+ e)-0pt(l) as the length of the input goes to infinity. [Karmakar and Karp, 82] propose a AFPAS with running time 0("'°,3"). The S algorithms produce solutions that obey Equation 4. Equation 4 A,(1)s(1+g)-0pz(1)+—12—+3 8 148(1) 3 (1+ £)-0pt(I) as It goes to infinity n: Number of objects A: (I): Number of bins used by A: on instance I 0pt(I): Minimum number of bins required for Instance I 4.2.3 Near-Absolute Approximation Scheme The Near-Absolute Approximation Scheme is a modification of the work of Karmakar and Karp [Johnson, 82]. This AFPAS has absolute error bounded by a polylogarithmic function of the optimal solution. The solutions obtained with this method are upper bounded by Equation 5. Equation 5 NAAS(I) s 0pt(I) + 0(log2 0pt(I)) NAAS (I): Number of bins used by the Near - Absolute Approximation Scheme for instance I 0pt(1): Minimum number of bins required for instance I 4.3 Practical Results 4.3.1 Open Loop Hybrid Algorithm [Bilchev, 94] proposes an Open Loop Hybrid Algorithm (OLHA) consisting of a Genetic Algorithm (GA) and a Multi-agent System (MAS). In order to describe the system, the MAS and the GA are described first. The MAS performs exchanges of objects between two bins that increase the value of the objective function given by Equation 6. Equation 6 fblAS : A.Aspace +BA A: Positive Constant num of objects B: Positive Constant Aspace = (Size of more full bin)flm, — (Size of more full bin) A initial m “0me = (Num of objects in less full bin)final - (Num of objects in less full bin),m,,,, A genetic algorithm is a search algorithm based on natural selection and natural genetics [Goldberg, 89]. GAS are more robust than conventional search methods. GAS can be applied to a wide array of problems and produce near-optimal solutions on difficult search-spaces. GAs require the problem’s parameter set to be coded as a finite-length string over some finite alphabet. The strings are commonly called chromosomes, their analogue in biology. Each chromosome represents a complete solution to the problem. The mapping of the parameters onto the chromosome is called the representation. GAs directly manipulate the chromosomes, not the parameters themselves. Each chromosome has a corresponding fitness, a scalar measure of the quality of the chromosome. GAs make use of an objective function, a function that evaluates the fitness of a chromosome. GAs sample the search-space using only fitness values of the samples to guide the search. GAs are said to be blind since they require no knowledge other than fitness values. Since every problem has some metric for evaluating the quality of a solution, GAs can be applied to many problems. GAs search using a set of chromosomes called a population. A population of chromosomes enables a GA to search many regions of the search-space simultaneously, a desirable characteristic for searching multi-modal search-spaces. A set of chromosomes contains more information than the chromosomes themselves. Similarities among the chromosomes and their relationship to fitness values can be analyzed. Important similarities among highly fit chromosomes are called schema or building blocks. Building blocks are small parts of a complete solution. The GAs implicitly analyze and process schema by using a survival of the fittest and a structured yet randomized information exchange between chromosomes. GAs start with an initial population of chromosomes and create subsequent generations from the previous generation. The search is performed using three fundamental operators: reproduction, crossover, and mutation. Reproduction randomly copies individual chromosomes into the new generation with a probability increasing with increasing objective function value. After reproduction, crossover randomly combines building blocks of two chromosomes (parents) to produce two new chromosomes (children). One example of crossover is called one-point crossover. One-point crossover selects a single crossover point at random dividing each parent into two parts. The left part of parent1 is combined with the right part of parent2 to create a child. Likewise, the right part of parent1 is combined with the left part of parent2 to create another child. Crossover recombines schema present in the parents and passes them to the children. Mutation randomly changes a chromosome enabling 10 the introduction of schema not present in the population. Although mutation plays a an important role in GAs, it is typically used much less frequently than crossover. High mutation rates are disruptive to the GA. Since crossover and mutation have a random component, they are said to be stochastic operators. GAs are useful since they preserve and recombine building blocks of solutions to make new solutions. The GA representation of the OLH is an ordering of the objects. The first gene represents the first object in the list, the second gene represents the second object, etc. Each object occurs exactly once in the chromosome. This representation is referred to as a permutation. Figure 3 shows an example of a permutation chromosome. The objects are given to First Fit in the order specified by the chromosome. The crossover used in this approach differs from other permutation crossovers. The placement of each object under First Fit depends on the placement of all objects appearing to the left in the chromosome. The crossover preserves schemata of the left side of the parent chromosome and passes them to the children as the left part of the chromosome. The GA uses Equation 7 as the objective function. Equation 7 a fGA :m+ m Z(fi_11-fi11.)2 m: Number of bins a: A positive constant fill,: The sum of the object sizes of the objects in bin 1' ——l M fill—mzfiu, r=I 11 A (I l I- Object1 is fourth Object 3 is third Object 0 is second Object 2 is first Figure 3: Permutation Chromosome Representation The Open Loop Hybrid Algorithm is composed of the GA and the MAS. The GA is employed for several generations until it produces a solution of desirable quality. The MAS further optimizes the solution to produce the final solution. Figure 4 shows the OLHA. Initial GA Solution MAS I I Solution Figure 4: Open Loop Hybrid Algorithm 4.3.2 The Reduction Method The Reduction Method is a powerful algorithm that produces near-optimal solutions to the BPP proposed by [Martello and Toth, 90]. In order to describe the algorithm, several definitions are necessary. Feasible set: A feasible set of objects is defined as any subset of the objects W whose sizes sum to less than or equal to the bin capacity C. 12 Fis a feasible set rffF ; Wand XS, 3 C ieF W = {1,2,...,n} The set of all objects 3, is the size of object 1' C is the bin capacity Consider an instance consisting of a set of objects W. If a feasible set F is assigned to a bin, then the instance W is reduced to an instance W— F . Dominance: Given two feasible sets F, and F2, F, dominates F2 iff the number of bins for the optimal solution of the reduced instance W — F, is not greater than the number of bins required for the optimal solution of the reduced instance W— F2. Dominance criterion: Given two distinct feasible sets F, and F2, if there exists a partition P: {P, ,...,P,} of F2 and a subset {i,,...,i,} of F, such that s“ 2 s, for kgp, h = 1,...1, then F, dominates F2. Figure 5 clarifies this definition. Checking if one feasible set F, dominates another feasible set F2 requires either solving the reduced instances W -F, and W —F2 or using the dominance criterion. Solving the reduced instances requires exponential-time. Using the dominance criterion is computationally less intensive since only the objects in the two feasible sets are examined. The Reduction Method makes use of the dominance criterion. This procedure reduces the size of an instance of BPP by considering all feasible sets, finding one (call it F) dominating all of the others, assigning F to a new bin and removing F from the set of remaining objects W. Since that leaves fewer objects to consider (W —F), the problem is reduced. The cardinality of the feasible sets considered are limited and checking for dominance is done only through the dominance criterion. If no set dominating all others can be found, the problem is relaxed by removing the smallest 13 F. F. Object 1 Object 2 Object 4 p < : : 7 1 Object 5 Object 3 Object 6 I P2 The size of P, is less than or equal to the size of Object 2. The size of P2 is less than or equal to the size of Object 3. F, dominates F2 Figure 5: Dominance Criterion object among those which are not yet assigned to any bin. These relaxed objects are later inserted with a different method such as FFD. 4.3.3 The Hybrid Grouping Genetic Algorithm Traditional GAs are ill-suited for grouping problems. Consider the representation using one gene per object as shown in Figure 6. Chromosomes using this representation exhibit redundancy. Many chromosomes describe the same solution. For example, the chromosomes AABB and BBAA have a group comprised of objects 0 and 1 and a group comprised of objects 2 and 3. Since the names of the groups are irrelevant, the two chromosomes are equivalent. The redundancy can grow exponentially as the number of objects increases. An exponential factor of redundancy drastically enlarges the search space. Traditional crossover, such as one-point crossover, does not pass meaningful information from parents to children. In the 14 example of Figure 7, none of the groups in the children exist in the parents. Infeasible solutions (overfilled bins) and poor solutions dominate the search-space. §~Object 3 is in Group B Object 2 is in Group B Object 1 is in Group A Object 0 is in Group A Figure 6: Traditional Chromosome Representation Parent 1: ABC|ABC Parent 2: AABIBCC Child 1: ABCBCC Child 2: AABABC Figure 7: Traditional Crossover Emanuel Falkenauer proposes a particular adaptation of GAs for grouping problems that is better suited for grouping problems than traditional GAs [Falkenauer, 92],[Falkenauer, 94A],[Falkenauer, 94B],[Falkenauer, 95]. He developed one of the most powerful methods known for solving the BPP, and it provides the basis for our work. Falkenauer identifies the schemata of grouping problems as the groups. He defines a representation, crossover operator, and a mutation operator that work with groups as the building blocks. He calls the modified GA a Grouping Genetic Algorithm (GGA). Crossover and mutation produce children with each object assigned to exactly one bin and no bin is overfilled. The GGA, therefore, is restricted to working only with feasible solutions. 15 The GGA’s chromosomes are composed of two parts: the object part and the group part. The object part has one locus for each object. The object part identifies which objects form which group. In Figure 8, the first object (Object 0) is in the group specified by the first gene (Group A). The group part lists each group exactly once in any order. Crossover and mutation work with the group part directly and use the object part indirectly. The group part is necessary to allow linkage among the groups under crossover. Groups listed near each other in the group part of the Chromosome are more likely to remain together after crossover. In Figure 8, the chromosome represents a configuration with three groups. The first group (Group B) is “closer” to the second group (Group A) than it is to the third group (Group C), in strength of linkage. Groups having strong linkage are more likely to remain together under crossover. Since the number of groups is not constant, the chromosomes can have different lengths. The goal of the GGA’s crossover is to pass possibly linked groups from parents to the children. Crossover is performed as follows [Falkenauer, 94A]: 1) Select at random two crossing sites in the group part, delimiting the crossing Object part Separator Group part \I/ : BAC Object 3 is in Group C Object 2 is in Group B Object l is in Group A Object 0 is in Group A Figure 8: Chromosome Representation of the Grouping Genetic Algorithm 2) 3) 16 section, in each of the two parents. Inject the contents of the crossing section of Parent 1 at the first crossing site of the Parent 2. This means injecting some of the groups from Parent 1 into Parent 2. Eliminate all items now occurring twice from the groups of which they were members in Parent 2. The ‘old’ membership of these items gives way to the membership specified by the ‘new’ injected groups. Some of the ‘old’ groups coming from the second parent are thus altered: they do not contain all the same items anymore, since some of those items had to be eliminated. Remove these groups from the group part of Parent 2 and place objects belonging to these groups in a queue of objects lacking membership in a group. 4) Assign each object in the queue to a group. The algorithm used is problem- 5) specific. For the BPP, the objects are reinserted using FFD. Perform Steps 2 through 4 on the two parents with their roles reversed in order to generate the second child. Example: Groups from Parent 1 are injected into Parent 2. Parent 2 is represented by small letters so that it can be differentiated from Parent 1. (Parent 1) AABCC:ACB (Parent 2) abcbczcab After step 1: (Parent 1) AABCC:|A|CB (Parent 2) abcbc:c|ab| 17 Injected Group Old Group From Parent 2 2 Figure 9: Crossover Example After step 2: (Parent 1) AABCC:|A|CB (Parent 2) abcbcchab After step 3: (Parent 1) AABCC:|A|CB (Parent 2) AAc®c:cA Queue = {object 2} Mutation in the GGA is performed as follows: 1) Select at random several groups to eliminate. 2) Place the objects in these groups into the queue. 3) Reinsert the objects in the queue into the solution. The algorithm used is problem- specific. For the BPP, the objects are reinserted using FFD. Falkenauer uses Equation 8 as the objective function for the BPP. Since the GGA’s crossover and mutation operators create only feasible solutions, the objective 18 Equation 8 fill-2 fBPP : 1:1sz m: the number of bins being used fill,: the sum of the sizes of the objects in bin, C: the bin capacity function does not need a penalty factor to discourage constraint violations. [Falkenauer, 92] and [Falkenauer, 94B] present results on the BPP as a graph. Falkenauer varied the difficulty of the problems by selecting object sizes so that an optimal solution can have some empty space remaining in each bin. The empty space is called leeway. Although the GGA outperformed FFD, better methods for the BPP exist such as the Reduction Method. Since the GGA utilizes FFD in crossover and mutation, Falkenauer compares the performance of the GGA to that of FFD to show that the better performance of GGA is the result of processing schemata. Falkenauer later added a heuristic hill-climber inspired by the Reduction Method to the GGA. He calls the new system the Hybrid Grouping Genetic Algorithm (HGGA). 100 90 80 70 1601 runs 60 ducin p:IIptimalg 50 solution ‘0 30 20 10 o . . E f i : E e s : 1.5 3 4.5 6 7.5 9 10.5 12 13.5 15 %leeway [:- -ooA FFD] Figure 10: GGA vs. FFD 19 The HGGA produces far more competitive results with the addition of the heuristic hill- climber. The heuristic is valid only for the BPP. The heuristic is added to the crossover and mutation operators. In both operators, the heuristic is inserted before using F F D to reinsert the objects from the queue. The heuristic performs a local optimization as follows: For each bin already in the solution, replacements of up to three objects in the bin by one or two objects in the queue are performed if they make the bin fuller without exceeding the bin capacity. Group 1 Group 2 Group 3 Group A 1 2 3 ,W; ................ .5. ..................... 6. ......... Group B § Group C 7 8 9 Figure 11: Example Demonstrating Mutation-like Behavior of the GGA’s Crossover The GGA’s crossover operator exhibits a mutation-like behavior. Crossover combines schemata from two parents to form children. The GGA’s crossover uses groups as the schemata. Unless the two parents are similar, the objects in a particular group in parent1 are spread among several groups in parent2. Figure 11 illustrates that the preservation of each group in one parent can inhibit the preservation of many groups from the other parent. Only a small portion of the groups present in the children can be obtained from the parents. A heuristic, such as FFD in the case of the BPP, assembles the remainder of the groups. Since a large portion of the schemata in the children is not present in the parents, the crossover operator 20 exhibits a mutation-like property. Figure 11 demonstrates that the preservation of groups in one parent can inhibit many groups in the other parent. Any crossover operator that works with groups as schemata exhibits this mutation-like behavior. 5. The Swapping Heuristic Applied to the Bin Packing Problem 5.1 Rationale for the Swapping Heuristic The Swapping Heuristic (SH) is the product of extensive work with Falkenauer’s HGGA. The solutions obtained with the HGGA are simply not attainable without the use of the Martello and Toth Heuristic. The heuristic, therefore, must be processing domain specific knowledge to help produce these solutions. Is the Martello and Toth Heuristic the best way to utilize this additional knowledge? This question began the work leading to the SH. The SH was designed as another heuristic for use in the HGGA either in conjunction with the Martello and Toth Heuristic or as a replacement. The SH became powerful enough to produce quality solutions on its own, making the GGA unnecessary. Falkenauer’s objective function (Equation 9) provided the GGA a metric for guiding the search. The same metric can be utilized directly by a local search technique. Exchanges can sometimes be found between two bins such that one bin after the exchange is fuller than either bin was before the exchange. These exchanges always increase the value of Falkenauer’s objective function. To prove this, there are two possible cases to consider: the number of bins remains the same (Case 1) and the number of bins decreases by one (Case 2). 21 Equation 9 ifiuf Falkenauer's objective function for BPP: ———-’=' X: the set of objects staying in Y: the set of objects staying in bmr A: the set of objects moving from binx to 1’1"? B: the set of objects moving from bm’ to me C 2m 5.1.1 Case 1: The Number Of Bins Stays The Same A A B Exchange _———’ B Y Y X X me b172,, bmx bin, binx. Figure 12: Case 1 Exchanges Under what conditions is f BPP (Before Exchange) < f BPP (After Exchange)? m m I II2 + II2 + 11.2 < [I2 + II2 + II.2 fix fi. 215% fi. fi. Zfi C.m ixl' iael’ fill}, + fill,2 < fill}, + fill,2 Before Exchange: fillx = (x+a), fill, = (y+b) After Exchange: fill X = (x+b), fill, = (y+a) (x+a)2 +(y+b)2 <(x+b)2 +(y+a)2 xz +2ax+¢2 +y2 +2by+ll2 0 then the value of the objective function increases for a < b If (x — y) < 0 then the value of the objective function increases for a > b Ifa resulting bin is filled more than both starting bins, the objective function always increases. 5.1.2 Case 2: The Number Of Bins Decreases Removed Exchange 3 -——> B X X bin, bm, bm, bzn, X: the set of objects staying in binx. Y: the set of objects staying in bin, A: the set of objects moving from bin, to bin, B: the set of objects moving from bi’h to bin, Figure 13: Case 2 Exchanges Under what conditions is f 3,, (Before Exchange) < f BPP (After Exchange)? __L_ C2(m—1) fill} + fillfi + Zfill,2 C2 < fill; + Zfill,2 3:5. ’" 13:5. ratl’ 2 2 1 2 I (fill, +fill,)— <( 1211,)— m m—l Before Exchange: fill, :2 x, fill, =b After Exchange: fill, = (x+b), bin, is removed. 23 (x2 +b2) < (x+b)2 m m—l x2 +b2 < x2 +2xb+b2 m m—l Value of Falkenauer's objective function increases for all x and b. (x and b are positive values) Falkenauer utilizes a genetic algorithm to optimize bin packing solutions relative to the objective function. It is shown that exchanges of objects between groups can be identified that increase the value of the objective function. Pairs of bins can be examined until no more of these exchanges can be found. This serves as the basis for the SH. 5.2 Description of the Swapping Heuristic Applied to the Bin Packing Problem Section 5.1 shows that gains which result from exchanges of objects between two bins can be used to optimize a solution to the BPP. The objective function value increases if, after an exchange, a resulting bin is fuller than each of the starting bins. Any solution to the Bin Packing Problem can possibly be made better by performing a local optimization. The local search is done by performing exchanges between any two bins such that after the exchange, one bin is fuller (the other is less full) than either bin was before the exchange. The less full bin often benefits the overall solution since it is easier to eliminate by moving the objects into other bins and has added room to accommodate more objects making the elimination of another bin easier. The SH can start with any solution and improve it. Thus, it can be used to enhance the performance of any other bin packing algorithm. An iteration is a pass through every pair of bins. The stopping criterion is a limit to the number of iterations performed in which no beneficial exchange has been 24 start with any initial solution counter=0; while (counterlarge) counter=0; void exchange (bin,,bin,) 1. Let 0 be the union of the set of Objects from bht and the set of Objects from bhy. 2. Compute the sizes of the elements of all binary partitions of 0 which do not exceed C and the number Of objects in the element satisfies the following condition: (number of objects in 0 — object limit) 3 (number of objects) 3 (object limit) 1. Select a partition: If there is exactly one largest partition from step 2, select it. If there is more than one largest partition from step 2, select one at random. 2. Using the selected partition from step 3, place the Objects in the larger element in bht and the objects in the smaller element in bhg. Figure 15: Swapping Heuristic with Object Limit 27 5.3 Worst-Case Performance Research involving algorithms focuses on determining and proving bounds on worst-case performance. This includes the worst-case quality of solution and the wost- case execution time. The worst-case solution is expressed in terms of the optimal solution. Figure 16 shows the instance giving rise to the currently known worst-case solution for the SH. The objects in the optimal arrangement require three bins. The objects in the arrangement produced by the SH require four bins. If this instance is proven to be the worst-case example for the SH, the performance of the SH would obey Equation 10. The worst-case performance, if proved, would be better than that of FFD and other simple methods but not the approximation schemes. Since the SH searches using a single point, the SH working alone can be deceived by such an instance. The SH working in conjunction with a GA can search more thoroughly and would less likely be deceived by such an instance. (:4) (:4) (:3) B * G) en), em) 6+2) Optimal Arrangement (T) 1+2, (gun) l-i-I (:23 (gs...) (g-..) (l-l g...) Arrangement Produced by SH Figure 16: Worst Known Case for the SH 28 Equation 10 SH(I)s30pt(l)+l SH(I): Number of bins required by the SH for instance I 0pt(l): Minimum number of bins required for instance I The worst-case execution time is expressed in terms of the size of the instance. The size of an instance of BPP is n, the number of objects. The SH’s counter makes determining the worst-case execution time difficult. Several runs have been performed to provide some indication of how the execution time increases as the number of objects increases. The runs use objects selected in the range [1,10000] and have bin capacity 10000. The execution times are the product of two parts: the number of iterations and the average time required for each iteration. Figure 19 shows the execution time per iteration of the runs to increase as a function of r22. The number of bins grows proportionally to the number of objects for the same bin capacity. An iteration involves working with every pair of bins. For m bins, (11,359 pairs of bins are analyzed in each iteration. Therefore, the time for each iteration is expected to increase as a function of n’. The number of iterations required are experimentally shown to increase approximately linearly as the number of objects increases. The third column in Table 1 shows that the number of iterations divided by the number of objects generally decreases and the number of objects increases. 29 Table 1: Execution Times for Increasing Number of Objects n Numflteranons w I'VTjglfTIBTgiiIi, ..,.“,.,., ,TIQOQH (53‘¥3!3551;IF3F?LJ>'fi1 Obiects Iterations 5"“ VerTm—e . .. x 1000 "d5 {21:32:2iff:-f3??;:{;§g?i;ff-f}ij§{jgif-‘g:3:i":*;':~:;r.:ii§§§ n 1000 119 119 267 €i44 2000 135 6715 1223 Ei35 3000 167 551' 3461 £104 4000 217 5433 8077 £102 5000 347 69A1 20259 £i45 6000 282 471) 24116 4182 7000 336 481) 39340 4L86 8000 311 38£3 47922 4L54 50000 45000 40000 35000 Execution 30000 Time 25000 (seconds) 20000 15000 10000 5000 0 4000 6000 Number of Objects 8000 Figure 17: Execution Time vs. Number of Objects 30 350 «- 300 I 250 I Number of no " Iterations 150 .. 100 50 0 . : s t : t : : 1 0 1000 2000 3000 4000 5000 6000 7000 8000 Number of Objects Figure 18: Number of Iterations vs. Number of Objects 160 140 120 100 Time per Iteration 80 60 40 20 0 . : s . : 0 2000 4000 6000 8000 Number of Objects Time I Iteration ----- 2.244‘X"2 Figure 19: Time per Iteration vs. Number of Objects 5.4 Results: Bin Packing Problem 5.4.1 Comparison to Standard Methods Table 2 compares the performance of the SH to that of FF, FFD, BF, and BFD. The runs use 1000 objects with integer object sizes selected uniformly random in the given range. Equation 11 provides a lower bound for runs 1 through 9. The performance bound of FFD (Equation 2) provides a tighter lower bound for run 10. These lower bounds may not be achievable. 31 Table 2: Results, Bin Packing Problem, Comparison to Standard Methods Numberofems 1 [1,1000] ' '2ooo ’ "2‘51”” ' :47 "251 247 247" "247 2 [1 .1000] 2500 200 198 200 198 198 198 3 [1,1000] 3000 166 165 166 165 165 165 4 [200, 1 000] 2000 309 302 308 302 297 297 5 [200,1000] 2500 245 240 245 240 238 238 6 [200.1000] 3000 203 201 203 201 198 198 7 [500,1000] 2000 422 417 422 417 400 375 8 [500,1000] 2500 323 313 323 31 3 300 300 9 [500,1 000] 3000 268 267 268 267 250 250 10 [800,1000] 2500 474 457 474 457 446 371 Equation 11 Lower Bound = —— 5.4.2 Comparison to Reduction Method and Hybrid Grouping Genetic Algorithm Martello and Toth tested the Reduction Method using various ranges and bin capacities and found instances with bin capacity C = 150 and integer object sizes selected uniformly random in the range [20,100] to be the most difficult. Falkenauer, however, wanted to know the optimal number of bins for each instance. He 32 accomplished this by using a procedure that selects object sizes so that they exactly fill the bins. Most object sizes are selected uniformly random in the range [20,100]. Some object sizes are selected in the range [20,100] so that they fill the bins completely leaving no space. All bins are full except possibly the last. Figure 20 describes the procedure in detail. Falkenauer generated 20 instances of the ‘Uniforms’ with 1000 objects. For each instance, Falkenauer ran the HGGA until it obtains the optimal number of bins and recorded the time. The SH , similarly, was run until it reaches the optimal number of bins. The HGGA, like the SH, is not guaranteed to determine the optimal number of bins in a finite amount of time. Table 3 and Table 4: use the following: . Theo: Theoretically minimum number of bins required for the instance . Loss: Number of bins in solution minus theoretically minimum number of bins . Eval: Number of objective function evaluations performed by the HGGA. . Time: Execution time in seconds on the machine indicated by footnotes. . Backs: Number of iterations performed during the reduction method. . Passes: Number of passes through the bins. . Speed-Up: HGGA execution time divided by the SH execution time 33 C=150; /* C is the Bin Capacity */ SzC; /* Initialize S, the available to the bin capacity */ for(i=1,i<=rLi-F+) I repeat R= random number generated in the range [20,100]; until (RZS) or (S-RZZO) if (RZS) { s,=S; S=C; } if(S—Rszd { .3 =R; SzS—R Figure 20: Procedure for Creating Instances of the ‘Uniforms’ Table 3 compares the executions times of the SH and the HGGA on the ‘Uniforms’ with 1000 objects. The SH is executed with the following parameter settings on the ‘Uniforms’: Starting object limit = 6, Final object limit=6, number of tries = 20. The execution times listed for the Reduction method and the HGGA in Table 3 are obtained from [Falkenauer, 94A]. The instances are those created by Falkenauer. Falkenauer identifies the ‘Triplets’ as another difficult set of bin packing instances. The ‘Triplets’ object sizes are selected so that three objects exactly fill a bin. The first object size is drawn uniformly from the range [380,490]. That leaves a space S remaining in the bin. The second object is drawn uniformly from [250,S/2). The third 34 object is chosen so that it completely fills the remaining space in the bin, leaving no leeway. These data sets are designed to be extremely difficult bin packing problems. Falkenauer generated 20 instances of ‘Triplets’ of 501 objects. Table 4 compares the execution times of the SH and the HGGA on the ‘Triplets’ instances with 501 objects. The ‘Triplets’ are run with the following parameters: starting object limit = 2, final object limit = 6, number of tries = 20. The instances used in Table 3 and Table 4 are part of a set of Operations Research benchmarks maintained at the Imperial College of Management (http:l/mscmga.ms.ic.ac.uk/info.html). These benchmark instances are available to all researchers to provide a way to compare methods. To date, the SH is the only known method capable of solving these instances in less time than the HGGA, and the time difference is very large. 35 Table 3: Results, Bin Packing Problem, ‘Uniforms’ 1 399 0 2211 2924.7 4 3.5M 3279.0 0 2 16.78 174.3 2 406 0 2948 4040.2 4 5M 4886.6 0 2 16.73 241.5 3 411 0 4958 6262.1 5 8.5M 6606.1 0 2 13.81 359.0 4 411 0 35376 32714.3 5 50M 40285.6 0 14 52.90 618.4 5 397 0 8844 1 1862.0 4 20M 20689.8 0 2 18.25 650.0 6 399 0 2948 3774.3 3 5M 4216.3 0 2 16.80 224.7 7 395 0 2010 3033.2 3 3M 3449.7 0 2 20.58 147.4 8 404 0 7303 9878.8 2 12.5M 12674.4 0 3 19.11 516.9 9 399 0 4355 5585.2 3 4.5M 6874.0 0 2 19.81 281.9 10 397 0 6968 8126.2 5 12.2M 9568.2 0 2 18.12 448.5 11 400 0 2278 3359.1 4 4M 3542.8 0 2 20.29 165.6 12 401 0 6700 6782.3 3 8.1 M 7422.4 0 2 15.26 444.4 13 393 0 1943 2537.4 3 3.2M 2714.0 0 2 20.49 123.8 14 396 0 14137 11828.8 5 20M 23319.4 0 2 17.41 679.4 15 394 0 5762 5838.1 5 5M 6770.9 0 4 25.00 233.5 16 402 0 13802 12610.8 5 20M 20458.4 0 5 24.12 522.8 17 404 0 2278 2740.8 3 3M 3139.6 0 2 14.83 184.8 18 404 0 2077 2379.4 3 3M 2506.4 0 2 18.72 127.1 19 399 0 1005 1329.7 4 1.5M 1353.2 0 2 14.70 90.5 20 400 0 2680 3564.2 5 3M 4109.6 0 2 14.82 240.5 Ave 7058.6 19.9 36 Table 4: Results, Bin Packing Problem, Triplets Distribution ‘z‘fs‘iiz Reduct ' 1 ' 167 i 0 3752 I 1806.7 I '17 I 1.5M 5828.9 0 56 40.62 44.5 2 167 0 3551 1582.2 14 1.5M 3437.4 0 87 67.18 23.6 3 167 0 1809 1234.5 10 1.5M 2358.7 0 44 31.87 38.7 4 167 0 3082 1821.9 13 1.5M 3398.0 0 94 73.49 24.8 5 167 0 5360 2355.2 14 1.5M 3709.8 0 81 62.76 37.5 6 167 0 2881 1424.0 16 1.5M 10624.4 0 89 67.70 21.0 7 167 0 1809 1161.4 16 1.5M 5788.5 0 119 91.80 12.7 8 167 0 2613 1503.7 16 1.5M 5798.9 0 164 128.68 11.7 9 167 0 3685 2138.4 10 1.5M 2991.3 0 52 36.78 58.1 10 167 0 3082 1550.1 18 1.5M 5626.3 0 51 35.98 43.1 11 167 0 2010 1052.9 12 1.5M 3771.4 0 68 50.12 21.0 12 167 0 2814 1334.9 11 1.5M 3063.7 0 128 99.41 13.4 13 167 0 3216 1502.2 20 1.5M 5787.1 0 33 21.17 71.0 14 167 0 5293 1951.0 14 1.5M 4494.9 0 148 108.40 7.8 175 142.33 15 167 0 3216 1473.9 16 1.5M 5929.5 0 151 120.11 12.3 16 167 0 4623 2350.6 14 1.5M 5306.9 0 57 41.53 56.6 17 167 0 2613 1178.8 16 1.5M 5522.0 0 129 110.28 5.2 136 115.63 18 167 0 3551 1754.2 16 1.5M 6277.2 0 203 160.38 10.9 19 167 0 3484 1775.5 13 1.5M 4164.2 0 117 93.33 19.0 20 167 0 4288 2307.2 21 1.5M 6519.4 0 122 98.92 16.9 52 37.23 Ave 1663.0 91.8 37 5.4.3 Comparison to the Open Loop Hybrid Algorithm Bilchev presents results using instances that demonstrate the worst-case performance of First Fit Descending. Five instances are created using m = 1,2. . .,5 0bjectsize(i) = %+ a for 1 S i S 6m objectsi e(i)- — %+ 23 for 6m m L 22 p. i=l Calculate the starting upper bound: Cu 2 maxi , maxms, {p,} ) 2 p, is the sum of all the job lengths. f=I max ,5,“ {p, } is the maximum job length of the instance. Perform a binary search with k iterations. for(I=1; Isk; I=I+l) { C C Calculate the midpoint: C = _LTZ_U if (FFD(C) s m) CU : C; else CL = C; } Figure 21: The Multifit Algorithm 6.2 Dual Approximation Schemes The Dual Approximation Schemes [Hochbaum and Shmoys, 87] provide a polynomial time algorithm with performance given by Equation 15 for any bounded relative error a. 41 Equation 15 DAA(I) 3 (1+ £)Opt(l) DAA(I): Makespan of the schedule produced by the Dual Approximation Algorithm 8: Relative error 0pt(1): Minimum makespan of instance 1. Although these algorithms do run in polynomial time, they have computation I ‘2 complexity of QUE) ] for relative error at most a. For relative error of at most 10% a a = 0.1, their algorithm would run in 001“”). For relative error of at most 5%, their algorithm would run in 0014”"). Although these algorithms have polynomial execution times for any given bounded error, these algorithms are not practical for large n. Their paper outlines the implementation of two methods, 3:1 and e=%. The latter algorithm is non-trivial to implement and its worst case bound is only slightly better than the Multifit Algorithm's. The implementation of the algorithms with smaller 3 are even more difficult. 6.3 Practical Methods Simulated annealing is a common practical search tool. [Rao and lyengar, 94] published results on a variation of the MMP using simulated annealing. Rather than trying to minimize the makespan, they minimize the cost function given by Equation 16. Simulated Annealing initializes the temperature parameter T to a high value Tm. The temperature parameter is gradually decreased until a small enough value for the temperature is reached. At each temperature, the system is perturbed several times. At the end of each set of perturbations, the new configuration is accepted or rejected. The new configuration is always accepted if it has a lower cost function. If the configuration has a higher cost function, the configuration is accepted with probability that decreases by the amount the cost function increases. The probability is 42 Equation 16 f... = in, J): m: The number of machines 1,: The sum of the processing times of jobs scheduled to machine j .. l "' t-ngi p, : Processing time of job 1' Equation 17 -AC/T P accept = 8 AC = C final — C‘inrrral given by Equation 17. A new configuration is generated by pertubating the current configuration. Pertubations for this problem are done using one of these two methods: 1. assignments of the two jobs. Randomly select a job. Relocate the job from the machine in which it is currently assigned to a randomly selected machine. These exchanges coursely optimize the solution. Randomly select two jobs currently assigned to different machines. Exchange the solution. These exchanges make fine adustments to the 43 Generate a Random Configuration C r=r,, While 73>R do I repeat I generate new configuration (7; AC:/(C')—f(C); n = uniformly random number in the range [0,1) if (AC< 0 0r 17< e'AC/T) (?=(7; } until thermal equilibrium is reached; T=F(T); } output (2 Figure 22: Description of the Simulated Annealing Algorithm 7. The Swapping Heuristic applied to the Minimum Makespan Problem 7.1 Rationale for the Swapping Heuristic Section 5.1 provided the basis for applying the SH to the BPP. An approach similar to the one used for the BPP exists for the MMP. In order to reduce the makespan of a schedule, the longest individual machine schedule must be made shorter by rescheduling jobs. Thus, a reasonable strategy is to identify the machines with the longest schedules and attempt to shorten their schedule by exchanging jobs 44 with other machines. This strategy provides the basis for the application of the SH to the MMP. 7.2 Description of the Swapping Heuristic Applied to the Minimum Makespan Problem The SH for the MMP is similar to the SH for the BPP. The SH uses a counter as the stopping criterion. If a successful exchange is performed, the counter is reset. A successful exchange is an exchange between two machines such that at least one machine has a schedule of length r, = Makespan before the exchange and both machines have a schedule of length r, < Makespan after the exchange. Resetting the counter allows the heuristic to continue working as long as it makes progress. The description of the SH applied to the MMP is provided In Figure 23. 45 Use Longest Job First Heuristic or any other method to produce starting solution. counter=0; while (counter<=number_of_tries) I counter++; makespan=determine_makespan(); for (i=1; i<=number_of_bins-l; i++) for (j=i+1; j<=number_of_bins; i++) l i f ( max { machine, , machine, } ==ma ke span) { exchange ( machine, ,machine, ) ; if ( max{machine, ,machine, }