Journal of Heuristics, 5: 437–454 (1999) c 1999 Kluwer Academic Publishers °
A Hybrid Genetic Algorithm for the Single Machine Scheduling Problem DAVID M. MILLER Commerce and Business Administration, University of Alabama, USA HUI-CHUAN CHEN College of Engineering, University of Alabama, USA JESSICA MATSON College of Engineering, Tennessee Tech, USA QIANG LIU McKesson HBOC Co., Atlanta GA, USA
Abstract A hybrid genetic algorithm (HGA) is proposed for the single machine, single stage, scheduling problem in a sequence dependent setup time environment within a fixed planning horizon (SSSDP). It incorporates the elitist ranking method, genetic operators, and a hill-climbing technique in each searching area. To improve the performance and efficiency, hill climbing is performed by uniting the Wagner-Whitin Algorithm with the problemspecific knowledge. The objective of the HGA is to minimize the sum of setup cost, inventory cost, and backlog cost. The HGA is able to obtain a superior solution, if it is not optimal, in a reasonable time. The computational results of this algorithm on real life SSSDP problems are promising. In our test cases, the HGA performed up to 50% better than the Just-In-Time heuristics and 30% better than the complete batching heuristics. Key Words: sequencing, scheduling, genetic algorithm
1.
Introduction
The heuristic solution procedure discussed in this article was developed to solve a scheduling optimization problem faced by a plant in the automotive supply chain. The plant was interested in increasing their productive use of press time through production schedules that minimized non-value added part changeover time while keeping inventory and backlog costs as low as possible. The underlying optimization problem can be characterized as a single machine scheduling problem with sequence dependent setups and a fixed planning horizon. It is a NP-hard problem, which necessitated that a heuristic solution approach be devised. In this paper, we describe that procedure, along with the problem it is designed to solve, as well as computational results from use and experimentation with the procedure. The heuristic is a hybrid genetic search algorithm. The Wagner-Whitin procedure is used for local searching.
438 2.
MILLER ET AL.
Motivating case
The single machine, single stage scheduling problem with sequence dependent setup times occurs in many different manufacturing environments. Examples include setups involving a changeover of colors in the production of plastics, die changeovers in metal processing, and changeovers for roll slitting in the paper industry. The specific problem investigated in this paper was motivated by our experience with the scheduling problem faced by a manufacturer of automotive parts. The manufacturing environment at the plant is composed of two main production areas: the assembly area and the press shop. Scheduling in the press shop is characterized by the single machine, single stage scheduling problem with sequence dependent setup times and due dates, as explained below. The press shop produces a total of over eight hundred different component parts using sixty progressive dies on eleven presses. The component parts are placed in an intermediate buffer storage area and then pulled as needed by the just-in-time assembly lines. Due to requirements of press tonnage and bed size, the progressive dies are press dependent. Thus, the dies are preassigned to a specific press, resulting in the need to schedule each press independently, i.e., the single machine scheduling problem. Demands on the assembly lines drive the demands in the press shop, which are calculated and reported through a Material Requirements Planning (MRP) system. Using the MRP demand information, schedules are generated daily in the press shop for a ten-day rolling planning horizon. Demands are deterministic and single stage within this framework, and due dates occur daily throughout the planning horizon. To meet the demand requirements, several products, sometimes as many as fifteen, must be produced on each press each day. Production capacity is limited by the production hours available each day. Scheduling of the individual presses is complicated both by the daily due dates and by the sequence dependent nature of setup times. Although there is a storage buffer between the press shop and the just-in-time assembly lines, meeting daily due dates is still crucial. The cost of a backorder in the press shop may be to shut down one or more assembly lines within the plant. A shutdown can result not only in the cost of the downtime within the plant, but also in significant monetary penalties if the outcome is a late shipment to a customer. Thus, the cost of backorders is very high. In any scheduling system, the cost of the in-process inventory should also be considered, so production prior to due date incurs an inventory carrying cost. However, at this plant the inventory carrying cost is considered to be much lower than the cost of backorders. The setup of a press to produce a different part requires one or more of the following setup tasks. ¥ ¥ ¥
Changeover of the progressive die (master die change) Changeover of a complete station of the progressive die (sub-die change) Changeover of one or more components of a station (die component change)
One would expect setups involving master die changes to require the most time. However, this is not always the case for the progressive dies at the plant. Setups that require several die component changeovers can actually result in a greater setup time than would be required for a master die change. Thus, setup times are sequence dependent, and a heuristics such
A HYBRID GENETIC ALGORITHM
439
as grouping products only by master die to determine sequence, may not produce the best sequence. Because the production rates of the presses at the plant are high, the production cycles tend to be short. A demand of several hundred parts may require a production cycle of only five minutes. Setup times, on the other hand, can range from a minimum of fifteen minutes to a maximum of several hours, depending upon the production sequence. Setups often constitute a larger proportion of time during the workday than does production. Even a small percentage reduction in setup time by making better sequencing decisions can yield substantial improvements in production capacity. Thus, given the required demands and due dates, the scheduling objective for the press shop at Arvin is to determine the best sequence and lot sizes for each press. An investigation of methods to achieve this objective is the motivation for the research reported here. 3.
Relevant literature
The single machine scheduling problem address here traditionally solved based on either single machine scheduling with lot sizing approach (Vollman et al., 1984; Wagner and Whitin, 1958), or the traveling salesman problem (TSP) approach (Feo, Sarathy, and McGahan, 1996; He and Kusiak, 1992; Ovacik and Uzsoy, 1994; White and Wilson, 1977), or genetic algorithms (Lee and Choi, 1995; Rubin and Ragatz, 1995; Yagiura and Ibaraki, 1996). However, most of the solution procedure of these traditional approaches are either over-simplified, which sacrifices performance, or too complex, which sacrifices efficiency. For example, although lot sizing and sequencing decisions are interdependent, their interaction is not explicitly considered in many approaches. Instead, most research has concentrated on either the lot sizing aspect (as for example, the Economical Lot Scheduling Problem and the Capacitated Lot Sizing Problem) or the sequencing aspect (as the TSP). Thus, the production schedule is frequently finalized in a two step procedure where the lot sizing decision precedes the sequencing decision or vice versa. Much of the work in this area has concentrated on the feature of sequence dependent setups. Here, minimizing total cost equates to solving the well-known TSP problem. There exist a number of good solution procedures for the TSP. The most popular approach in these procedures has been branch-and-bound. Balas and Toth (1986) give an excellent summary and evaluation of these branch-and-bound methods. Golden and Stewart (1986) provide a summary of construction and improvement heuristics that have been developed for TSP. There are a number of articles focused on applying the TSP in single machine scheduling. White (1966) and White and Wilson (1977) developed a heuristic solution procedure similar to the nearest neighbor rule. He and Kusiak (1992) presented a mixed integer programming model for it. Ovacik and Uzsoy (1994) illustrated a dynamic programming approach for this problem. Feo, Sarathy, and McGahan (1996) developed a new heuristic procedure, which they named GRASP for Greedy Randomized Adaptive Search Procedure. Although these works considered scheduling with sequence dependent setups, lot sizing was not considered in any of their models and solution procedures. Separately, there is a large body of published work in the lot sizing area. In order to minimize the total ordering cost and inventory cost, Wagner and Whitin (1958) formulated an early dynamic version of the economic lot-sizing model. Vollman, Berry and Whybark
440
MILLER ET AL.
(1984) developed Wagner and Whitin’s approach, considered some new features in master production scheduling. Neither approach considered the feature of sequence dependent setups. Several authors have combined sequencing and lot sizing in a sequence dependent setup environment. Smith-Daniels and Smith-Daniels (1986) examined a sequence dependent scheduling problem in a packaging industry, in which they tried to minimize the total setup cost, inventory cost and backorder cost. Fleischmann (1994) developed a two-stage heuristic procedure to obtain a solution. Arosio and Sianesi (1993) developed a mixed integer programming model with an objective function that minimizes the inventory carrying costs, production costs and outsourcing cost. Cho, Kim and Kim (1994) formulated a mixed integer programming model based on group technology. Noting this problem is known to be NP-hard, they developed a two-stage heuristic procedure to obtain solutions. While these authors considered sequencing and lot sizing simultaneously, multiple periods are not included in their model and solution procedure. Multiple time periods are an important feature of the problem we are addressing in this paper. Sahay (1997) investigated the SSSDP with lot sizing, setup carryover and multiple time periods (due dates). He developed several models and a three-stage heuristic solution procedure that focused on just-in-time sequencing. This paper extends his basic work, with the exception of setup carryover, by incorporating a genetic algorithm solution procedure. In recent years, the use of metaheuristic search procedures for combinatorial optimization problems has attracted attention. Glover and Greenberg (1989) presented a review of five methods: genetic algorithm, neural networks, simulated annealing, tabu search, and target analysis. They conclude that these methods have shown promise in some investigations, but how to implement them in real life problems and their efficiency still need further research and effort. There are some authors who have studied the application of genetic search for solving the single machine scheduling problem. Goldberg (1986) provides a good introduction to genetic algorithms, including a summary of applications. Rubin and Ragatz (1995) developed a genetic search procedure to minimize the total tardiness in single machine scheduling problems in a sequence dependent setup environment. Having compared their results with results obtained in a branch-and-bound procedure, they conclude a genetic search algorithm is competitive with, if not superior to, branch-and-bound in finding a good (but not necessary optimal) schedule fairly quickly. While they considered sequence dependent setups in their problem, their formulation was only for a single time period. Lee and Choi (1995) presented a GA procedure for problems of sequencing a set of jobs on a single machine with distinct due dates and general early-tardy penalty weight. After testing different genetic operators, they concluded that uniform order based crossover and intra-block mutation operator, along with N best reproduction without duplicates, are good choices in this kind of problem. While they considered scheduling in a fixed planning horizon just as we did in our problem, they did not consider the feature of sequence dependent setups. Yagiura and Ibaraki (1996) investigated several metaheuristics procedures in single machine scheduling problems. In their work, they tested genetic algorithm, simulated annealing, tabu search and random multi-start local search. They concluded that a GA combined
441
A HYBRID GENETIC ALGORITHM
with local search is quite effective if longer computational time is allowed, and its performance is not sensitive to crossover. Unfortunately, they did not consider sequence dependent setups. 4.
Problem formulation
The single machine scheduling problem has many variations due to a variety of operating environments and objectives. In this paper we focus on the single machine, single stage scheduling problem in a sequence dependent setup time environment within a finite planning horizon. The objective is to minimize the sum of setup cost, inventory cost, and backlog cost. We assume that each period t (t = 1 . . T ) is a large time bucket, wherein multiple changeovers and production of multiple products are possible and each product i (i = 1 . . N ) can only be scheduled once in each period. Mathematically, the objective function of this problem can be formulated as follows: Min
XX t
à h i Iit + gi βit +
X
! Si j yi jt
j6=i
i
where h i is inventory cost of product i per unit per time period Iit is inventory units of product i at the end of period t gi is backlog cost per unit of product i per time period βit is backlog units of product i in time period t Si j is setup cost of changeover from product i to j yi jt is changeover units from product i to j in period t (yi jt = 0 or 1) subject to the following constraints: 1. Inventory balance constraints Ii,t−1 + xit − Iit − βi,t−1 + βit = dit
∀i, t
where xit is the production quantity of product i in period t dit is demand of product i in period t 2. Production time capacity constraint X i
where
à pit xit +
X j6=1
! ti j yi jt
≤ bt ,
∀t
442
MILLER ET AL.
pit is time required to produce product i in period t ti j is changeover time from product i to product j bt is capacity in terms of production time in period t 3. Setup constraints X yi jt , x jt ≤ M
∀ j, t (product j produced only if there is setup of j)
i6= j
where M is a very big number and the value of x jt will either be positive or 0 depending on yi jt being 1 or 0 respectively. 4. Assignment constraints X yi jt ≤ 1, ∀i, t (At most one change from i is possible in a time period t) j
X
yi jt ≤ 1, ∀ j, t (At most one changeover to j is possible in a time period t)
i
XX t
yi jt = 1, ∀ j (Only one changeover to j in the planning horizon)
i
5. Sub-tour breaking constraints XX yi jt ≥ 1, ∀t Q ⊂ V, V is the set of all products (i and j) i∈Q j∈Q
Q and Q 0 are the proper subsets of V and Q is complementary to Q 0 . Note that the above scheduling problem is a mixed integer programming problem. Unfortunately, an optimal solution can be found only for small problems. For moderate size and large-scale problems, no existing analytical algorithms can solve them within a reasonable time. In a typical application of this model at the press shop of the plant in question, the number of integer variables for a thirty-product problem within a ten-day planning horizon is about ten thousand. In addition, the total number of constraints is more than one billion. Traditionally, a heuristic algorithm solves this type of problem. The solution may be far from the optimal solution. To resolve this problem, a genetic algorithm (GA) is proposed to perform a global search for superior, if not optimal, solutions. In addition, GAs consider many solutions in the search space simultaneously while performing operations individually and independently on each solution in order to improve the performance. Thus, they are highly adaptable to parallel computation and more attractive for this type of large-scale problem. 5.
Genetic algorithms
A genetic algorithm is an optimal search method motivated by natural selection and natural evolution. It maintains a population where each individual is characterized by its chromosome. Each chromosome consists of a sequence of genes. In this paper, a gene corresponds
A HYBRID GENETIC ALGORITHM
443
to one of N products and a chromosome corresponds to a solution (a sequence of products). The quality of a chromosome is measured by the objective value of its sequence. A population is a collection of solutions or chromosomes. To mimic natural selection GA uses the quality of a chromosome to determine its fitness, which is then used to determine the probability that a chromosome will survive to the next generation. GA generates offsprings from a pair of chromosomes in the population. Chromosomes with high fitness values will survive and those with low fitness values will die out. The process is designed to produce a new generation that tends to have chromosomes that are better than those in the previous generation. In the standard GA, a finite length of string represents each chromosome. A string may consist of binary bits, integers, or characters. A problem solution must be encoded in strings. The encoding scheme is important because it has a significant effect on the accuracy of the GA. In our problem, we represent a solution (or chromosome) by an integer string stored in an array S. The length of string is equal to the total number of products needed in the planning horizon. Any products that are demanded for different due dates are treated as multiple products. The value of an allele, which is used to represent the period when this demand will be produced, is an integer. For example, to represent the demand for product 8 to be produced in period 9, the corresponding chromosome allele is S[8] = 9. If there are 40 products needed in the planning horizon, the length of each chromosome is 40. Basically, the GA procedure includes chromosome reproduction, chromosome crossover, gene mutation, chromosome fitness, and natural selection. The reproduction operator will reproduce the next generation based on their fitness value. The crossover operator, the most important step in a GA, exchanges a pair of sub-strings of their parents to generate offspring chromosomes. The mutation operator randomly selects some of the genes of each chromosome and changes their values. In this problem, the GA is implemented in the following way. (1) Reproduction scheme & evaluation. The reproduction scheme adopted here is an elitist ranking in which the individuals are sorted by their fitness value. Then, the best n individuals will survive to the next generation. In the next generation, the new n offsprings, which are generated from the previous generation, will be put in the “gene pool”. Then, the gene pool is sorted and the n best individuals are selected to survive to the next generation. In this study, the cost function consisted of the setup cost, inventory carrying cost, and backlog cost. This function is used for the evaluation of each chromosome. (2) GA operators. The two-point ring-like crossover operator is employed because it offers a less positional bias than the one-point standard crossover without introducing any distribution bias. Other ordered crossover operators, such as PMX and others, have also been tested. But their performance is almost the same as the two-point ring-like operator. The mutation operator employed here is a constrained mutation operator. It possesses the characteristics to forbid any attempt to mutate a job later than its due date. The mutated position is randomly chosen. The value in it will be changed to another randomly generated number that is less than or equal to its due date.
444
MILLER ET AL.
Inversion is applied in the HGA approach in which a contiguous section of the chromosome is inverted. In HGA, the chromosome is treated as a ring. Inversion at a low rate helps introduce new building blocks into the population. (3) GA parameters. Another important feature of the GA procedure is the operator rates. It has become widely recognized that variable operator rates are useful for maintaining diversity in the population and, hence, for alleviating the premature convergence problem. A crossover rate of 50% and a mutation rate of 2.5% are used in this application. The most attractive feature of the GA optimization lies in its attempt to explore the search space in a global fashion by studying the entire population of the chromosomes. However, the implementation of a standard GA often encounters the problem of either premature convergence to the local optima, or of an inefficient search requiring a long time to reach an optimal solution (Goldberg, 1989). To overcome these difficulties, we propose a hybrid genetic algorithm. This algorithm uses the modifications to the standard GA as described above. Other aspects of the procedure are discussed in the following section. 6.
Hybrid genetic algorithm
The proposed hybrid genetic algorithm (HGA) based on the standard GA, incorporates different search techniques to obtain certain desired characteristics of the population and to improve the performance. As displayed in figure 1, the HGA procedure contains the following steps: 1. 2. 3. 4. 5.
Generate an initial population. Produce a new generation. Improve the characteristics of the population. Enforce the feasibility. Repeat Steps 2–4 until the prescribed stop criterion is satisfied.
Each step will be explained in the following sections. (1) Generate an initial population. In this step, initial chromosomes (or individuals), that are the initial solutions, are generated under some controls. For example, one initial solution is generated based on a Just-in-Time (JIT) heuristics, in which demands are produced only on the due date. Then, the HGA randomly generates other initial solutions until the population size is full. We let the population contain a maximum of 6 chromosomes dues to the consideration of time constrain in this single machine problem. In the plant’s real operations environment, the production schedule must be generated daily (early in the morning), and there is only a small time slot available for scheduling. A larger population size would take too long to generate a schedule. In order to test the effectiveness of this parameter, we have investigated solutions of problems with different population sizes. It is found that there is no significant improvement in the final solution when applying a larger population size (say, 10, 16, or 20). Thus, a population consisting of 6 chromosomes was chosen. This population size possesses the desired effectiveness as well as the required efficiency within the plant’s time constraint.
A HYBRID GENETIC ALGORITHM
Figure 1.
445
Structure of hybrid genetic algorithm.
In the process of initialization, the feasibility of each solution is checked to see whether all constraints in the model explained in Section 4 are satisfied. If feasibility fails, another individual solution will be generated randomly. (2) Produce a new generation. In step 2, the HGA uses the standard GA procedure to generate offsprings and conduct the global search. The constraint of lot sizing is considered in this step and the sequence dependent feature is ignored. In addition, the HGA assigns products to each period t subject to the model assignment constraints. There are four GA operators, which are reproduction, crossover, mutation, and inversion, are employed in the HGA. They are implemented in the same way as the standard GA described in the last section. (3) Improve the characteristics of the population. After the GA generates a new population, some special characteristics, such as meeting due dates and inventory balance, are desired. A hill-climbing technique based on the Wagner-Whitin algorithm (WWA) is applied to obtain these desirable characteristics through a local search. As a result, the feasibility is improved, the setup cost is decreased, and the total cost is reduced. A set of
446
MILLER ET AL.
heuristic rules stated below is employed to guide the search for finding the best production combination within the searching space for each chromosome. Based on the problem-specific knowledge, we have identified the following properties of this problem. • • • •
Backlog cost is almost 1000 times higher than inventory cost Backlog cost is higher than setup cost in most cases Inventory cost is much lower than setup cost Setup cost within the same master die group is lower than that between different master die groups • Setup cost is mainly determined by the master die setup cost Combined with these properties and propositions of the WWA, we developed three productshifting heuristic rules for reducing the total cost. The first rule shifts a production to a period where the same product setup exists; the second rule shifts a product to a period where the same master die setup exists; and the third rule shifts a product to a period without the same master die setup. The first two shifting rules are implemented during the hill-climbing search to reduce setup cost. The third shifting rule is implemented by the GA through shifting products to an earlier period to reduce backlog cost. Since the backlog cost is much greater than the inventory cost, the HGA will mainly execute the left-directed shifting to minimize the total cost. (4) Enforce the feasibility. In this step, the Branch-and-Bound method used for TSP is employed to determine the sequence of products in each chromosome, and the feasibility of each chromosome is checked. If the feasibility is violated, the backward-forward heuristic procedure is employed to enforce the feasibility. The difficulty of this problem lies in the large number of constraints. There are some capacitated constraints that must be satisfied by all solutions. Some constraints are ensured in the process of generating new solutions but the production capacity constraint is checked and ensured after sequencing. If it is violated, the HGA employs the backward-forward heuristics to ensure the production capacity. The backward-forward heuristics include the following steps: 1. If period t is over-capacitated, move the products produced at the start of period t to the end of period t − 1 until period t is not over-capacitated. 2. Repeat step 1 for all t, starting from t = 10 to t = 1. 3. If period 1 is still under-capacitated, which means the production capacity constraint is satisfied, the HGA exits the backward-forward procedure; otherwise go to the forward operation in Step 4. 4. If period t is over-capacitated, move the products produced at the end of period t to the start of period t + 1 until t is not over-capacitated. 5. Repeat step 4 for all t starting from t = 1 and stopping at t = 10. 6. If period 10 is still under-capacitated, which means the production capacity constraint is satisfied, the HGA exits the backward-forward procedure; otherwise the
A HYBRID GENETIC ALGORITHM
447
backward-forward procedure fails to enforce production capacity and the HGA will discard this infeasible solution and return to the TSP for an alternative solution. (5) Repeat Steps 2–4 until the prescribed stop criterion is satisfied. Now, the fitness value of each chromosome is obtained in this step. In this paper, the objective function of the model given in Section 4 is used for the fitness of each chromosome. Then the HGA checks the stop criterion. If it is satisfied, HGA outputs the best solution in the final population and exits. Otherwise, HGA repeats steps 2–4. 7.
Computational results
In this section we discuss the computational results of the HGA developed for the single machine scheduling problem. The HGA developed in this study is coded in Visual Basic and executed in a Windows NT environment. In order to balance performance and efficiency, the HGA employed the generation limit as the stop criterion. The HGA terminates when it iterates the pre-set number of searching generations. In our tests, we take the plant’s actual press requirements, which are their Material Requirements Planning data, for each planning horizon as input data, and try to minimize the total cost. All parameters also come from the plant’s management information system. The first type of test compares the performance between the Standard GA (SGA) and the HGA. Both of them have the same population size. The result of one sample is illustrated in figure 2. In this type of test, the genetic operators are the same in both methods except the HGA embeds one hill-climbing technique, the Wagner-Whitin algorithm. From figure 2, it is shown that the HGA improves much faster than the SGA, which is an advantageous feature of the HGA. In addition, the execution time for the HGA is almost the same as the SGA. The time spent in the hill-climbing procedure is negligible. In all our test cases, the HGA performed at least as efficiently as the SGA.
Figure 2.
Comparison between HGA and standard GA.
448
Figure 3.
MILLER ET AL.
Comparison in HGA, JIT and the complete batching approach.
The second type of test compares the performance among the HGA, the Just-in-Time (JIT) heuristic, and a “complete” batching heuristic. This complete batching procedure tries to produce the entire set of a product’s requirements in the earliest possible time bucket allowed by production capacity. The result of the same sample is illustrated in figure 3, which shows that the HGA can obtain a much better solution than the JIT heuristic and the complete batching heuristic. In this real world test case, the HGA performs up to 50% better than the JIT heuristic and 30% better than the batching heuristic. A detailed cost comparison among them is given in Tables 1 and 2, and a description of the cost changes in the first 50 generations of the HGA is depicted in figure 4. Table 1.
Cost comparison in HGA and JIT heuristic.
Gen.
Hybrid total cost
Genetic setup
Algorithm inventory
Backlog
JIT total cost
Heuristic setup
Icost
Bcost
0
936.9363
936.9363
0
0
936.9363
936.9363
0
0
1
685.5151
633.9667
51.5485
0
936.9363
936.9363
0
0
5
615.4512
557.8907
57.5605
0
936.9363
936.9363
0
0
10
563.0367
485.8186
77.219
0
936.9363
936.9363
0
0
15
549.1564
469.8026
79.3536
0
936.9363
936.9363
0
0
20
527.5374
441.7746
85.7627
0
936.9363
936.9363
0
0
25
527.0311
439.1053
87.9258
0
936.9363
936.9363
0
0
30
488.4542
400.3999
88.0542
0
936.9363
936.9363
0
0
35
488.4542
400.3999
88.0542
0
936.9363
936.9363
0
0
40
488.4542
400.3999
88.0542
0
936.9363
936.9363
0
0
45
488.4542
400.3999
88.0542
0
936.9363
936.9363
0
0
50
488.4542
400.3999
88.0542
0
936.9363
936.9363
0
0
449
A HYBRID GENETIC ALGORITHM Table 2.
Cost comparison in HGA and batching approach.
Gen.
Hybrid total cost
Genetic setup
0
936.9363
1
685.5151
5
Algorithm inventory
Backlog
Batching total cost
Heuristic setup
Icost
Bcost
936.9363
0
0
685.5151
633.9667
51.55
0
633.9667
51.5485
0
685.5151
633.9667
51.55
0
615.4512
557.8907
57.5605
0
685.5151
633.9667
51.55
0
10
563.0367
485.8186
77.219
0
685.5151
633.9667
51.55
0
15
549.1564
469.8026
79.3536
0
685.5151
633.9667
51.55
0
20
527.5374
441.7746
85.7627
0
685.5151
633.9667
51.55
0
25
527.0311
439.1053
87.9258
0
685.5151
633.9667
51.55
0
30
488.4542
400.3999
88.0542
0
685.5151
633.9667
51.55
0
35
488.4542
400.3999
88.0542
0
685.5151
633.9667
51.55
0
40
488.4542
400.3999
88.0542
0
685.5151
633.9667
51.55
0
45
488.4542
400.3999
88.0542
0
685.5151
633.9667
51.55
0
50
488.4542
400.3999
88.0542
0
685.5151
633.9667
51.55
0
Figure 4.
Comparison in cost changing curve.
In addition to the first sample that has been used to illustrate the basic concept, another 46 samples were collected to test the HGA performance. In our test phase, two different types of comparisons had been performed to evaluate the difference between HAG and SGA. They are listed as follows. 1. A comparison on the percentage of improvement of HGA and SGA over JIT heuristics is shown in figure 5(a). Figure 5(b) shows the percentage of improvement of HGA over SGA when both started with JIT heuristics.
450
MILLER ET AL.
(a)
(b) Figure 5.
Comparison in HGA and SGA started with JIT heuristics.
2. A comparison on the percentage of improvement of HGA and SGA over the complete batching heuristics is shown in figure 6(a). Figure 6(b) shows the percentage of improvement for HGA over SGA when both started with batching heuristics. Compared to the JIT heuristics, the average improvement of HGA over SGA in case 1 (in which both started with the JIT heuristics) is 35%. The maximum and minimum
451
A HYBRID GENETIC ALGORITHM
(a)
(b) Figure 6.
Comparison in HGA and SGA started with the complete batching heuristic.
452
MILLER ET AL.
Figure 7.
Comparison in HGA and SGA started with complete batching/JIT heuristics.
improvements are 43% and 18% respectively. In case 2 (in which both started with the complete batching heuristics), the average improvement of HGA over SGA is 21%, with a maximum of 32%, and a minimum of 6%. To investigate the sensitivity of initial solution for HGA and SGA, we performed tests for two different initial solutions, i.e. JIT initially and complete batching initially. A comparison between HGA and SGA for various initial solutions is illustrated in figure 7. The figure shows HGA from complete batching initially has the best performance. In addition, although SGA started with the complete batching initial is the best one in all SGA initial options, the figure 7 also suggests that the HGA started with JIT initial still outperforms the SGA started with complete batching initial. From the above test results, we conclude that the HGA outperforms the SGA for this single machine problem. The efficiency of the HGA is quite encouraging as it often can obtain a superior solution within a reasonable running time. 8.
Summary and conclusion
The purpose of this research was to develop an efficient as well as effective metaheuristic procedure to solve a class of single machine scheduling problems. The work reported here was done in conjunction with a muffler manufacturing plant in our area. In our approach, a unique idea is introduced in the structure of the HGA, in which we combined three searching techniques, Standard GA, Wagner-Whitin algorithm and TSP modeling. A standard GA is applied to do the global searching, working to obtain the best solution area. A Wagner-Whitin algorithm is applied to do the local searching, in which a local optimal can be obtained. TSP modeling is applied to sequence products in each
A HYBRID GENETIC ALGORITHM
453
period, so that the best sequence of products in each period can finally be obtained. Its performance can also be improved by exploiting any information that is available in addition to the objective function. Experiments using real life data showed the solutions generated by the HGA approach were much better than JIT and batching, and its efficiency is much faster than the standard GA approach. The results are quite encouraging. References Arosio, M. and A. Sianesi. (1993). “A Heuristic Algorithm for Master Production Schedule Generation with Finite Capacity and Sequence Dependent Setups,” International Journal of Production Research 31(3), 531–553. Bellman, R., A.O. Esogbue, and I. Nabeshima. (1982). Mathematical Aspects of Scheduling and Applications. Pergamon Press. Brandimarte, P. and A. Villa. (1995). Optimization Models and Concepts in Production Management. Gordon and Breach Publisher. Caveny, R.S. (1994). “Max-Min Allocation of a Multi-item, Single Machine Production System with Different Setup Times,” PhD Dissertation, Department of Management Science and Statistics, The University of Alabama. Cheng, T.C.E., Z.L. Chen, and C. Oguz. (1994). “One Machine Batching and Sequencing of Multiple-Type Items,” Computers and Operations Research 21(7), 717–721. Cho, Kyu-Kab, Kap Hwan Kim, and Chan Soo Kim. (1994). “A Heuristic Lot-sizing Algorithm for a GT Cell,” Computers and Industrial Engineering 26(1), 1–9. Dilts, D.M. and K.D. Ramsing. (1989). “Joint Lot Sizing and Scheduling of Multiple Items with Sequence dependent Setup Costs,” Decision Science 20, 120–133. Dobson, Gregory, U.S. Karmarkar, and Jeffery L. Rummel. (1987). “Batching to Minimize Flow Times on One Machine,” Management Science 33(6), 784–789. Doll, C.L. and D.C. Whybark. (1973). “An Iterative Procedure for the Single Machine Multi-Product Lot Scheduling Problem,” Management Science 20, 0–55. Driscoll, W.C. and H. Emmons. (1977). “Scheduling Production on One Machine with Changeover Costs,” AIIE Transactions 9, 388–395. Feo, Thomas A., Kishore Sarathy, and John McGahan. (1996). “A GRASP for Single Machine Scheduling with Sequence Dependent Setup Costs and Linear Delay Penalties,” Computers and Operations Research 23(9), 881–895. Fleischmann, Berhard. (1994). “The Discrete Lot Sizing and Scheduling Problem (DLSP) with Sequence Dependent Setup Costs,” European Journal of Operational Research 75(1), 395–404. Galvin, T.M. (1987). “Economic Lot Scheduling Problem with Sequence Dependent Setup Costs,” Production and Inventory Management, First Quarter, 96–105. Glover, F. and H.J. Greenberg. (1989). “New Approaches for Heuristic Search: A Bilateral Linkage with Artificial Intelligence,” European Journal of Operational Research 39, 119–130. Goldberg, David E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, Inc. Gopalakrishnan, Mohan. (1992). “Tool Requirement Planning and Lot Size Scheduling in Large Time Bucket Settings with Setup Carryover.” PhD Dissertation, Department of Management Science and Statistics, The University of Alabama. He, Weihua and Andrew Kusiak. (1992). “Scheduling Manufacturing Systems,” Computers in Industry 22(1), 163–175. Heuts, R.M.J., H.P. Siedel, and W.J. Selen. (1992). “A Comparison of Two Lot Sizing Sequencing Heuristics for the Process Industry,” European Journal of Operational Research 59(1), 413–424. Hu, T.C., T.S. Kuo, and F. Ruskey. (1987). “Some Optimal Algorithms for Scheduling Problems with Changeover Costs,” Operations Research 39, 94–99. Lawler, E.L., J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys. (1986). The Traveling Salesman Problem. A Wiley-Interscience Publication.
454
MILLER ET AL.
Lee, C.Y. and J.Y. Choi. (1995). “A Genetic Algorithm for Job Sequencing Problems with Distinct Due Dates and General Early-Tardy Penalty Weights,” Computers and Operation Research 22(8), 857–869. McKinney, Jacqueline. (1980). “Optimal Multi-Product Scheduling on One Machine over a Finite Horizon.” PhD Dissertation, Johns Hopkins University, UMI Dissertation Services. Ovacik, I.M. and R. Uzsoy. (1994). “Rolling Horizon Algorithms for a Single Machine Dynamic Scheduling Problem with Sequence Dependent Setup Times,” International Journal of Production Research 32(6), 1243– 1263. Pinedo, M. (1995). Scheduling: Theory, Algorithms and Systems. New Jersey: Prentice Hall. Poon, P.W. and J.N. Carter. (1995). “Genetic Algorithm Crossover Operators for Ordering Applications,” Computers and Operations Research 22(1), 135–147. Rinooy Kan, A.H.G., B.J. Lageweg, and J.K. Lenstoa. (1975). “Minimizing Total Cost in One Machine Scheduling,” Operations Research 23, 908–927. Rubin, Paul A. and Gary L. Ragatz. (1995). “Scheduling in Sequence Dependent Setup Environment with Genetic Search,” Computers and Operations Research 22(1), 85–99. Sahay, Rakesh. (1997). “Scheduling in a Sequence Dependent Setup Time Environment with Setup Carryovers.” Master’s Thesis, Department of Industrial Engineering, The University of Alabama. Sianesi, A., M. Croci, and A. Meroni. (1993). “An Improvement of the LP-Based Aucamp Model for the Solution of Multi-Item Lot-Sizing Capacity-Constrained Problem,” Production Planning and Control 4(3), 223– 238. Smith-Daniels, Vickie L., and Dwight E. Smith-Daniels. (1986). “A Mixed Integer Programming Model for Lot Sizing and Sequencing Packaging Lines in the Process Industry,” IIE Transactions 18(3), 278–285. Vollman, Thomas E., William L. Berry, and D. Clay Whybark. (1984). Manufacturing and Control Systems. Richard D. Irwin, Inc. Wagner, H.M. and T.M. Whitin. (1958). “Dynamic Version of the Economic Lot Sizing Model,” Management Science 5(1), 89–96. White, C.H. and Richard C. Wilson. (1977). “Sequence Dependent Setup Times and Job Sequencing,” International Journal of Production Research 15(2), 191–202. Yilmaz, Cengiz. (1981). “A Lot Sizing Technique.” PhD Dissertation, The University of Iowa, UMI Dissertation Services. Yagiura, M. and T. Ibaraki. (1996). “Metaheuristics as Robust and Simple Optimization Tools,” 1996 IEEE International Conference on Evolutionary Computation. pp. 541–546.
