Back
 CS  Vol.7 No.6 , May 2016
Solving Level Scheduling in Mixed Model Assembly Line by Simulated Annealing Method
Abstract: This paper presents an application of the simulated annealing algorithm to solve level schedules in mixed model assembly line. Solving production sequences with both number of setups and material usage rates to the minimum rate will optimize the level schedule. Miltenburg algorithm (1989) is first used to get seed sequence to optimize further. For this the utility time of the line and setup time requirement on each station is considered. This seed sequence is optimized by simulated annealing. This investigation helps to understand the importance of utility in the assembly line. Up to 15 product sequences are taken and constructed by using randomizing method and find the objective function value for this. For a sequence optimization, a meta-heuristic seems much more promising to guide the search into feasible regions of the solution space. Simulated annealing is a stochastic local search meta-heuristic, which bases the acceptance of a modified neighboring solution on a probabilistic scheme inspired by thermal processes for obtaining low-energy states in heat baths. Experimental results show that the simulated annealing approach is favorable and competitive compared to Miltenburg’s constructive algorithm for the problems set considered. It is proposed to found 16,985 solutions, the time taken for computation is 23.47 to 130.35, and the simulated annealing improves 49.33% than Miltenberg.

Received 23 March 2016; accepted 13 May 2016; published 18 May 2016

1. Introduction

Mixed Model Assembly Line (MMAL) sequencing is a problem of determining a sequence of the product models whereby a major emphasis is placed on maximizing the line utilization. MMAL is a type of production line, in which variety of product models is assembled and many industries use MMALs for diversified small-lot productions. In mixed model assembly, industrial scheduling is the most important concept, i.e., correct sequence is necessary of effective utilization of assembly lines. It addresses two key problems: i) Level scheduling and ii) Line balancing problem. The balancing problem is the reasonable distribution of the operation units and it is a long time decision problem. The scheduling is short time decision making problem. Level scheduling problem in a mixed model assembly line is a famous approach for resulting short term sequence to facilitate a just-in-time supply. In the past, research on sequencing problem in MMAL are considered with the objectives of optimizing minimum cycle time, constant rate usage of parts, minimum variable parts usage, minimum number of workstation and minimum total work over load time by using various methods like genetic algorithm, particle swarm optimization, mathematical models and many heuristic procedures. In a Just-in-Time (JIT) production system, only the necessary products at the necessary time, in the necessary quantity are manufactured and stock on hand is held to minimum. Assembly is the process of collecting the various parts from raw material and putting together to form a product. The assembly line is classified into single model assembly, multi model assembly, mixed model assembly. In the single, multi and mixed models, lines are shown in Figure 1.

The single model assembly line has been used to produce single model only. In this production line, large quantity of products can be produced without changing the setup. In multi model assembly line, similar products are manufactured in one or more assembly lines. In mixed model assembly line, two or more products are produced in the same assembly line.

In [1] it shows that the production sequence of introducing variety of product models to the mixed model assembly line is different due to different objective goal of controlling the line. The problem of scheduling the sequence of products to be assembled by a line is:

Leveling the load on each station on the line,

Keeping constant rate of usage of every parts used by the line.

The customers need the different models as per their necessity. According to the customers demand the need to produce the different model is must. In mixed model assembly line, the different models are produced as similar product characteristics are assembled. The two main objectives are line balancing and scheduling. The line balancing is leveling the work load to each work station is uniform. The operation times at each station are not the same. The certain work station operation time is exceeding to cycle time. The assembly line is adjusted by this cycle time without line stoppage. However, the successive scheduling creates delays and it leads to line stoppage, so it is essential to minimize the line stoppage.

The scheduling is much more important than line balancing. The quantity of each part used by the mixed model assembly line per unit time should be kept as constant as possible and always there will be little variation between the actual production and desirable production. To implement effective utilization of the mixed model assembly line the following objective functions are to be solved.

Single Model Line

(a)Multi Model(b)Mixed Model(c)

Figure 1. (a)-(c) Single, multi and mixed model lines.

Determination of line cycle times;

Determination of the number and sequence of station on the line;

Line balancing;

Determination of sequencing scheduling for producing different products on the line.

In mixed model assembly line, it requires production sequence to solve the following objectives;

Determination of cycle time;

Determination of work in process;

Determination of effective utilization;

Determination of setup time;

Determination of make span.

Determination of cycle time is the maximum time spent at any one work station. The amount of time is available at each work station to complete all assigned work. Work in process is the arrange number of units in the production system at any given time as the result of the production sequence. Effective utilization is the measure of the ability to keep the schedule level of evenly intermixed by keeping the raw materials for different products of arriving at the system as constant as possible. Setup is required when the different products are produced in the same assembly line. Makeup is the length of production run in the production sequence.

Our objective functions are to minimize the both usage rate and required setups. Setup is required when the two consecutive products in the production sequence are different. The usage rate is a measure of the ability arriving to keep the schedule level on evenly intermixed by keeping the raw materials for different products arriving at the system rate as constant as possible. Generally, the setup and utility are inversely proportional functions. When the utility is low the setup is high. When the utility is high the setup is more. So it has to be balanced between the setup and utility. The weightage of setup and utility has been used, for that the composite objective function value is required.

As an enormous number of possible production sequence, it is difficult to find the optimal solution by using the traditional optimization methods like branch and bound algorithm, goal chasing algorithm, liner and non-li- near programming methods and dynamic programming algorithm. It is taking more computation time and also more complexity. Recent trend in solving the optimization problems is heuristic. The heuristic method is used to solve many big problems using simple formula. The algorithms are used to address this type of multiple objective sequencing problems. Many heuristic methods are used to solve the mixed model assembly line problem. The heuristic methods are Genetic Algorithm (GA), Ant-Colony Algorithm (ACA), Particle Swarm Optimization (PSO), Simulated Annealing (SA) and Tabu Search (TS).

It is proposed that the sequence obtained from Miltenburg algorithm is considered as seed. From this seed, the sequence has altered randomly. The utility and setup has been taken as objective function value to optimize the level schedules in JIT production sequence. For this objective function value, different weightages give utility and setup as E = WuU + Wss. The weights Ws and Wu used for the objective function values are to emphasize the importance of the setup and utility. The weights are determines as Ws = c/number of setups from initial solution, Wu = c/number of utility from initial solution, c = constant = 1000. Four types of heuristics are used as per varying the importance of setup and utility.

The objective function value for different weightage has been found from heuristic 1 to 4. The simulated annealing algorithm has utilized to find the optimum function value and optimum sequence. In Section 2, the literature survey of mixed model assembly line and simulated annealing has been presented. In Section 3, the detailed description of the mixed model assembly line model and Miltenburg algorithm has been discussed. In Section 4, the simulated annealing procedure and algorithm have been discussed. Similarly in Section 5 and Section 6, the numerical example and experimental results are presented. Section 7 describes about the computational time and the conclusion is presented in Section 8.

2. Literature Survey

The Toyota production system discusses the leveling and balancing schedule. It shows that the sequence of models in mixed model assembly line is different due to different level of load and usage of parts [1] . The best production schedule by algorithm1 is discussed in [2] , but this algorithm is not feasible for the same number of product. The feasible algorithm 2, algorithm 3 are discussed in [2] , it also presents heuristics 1, 2. Finally the optimal scheduling algorithm with low variation by heuristics 2 has discussed. An optimal sequence of units that minimizes total line stoppage is discussed in [3] . In [3] the branch and bound method to derive the lower and upper bounds of the total line stoppage time and idle time has been proposed. In [4] , the technique utilized is Tabu search to find a sequence when minimization of both material usage rates and setup are of concern, this technique is applied to several problems and resulting sequences are simulated to determine production performance measures of production make span, average work in progress of inventory level. The genetic algorithm provide formidable solution to the multiproduct JIT production sequencing problem with setup and compare favorable to those found using the search techniques of Tabu search and simulated annealing [5] [6] . In [7] , an application of the relatively new approach of Ant Colony Optimization (ACO) of address a production sequencing problem, when two objectives are preset, simulated the artificial intelligence agents of virtual ants to obtain desirable solution to a manufacturing logistic problem is discussed.

The two stage variation in mixed model sequencing problem reduces the part variation which is discussed in [8] . A transformed two stage heuristic using product level for reducing the par-level variation in sequencing mixed model assembly line is provided. The performance of genetic algorithm for sequencing problem in mixed model assembly line is investigated in [9] . The results of evaluation indicate that the genetic algorithm that uses the parents-stratum niche cubicle performs better than genetic algorithm with other selection mechanisms. In [10] , a multi objective GA for MMAL on JIT assembly line problem where variation of production rates and number of setups are to be optimized minimization of the production rates variation and setup are discussed. The research in JIT sequencing and a Pseudo-polynomial binary search for a feasible B-bounded sequence obtained through perfect matching in bipartite graph solves the single-level min-max absolute-deviation problem are reviewed in [11] .

In [12] the major planning approaches in mixed model car assembly sequencing, level scheduling and provides a hierarchical classification scheme to systematically record the efforts in each field has been discussed. It also gives the structure of the vast field of assembly line balancing according to characteristic practical settings and highlights relevant model extension which is required to reflect real world problems. In [12] , the reviews on important problem setting alternative buffer configurations, resulting decisions problems are described. The assembly line balancing besides the advantage of genetic algorithm and soft computing and hybrid systems increases the multi objective assembly line problems are studied in [13] . In [14] , it presents an integer programming formulation for sequencing problem in mixed model assembly lines where number of temporarily hired utility works and setup are to be optimized simultaneously through a cost function. In [15] , it has been proposed to balance the product variety and manufacturing complexity by relative complexity method and find the best set of product variants to be offered while balancing market share and complexity. The multi objective ant colony optimization algorithm for smooth production has been discussed in [16] . The objective is to have minimum number of stations for given cycle time.

The particle swarm optimization algorithm with negative knowledge to solve multi-objective two sided MMAL problems is discussed in [17] . The knowledge of poor solutions is also utility to avoid the pairs of adjacent tasks appearing in the poor solutions from being selected as part or new solutions in the next generation. In [18] it has been solve the balancing and sequencing problem in MMAL to minimize total utility by new mixed integer linear programming model is developed to provide the exact solutions of the problem with standard time. A new hybrid algorithm which executes ant colony optimizations in combination with genetic algorithm (ACO-GA) for MMALBP-1 (mixed model assembly line balancing problem) such as parallel workstations, zoning constraints, and sequence dependent setup times between tasks has been presented in [19] . The multiple colony hybrid bees algorithm for mixed model assembly line balancing problem for low, medium, high variability of setup times and compared with single colony algorithm in terms of computation time and solution quality is discussed in [20] .

From the above literature survey, Mondon find the sequence for mixed model assembly, Mitenberg develop it and find feasible algorithm for low variation parts, we use his algorithm as seed, McMullan derive five types of heustics and compare genetic algorithm, tabu, and ant colony algorithm, and from this we use heustics weightages. We study the various types mixed model assembly application, problems and solutions.

3. Mixed Model Assembly Line

The mixed model assembly line may vary from product to product, when large lots of parts assembly, the scheduling is difficult. The usage rate is high or low which depends upon the product assembly. The just in time system works for constant rate of usage for all parts. The small lot of sequence of products is minimizing the variation in the usage of each part that it can achieve a constant rate of part usage by considering only the demand rates for the products.

Minimizing setup is also important in the production line. A set up is required each time two consecutive items in the production sequence are different. An objective function value for the production sequence is utility and setup, then determinate a composite measure of utility and setup. The main aim is to minimize the utility and setup which is combination natural problem. The weightage of each utility and setup has introduced for various weightages applied to utility and setup and find the optimum weightage of function value and sequence.

3.1. Notations

N products with demand. Totally units are to be produced., is the proposition of product “I” demand to the total demand.

The objective is to schedule the assembly line that the proportion of product “i” produced to the total production is close to r1 as possible.

Let Si,k, , , where Si,k is either 0 or 1 be a production schedule.

If Si,k = 1 then product i will be produced during stage k.

, for all k, because only one product can be produced during each stage.

Let, be the total production of product i over stages 1 to k.

Clearly, is a non-negative integer and, for all k. The objective might be one of the following,

(1)

(2)

(3)

The objective function is equal to zero and constraints are satisfied.

(4)

3.2. Miltenberg Algorithm

The flowchart of miltenberg’s algorithm is shown in Figure 2 and it finds the nearest point M to point X, where

1. Calculate

2. Find the nearest non-negative integer mi to each coordinate xi, that is, Find mi, so that,.

3. Calculate

a) If stop. The nearest integer point is

b) If go to step 5

c) If go to step 6

4. Find the coordinate xi with the smallest mi − xi increment the value of this mi; mi → mi + 1 Go to step 3

5. Find the coordinate xi with largest mi − xi decrement the value of this mi; mi → mi − 1Go to step 3

Figure 2. Flowchart of Miltenberg’s algorithm.

3.3. Objective Function

3.3.1. Minimizing the Setups

The number of setup

(5)

where, k = Index of the position in the sequence if the product in position k is different from product in position k − 1, then setup is require and Sk = 1, 0 otherwise it is assumed here that initial setup is required regardless in sequence. It should be noted that the setup time are assumed to sequence independent, so that the machine does not depend on which other product preceded it on that machine.

3.3.2. Minimizing the Utility

(6)

While keeping the usage of materials as constant as smooth as possible is of extreme importance when different products are to be made on an assembling line, this usage rate of material is especially sensitive to the production sequence. Because the material usage rate is sensitive to the production sequence, considerable effect has gone into development or techniques intended to minimize this material usage rate.

3.4. Composite Objective Function Value

An objective function value of the production sequence is then determined with composite measure of utility and setup, where Wu is the weight placed upon the usage rate and Ws is the weight place upon the number of setups. The composite functions is

(7)

Sequencing Heuristics Used

In [5] , it derives the different heuristics according to different weightage of utility and setup. The different heuristic are used to obtain the different objective function are

Heuristic 1

(8)

This heuristic sequences the products in such a way that the required number of set ups is minimized. It does not require minimum setup, it does not require heuristics, it get from inspection.

Heuristic 2

(9)

This heuristic minimizes the material usage rate and it is addressed in [21] , which is simplification of Miltenburgs sequence in [2] .

Heuristic 3

(10)

This heuristic sequence produces in such a way that composite function of both utility and set up is minimized. The coefficients used for this objective function come from sampling in such a way that both utility and setups are gives equal contribution. The coefficient is derived in [4] .

Heuristic 4

(11)

In this heuristic, the number of setup is 3 times minimizing, so that the utility and setups are minimizing. The importance of setup time is three times more than utility but the utility importance is still considered.

Heuristic 5

(12)

In this the minimizing utility is 3 times as minimizing the number of setup. The utility and setup is consider but the importance of utility is three time than setup.

For first two objectives, it does not require to minimize, because it comes directly from its own minimizes the number of require setups and utility rates. But other objectives to be minimize by using simulated annealing with respect of the weights Wu, Ws, it reflect the level of importance of setup and utility. Four objective functions were evaluated and for varying weightages can be placed to lower the number of setups and usage rates. The

used four types of heuristics are, , ,.

3.5. Heuristic Methods and Proposed Algorithm

A Heuristic is simply a rule of thumb, hopefully will find a good answer. Heuristic are typically used to solve complex, large, non-liner non-convex multivariate combinational optimization problems that rate difficult to solve to optimality. Many heuristic methods are simulated annealing, Genetic algorithm, particle swarm optimization, ant colony algorithm and Tabu search.

A genetic algorithm is a search strategy. To implement GA, a representation of the parameters in the problem to be searched is developed first, several initial GA solutions are formed to make an initial populations of several so called chromosomes, and then the GA operations selection, recombination and mutations are employed to improve the search repetitively as measured by a fitness or evaluation function. Particle optimization is developed from the behavior of bird and fish while searching for food, the birds are either scattered or go together before they locate the place where they can find the food while searching food they go from one place to another place where good food resource available. This information is transmitted and good information is equal most optimist solution. Ant colony optimization is the behavioral simulation of social insects such as Bees, ant, wasps. ACO simulate the collective forging habits of ants venturing out for food. A chemical substance deposited by ants as they travel, pheromone provides ants with ability to communicate with each other. Ants move randomly when they encounter a pheromone trail, they decide whether or not to follow it. The probability that an ant choose one path over another is governed by the amount of pheromone on potential path of interest. Tabu search setup that it utilities a short term memory component of previous solutions which presents cycling, which can be in turn result in being trapped at local optima thereby preventing finding an optimal solution. Tabu search takes initial solutions and makes changes to this solution during the iterative process. As changes are made, they are recorded on a Tabu list which is simply a listing of the recent changes or moves. It a move under consideration appears on the list, the move is forbidden unless its objective function value satisfies what known as aspiration criteria. The basic procedure is repeated until user specified stopping criteria are met. Any efficient optimization algorithm must use these techniques to find global maximum by exploration, new and unknown search space to make use of knowledge found at point previously visited. These two requirements are full filled by simulated annealing algorithm. SA can deal with highly now-liner models, chaotic and noisy data and many constraints. It is robust and general technique. The simulated annealing algorithm is better than local search methods in flexibility and ability to approve global optimality. The algorithm is quite versatile since it does not rely on any restrictive properties of the model. The Figure 3 shows the structure of SA algorithm.

Figure 3. Structure of SA algorithm.

4. Simulated Annealing

Simulated annealing is a random search technique which exploits an analogy between the ways in which a Meta cools into minimum energy crystalline structure. The simulated annealing method is for obtaining good solutions to difficult optimization problems. In the early 80’s, the concept of annealing has been discussed in [22] . In simulated annealing, first melt the solid by increasing the temperature then slowly cool it so it crystallizes into perfect lattice. Solution considered as states of the physical system, objective function as energy and control parameter as temperature.

In simulated annealing, the initial state of a thermodynamic system energy E, temperature T and the change in energy is completed. If the change in energy is negative, the new state is accepted. If the change in energy is positive is accepted with, then the processes is then repeated sufficient times to give good sampling sta-

tistics of current temperature and then temperature is decremented until the final temperature or number of iteration or sufficient computational time is attain. In this, the parameter selection is very important. The parameters are initial temperature, final temperature and the number of iterations. If high initial temperature is chosen, it takes number of iterations for convergence. If a small initial temperature, the search is not adequate to the search space before finding the time optimum. The advantage of simulated annealing is the ability to move from local optimization thus the ability to find the global optimum is not related to the initial condition. The disadvantage of simulated annealing is the subjective nature of choosing the configuration parameters.

4.1. Annealing Procedure

4.1.1. Initial Temperature

In [25] , the initial and final temperature were determined by information obtained the trial to annealing process. In this trial, a certain number of random moves were performed to record the changes in results in the objective function. From this result, the minimum temperature is given by,

(13)

(14)

4.1.2. Decrementing Temperature

One of the major issues is related to the annealing schedule to cool the temperature during the annealing process. Various methods are used to reduce the temperature as shown in Table 1.

The Connolly method is selected because it is clear that when the temperature is too high, a lot of uphill moves are accepted, when the temperature is too low, the probability is falling into a local minimum. The temperature should be between these two extreme that the temperature is high but the cooling is low. The Connolly was designed based on this idea; hence this method has been adopted.

In Connolly method, during these trials the initial temperature T0 and final temperature Tf are determined and M refers to the number of pair wise exchanges examined.

, (15)

(16)

Table 1. Methods to reduce the temperature during annealing process.

In this equation parameter usually has a small value and there after the temperature reduction proceeds slowly and n is the number of demand. The algorithm perform depends upon the cooling rate than individual temperature for better result, reduction rate should be slower in middle temperature range.

4.1.3. Random Number Generation

A significant component of an SA code is the random number generator, which is used both for generating random changes in the control variables and for the increase acceptance test. It is important, particularly when tacking large scale problems requiring thousands of iterations, so that the random numbers generator used have good spectral properties. The Microsoft excel VBA procedure method is inbuilt into the program for find the random number generation.

4.1.4. Number of Iteration

A constant number of iteration at each temperature is generally employed. Another method is only one iteration at each temperature but to decrease the temperature very slowly. The iterations at each temperature is proportional to n = t/(t + 1). An alternative is to dynamically change the number of iterations as the algorithm progress. We use the number of iteration is total number product.

4.1.5. Stopping Criteria

A given total number of iterations have been completed or fixed amount of execution time, the stopping criteria can either be a suitably low temperature or when the system is “frozen” at the current temperature (i.e. no better or worse moves are being accepted). Once the final temperature has been attained, the process will stop.

4.1.6. Parameter Set

The initial and final temperatures were determined by information obtained in trail to the annealing process. In this trail certain number of random moves was performed to record the resulting changes in the objective function. From this result, the minimum value of ∆E min and maximum value of ∆E max are to be final. The initial temperature is set as

(17)

and the final temperature

Another annealing schedule is how to cool the temperature during the annealing process

, , (18)

where, M refers to the number of pair wise exchange examined,

Ti +1 = next temperature to be set, n = no of demand.

4.2. Simulated Annealing Algorithm

Choose initial temperature, temperature reduction factor and final temperature;

Select the objective function;

Select the number of iteration;

Find the initial energy state (E0);

Find the randomizing, select the another energy state (E1);

Find the difference between the two energy states;

Check whether ΔE < 0. If yes store the energy and find the randomly energy state. If no generate randomly X Î U(0, 1) Check the whether;

If yes store the energy state otherwise go for iteration. The above function is repeating until the all the iteration and reduce the temperature according to reduction factor. Continue the above procedure until reach up to final temperature.

Generate initial sequence by Miltenberg algorithm and calculate objective function E. The flowchart for simulated algorithm and proposed algorithm are shown in Figure 4 and Figure 5.

Select an initial solution E0 and E1, E1 = E;

Select an initial temperature Ti > 0;

Select a temperature reduction function Ti+1

Select an final temperature Tf ;

Maximum iteration count Max IT;

Repeat

Set iteration count IT = 0;

IT = IT + 1;

Randomly generate sequence by VBA method and calculate E1;

set ∆E = f(E1) − f(E0);

Figure 4. Flowchart of simulated algorithm.

Figure 5. Flowchart of proposed algorithm.

If ∆E < 0;

then set E0 = E1 (downhill move) else;

generate random X uniformly in the range [0, 1];

If x < exp(−∆E/T) ;

then set E0 = E(uphill move) ;

If f(E0) < f(E) then E1 = E0.

Until IT = Max;

Set Ti = (Ti+1);

Until stopping condition becomes true.

Output E0 as an approximation to the optimal solution.

5. Numerical Example

5.1. Miltenberg Algorithm

In Table 2, a test problem of 5 types of products A, B, C, D and E are to be produced and their demands of each type requires 2. The following steps will illustrate the working of Miltenburg algorithm.

DT = A + B + C + D + E

DT = 2+2+2+2+2 = 10

d1 = 2, d2 = 2, d3 = 2, d4 = 2 d5 = 2

r1 = r2 = r3 = r4 = r5 = 2/10

K = No of stages = 2 + 2 + 2 + 2 + 2 = 10

M = (M1, M2 ……M10) X = (x1, x2 ……x10)

At stage K = 1

X1 = K (r1, r2, r3, r4, r5)

X1 = 1(2/10, 2/10, 2/10, 2/10, 2/10)

X1 = (0, 0, 0, 0, 0)

M1 = (0, 0, 0, 0, 0)

Km = 0 + 0 + 1 = 1, k-km = 1 − 0 = 1 > 0 go to step 5

Find the smallest coordinate of M

Select m1 → m1 +1 = 0 + 1 = 1

X1 = (1, 0, 0, 0, 0)

Km = 0 + 0 + 1 = 1, k-km = 1 − 1 = 0 stop

Schedule product-A

At stage K = 2

X2 = 2(2/10, 2/10, 2/10, 2/10, 2/10)

X2 = (0, 0, 0, 0, 0)

M2 = (0, 0, 0, 0, 0)

Km = 0 + 0 + 1 = 1 k-km = 1 − 0 = 1 0 go to step 5

Find the smallest coordinate of M

Select m1 → m1 + 1 = 0 + 1 = 1

X2 = (1, 0, 0, 0, 0)

Km = 0 + 0 + 1 = 1 k-km = 2 − 1 = 1 > 0 go to step 5

Find the smallest coordinate of M

Table 2. Test problem.

Select m2 → m2 + 1 = 0 + 1 = 1

X2 = (1, 1, 0, 0, 0)

Km = 0 + 1 + 1 = 2, k-km = 2 − 2 = 0 stop

Schedule product-B

At stage K = 3

X3 = 3(2/10, 2/10, 2/10, 2/10, 2/10)

X3 = (1, 1, 1, 1, 1)

M3 = (1, 1, 1, 1, 1)

Km = 1+ 1+1+1+1 = 5 k-km = 3 − 5 = −2 < 0 go to step 6

Find the Largest coordinate of M3

Select m5 → m5 -1 = 1 − 1 = 0

X3 = (1, 1, 1, 1, 0)

Km = 4, k-km = 3 − 4 = −1 < 0 go to step 6

Find the Largest coordinate of M3

Select m4 → m4 − 1 = 1 − 1 = 0

X6 = (1, 1, 1, 0, 0)

Km = 3, k-km = 3 − 3 = 0 stop

Schedule product-C

At stage K = 4

X4 = 4(2/10, 2/10, 2/10, 2/10, 2/10)

X4 = (1, 1, 1, 1, 1)

M4 = (1, 1, 1, 1, 1)

Km = 1 + 1 + 1 + 1 + 1 = 5, k-km = 4 − 5 = −1 < 0 go to step 6

Find the Largest coordinate of M4

Select m5 → m5 -1 = 1 − 1 = 0

X4 = (1, 1, 1, 1, 0)

Km = 4, k-km = 4 − 4 = 0 Stop

Schedule product - D

At stage K = 5

X5 = 5(2/10, 2/10, 2/10, 2/10, 2/10)

X5 = (1, 1, 1, 1, 1)

M5 = (1, 1, 1, 1, 1)

Km = 5, k-km = 5 − 5 = 0 Stop

Schedule product ? E

At stage K = 6

X6 = K (r1, r2, r3, r4, r5)

X6 = 6(2/10, 2/10, 2/10, 2/10, 2/10)

X6 = (1, 1, 1, 1, 1)

M6 = (1, 1, 1, 1, 1)

Km = 5, k-km = 6 − 5 = 1 > 0 go to step 5

Find the smallest coordinate of M

Select m1 → m1 + 1 = 0 + 1 = 1

X6 = (2, 1, 1, 1, 1)

Km = 6, k-km = 6 − 6 = 0 stop

Schedule product-A

At stage K = 7

X7 = K (r1, r2, r3, r4, r5)

X7 = 7(2/10, 2/10, 2/10, 2/10, 2/10)

X7 = (1, 1, 1, 1, 1)

M7 = (1, 1, 1, 1, 1)

Km = 5, k-km = 7 − 5 = 2 > 0 go to step 5

Find the smallest coordinate of M

Select m1 → m1 +1 = 1+ 1 = 2

X7 = (2, 1, 1, 1, 1)

Km = 8, k-km = 7 − 6 = 1 2 > 0 go to step 5

Find the smallest coordinate of M

Select m2 → m2 + 1 = 1 + 1 = 2

X7 = (2, 2, 1, 1, 1)

Km = 7, k-km = 7 − 7 = 0 Stop

Schedule product-B

At stage K = 8

X8 = 8(2/10, 2/10, 2/10, 2/10, 2/10)

X8 = (2, 2, 2, 2, 2)

M8 = (2, 2, 2, 2, 2)

Km = 10, k-km = 8-10 = −2 < 0 go to step 6

Find the Largest coordinate of M4

Select m5 → m5 − 1 = 2 − 1 = 1

X8 = (2, 2, 2, 2, 1)

Km = 9, k-km = 8-9 = −1 < 0 go to step 6

Find the Largest coordinate of M4

Select m4 → m4 − 1 = 2 − 1 = 1

X8 = (2, 2, 2, 1, 1)

Km = 8, k-km = 8 − 8 = −0 Stop

Schedule product-C

At stage K = 9

X9 = 9(2/10, 2/10, 2/10, 2/10, 2/10)

X9 = (2, 2, 2, 2, 2)

M9 = (2, 2, 2, 2, 2)

Km = 10 k-km = 9-10 = −1 < 0 go to step 6

Find the Largest coordinate of M5

Select m5 → m5 -1 = 2 − 1 = 1

X9 = (2, 2, 2, 2, 1)

Km = 9, k-km = 9 − 9 = −0 Stop

Schedule product-D

At stage K = 10

X10 = 10(2/10, 2/10, 2/10, 2/10, 2/10)

X10 = (2, 2, 2, 2, 2)

M10 = (2, 2, 2, 2, 2)

Km = 10, k-km = 10 − 10 = 0 Stop

Schedule product-E

Final sequence is A, B, C, D, E, A, B, C, D, E

Set up: The number of setup require is 9

Utility =

(1 −2/10)2 + (0 − 2/10)2 + (0 − 2/10)2 + (0 − 2/10)2 + (0 − 2/10)2 + (1 − 4/10)2 + (1 − 4/10)2 + (0 − 4/10)2 + (0 − 4/10)2 + (0 − 4/10)2 + (1 − 6/10)2 + (1− 6/10)2 + (1− 6/10)2 + (0 − 6/10)2 + (0 − 6/10)2 + (1 − 8/10)2 + (1 − 8/10)2 + (1 − 8/10)2 + (1 − 8/10)2 + (0 − 8/10)2 + (1 − 10/10)2 + (1 − 10/10)2 + (1 − 10/10)2 + (1 − 10/10)2 + (1 − 10/10)2 + (2 − 12/10)2 + (1 − 12/10)2 + (1 − 12/10)2 + (1 − 12/10)+ (1 − 12/10)2 + (2 − 14/10)2 + (2 − 14/10)2 + (1 − 14/10)2 + (1 − 14/10)2 + (1 − 14/10)2 + (2 − 16/10)2 (2 − 16/10)2 + (2 − 16/10)2 + (1 − 16/10)2 + (1 − 16/10)2 + (2 − 18/10)2 + (2 − 18/10)2 + (2 − 18/10)2 + (2 − 18/10)2 + (1 − 18/10)2 + (2 − 20/10)2 + (2 − 20/10)2 + (2 − 20/10)2 + (2 − 20/10)2 + (2 − 20/10)2

U = 7.99

E = WuU + WsS = (1 ´ 7.99 +1 ´ 9) = 16.99 (Wu = 1, Ws = 1),

E = 17

The obtained Miltenburg algorithm sequence is A, B, C, D, E, A, B, C, D, E. Now this seed sequence will generate the following five sequences randomly by using method of VBA Microsoft excel for the position of product to be produced like sequence-1 as A, C, E, B, D, C, D, A, E, B, sequence-2 as E, A, C, D, A, B, B, D, C, E, sequence-3 as B, C, C, B, A, E, A, D, D, E, sequence-4 as B, E, A, B, D, A, C, D, C, E, and sequence-5 as D, C, C, B, A, E, A, B, D. For initial trial, five random sequences as said above are generated and the corresponding objective function values are calculated as E1 = 17, E2 = 18, E3 = 29, E4 = 23, E5 = 21.

5.2. SA Algorithm

Step 1: Find the initial temperature

From initial trial, take Emax, Emin

T0 = 18.200

Step 2: Final temperature, Tfinal = ΔEmin = 17.00

Step 3: Temperature change

T1 = 18.2000, T2 = 18.1964, T3 = 18.1928

T4 = 18.1892 as like T5 = 18.18 to Tn

Step 4:

Consider initial sequence obtained from Miltenburg algorithm and the initial energy state is its objective function value (E0) = 17. Now randomly generate sequences by VBA Microsoft excel method and calculate corresponding energy state by its objective function value

E1 = 19, E2 = 17, E3 = 20

E4 = 26, E5 = 19, E6 = 32, ×××, En

ΔE = E1 − E0 = 19 − 17 = 2

Step 5

Check whether ΔE < 0, 2 < 0, No, generate random number X = 0.90

Find

Check X < e-∆E/T, 0.90 < 0.89 No, the energy state is rejected.

Go to step 4, generate another sequence by random method

New sequence is 3425123145 and objective function value E2 = 17,

, yes, store the energy state, E0 = E2

Go to step 4, generate another sequence by random method

New sequence is 5341132425 and objective function value E3 = 20,

, NO, find

Generate random number X = 0.46, Check 0.46 < 0.84 then accept the energy state reset E = E2 then go to next iteration, up to 10 iteration, repeat procedure then reduce the temperature from 18.22 to 18.19 and continue the process. Up to reach of final temperature 17.00, the number of sequence generated is 3594. Finally, the obtained sequence is E, D, C, B, A, D, A, C, B, E and objective value is 15.99 by simulated annealing, which is minimum compared with Miltenburg algorithm. The comparison of numerical results sequence is shown in Table 3.

6. Experimental Design and Discussion of Results

The three problem sets are taken from [7] for analysis. The problem set 1 contains 7 types of problems with total demand is 10 each. The obtained results are tabulated in Table 4. The solution obtained is 2524 to 4104. The

Table 3. Comparison numerical results sequence.

Table 4. Solution for problem set 1.

Sequence (A-1, B-2, C-3, D-4, E-5).

problem set 2 contains 9 types of problems with total demand is 12 each and the results are tabulated in Table 5. The solution obtained is 4300 to 5680. The problem set 3 contains 9 types of problems with total demand is 15 each and the results are in Table 6. The solution obtained is 8524 to 11104.

Table 5. Solution for problem set 2.

Sequence (A-1, B-2, C-3, D-4, E-5).

Table 6. Solution for problem set 3.

Sequence (A-1, B-2, C-3, D-4, E-5).

The Miltenburg algorithm, Random generation algorithm and simulated annealing algorithm are coded in Microsoft Excel in macro and executed on an Intel processor at 2 GB under windows XP using 250 MB of RAM. The problem set 1 has solved with 7 types problem for all problems to all demand of product is equal but demand of each product is different for each problem.

The 4 types of heuristics have been solved. The Heuristics 1 has minimum weightage for both setups a usage rate. Heuristics 2 have a composite value of 14.755 for setup. The coefficient used from the sampling, so the setup and material usage made equal contribution to the objective function. Heuristics 3 is weighted three times important of setup than minimum usage rate. Heuristics 4 is three times of usage rate than setup. So the importance of usage rate is three times than minimum setup. The all the problems with heuristics 1 to 4 are solved by Miltenburg algorithm and simulated annealing algorithm. The two methods are compared by RPT.

As shown in Table 7, in Heuristics1 (Wu = 1, Ws = 1) the weightages of setup and utility are 1, denote as w. In Heuristics 2 (Wu = 1, Ws = 14.27) the weightages of setup is 14.27 and utility are 1, denote as w1. Heuristics3 (Wu = 1, Ws = 42.81) the weightages of setup is 42.81 and utility are 1, denote as w2. Heuristics 4 (Wu = 3, Ws = 14.27) the weightages of setup is 14.27 and utility are 3 denote, as w3 . All the results obtained by heuristics 1 to 4 are tabulated. For all the problem sets, the solutions obtained by Simulated Annealing heuristics shows minimum compared with Miltenburg Algorithm.

The number of setup is equal or small reduction. The comparison results of heuristics 1 to 4 are tabulated in Table 8. Heuristics 1 show RPT of 0% to 7.01% and number or setup is low in SA compare with Miltenburg. In SA number or setup is requires is 4 to 8 where as in Miltenburg are 7 to 9. The objective function in SA is 13 to 14.69 where as in Miltenburg are 13.90 to 17. In this number or setup and usage rates is balance in SA compare with Miltenburg.

In heuristics 2 shows RPT of 24 to 38.47% and number or setup is low in SA compare with Miltenburg. In SA number or setup is requires is 4 to 7 where as in Miltenburg are 9. The objective function in SA is 85 to 80.35 where as in Miltenburg are 136.47 to 106.89. In this number or setup and usage rates is balance in SA compare with Miltenburg.

In heuristics 3 the RPT is 49.35 to 35.45 Miltenburg the number or setup is 9. The objective function in SA is 202.2 to 198.30 whereas in Miltenburg are 391.23 to 306.7. So the setup and usage rate is much balance in simulated annealing but in heuristics 4, the RPT is 27.85 to 13.75 the objective function value in SA is 127.65 to 98.67 but in Miltenburg is 152.47 to 104.37.

In problem set 1, heuristic 3 shows high RPT. But the utility is more and setup is less. In heuristic 1 and 4 shows low utility and setup is high. In heuristic 2, balancing the setup and utility as well as the RPT is high. The Problem type F (5 2 1 1 1) shows utility 11.02 and setup 5, objective function value is 82.37 RPT is 38.4. The

Table 7. Heuristic weightages.

Table 8. Comparison results of Miltenburg and simulated annealing for heuristic 1 to 4.

optimum sequence is D, A, A, A, B, B, E, C. In problem set 2 the heuristic 3 shows high RPT. But the utility is more and setup is less. In heuristic 1 and 4 show low utility and setup is high and RPT is low. But in heuristic 2 shows the RPT is moderate as well as balancing the utility and setup.

In problem type F (5 2 2 2 1) shows the utility 20.69 and setup 6 and objective function value is 106.31 and RPT is 43.25. So the obtained optimum sequence is D, E, A, A, A, A, B, B, C, C, D, A. In problem set 3 the heuristic 3 shows high RPT of 32.86, but the utility is more and setup is less. In heuristic 1 and 4 show low utility and setup is high and RPT is low. But in heuristic 2 shows the RPT is moderate as well as balancing the utility and setup. In problem type D (93111) shows the utility13.86 and setup 8 and objective function value is and RPT is 28.67. So the obtained optimum sequence is A, A, A, B, B, C, D, A, A, A, E, A, A, B, A.

So it has been concluded that from the above problem sets analysis, RPT is high in heuristic3 for the problem set1. The simulated annealing solution is 49.35% improved then Miltenberg algorithm. The utility and setups are most minimized. The RPT is low in heustics 1 for problem set 3. The simulated annealing solution is only 5.88% improved then Miltenberg algorithm solution. From the above results, we conclude that setup is three times more important than utility.

7. Computational Time

The solutions for all the three problem sets are found and CPU time taken from each heuristic is presented. The details are presented in Tables 9-12 and the problem sets are mentioned in Annexure. In the computational problems, finding the CPU time is important because CPU time should be less. In the problem sets, the average cpu time is 70.66.and solutions is 5662.

In problem set 1, the average CPU time is 23.47 and solution is 2947. For problem set 2 average CPU time is 58.16 and solution is 4820. For problem set 3 average CPU time is 130.35 and solution is 9218.

The comparison of CPU time is shown in Figure 6. Among the all weightages, W3 have less CPU time of 66.61, no of solution is 5229 and w2 take CPU time of 66.97 for 5342 solution, and w1 take CPU time of 81.12 for 6288 solutions.

Figure 6. Comparison of CPU time.

Table 9. Computational time for problem set 1.

Table 10. Computational time for problem set 2.

Table 11. Computational time for problem set 3.

Table 12. Total average number of solutions and CPU time.

8. Conclusion

In this paper, the various heuristic methods based on simulated annealing have been studied for solving production sequence in level schedule optimization problem. The Miltenburg algorithm has been used to find the sequence for scheduling. The sequence has been modified to obtain another sequence and to get utility and setup estimations by giving different weightages. These weights are then adjusted to obtain the desired value. According to different weightages, the utility and number of setups are obtained for heuristics 1 to 4. These selective heuristics procedures are applied for both Miltenburg algorithm and simulated annealing algorithm. The proposed algorithm based on simulated annealing technique has been applied to find production sequences when objective function values of setup and usage rates are desired as minimum. The results obtained are found to be useful to take good managerial decisions on production sequences. Three problem sets up to 15 numbers of products are solved and the results obtained for all the heuristics and results are compared to obtain balanced setup and utility and minimize the objective function value.

Annexure

Problem Set 1

Problem Set 2

Problem Set 3

Cite this paper: Ramalingam, S. and Subramanian, R. (2016) Solving Level Scheduling in Mixed Model Assembly Line by Simulated Annealing Method. Circuits and Systems, 7, 907-931. doi: 10.4236/cs.2016.76078.
References

[1]   Monden, Y. (1983) Toyota Production System. Institute of Industrial Engineers Press, Norcross.

[2]   Miltenburg, J. (1989) Level Schedules for Mixed-Model Assembly Lines in Just-in-Time Production System. Management Science, 35, 192-207. http://dx.doi.org/10.1287/mnsc.35.2.192

[3]   Zhao, X.P. and Ohno, K. (1994) A Sequencing Problem for a Mixed-Model Assembly Line in a JIT Production System. Computers & Industrial Engineering, 27, 71-74. http://dx.doi.org/10.1016/0360-8352(94)90240-2

[4]   McMullen, P.R. (1998) JIT Sequencing for Mixed-Model Assembling Lines with Setups Using Tabu Search. Production Planning & Control, 19, 504-510. http://dx.doi.org/10.1080/095372898233984

[5]   McMullen, P.R. and Taransewich, P. (2000) Using Genetic Algorithm to Solve the Multi-Product JIT Sequencing Problem with Set-Ups. International Journal of Production Research, 38, 2653-2670.
http://dx.doi.org/10.1080/002075400411411

[6]   McMullen, P.R. and Frazier, G.V. (2000) A Simulated Annealing Approach to Mixed-Model Sequencing with Multiple Objectives on a Just-in-Time Line. Institution of Industrial Engineering Transactions, 32, 679-686.
http://dx.doi.org/10.1080/07408170008967426

[7]   McMullen, P.R. (2001) An Ant Colony Optimization Approach to Addressing a JIT Sequencing Problem with Multiple Objectives. Artificial Intelligence in Engineering, 15, 309-317. http://dx.doi.org/10.1016/S0954-1810(01)00004-8

[8]   Ding, Y. and Zhu, J. (2000) A Transformed Two-Stage Method for Reducing the Part-Usage Variation and a Comparison of the Product-Level and Part-Level Solutions in Sequencing Mixed-Model Assembly Line. European Journal of Operational Research, 127, 203-216. http://dx.doi.org/10.1016/S0377-2217(99)00322-7

[9]   Ponnambalam, S.G., Aravindan, P. and Subba Rao, M. (2003) Genetic Algorithms for Sequencing Problems in Mixed Model Assembly Lines. Journal of Computers and Industrial Engineering, 45, 669-690.
http://dx.doi.org/10.1016/j.cie.2003.09.001

[10]   Mansouri, A. (2005) A Multi-Objective Genetic Algorithm for Mixed-Model Sequencing on JIT Assembly Lines. European Journal of Operational Research, 167, 696-716.
http://dx.doi.org/10.1016/j.ejor.2004.07.016

[11]   Dhamala, T.N. and Kubiak, W. (2005) A Brief Survey of Just-in-Time Sequencing of Mixed-Model System. International Journal of Operations Research, 2, 38-47.

[12]   Boyson, N. and Scholle, A. (2012) Resequencing of Mixed-Model Assembly Lines: Survey and Research Agenda. European Journal of Operational Research, 216, 594-604.
http://dx.doi.org/10.1016/j.ejor.2011.08.009

[13]   Matondang, M.Z. and Jambak, M.I. (2010) Soft Computing in Optimizing Assembly Line Balancing. Journal of Computer Science, 6, 141-162. http://dx.doi.org/10.3844/jcssp.2010.141.162

[14]   Goard, V. and Jennet, J. (2010) Optimal Sequencing of Mixed Models with Sequence-Dependent Setups and Utility Workers on an Assembly Line. International Journal of Production Economics, 123, 290-300.
http://dx.doi.org/10.1016/j.ijpe.2009.09.001

[15]   Wang, H., Zhu, X.W., Wang, H., Hu, S.J., Lin, Z.Q. and Chen, G.L. (2011) Multi-Objective Optimization for Product Variety and Manufacturing Complexity in Mixed-Model Assembly Systems. Journal of Manufacturing Systems, 30, 16-27. http://dx.doi.org/10.1016/j.jmsy.2011.03.002

[16]   Yagmahan, M.M.A.L. (2011) Mixed-Model Assembly Line Balancing Using a Multi-Objective Ant Colony Optimization Approach. Expert Systems with Applications, 38, 12453-12461.
http://dx.doi.org/10.1016/j.eswa.2011.04.026

[17]   Chutima, P. and Chimklai, P. (2012) Multi-Objective Two-Sided Mixed-Model Assembly Line Balancing Using Particle Swarm Optimization with Negative Knowledge. Journal Computers and Industrial Engineering, 62, 39-55.
http://dx.doi.org/10.1016/j.cie.2011.08.015

[18]   Mosadegh, M., Zandign, M. and Fatemi Ghomi, S.M.T. (2012) Simultaneous Solving of Balancing and Sequencing Problems with Station-Dependent Assembly Times for Mixed-Model Assembly Lines. Applied Soft Computing, 12, 1359-1370. http://dx.doi.org/10.1016/j.asoc.2011.11.027

[19]   Akpinar, S., Bayhan, M. and Baykasoglu, A. (2013) Hybridizing ant Colony Optimization via Genetic Algorithm for Mixed-Model Assembly Line Balancing Problem with Sequence Dependent Setup Time between Tasks. Applied Soft Computing, 13, 574-589. http://dx.doi.org/10.1016/j.asoc.2012.07.024

[20]   Akpinar, S. and Baykasoglu, A. (2014) Modeling and Solving Mixed-Model Assembly Line Balancing Problem with Setups. Part II: A Multiple Colony Hybrid Bees Algorithm. Journal of Manufacturing Systems, 33, 445-461.
http://dx.doi.org/10.1016/j.jmsy.2014.04.001

[21]   Ding, F.Y. and Cheng, L.P. (1993) An Effective Mixed-Model Assembly Line Sequencing Heuristic for Just-in-Time Production Systems. Journal of Operations Management, 11, 45-50.
http://dx.doi.org/10.1016/0272-6963(93)90032-K

[22]   Kirkpatrick, S.C.D., Gelatt Jr., C.D. and Vecchi, M.P. (1983) Optimization by Simulated Annealing. Science, 220, 671- 680.
http://dx.doi.org/10.1126/science.220.4598.671

[23]   Wilhelm, M.R. and Thomas, L.W. (1987) Solving Quadratic Assignment Problems by “Simulated Annealing”. Institution of Industrial Engineering Transactions, 19, 107-119.
http://dx.doi.org/10.1080/07408178708975376

[24]   Golden, B.L. and Skiscim, C.C. (1986) Using Simulated Annealing to Solve Routing and Location Problems. Naval Research Logistics Quarterly, 33, 261-279.
http://dx.doi.org/10.1002/nav.3800330209

[25]   Connolly, D.T. (1990) An Improved Annealing Scheme for the QAP. European Journal of Operational Research, 46, 93-100.
http://dx.doi.org/10.1016/0377-2217(90)90301-Q

[26]   Vilarinho, P.M. and Simaria, A.S. (2002) A Two-Stage Heuristic Method for Balancing Method for Balancing Mixed- Model Assembly Line with Parallel Workstations. International Journal of Production Research, 40, 1405-1420.
http://dx.doi.org/10.1080/00207540110116273

 
 
Top