SINERGI Vol.
No.
June 2022: 137-144 http://publikasi.
id/index.
php/sinergi http://doi.
org/10.
22441/sinergi.
How to boost the flow shop manufacturing agility using hybrid Genetic Tabu Search in scheduling Moch Saiful Umam1* Jutono Gondohanindijo2 Magister Program of Information System.
School of Postgraduate Studies.
Diponegoro University.
Indonesia Department of Informatics.
Faculty of Engineering and Informatics.
AKI University.
Indonesia Abstract The hybridization between evolutionary genetic algorithm and tabu search has been proposed in this paper to address flow shop It accommodates jobs that need to be rearranged and executed on identical machines serially.
High agility is required in the manufacturing process, especially for the garment industry to be able to stand facing competitors.
The manufacturing related to scheduling to deliver a product as early as possible, the tardiness, and waiting time are also concerned.
A Genetic Algorithm was widely used to deal with this.
which finds an optimal solution to the problems because it can obtain a more optimal solution.
Unfortunately, it is easy to get stuck in optimum local .
arly convergence is faste.
The tabu search algorithm works as a local explorer to better find and exploit the optimum local area, which can be combined with a Genetic Algorithm.
This study aims to minimize the three objectives mentioned above to increase production agility.
These strategies are evaluated on Taillard benchmark problems to show the significance of the proposed algorithm.
The outcomes prove that the hybrid mechanism can boost the solution quality by 75% compared to our previous work and can resolve all of Taillard instances better.
It has been proven by a 0.
28% percentage relative deviation, which shows the error rate is lower and means Keywords:
Agility.
Flow Shop.
Genetic Algorithm.
Production Scheduling.
Article History:
Received: May 2, 2021 Revised: December 15, 2021 Accepted: December 26, 2021 Published: June 1, 2022 Corresponding Author:
Moch Saiful Umam Magister Program of Information System.
School of Postgraduate Studies.
Diponegoro University.
Indonesia Email: itgov@yandex.
This is an open access article under the CC BY-NC license INTRODUCTION The fashion industry's growth reached the international business level across all sectors Ae from independent boutiques to worldwide brands, from raw material to finished goods selling, and also comes from small retailers to big wholesalers .
The fashion industry business model must provide services or goods as quickly as possible to the shopper, known for its agility due to information technology innovation, short product cycles under competitive market pressures, changing consumer needs, and unreliable demand conditions .
Agility is strongly influenced by activities in the production process, especially in the scheduling of products to be made .
, so good production scheduling is needed to adapt to varying market changes.
In addition, scheduling is one of the most critical elements in business administration and information systems because a good schedule allows management to have all necessary parts at hand when they are needed .
Production scheduling is defined as a process that combines sales forecasting and manufacturing planning .
They are important to control resources in a complex production environment with many different machines and While the two are separate, when combined, they have the potential to increase a business's productivity, accuracy, and agility .
A well-known scheduling problem that Umam & J.
Gondohanindijo.
How to boost the flow shop manufacturing agility using A SINERGI Vol.
No.
June 2022: 137-144 attracts many researchers is flow shop scheduling which is used when the product is similar in nature and requires almost identical processing time for each job, such as garment production .
A flow shop is a family of scheduling problems for which there is a precedence relationship between tasks and also capacity limits on resources along with .
Production scheduling means controlling the resources .
to produce useful results at minimum cost with maximum effectiveness.
Unfortunately, a problem occurs in scheduling when several tasks have to be completed in a given time with limited resources.
Still, there is no clear instruction on which tasks should be completed first and which later.
A Genetic Algorithm (GA) is widely utilized to deal with problems in scheduling .
and is categorized as an evolutionary algorithm that is motivated by genetic evolution through natural selection .
The algorithm selects the optimal solution for its fitness or objective function and puts it into a new generation.
In some cases, those solutions are then modified by operators such as manipulating algorithms.
The common sense of GA is that it copies the parent's strategy and modifies it for producing children, which are realistic solutions hard to find through common optimization algorithms.
Unfortunately.
GA often suffers from the drawbacks of premature convergence and weak exploitation capabilities trapped in optimum local .
In other places, there is a good algorithm in performing exploitation for flow shop where the goal is to seek for a result with high-quality criteria, rather than merely find a solution called with tabu search .
, 14, .
The Tabu Search (TS) idea is quite straightforward.
The algorithm begins with a solution and then explores its neighborhood for a suitable new neighborhood.
The search approach extends beyond local optimality to examine the solution space by allowing moves to neighbors with poorer The important aspects of the exploration track are selectively memorized .
ia a tabu lis.
, and proactive decisions are taken so that they can steer the exploration away from optimum local toward different areas inside the solution space.
If a halting criterion is met, then the algorithm terminates itself.
This study introduces a hybrid method to address the GA's shortcomings.
These are tabu search algorithms combined with GA to increase the manufacturing agility in the The rest of the article's structure is mentioned as the following.
A concise summary of the research that has been done is presented in the materials.
The method section also discusses the fusion of the proposed GA and TS algorithms.
Then, experimental studies are presented in the next section, and conclusions with future works in the conclusion section.
METHOD
An improved hybridization between GA and TS methods is proposed for achieving manufacturing agility using three steps.
First, data gathered from the Taillard dataset is partitioned into several subsets.
Second.
GA is applied to the first subset to get the initial Third.
TS is utilized to enhance the solution quality found by GA.
The Proposed Algorithms Throughout this section, the multi-objective scenario is given first as the paper's contribution to developing an optimization algorithm based on partial opposed-based learning.
Notably, the initialization uses a partial opposed-based approach, consistent with our previous work .
There are a few parallels between them.
In detail, both algorithms randomize, then divide the population into two sections and create one of them using an opposed-based strategy.
According to our earlier work, this algorithm is only applicable to single-objective optimization Although the number of objectives in this paper is significantly greater than in our prior work, it is designed to deal with multi-objective optimization problems.
Thus, it is started by describing a multi-objective problem, followed by GA and TS parts.
Multi-Objective Problem The paper considers the multi-objective optimizer for scheduling problems to discover a feasible solution under three different objectives:
finding the shortest job completion time, minimal tardiness, and total waiting time between jobs at the same time.
The optimal solution is declared as the following:
Supplied with are the objectives to be lessened, x is the decision vector, while the X is the decision space.
Inserting TS into GA The key idea of the GA is based on the fact that human beings make decisions by comparing the current situation with the previous In order to make GA more intelligent.
TS helps GA by integrating TS into the GA Umam & J.
Gondohanindijo.
How to boost the flow shop manufacturing agility using A p-ISSN: 1410-2331 e-ISSN: 2460-1217 process to result in a more optimal solution.
uses fine-tuned parameter configuration provided in Table 1 and contains some phases.
Table 1.
Configuration for GA-TS
Configuration Iteration Population Crossover Mutation Tournament length
Tabu length
Size
Phase 1: encoding the solution 1 Gene C set of job
2 Chromosome C set of job sequence 3 Distribute time t needed on every gene
Phase 2: population initialization 1 Generate n size population randomly 2 Split population becomes two section
3 Process section part by partial opposition based strategy to take the best fitness by comparing opposite point
Phase 3: fitness checking 1 If iteration is not reached, do 2 Evaluate population by fitness objective 3 Update the solution Phase 4: parent selection 1 E C elitist fitness 2 F C current fittest solution 3 For an individual to tournament size, do 4 NF C new fittest solution resulted from 5 If NF > F
6 F C NF
7 Return F and save to elitist Phase 5: offspring generation 1 // crossover .
wo-poin.
2 Randomly decide on two chromosome 3 Choose two barriers to exchanging 4 Exchange chromosome inside the barrier to generating solution 5 // mutation .
6 Select two points in a chromosome 7 Swap the chosen point to generate a new Phase 6: tabu search task 1 Rule the tabu list size, aspiration criteria, and stop regulation 2 Make a move to search solution space using insertion and swap strategy 3 Renew the solution using the best new one which is not saved in the tabu list 4 Stop exploration when stop regulation Phase 7: decoding the solution 1 Gathering job sequence 2 Gathering machine with processing time 3 Load Gantt chart construction Visually, the algorithm runs using flow as shown in Figure 1, starting with solution encoding as a sequence table followed by initializing the population using the partial opposed-based method from our previous study.
Then do a fitness check.
This paper has three objectives function to minimize the makespan or the shortest of job finished time, minimal tardiness, and total waiting time, respectively:
Where:
: set of job : set of machine C(Ji, .
: completion time job J, machine m T(Ji, .
: job J tardiness which is processed on machine m W(Ji, .
: waiting time job J, machine m .
= 1, 2.
A, .
= 1, 2.
A, .
This study assumes that operation preemption is prohibited.
Thus, a machine can execute a job operation if only the previous operation has already finished its process.
Also, processing time may be zero because not all operations are processed on all machines.
A flow shop is how to rearrange the order of the jobs using an identical machining sequence.
Next, two chromosomes are selected as a parent using tournament selection which is commonly used by the researcher .
, 18, .
, and the best chromosomes are saved to the elitist solution.
It is intended to generate offspring using two-point crossover .
and swap mutation .
to maintain diversity for entering the reproduction phase 5.
Figure 1.
Proposed GA-TS Algorithm Umam & J.
Gondohanindijo.
How to boost the flow shop manufacturing agility using A SINERGI Vol.
No.
June 2022: 137-144 Figure 2.
Example of Gantt Chart After passing the genetic operator, the chromosome is processed by tabu search exploiting the solution space using the insertion and swap strategy .
to result in the new Finally, the algorithm decodes the optimal solution as the Gantt chart, which provides the job sequence and needs time to make products.
Figure 2 shows the chart of how to schedule three different jobs and types of RESULTS AND DISCUSSION The hybrid GA-TS is applied to the Taillard problem .
to provide a fair computational experiment throughout this section.
This dataset is publicly available and contains the results of a competition to examine the best possible solution to a problem.
The dataset contains 120 instances, each of which has a different solution.
Therefore, the compared algorithms treated all instances for simplicity.
The proposed algorithm is executed by employing a 1.
9 GHz processor, using a memory of 4 GB, and coded in Python The best solution is presented in Table 2, which summarizes the findings.
Additionally, for numerical analysis, we collect the Percentage of Relative Deviation (PRD) for the 120 instances over ten number runs to show the average error among a solution of the proposed algorithm and the lowest known upper bound values, where a lower PRD indicates a better algorithm, formulated as:
Where:
: number of instances GATS2 : best solution from proposed GA-TS : Taillard upper bound, the best known solution for Taillard Regarding the hybrid strategy.
GA has been hybridized to achieve one or more objectives with various algorithms, such as tabu search .
, which successfully improves the solution quality by 115 of 120 Taillard instances over hybrid genetic simulated annealing five other GA cooperation with PRD 3.
Thus, this proposed algorithm (GATS.
is compared to the algorithm in our previous work (GATS.
, genetic (GAVNS) by .
, which is superior to the single variable neighborhood search algorithm, and finally compared to hybrid evolution strategy (HESSA) studied by .
The proposed GA-TS solves each Taillard instance.
The best-known upper bounds or optimal solutions for these problems are utilized to facilitate comparison.
compare algorithm performance using the percentage of increase (PI) between the current algorithm upper bound and Taillard upper bound, calculated as:
Here we go for the experiment result.
Please note that the last column of Table 2 indicates the percentage of increase for GATS2 compared to every Taillard upper bound and can be used to calculate PRD.
Table 2.
Experimental Results Problem
GAVNS GATS1
HESSA GATS2
Tai001
Tai002
Tai003
Tai004
Tai005
Tai006
Tai007
Tai008
Tai009
Tai010
Tai011
Tai012
Tai013
Tai014
Tai015
Tai016
Tai017
Tai018
Tai019
Tai020
Tai021
Tai022
Tai023
Tai024
Tai025
Tai026
Tai027
Tai028
Tai029
Tai030
Tai031
Tai032
Tai033
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
Umam & J.
Gondohanindijo.
How to boost the flow shop manufacturing agility using A p-ISSN: 1410-2331 e-ISSN: 2460-1217
Problem
GAVNS GATS1
HESSA GATS2
Problem
Tai034
Tai035
Tai036
Tai037
Tai038
Tai039
Tai040
Tai041
Tai042
Tai043
Tai044
Tai045
Tai046
Tai047
Tai048
Tai049
Tai050
Tai051
Tai052
Tai053
Tai054
Tai055
Tai056
Tai057
Tai058
Tai059
Tai060
Tai061
Tai062
Tai063
Tai064
Tai065
Tai066
Tai067
Tai068
Tai069
Tai070
Tai071
Tai072
Tai073
Tai074
Tai075
Tai076
Tai077
Tai078
Tai079
Tai080
Tai081
Tai082
Tai083
Tai084
Tai085
Tai086
Tai087
Tai088
Tai089
Tai090
0,00
0,00
0,00
0,00
0,00
0,00
0,00
1,10
0,52
0,46
0,00
0,20
0,00
0,19
0,03
0,17
0,39
1,01
0,43
0,74
0,91
0,94
0,73
1,35
0,54
0,77
0,59
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,02
0,00
0,00
0,02
0,02
0,14
0,07
0,00
0,89
0,65
0,86
0,54
1,05
1,05
0,61
1,11
0,88
0,34
Tai091
Tai092
Tai093
Tai094
Tai095
Tai096
Tai097
Tai098
Tai099
Tai100
Tai101
Tai102
Tai103
Tai104
Tai105
Tai106
Tai107
Tai108
Tai109
Tai110
Tai111
Tai112
Tai113
Tai114
Tai115
Tai116
Tai117
Tai118
Tai119
Tai120
GAVNS GATS1
HESSA GATS2
0,09
0,07
0,00
0,00
0,02
0,04
0,13
0,01
0,15
0,22
0,76
0,62
0,86
0,90
0,45
0,80
0,62
0,56
0,65
0,59
0,49
0,98
0,47
0,61
0,63
0,64
0,53
0,80
0,84
0,60
Table 2 demonstrates that the GA-TS method makes deeper exploitation inside the solution space and discovers a higher quality of Visual charts of the data can be seen in Figure 3 for 1 to 60 instances and Figure 4 for 61 to 120 instances.
We know from these two figures that HESSA and GATS2 are very close in the resulting solution, so we bold the better solution between the two algorithms in Table 2.
Figure 3.
Solution for Tai001 Ae Tai060 Umam & J.
Gondohanindijo.
How to boost the flow shop manufacturing agility using A SINERGI Vol.
No.
June 2022: 137-144 algorithms so that each algorithm contributes to the solution process to solve the objective Therefore, any problem solved using both GA and TS can benefit from this algorithm since its hybridization feature brings significant improvements in solution quality.
Table 3.
Average Execution Time of GA-TS Figure 4.
Solution for Tai061 Ae Tai120 From the computation time used, we can average the time needed in Table 3.
The table shows that the more significant problem instance to be solved, it needs more time for the proposed GA-TS to solve.
Based on Table 2, the PI column's sum can be calculated that the sum is 33.
So, the PRD for the GA-TS algorithm is calculated as Problem Time .
0,994 2,337 5,872 3,671 13,138 34,058 Problem Time .
9,797 27,335 65,923 76,429 246,892 839,868 Table 4.
PRD Comparison
Algorithm
GAVNS
GATS1
HESSA
GATS2-120
GATS2-110
Instance Eu PI
4588,16
366,09
40,67
33,46
26,87
PRD (%)
41,71
3,05
0,34
0,28
0,24
Table 5.
Percentage of Increase A comparison of PRD for another algorithm is presented in Table 4.
There is a difference between GAVNS, it is only used for the first 110 of the Taillard instance, so we calculate for the GATS2 twice to make a fair comparison.
The first contains 120 instances, and the second contains the first 110 instances.
The result that both GA-TS using 110 or 120 instances achieve the lowest PRD, which is the best, can be visually conferred in Figure 5.
The main goal of this hybridization is to combine the power and flexibility of both Problem
Size
Average PI of GATS2 Compared to GAVNS
GATS1
HESSA
21,10
1,78
0,00
31,01
3,15
0,00
32,97
3,04
0,00
19,50
0,98
0,02
42,81
4,52
0,12
57,70
5,97
-0,02
18,67
0,85
0,00
42,43
2,00
0,09
68,43
1,75
0,14
42,96
2,04
0,04
76,10
4,89
0,32
2,06
0,01
41,24
2,75
0,06
Figure 5.
PRD Comparison Umam & J.
Gondohanindijo.
How to boost the flow shop manufacturing agility using A p-ISSN: 1410-2331 e-ISSN: 2460-1217 Figure 6.
PI of GA-TS Compared We can measure the improvement using a percentage increase provided in Table 5, which compares the proposed GA-TS (GATS.
algorithm improvement with other algorithms.
The GA-TS algorithm can improve solution quality in all Taillard instances.
Figure 6 shows the percentage of achieved improvement.
The GA-TS improved HESSA by 0.
06% on average, improved the GAVNS by 41.
24% on average, and improved our previous work on GA-TS by 75% on average.
CONCLUSION
This paper gave GA-TS hybridization to deal with the scheduling problem of flow shop to improve solution quality.
By using our partial opposed initialization in GA, it is effective in addressing multi-objective scenarios.
In addition, proper parameter tuning such as two-point crossover and simple swap mutation help GA-TS to perform their task easily.
By employing the insertion and swap method for TS, the GA perform exploitation deeply and results in better solution quality.
The experiment shows that the GA-TS has the lowest PRD .
28%) and can improve all Taillard instances.
Also can improve the previous work by 2.
Future work will examine the extensive use of another evolutionary algorithm combined with GA because of its superiority.
REFERENCES