Int J Adv Manuf Technol (2009) 43:1251–1260 DOI 10.1007/s00170-008-1808-7

ORIGINAL ARTICLE

Genetic algorithms for the multiple-machine economic lot scheduling problem Hainan Sun · Huei-Chuen Huang · Wikrom Jaruphongsa

Received: 6 July 2008 / Accepted: 17 October 2008 / Published online: 12 November 2008 © Springer-Verlag London Limited 2008

Abstract This paper focuses on an extension of the Economic Lot Scheduling Problem, which schedules productions of products on multiple identical machines. The objective is to minimize the total average production and inventory costs per unit time for all products. We develop a genetic algorithm under the Common Cycle policy and compare it with an existing heuristic under the same policy. Computational results show that our genetic algorithm outperforms the existing heuristic and its running time does not increase much even for high utilization problems, while the latter requires substantial time to solve most of the high utilization problems. In addition, a genetic algorithm under the Extended Basic Period and Power-of-Two policy is proposed. This new heuristic performs much better, especially when the number of machines is small and the machine utilization is not very high.

1 Introduction The Economic Lot Scheduling Problem (ELSP) is a single-machine production problem frequently encountered in the manufacturing industry. In this paper, an extension of the problem to multiple machines is studied. This problem is referred to as the Multiple-machine Economic Lot Scheduling Problem (MELSP), which determines the allocation, the lot sizes, and the production schedule of multiple products on a given number of identical machines. The objective is to find a production schedule that minimizes the long-run average cost per unit time of production and inventory for all products. The problem has the following characteristics: – –

Keywords Economic lot scheduling · Genetic algorithm · Power-of-two

– –

H. Sun TECH Semiconductor Pte. Ltd., 1 Woodlands Industrial Park D, Street 1, 738799, Singapore, Singapore e-mail: [email protected] H.-C. Huang (B) · W. Jaruphongsa Department of Industrial and Systems Engineering, National University of Singapore, 1 Engineering Drive 2, 117576, Singapore, Singapore e-mail: [email protected] W. Jaruphongsa e-mail: [email protected]

– – –

Only one product can be produced at a time on a machine. There is a setup cost and a setup time associated with the production of each product. The setup cost and setup time depend only on the product. The demand rate and production rate of each product are known and constant over an infinite planning horizon, and all demands must be met without backlogging. Holding costs are directly proportional to inventory levels. The machines are identical with respect to production cost and production rate for each product. The production of a product cannot be split on different machines.

It is very difficult to find an optimal solution for the MELSP. Even for the single-machine problem, no one has characterized an algorithm to find the optimal

1252

solution. The most popular method for the ELSP is to solve a restricted version of the problem. Mainly, the policies used are the Common Cycle (CC) policy, the Basic Period (BP) policy, the Extended Basic Period (EBP) policy, and the time-varying lot sizes policy. The CC policy [8] assumes that all products have a CC time. The BP policy [1] assumes that the cycle time of each product is a multiple of a BP. For ease of scheduling, the BP is assumed to be long enough to accommodate the production of all products. The EBP policy [6] relaxes the latter requirement on the BP, and in its replacement, it allows the capacity of two consecutive BPs to be pooled together to produce the products. Further relaxation on the capacity requirement to cater for the production has been extended to the EBP and Power-of-Two (PoT) policy, which assumes the cycle time of each product is a PoT multiple of the BP [9]. The time varying lot sizes policy assumes that the lot sizes of a product are different at different time [4, 5, 12], which is a very flexible policy. However, it is very difficult to solve the ELSP under this policy and the resulted schedule may have a very long cycle time that is not applicable in practice. In this paper, we focus on the CC policy and the EBP and PoT policy for the MELSP. Although many people have discussed the ELSP, not much literature exists on the MELSP. Maxwell and Singh [11] is the first paper to address the MELSP, in which they stated some conditions to motivate heuristic procedures. They proposed that the cycle times of the products should be restricted to the set S(w : k : m), which assumes that each product’s cycle time takes the form of w, kw, . . . , km−1 w, where m, k, and w are all positive integers. However, they did not propose any detailed procedure. Subsequently, [2] presented a heuristic method to solve the problem under the CC policy. The CC policy for the multiple-machine problem assumes that products on the same machine must have a CC time but different machines can assume different cycle times. Due to the flexibility of different cycle times, the problem becomes difficult. To tackle the problem, [2] decomposed the problem into two stages and solved the problem alternatively between the two stages. The solution procedure goes as follows: Given a feasible solution, the cycle times of the machines are held fixed and a generalized assignment problem is solved to improve the product allocation. If an improvement is found, the best CC time of each machine based on the new allocation will be determined. The iteration then continues until no further improvement is found. As the generalized assignment problem is NP-hard, [2] proposed a heuristic to solve the assignment problem and to ensure the running time stays

Int J Adv Manuf Technol (2009) 43:1251–1260

within a reasonable limit, a cap on the total running time was imposed. We propose a genetic algorithm (GA) under the CC policy to solve the problem as a whole instead of alternating between the two stages as the best solution obtained from the latter is at best a local optimum. We denote the heuristic in [2] by Carreno’s heuristic in this paper. Computational results show that the GA outperforms Carreno’s heuristic. Most importantly, the GA can solve the problem consistently in a short period of time even when the machine utilizations are high. This is in contrast with Carreno’s method, which stops only due to the cap imposed on the total running time. Ignoring all constraints, the cycle time of an individual product that minimizes its setup and holding cost is called an independent cycle time in this paper. For the CC policy, all products produced in the same machine must have the same cycle time. Hence, the cycle time of a machine can be very different from the independent cycle times of the products produced in the machine. In return, this will result in higher cost when the products differ greatly in their independent cycle times. We therefore design a new GA under the EBP and PoT policy. It has been shown that the EBP policy performs much better than the CC policy for the ELSP [3, 10]. We will show that, for the MELSP, the GA solutions under this policy are also better than those under the CC policy, especially when the number of machines is small. The rest of the paper is organized as follows: In Section 2, a GA under the CC policy (GACC) is presented. In Section 3, a GA under the EBP and PoT policy (GAEBP) is presented. The computational results are reported in Section 4 and the conclusion is made in Section 5.

2 GA under the CC policy The following notation is used in the paper: I M Ai si ri pi ρi ρ ρ¯ hi Hi

Number of products Number of machines Setup cost for product i Setup time for product i Demand rate for product i Production rate for product i r i / pi , production density for product i I i=1 ρi , sum of production densities for all products I i=1 ρi /M, utilization of the problem Inventory holding cost per unit time per unit hi ri (1 − ρi )/2, the factor of inventory holding cost

Int J Adv Manuf Technol (2009) 43:1251–1260

Tm Wm ai Km ni ji

1253

Cycle time for products on machine m BP for products on machine m Machine number on which product i is produced Number of BPs in a cycle for machine m Multiplier for product i, ni ∈ {1, 2, 4, . . . } Production position for product i

GACC uses the CC policy, where products produced on the same machine have a CC time. Under this policy, the problem is to determine the optimal way to allocate products on different machines so that the total cost is minimized. Once the allocation is determined, it is not difficult to find the optimal CC time for the products on each machine. With this observation, we present an encoding scheme to represent the product allocation and use it to search for the optimal solution. 2.1 Encoding scheme An array of integers a = (a1 , a2 , . . . , a I ) in Fig. 1 is used to represent the allocation, where ai represents the machine number on which product i is produced. We call a the chromosome in GA. Given a, the set of products on machine m, denoted by Pm , is determined. Formally, Pm = {i : ai = m}, m = 1, . . . , M. The cycle times Tm are not encoded explicitly in the chromosome.

search will be more diversified and is observed to converge faster, especially for high utilization problems. In GA, the offspring inherits characteristics from parents. If parents are infeasible, it is more likely that their offsprings will be infeasible as well. With this reason, we introduce a repair procedure to make an infeasible chromosome feasible, if possible, or at least to reduce its degree of infeasibility. If a solution is  not feasible, i∈Pm ρi ≥ 1 for at least one machine. An intuitive way to repair the infeasibility is to repack the  products so that i∈Pm ρi < 1 for all m. However, it is possible that the CC times of some of the machines may be unreasonably large due to the setup times of their assigned products. With this observation, we also consider setup times in repacking. As cycle times are not explicitly encoded in the chromosome, in order to include the setup times in repacking, we need to assume some CC time. It is easy to see that, for any feasible solution, we must have  M   si + ρi ≤ M. ρ< Tm m=1 i∈Pm

2.2 Feasibility

In this paper, we select only one cycle time value Tc for all the machines such that  I   si ρ+M , + ρi = Tc 2 i=1

A chromosome represents a feasible solution if and only if  ρi < 1, m = 1, . . . , M. (1)

where (ρ + M)/2 is the midpoint between ρ and M. That is, I 2 i=1 si Tc = . M−ρ

i∈Pm

In the case that inequalities 1 are not satisfied for any of the machines, the chromosome does not represent a feasible solution. In GA, a number of chromosomes are kept in the solution pool (population) to evolve until the stopping criterion is met. Some of the GAs only keep the feasible chromosomes in the population. However, searching for feasible solutions for our problem is as difficult as solving a bin-packing problem, which is well-known to be NP-hard [7]. Hence, in our GA, we keep both feasible and infeasible chromosomes in the population as a big proportion of the possible encoded chromosomes are infeasible, especially for high utilization problems. With infeasible chromosomes, the

Instead of using ρi to repack the products, we use ρi = ρi + si /Tc in repacking. In the repair procedure, we will repair only those machines that are infeasible. First, products on them are removed. These products are then repacked one by one back into all the M machines. In the packing, the product with the largest value of ρi is selected and assigned to the machine with the smallest sum of ρi . The repair procedure attempts to find a feasible product allocation considering both setup times and production densities. Note that it is still possible that some machines remain infeasible, especially when the utilization is high. Despite this, the repair procedure will decrease their degrees of infeasibility. 2.3 Fitness value

Fig. 1 Chromosome under the CC policy

a1

a2

…

aI

M Let f = m=1 fm be the fitness value of a chromosome, where fm is the fitness value of machine m. Given a

1254

Int J Adv Manuf Technol (2009) 43:1251–1260

 feasible chromosome ( i∈Pm ρi < 1, ∀ m), the CC time ∗ on machine m is chosen to be Tm , which minimizes   (A /T + H T ) subject to i m i m i∈Pm i∈Pm (si + ρi Tm ) ≤ Tm . That is,   ∗ Tm = max

i∈Pm

Ai

i∈Pm

Hi



,

i∈Pm si

1−



i∈Pm

2.5 Selection





ρi

.

The average inventory and setup costs of machine m is fm =

   Ai ∗ + H T i m . ∗ Tm i∈P m

We extend the definition to the infeasible chromosomes where penalty values will be imposed if they remain infeasible after the repair procedure. To be more specific, if machine m does not have enough capacity to produce its assigned products, the fitness value is penalized and it is given by fm = 2

 i∈Pm

Ai



Hi + penaltym .

i∈Pm



 Note that 2 i∈Pm Ai i∈Pm Hi is the minimum cost on machine m ignoring the capacity constraints. We suggest the value of penaltym to be related to: – – –

The degree of infeasibility The average utilization of the problem, denoted by ρ¯ = ρ/M The number of generations, denoted by g

In this paper, we let penaltym = tm P(ρ)Q(g), ¯ where tm =



{1, 2, . . . , M} × · · · × {1, 2, . . . , M}. If a generated chromosome happens to be infeasible, it will go through a repair procedure first.

ρi − 1, P(ρ) ¯ = 1/ρ, ¯ Q(g) = g.

i∈Pm

tm is related to the degree of infeasibility on machine m. The bigger tm is, the more the fitness value is penalized. The average utilization over all machines is an important factor that affects the difficulty of solving the problem. The bigger ρ¯ is, the less the fitness value is penalized so that more infeasible solutions are kept in the population for the high utilization problem. The third factor of the product g makes the infeasible solutions less likely to stay in the population after more generations have evolved.

Selection plays an important role in GA. We use a binary tournament selection to form a parent pool of a target size for reproduction. To form a pool, the tournament selects two chromosomes randomly from the population and adds the one with the smaller fitness value to the pool if it has not been added earlier. Once a parent pool with a target size of N  is created, the reproduction will start, which is done by repeatedly selecting two parents from the pool randomly to form a new offspring. Also to maintain good-quality solutions in the subsequent generations, a percentage of the best solutions of the current generation are kept for the next generation. 2.6 Crossover and mutation A uniform crossover is used to produce an offspring from two parents in which the genes of the new offspring are copied from the corresponding genes of the two parents with equal probability. An illustration of the crossover is given in Fig. 2. Each new offspring is assigned a small probability for the possible mutation. If a mutation takes place, two of its genes will be randomly selected and the values of the two genes are interchanged. 2.7 Values of parameters and the termination condition The values used in the GA are: N = 50, N  = 30. The mutation rate is 0.1. The GA terminates if the solution

Parent 1

+ Parent 2

2.4 Initialization Offspring

The initial population of N chromosomes is randomly generated from the product set of I sets, {1, 2, . . . , M}×

Fig. 2 Uniform crossover under the CC policy

Int J Adv Manuf Technol (2009) 43:1251–1260 Table 1 Data of the simple example

1255

Product

Ai ($)

si (day)

ri (units/day)

pi (units/day)

hi ($/day/unit)

1 2 3 4

10 20 30 40

0.1 0.1 0.1 0.3

120 120 120 200

400 400 400 400

0.1 0.1 0.1 0.1

does not improve over 1,000 generations or the total number of generations reaches 10,000. The percentage of the best solutions to be kept to the next generation is 20%. 2.8 A simple example to illustrate the GA A simple example with four products and two machines is constructed. The data for the example are given in Table 1. Let us consider a chromosome (1, 1, 1, 1) corresponding to a solution that all products are produced on machine 1. 4The chromosome (1, 1, 1, 1) is not feasible as ρ = i=1 ri / pi = 1.4, and thus, it is repaired when it is first encountered. In the repair, Tc = 2 and ρ1 = ρ2 = ρ3 = 0.35, ρ4 = 0.65. The products are ordered decreasingly by ρi , with the order as 4, 1, 2, and 3. Product 4 is packed to machine 1 first. Then, products 1 and 2 are packed to machine 2. Finally, product 3 is packed to machine 1. The repaired chromosome to replace (1, 1, 1, 1) is (2, 2, 1, 1). After a population is generated, the fitness values are evaluated. The calculation of fitness values for some sample chromosomes is illustrated in Table 2. Twenty percent of the chromosomes with the best fitness values are selected for the population in the next generation, while the other chromosomes in the new population are generated by GA operators. For the GA operators, it is assumed that (2, 1, 1, 2) and (1, 2, 1, 2) are selected as parents. To apply the crossover operator, the values of the new offspring are selected from the two parents with equal probability. If the values of products 1 and 4 are from (1, 2, 1, 2) and the values of products 2 and 3 are from (2, 1, 1, 2), the new offspring will be (1, 1, 1, 2). The probability of mutation for this offspring is 0.1. If a mutation happens, two elements are randomly selected and the values of these two elements are swapped.

Table 2 Calculation of the fitness values

3 GA under the EBP and PoT policy The EBP and PoT policy assumes that each machine is associated with a BP Wm . The cycle times of the products on the machine are PoT multiples of the BP. Denote the multiplier of product i by ni . Under this policy, a solution for the MELSP is specified by three decisions. The first involves the allocation of the products to the M machines. The second involves the determination of the BPs for the M machines. The third involves the choice of the product cycle times expressed as PoT multiples of the BPs, as well as the staggering or production positions of the products. 3.1 Encoding scheme We use three arrays of integers (a, n, j) as a chromosome to represent a solution (see Fig. 3). As before, a = (a1 , a2 , . . . , a I ) defines the machine numbers on which the products are produced. The multiplier vector n = (n1 , n2 , . . . , n I ) and the production position vector j = ( j1 , j2 , . . . , jI ), respectively, define the product cycle times expressed as PoT multiples of the BPs and the production positions of the products. For example, if we have two machines and four products and a chromosome has a1 = 1, a2 = 2, a3 = 1, a4 = 2, n1 = 1, n2 = 1, n3 = 2, n4 = 2, j1 = 1, j2 = 1, j3 = 1, j4 = 2, then the production schedule can be constructed as in Fig. 4. Similar to GACC, we do not encode the values of the BPs in the chromosome explicitly. As before, we let Pm denote the set of products allocated to machine m. Let Km be the number of BPs until the product schedule repeats on machine m. Given that all the multipliers are powers of two, Km is equal to the maximum of ni , i ∈ Pm . For m = 1, . . . , M, let Smk be the set of products produced on the

ID

Chromosome

P1

P2

T1 (day)

T2 (day)

f1 ($)

f2 ($)

f ($)

1 2 3 4

(2, 1, 1, 2) (1, 2, 1, 2) (2, 2, 1, 1) (1, 1, 1, 2)

{2, 3} {1, 3} {3, 4} {1, 2, 3}

{1, 4} {2, 4} {1, 2} {4}

2.44 2.18 2.76 3.00

2.33 2.55 1.89 2.83

40.99 36.66 50.75 57.80

42.90 46.99 31.75 28.28

83.89 83.65 82.50 86.08

1256

Int J Adv Manuf Technol (2009) 43:1251–1260

Fig. 3 Chromosome under the EBP and PoT policy

a1

a2

…

aI

n1

n2

…

nI

j1

j2

…

jI

common value for BPs, denoted by Wc . In our work, we select the value of Wc such that  I   si ρ+M + ρi = . ni Wc 2 i=1 That is, Wc =

kth BP of machine m. Formally, Pm = {i : ai = m}, m = 1, . . . , M; Km = maxi∈Pm {ni }, m = 1, . . . , M; and Smk = {i ∈ Pm : ji = (k − 1)(mod ni ) + 1}, m = 1, . . . , M and k = 1, . . . , Km . 3.2 Feasibility A chromosome is feasible only when each machine can produce its assigned products according to the given multipliers and production positions. Therefore, the feasibility is determined by the respective machine resource utilizations as well as the production frequencies and production positions. Ignoring the constraints imposed by the production frequencies and positions, the necessary conditions for a solution to be feasible are 

ρi < 1, m = 1, . . . , M.

(2)

i∈Pm

These conditions state that the allocation of products to different machines  should ensure that no machine is over utilized. If i∈Pm ρi ≥ 1 for some m, the chromosome does not represent a feasible solution and it will be repaired by a repair procedure that is similar to that described in GACC. To use it, we need to select a

machine 1 1

3

period 1

1

1

3

1

period 2

period 3

period 4

machine 2 2

2

4

period 1

period 2

2

2

period 3

period 4

Fig. 4 Production schedule of a simple example

4

2

I

i=1 si /ni

M−ρ

.

The same repair procedure as in GACC is then applied,  except that ρi = ρi + si /(ni Wc ). If i∈Pm ρi remains greater than or equal to 1 for some of the machines after the repair, the chromosome will be declared infeasible and a penalty described later will be imposed on the fitness value. For machine m, necessary and sufficient conditions for feasibility under EBP and PoT are  ni ρi < 1, k = 1, . . . , Km . (3) i∈Smk

If conditions 3 hold for all k = 1, . . . , Km , then we can always find a BP that is long enough to produce all the products in Smk regardless of the values of setup times. For example, in Fig. 4, K1 = 2, S11 = {1, 3}, S12 = {1}; K2 = 2, S21 = {2}, S22 = {2, 4}. If ρ1 + 2ρ3 < 1, then a feasible production schedule can be constructed for machine 1. Similarly, if ρ2 + 2ρ4 < 1, then a feasible production schedule can be constructed for machine 2. For the machines that satisfy Eq. 2, we check the necessary and sufficient conditions 3. If conditions 3 fail for machine m, a repair procedure will be applied. This procedure reassigns the production positions of products on machine m so as to induce the feasibility. To do this, we need to select a value of the BP in the repair procedure. The selected value of the BP     i∈Pm Ai /ni i∈Pm si /ni   (4) Wm = max , 1 − i∈Pm ρi i∈Pm Hi ni is used to estimate the sum of setup time and processing time σi = si + ρi ni Wm , ∀ i ∈ Pm . To reassign the production positions, the products are ordered increasingly by ni . For products with the same multiplier, they are ordered decreasingly by σi . Based on the list, the firstfit heuristic is applied to pack the products one by one to the first BP that can accommodate the product. The production schedule for product i is repeated every ni periods. Hence, each product is packed in Km /ni BPs. In the packing, it may happen that none of the BPs have enough time to accommodate the production of some of the products. In this case, these products are packed in the period that has the smallest sum of ni ρi . As a

Int J Adv Manuf Technol (2009) 43:1251–1260

1257

result, the lengths of the periods receiving the products will exceed Wm . In the end, this repair procedure may give a feasible schedule on machine m or reduce the degree of infeasibility of the schedule.

is the value that minimizes the total cost ignoring the capacity constraint. In this paper, we let

3.3 Fitness value

where M

Similar to GACC, we define f = m=1 fm as the fitness value of a chromosome, where fm is the fitness value of machine m. There are three cases for the calculation of fm . Case i Conditions 3 hold for all k. This is a feasible  solution. The optimal BP that minimizes i∈Pm (Ai / (ni Wm ) + Hi ni Wm ) subject to Eq. 3 is given by   ∗ Wm

i∈Pm

= max  max



i∈Pm

Hi ni



i∈Smk

,



i∈Smk si

1−

k=1,...,Km

Ai /ni

ni ρi

.

Thus, the fitness value of machine m is given by    Ai ∗ fm = + Hi ni Wm . ∗ ni Wm i∈P m

Case ii Conditions 3 do not hold for some k and  i∈Pm ρi < 1. In this case, a penalty will be imposed on the fitness value of machine m, and fm is given by

  Ai fm = + Hi ni Wm + Penaltym,1 , ni Wm i∈P m

where Wm is given by Eq. 4. In this paper, we let Penaltym,1 = tm,1 P(ρ)Q(g), ¯ where tm,1 =

Km 

⎛ ⎝

k=1

⎞+



ni ρi − 1⎠ , P(ρ) ¯ = 1/ρ, ¯ Q(g) = g.

i∈Smk

 Case iii i∈Pm ρi ≥ 1. In this case, machine m does not have enough capacity to produce the assigned products. Similar to GACC, the fitness value of machine m is given by    Ai ˆ fm = + Hi ni Wm + Penaltym,2 , (5) ˆ i∈Pm ni Wm where ˆm = W

 i∈Pm i∈Pm

Ai /ni Hi ni

Penaltym,2 = tm,2 P(ρ)Q(g), ¯ ⎛ tm,2 = ⎝



⎞ ρi − 1⎠ max{ni }, P(ρ) ¯ = 1/ρ, ¯ Q(g) = g.

i∈Pm

i∈Pm

3.4 Initialization N chromosomes are generated in the initial population. Ten percent of the chromosomes are generated using the following procedure. To generate a chromosome representation, the products are added one by one to the machines. In each iteration, a product is selected randomly from the remaining products and added to the first machine that can accommodate it. To check whether a product can be added to a machine, the sum of ρi for all the products already assigned to the machine plus the current product is calculated. If it is less than 1, the product is added to this machine. Otherwise, the product is assigned to the next machine that can fit it. If the machine happens to be the last machine, all the products will be assigned to the last machine without checking the sum of ρi . After all the products have been packed, a is known. Let n = j = (1, 1, . . . , 1). There is a great chance that a generated solution is feasible, and with the injection of highly likely initial feasible solutions, the algorithm often improves faster. The other 90% of the initial chromosomes are randomly generated from the appropriate ranges. That is, for each chromosome, a is randomly generated from the product set of I sets, {1, 2, . . . , M} × {1, 2, . . . , M}× · · · × {1, 2, . . . , M}, n is also randomly generated from {1, 2, 22 , . . . , n1 } × {1, 2, 22 , . . . , n2 } × · · · × {1, 2, 22 , . . . , n I }, and j is generated from {1, 2, . . . , n1 } × {1, 2, . . . , n2 } × · · · × {1, 2, . . . , n I }, where ni is an upper bound of ni , which is chosen to be the biggest PoT integer that is less than 1/ρi . 3.5 Selection and crossover The selection and crossover are similar to the ones used in GACC. In other words, a target size of a parent pool is selected by a binary tournament for reproduction. Also a uniform crossover is used to produce new offsprings from randomly selected parents. A percentage of the best chromosomes is kept for the next generation.

1258

3.6 Mutation Each new offspring has a small probability of being mutated. When a mutation takes place, the following two operators will be used randomly with equal probability. –

–

MUT1: Each multiplier has a small probability of being changed. If a change occurs, a multiplier will be either doubled or halved randomly with equal probability. In the case that the multiplier is equal to 1, it will be simply increased to 2. Once a multiplier is changed, it may happen that ji > ni . In this case, ji is replaced by a random number in {1, 2, . . . , ni }. MUT2: Select a random number r from {2, 3, . . . , M}. Select any r machines, and for each of the selected machines, randomly choose a product from the machine. These products are then rotated from one machine to another among all the machines. For example, if three machines are selected, the product on the first machine will be moved to the second machine, the product on the second machine will be moved to the third machine, and the product on the third machine will be moved to the first machine.

3.7 Values of the parameters and termination condition The parameters used in GAEBP are summarized here. The population size is N = 100. The size of the targeted parent pool is N  = 60. The mutation rate is 0.1. In MUT1, each multiplier has a probability of 0.1 to be changed. The termination condition is that either the best solution does not improve after 1,000 generations or 10,000 generations have been generated. Again, 20% of the best solutions are kept for the next generation.

4 Computational result Three algorithms, Carreno’s heuristic and the two GAs in this paper, are compared on randomly generated problems. The algorithms are coded in C++ and run on an Intel Pentium CPU 3-GHz personal computer with a memory of 0.99 GB. The problems are generated for five different numbers of machines—two, four, six, eight, and ten. The number of products is five times the number of machines. For each problem setting, ten problems are generated, where their parameters are randomly generated from the ranges given in Table 3. The settings in the table are the same as those used by [2].

Int J Adv Manuf Technol (2009) 43:1251–1260 Table 3 Ranges of parameters for MELSP Parameter

Mean

Range

Production rate (unit/day) Setup cost ($) Setup time (day) Holding cost ($/unit/year) Demand rate (unit/day)

14,000.00 200.00 0.28 0.35 2,500.00

5,000.00 400.00 0.44 0.70 4,800.00

We use GAP = (solution’s value − LB)/LB to measure the performance of the heuristics, where LB is the lower bound of the problem used in [2]. For ease of reference, a description of LB is included in the Appendix. For each number of machines and utilizations, the average GAP of ten problems is reported in Table 4. The cap of running time for Carreno’s heuristic is set at 50 s. From the computational results, we find that solutions of GACC dominate solutions of Carreno’s heuristic for all the different settings. For the high utilization problems, GACC is a lot better than Carreno’s heuristic. This is mainly due to the difficulty of using Carreno’s heuristic to solve the high utilization problems. The running time of GACC does not increase much when the number of machines increases, but the running time of Carreno’s heuristic increases dramatically when the utilization and machine number increase and the cap of running time is reached for a number of them. GAEBP is slower than GACC, but the solution of GAEBP dominates GACC for all the settings. For the problems with two machines, GAEBP is much better than GACC for low-utilization problems, but it is not difficult to see that the improvement of GAEBP over GACC decreases as the number of machines increases. In general, the more machines we have, the more flexibility we have for cycle times under the CC policy. For the ten-machine problems, the algorithms under the CC policy perform well. Their average GAPs are around 1% or less for low-utilization problems. This is because the restriction of the CC policy is alleviated by the flexibility of using different cycle times on different machines. When there are ten machines, it is not difficult to find a good grouping so that the CC time of the machine is close to the independent cycle times of all products produced in that machine. However, when there are a few machines, products with much different independent cycle times may have to be produced in the same machine. As a result, the performance of the heuristics under the CC policy deteriorates when the number of machines decreases. It is clearly seen that GAEBP performs much better than the other two heuristics, especially when the number of machines is small and the machine utilization is not too high.

Int J Adv Manuf Technol (2009) 43:1251–1260 Table 4 Computational results for randomly generated problems

No. 2 2 2 2 2 2 4 4 4 4 4 4 6 6 6 6 6 6 8 8 8 8 8 8 10 10 10 10 10 10

Util 0.6 0.7 0.8 0.85 0.9 0.95 0.6 0.7 0.8 0.85 0.9 0.95 0.6 0.7 0.8 0.85 0.9 0.95 0.6 0.7 0.8 0.85 0.9 0.95 0.6 0.7 0.8 0.85 0.9 0.95

1259 GAP GAEBP

GACC

Carreno

Time (seconds) GAEBP GACC

Carreno

0.72% 0.70% 1.63% 2.10% 3.79% 8.18% 0.32% 0.33% 0.61% 1.49% 2.49% 6.39% 0.22% 0.27% 0.75% 1.27% 2.33% 8.16% 0.18% 0.22% 0.58% 1.03% 2.48% 9.87% 0.12% 0.21% 0.50% 1.06% 2.90% 8.56%

5.20% 4.31% 5.22% 4.75% 4.29% 9.28% 1.44% 1.68% 1.72% 2.83% 3.70% 8.13% 0.74% 0.67% 1.76% 1.86% 2.90% 8.64% 0.41% 0.54% 1.15% 1.45% 2.70% 11.94% 0.34% 0.41% 0.84% 1.49% 3.01% 11.91%

5.43% 4.44% 6.73% 5.89% 5.35% 13.21% 1.93% 1.88% 2.41% 4.19% 6.16% 19.85% 1.27% 0.94% 1.92% 2.39% 7.37% 21.59% 0.71% 0.83% 1.53% 1.56% 9.19% 21.81% 0.52% 0.52% 1.26% 2.04% 15.08% 25.87%

7.586 7.166 6.480 6.974 6.730 8.990 11.947 12.298 14.790 11.841 14.458 14.590 24.571 20.172 25.364 23.971 28.303 24.555 36.755 32.659 34.087 37.205 42.011 26.522 54.415 44.059 59.940 73.585 70.225 29.706

0.002 0.002 0.002 0.003 0.003 0.005 0.003 0.002 0.008 0.006 10.808 50.000 0.002 0.002 5.221 15.154 45.810 50.000 0.002 0.014 18.518 25.468 50.000 50.000 5.003 5.234 23.751 40.012 50.000 50.000

5 Conclusions In this paper, we discuss two different policies for the MELSP and propose two GAs under the two policies. The first policy we use is the CC policy, which assumes that the products produced on the same machine have a CC time. It is shown empirically that GACC can find better solutions than Carreno’s heuristic for all the different settings, and compared with the latter, it requires less running time for the high utilization problems. Among all three algorithms, GAEBP performs best, though it requires a longer running time. It is observed that the GAP of Carreno’s heuristic is bigger when the number of machines is small. For the two-machine problem, the average GAP can be improved dramatically by using a GA under the EBP and PoT policy. A GA under this policy can find very good solutions for the MELSP. From the computational experiment, we see that the solution quality of GAEBP dominates GACC and Carreno’s heuristic for all different settings. Particularly, it finds better solu-

0.700 0.664 0.669 0.692 0.716 0.840 1.080 1.080 1.210 1.658 1.885 1.969 1.917 1.957 2.827 3.086 4.480 3.990 2.774 4.002 3.424 4.811 8.041 4.042 3.912 5.172 5.944 8.105 14.954 4.431

tions when the number of machines is small and the machine utilization is not too high.

Appendix Lower bound A lower bound can be obtained from the optimal value of the following convex program [2]. min

I   Ai i=1

ti

 + Hi ti

subject to I  

ρi +

i=1

si ti

 ≤M ti > 0, ∀ i,

1260

Int J Adv Manuf Technol (2009) 43:1251–1260

where ti is the cycle time of product i. The optimal solution of the convex program is given by:  Ai + λsi ti∗ = , ∀i Hi   I si √ The value of λ is 0 when ρ + ≤ M. i i=1 Ai /Hi   I ρi + √ si > M, λ and ti∗ values satisfy When i=1 Ai /Hi

the following system of equations:  Ai + λsi ∗ ti = , ∀i and Hi  I   si ρi + ∗ = M ti i=1

References 1. Bomberger E (1966) A dynamic programming approach to a lot size scheduling problem. Manage Sci 12:778–784

2. Carreno JJ (1990) Economic lot scheduling for multiple products on parallel identical processors. Manage Sci 36:348–358 3. Chatfield D (2007) The economic lot scheduling problem: a pure genetic search approach. Comput Oper Res 34:2865– 2881 4. Delaporte CM, Thomas LJ (1977) Lot size and sequencing for N products on one facility. Manage Sci 23:1070–1079 5. Dobson G (1987) The economic lot scheduling problem: achieving feasibility using time-varying lot sizes. Oper Res 35:764–771 6. Elmaghraby SE (1978) The economic lot scheduling problem (ELSP): review and extensions. Manage Sci 24:587–598 7. Garey MR, Johnson DS (1977) Computers and intractability: a guide to the theory of NP-completeness (see problem [SR1], page 226). W. H. Freeman, New York 8. Hanssman F (1962) Operations research in production and inventory. Wiley, New York 9. Haessler R (1979) An improved extended basic period procedure for solving the economic lot scheduling problem. AIIE Trans 11:336–340 10. Lopez MN, Kingsman BG (1991) The economic lot scheduling problem: theory and practice. Int J Prod Econ 23: 147–164 11. Maxwell WL, Singh H (1986) Scheduling cyclic production on several identical machines. Oper Res 34:460–463 12. Zipkin P (1991) Computing optimal lot sizes in the economic lot scheduling problem. Oper Res 39:56–63