0021-01-0036-0004-16.pdf491.5KB

• 1. Introduction
• 2. Process Analysis
• 2.1 Production Process Analysis
• 2.2 Scheduling Analysis
• 3. Development of Genetic Algorithm Applied Model
• 3.1 Initial Population Generation
• 3.2 Chromosome Pair Selection
• 3.3 Crossover
• 3.4 Mutation
• 3.5 Generate New Population
• 4. Comparison of Worker Assigning Case to Machine
• 4.1 Case 1
• 4.2 Case 2
• 4.3 Case 3
• 4.4 Result Comparison
• 5. Dynamic Scheduling Model Verification by Simulation
• 6. Conclusion
• Acknowledgement

1. Introduction

Companies are getting more interested in production scheduling because it is an essential element in reducing lead time, enhancing production efficiency and resource utilization to ultimately improve company-wide competitiveness and productivity. To this end, scheduling should be made in consideration of unique and specific individual processes and work order should be designed by reflecting a deadline to cut the cycle time to a minimum level. 

There has been a various ways of approaching to scheduling problem using GA. To get an efficient answer, GA and other scheduling rules, shortest processing time (SPT), Maximum Work Remaining (MWKR) integrated [1]. When comparing tabu search and GA for scheduling problems, it is proved that GA show more effective [2]. Hybrid GA also applied for the job shop scheduling problem [3]. GA applied to manufacturing systems, which is based on simulation and analyzed by experimental design [4]. Parallel machine scheduling problem was approached by GA and simulation to minimize the maximum completion time (makespan) [5]. Integration of scheduling heuristic and GA applied to job-shop scheduling problem to minimize weighted tardiness [6]. A twostage methodology designed for short-term batch plant scheduling like semiconductor application. In this research, first stage is done by discrete-event simulation and second stage was investigated by GA. This approach was opposite way of our research [7]. 

This research analyzed the real manufacturing problems. The company wants to meet a due date, avoid deadlock, and increase resource utilization within limited resources. Based on existed scheduling data, the study will develop GA applied dynamic scheduling model. Through dynamic scheduling model, optimal work order sequence will be given to manufacturing department depends on given work scheduling data and it will be verified through simulation software, Arena.  

2. Process Analysis

Process analysis is to understand the current production process and analyze the original scheduling, which will be rescheduled according to this research. 

2.1 Production Process Analysis

Currently the production process is structured by following the work order. C1 process is the first stage for product coating and then C2 is a process for work preparation and second coating. In these processes, an ordered number of products are manufactured for each roll. 

<Figure 1> Production Process

The next step is processed by an outsourced company before releasing. C1 process requires 1 machine and 1 employee and C2 process needs 2 sets. Each of set composed of 2 machines and 3 workers. For the outsourced process, 2 sets of machines should be operated by 6 workers. In the C2 process, for each set, work preparation required 2 workers and second coating needs just one worker. When both of machine have to work preparation within each set, two workers will be assigned to available machine, however one worker have to wait until they are finished, because two workers needed for the preparation work. Here arises the possibility of work delay and long cycle time due to work overlap during the preparation. 

<Figure 2> C2 Process

As process go on, there will be a long queue, lead time for the production will be increased and workers will be in an idle status. When considering total process, C2 process will be a bottleneck process. This study will focus on C2 process to resolve the bottleneck problem. There will be no change for C1 process and outsourced process since there have efficient work flows. 

2.2 Scheduling Analysis

Pre-scheduling is always given for 7~15 days production planning in advance. But, if producing with given schedule, there will be lots of works are overlapped for each set and this causes a bottleneck and long cycle time like shown in <Figure 3>. And also it is difficult to finish all of the work within the due date.  

<Figure 3> Work Sequences for Pre-schedule in C2 Process

 To avoid overlapping and to meet the due date, the preschedule have to be rescheduled by using GA with limited work resources in each set. The overlap works are only existed in preparation time since this work needed two workers. 

3. Development of Genetic Algorithm Applied Model

Based on pre-scheduled data, this study will perform the rescheduling of the current C2 work process by using GA and coded in Matlab software environment. The current process modeling followed the work order of the pre scheduling 

Work Order = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35]  

The Completion time of C2 process is shown below in <Table 1>. C2 process work finish time of this schedule is 278.7 hours and 2.4 hours were found to be the overlapping time.  

<Table 1> C2 Process Work Completion Time

GA is a statistics-based search algorithm and develops a dynamic scheduling model in phases as follows. 

<Figure 4> Development Stage of the Genetic Algorithm Model

3.1 Initial Population Generation

Before developing GA applied model, setting the size and crossover probability of a universe and crossover rate. Generally N, the size of population is set at 50; Pc, a general ratio, is 0.7; Pm, crossover ratio, is normally set range of 0.001~0.01, fix at the value of 0.001. Initial 50 populations will be generated randomly, but there will be a constraint about work overlapping time. Choose the initial population which has the under the 300 hours of cycle time to find a solution fast.  

<Figure 5> Generate Initial Population

And a fitness function is defined to measure each chromosome performance, goodness of fit and goodness-of-fit ratio. 

F(p) =
F(P) = Fitness function, C_T = Finish time of C2 Process
M_1T = Finish time of machine1, M_2T = Finish time of machine2
M_3T = Finish time of machine3, M_4T = Finish time of machine4
O_T = Overlap time 

3.2 Chromosome Pair Selection

Chromosome pair selection is a phase to select a pair of chromosome for crossover. 50 populations will be in 25 pairs by using the method of Roulette Wheel Selection. The Roulette Wheel Selection method shows that higher goodness of fit has the wide area as shown in Figure 6. And the wider area has the higher possibility to be chosen as a pair. 

<Figure 6> Roulette Wheel Selection

This study creates a random number first and with this random number choose chromosome having the corresponding accumulated goodness-of-fit ratio. Such selection method will be repeated 50times until match all of the 50 populations. At the end 25 pairs will be acquired. 

3.3 Crossover

Crossover operator should determine the breaking point from a pair of parent chromosome. If setting the crossover rate as 0.7, a breaking point will be chosen to carry out the crossover. As shown in <Figure 8>, crossed chromosomes among the overlapped chromosomes are left and not crossed ones are chosen to do the crossover. This process excludes the same gene in the same group to avoid the duplicate work order between 1 and 35. 

<Figure 7> A Pair of Chromosomes was Selected

<Figure 8> Step of Crossover

3.4 Mutation

Mutation operator is a stage of randomly choosing a chromosome and exchanges the gene. Mutation ratio of 0.001 applied to conduct the mutation of the randomly selected chromosome as in the <Figure 9>.  

<Figure 9> Step of Mutation

<Figure 10> Initial Population and Newly Generated Population

3.5 Generate New Population

Through crossover and mutation processes, new 50 populations are generated from initial 50 chromosomes. The new populations follow the same process from the goodness-of-fit calculation step and repeat the crossover and mutation again. This process will be repeated until reach to the 100^th round in consideration of empirical appropriateness of convergence. 

As shown in the above results, 50 randomly chosen groups are created under the condition within 3 overlapping work hours. And these groups will determine 35 work orders. If crossover and mutation are repeated by utilizing GA, 50 new groups are generated continuously and work order will be converged. If we could get optimal work order before 100^th step, then the process will be stopped. 

4. Comparison of Worker Assigning Case to Machine

The result gained by applying GA to a dynamic scheduling model is compared with pre-scheduling, which is called original in this chapter. There will be 3 cases. In case 1, as shown in <Figure 2>, <Figure 3> workers assigned to 2 machines. For the case 2, workers can be committed to any machines. Only 2 workers can be charged to any machines in case 3. For each case, generate the work order depends on each case. So there will be 3 work orders will be obtained. 

4.1 Case 1

As a result of applying a dynamic scheduling model to the process of 3-worker teams managing 2 machines, it was found that the groups work order converged to an identical order. 

Order_Case1 = [6 12 5 17 24 18 21 30 23 3 34 22 9 29 19 15 35 10 25 16 2 27 31 14 28 13 11 26 1 32 8 4 20 33 7]  

As the processes are repeated, an optimal work order emerged and the nature of forming the same work order group was found. In this process, the average values of goodness of fit were converged and so was the optimal goodness of fit. The maximum value of the group’s goodness of fit, work completion hours and overlap time are found as below : 

Fitness_Max = 36.4100
Completed_Time = 266.8000
Overlap_Time = 0 

4.2 Case 2

The result of applying a dynamic scheduling model to the process of all 6-workers managing all of the machines is the following work order.  

Order_Case2 = [6 34 29 10 35 2 19 12 32 27 8 5 21 26 1 17 4 33 23 9 31 24 13 20 18 25 7 14 11 16 30 15 28 22 3] 

The maximum value of this group’s average goodness of fit, and work completion hours and overlap time showed the following results. 

Fitness_Max = 39.5700
Completed_Time = 261.9000
Overlap_Time = 0 

4.3 Case 3

The result of applying a dynamic scheduling model to the process of groups of 2 workers operating 2 machines and the remaining two workers managing all the 2 machines was found as follows. 

Order_Case3 = [16 6 2 13 30 11 18 12 3 25 1 7 10 28 4 19 35 33 5 14 26 15 29 9 21 24 34 27 17 31 32 8 20 23 22] 

Fitness_Max = 36.6800
Completed_Time = 261.8000
Overlap_Time = 0 

4.4 Result Comparison

This study compared the results from the prescheduled production process model and those from each case above in the following table. 

From the <Table 2>, Case 1, 2, and 3 have the higher values of goodness of fit and ensure the more efficient processes. By clearing all of the overlap time, cycle time for C2 process has decreased. These lead to the conclusion that GA applied dynamic scheduling model played a great role in finding an efficient work order. Especially, case 2 and 3 show distinguished decrease of cycle time. With such an efficient scheduling in place, producers can get the minimum hours required to meet a deadline or to complete work, minimum inventory under process, and minimum machine and worker idling hours. Therefore, case 2 and 3 can be recommended to the director of production field. 

<Table 2> Dynamic Scheduling Model Result Comparison

5. Dynamic Scheduling Model Verification by Simulation

After developing dynamic scheduling model, wants to verify that this model can be applied to the work area in real by Arena, simulation software. If there is a big difference about C2 process cycle time between the obtained schedules and simulated model, it implies that one of the models has a critical problem. Or if there is a bottle neck or overlap existed, it cannot be directly implement to the work field. In either case, have to go back to the previous process and try to get another GA applied schedule that can be executed to the work area right away. This is the reason why name it as dynamic schedule. For each case 1, 2 and 3, 50 different populations will be generated, and each of population will be simulated. The C2 process cycle time will be verified for each population by using paired t-test. If there is a statistically difference between GA applied model and simulated model, then we could conclude that two models are different and cannot be applied to the work field. Output Analyzer analysis involves paired t-test with confidence level at 95%. 

H0 : Two models are identical
H1 : Two models are different 

As for Case 1, the simulation result was insignificant which is shown in <Figure 11>. That is, the result of the GA applied model and the result of simulation are statistically not different. 

<Figure 11> Pair t-test Result (Case 1)

The above <Figure 12> is Case 2 model comparison. The simulation result is also not significant. This means that the result of the two models under the 95% confidence level is statistically identical model.  

<Figure 12> Pair t-test Result (Case 2)

The <Figure 13> is Case 3 model comparison. Case 3 also presented insignificant simulation findings. This means the same conclusion with the result of the simulation under the 95% confidence-level paired t-test. 

<Figure 13> Pair t-test Result (Case 3)

These lead us to the conclusion that all of the 3 cases are statistically insignificant. The simulation which was performed to see if GA applied dynamic scheduling model can be used in the actual production area, verified no difference in the measured C2 process cycle time. And developed schedule avoid overlapping time so it will reduce the cycle time. Such a finding enables our expectation that applying a dynamic scheduling model can give great benefits in enhancing compliance with deadline and maximizing machine and personnel efficiency. 

6. Conclusion

This study developed the genetic algorithm applied dynamic scheduling model and verified the developed model through simulation. The purposes of this study were deadline compliance, minimize total cycle time, minimum inventory under process, and minimize machine and personnel idling time.  

This research found that applying work order coordinated by genetic algorithm to a bottleneck process node, deadline satisfaction rate could grow higher, total cycle time could be minimized, work overlap can be removed and machine and personnel utilization could be maximized to cut their hours in idle status to the minimum. This research also suggested 3 cases of assigning workers to machines and showed that which case is the best. And all of 3 cases simulated to see that these cases could be applied to work area. After simulating the C2 process cycle time for statistical verification, reached a conclusion that the developed work schedule was not different from the simulation model. It implies that genetic algorithm applied schedule can be practically implemented in the work field.  

Further study seems to be needed in terms of the comparison of labor cost and machine operation cost to set a more cost effective work order. Since this study examined processes which tend to require longer working hours to deal with a single order, it had to develop a scheduling model only for 35 orders of products. But with larger scheduling data collection, the model will become more valid to be used in the field. 

Acknowledgement

This paper was supported by Research Fund, Kumoh National Institute of Technology.