Jurnal Teknik Industri Vol.
No.
February 2023, pp.
ISSN: 1978-1431 print | 2527-4112 online Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan Eka Pakpahan a*.
Kenneth David Sumarna a a Institut Teknologi Harapan Bangsa.
Bandung.
Indonesia * Corresponding author: eka@ithb.
ARTICLE INFO
Article history Received.
June 14, 2022 Revised.
November 4, 2022 Accepted.
December 23, 2022 Available Online.
March 27, 2023 Keywords Scheduling Heuristic Algorithms Flexible machines Job Shop Makespan ABSTRACT This research examined the scheduling of jobs with multiple stages unto identical parallel machines to minimize the The work is motivated by a Flexible Manufacturing System case that produces various parts and has multiple machining centers.
Early research towards this system proposed a stage-by-stage independent scheduling, resulting in a nonoptimal solution.
This study aimed to create a better solution for the system by developing a novel heuristic algorithm based on the classical longest processing time algorithm and simultaneously considering processing time for all stages when deciding the job sequencing and job-machine allocation.
The algorithm is defined as Modified LPT for Multiple Identical Machine with Multiprocess Capability (M-LPT MIMMPC).
We performed a numerical experiment to assess the algorithm's performance by incorporating various cases.
We concluded that the resulting makespans are always better than LPT's theoretical bound for parallel machine scheduling.
In some cases, it successfully gave an optimal value.
Although the experiment scope was still limited, the algorithm showed promising performance results.
This is an open-access article under the CCAeBY-SA license.
Introduction Delivering products at the right time begins with proper production scheduling.
Scheduling is about deciding the sequence and resource allocation.
This is especially true when considering multiple resources in our system .
The scheduling target varies from minimizing processing time, minimizing work in process and customer waiting time, and maximizing resource utilities and throughput.
This research is motivated by a situation faced by a flexible manufacturing production system mentioned in .
During the planning stage, the management must decide on the production schedule.
Multiple jobs must be scheduled, each of which needs several operation stages.
These stages are associated with the feature creation sequence, making them strictly non-violated.
Each job has different operation sequences.
The system has multiple identical machining centers to process the jobs, each having a multi-process capability.
The target of the system is minimizing the makespan.
Research by .
developed a mathematical model for this https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
http://ejournal.
id/index.
php/industri jurnal@umm.
Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
ISSN: 1978-1431 print | 2527-4112 online Jurnal Teknik Industri Vol.
No.
February 2023, pp.
system's scheduling problem.
They solved the model through an analytical approach but suffered inefficiency in computational time.
Research by .
proposed an ant colony optimization method to create a schedule for the same system.
Although metaheuristic implementation has improved the efficiency of solution finding.
LPT is still used to decide the job processing sequence at each stage.
Therefore, further research should be done to improve the quality of the solution while maintaining computational efficiency, which is the aim of this research.
Minimizing makespan on scheduling jobs unto identical parallel machines has been an interesting research topic for years.
Implementing the heuristic method is often preferable because the problem is NP-Hard.
The classic Longest Processing Time (LPT) algorithm is the most popular heuristic algorithm.
This algorithm is known to generate a schedule with makespan satisfying error bound as much as Oe .
ith yco = the number 3yco of parallel machines availabl.
On the other side, in terms of computational efficiency.
LPT has also shown high computational efficiency .
A continuous effort has been conducted to improve the performance of LPT, such as done by .
Research by .
modified the LPT algorithm for scheduling jobs into two uniform parallel machines, and it passed the makespan performance proposed by the classical LPT.
Research by .
proposed the iterative use of the LPT algorithm and presented a novel approximation algorithm for minimizing makespan, whereas .
combined LPT with local search iteration and effectively reduced makespan value in more than 80% of the cases studied.
Another heuristic approach was proposed by .
after careful analysis of the classical LPT Another approach taken was by applying the approximation method .
, metaheuristics such as Particle Swarm Optimization .
and Grey Wolf Optimizer .
, and simulation .
While this research shows promising performance, they only consider single-stage jobs.
Research on multiple stages is divided into flow shop (FS) and job shop (JS) FS situation is when there are jobs that have similar stage sequence Each stage represents an operation on a particular machine.
Research dealing with flow shop scheduling is done by .
Compared to FS, the JS situation happens when the jobs have various stage sequence requirements and mostly do not necessarily have the same number of stages .
The production system considered in this research falls into the job shop situation, which aims to schedule several jobs over some machines in which each job has a unique machine route.
A review of the problem and solution algorithm for job shop scheduling was given by .
We mainly consider the type of job shop where multiple identical machines with multi-processing capability are available to service jobs, called Flexible Job Shop (FJS) .
The multi-capability embedded in each machine would affect the scheduling mechanism.
The scheduler would have more flexibility when choosing which machine to process a job.
Numerous papers were written in the context of FJS.
them, minimizing makespan is one of the most common targets .
The research can be divided into four groups.
The first group considers the exact algorithm as a way to generate a schedule .
Research by .
proposed constraint programming after analyzing the MILP (Mixed Integer Linear Programmin.
model of FJS, .
adopted a branch and bound approach, and .
introduced quantum computing-based optimization, which resulted in satisfactory performance and high practicability.
The second group considers using the heuristic algorithm in dynamic FJS .
Research by .
proposed a heuristic algorithm to accommodate variable processing time, .
implemented greedy randomized adaptive search, and .
combined local search and acceptance technique as an improved Jaya algorithm, thus resulting in solution quality improvement.
The third Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
Jurnal Teknik Industri Vol.
No.
February 2023, pp.
ISSN: 1978-1431 print | 2527-4112 online group used metaheuristic algorithms, including swarm optimization .
, .
, grey wolf optimization .
, and genetic algorithm .
The fourth group includes research considering simulation .
and machine learning methods .
The position of this paper is in the second group, which considers the implementation of a heuristic algorithm on FJS, in this case.
LPT.
Our research aims to improve the research done by .
by modifying the LPT algorithm to minimize Although the LPT algorithm has shown superior performance in minimizing makespan and delivering efficient computational time, research concerning LPT implementation in the FJS context is still rare.
The following points summarize the contributions of this paper.
First, we developed a novel algorithm based on the classic LPT algorithm to minimize makespan scheduling jobs with multiple stages unto multiple identical machines with multi-process capability.
Second, we provided experiments and showed the effectiveness and computation efficiency of the proposed algorithm.
Methods 1 Problem Description and Assumptions List We considered a production system described in .
There are ya jobs, and each will be denoted by index yc .
c = 1,2.
A , y.
Each job has ycI stages to accomplish, and each stage will be denoted by index yc .
c = 1,2.
A , ycI).
The earlier stage must be completed before the next stage can begin.
There are ycA available machines to process the jobs.
Each machine has the same multi-process capability and can process any job allocated to it.
The problem faced by the production planner is to allocate job-yc, stage-yc, on machine-yco to obtain minimum makespan.
We introduce a list of mathematical notations and models for the problem.
Parameters:
ycyc,yc Variables:
yaycNycoycaycu yaycNyc yaycNyc,yc,yco ycIycNyc,yc,yco Decision Variables:
ycUyc,yc,yco : Processing time of job-yc stage-yc Makespan Completion time of job-yc Completion time of job-yc, stage-yc, at machine-yco Start time of job-yc, stage-yc, at machine-yco : 1, if job-yc, stage-yc is assigned to machine-yco.
0, otherwise Objective function:
Min yaycNycoycaycu Constraints:
yaycNycoycaycu Ou yaycNyc .
OAyc yaycNyc Ou OcycA yco=1 yaycNyc,yc=ycI,yco , .
OAyc yaycNyc,yc,yco Ou .
cIycNyc,yc,yco ycyc,yc ) Oe .
Oe ycUyc,yc,yco )ya.
OAyc.
OAyc.
OAyco OcycA yco=1 ycIycNyc,yc,yco Ou Ocyco=1 yaycNyc,.
cOe.
,yco .
OAyc.
OAyc yaycNyc,yc=0,yco = 0.
OAyc.
OAyco Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
ISSN: 1978-1431 print | 2527-4112 online ycIycNyc,yc,yco yaycNyc,yc,yco O ycUyc,yc,yco .
ya ycUyc,yc,yco OO .
OAyc.
OAyc.
OAyco ycA Jurnal Teknik Industri Vol.
No.
February 2023, pp.
Oc ycUyc,yc,yco = 1 .
OAyc.
OAyc yco=1 ycIycNyc,yc,yco Ou 0.
OAyc.
OAyc.
OAyco yaycNyc,yc,yco Ou 0.
OAyc.
OAyc.
OAyco yaycNyc Ou 0.
OAyc yaycNycoycaycu Ou 0 Equation .
defines the problem's objective function, minimizing the schedule's Equation .
defines makespan as the maximum value of a job's completion Equation .
states that a job's completion time depends on the completion time of its last stage process.
Equation .
defines the completion time of jobOeyc, stage-yc at machine-yco.
It depends on the starting time, processing time, and machine allocation.
Equation .
states that a job for a particular stage cannot start before its predecessor stage has finished.
Equation .
complements Equation .
by providing the completion time value for job-yc, stage-0, which means that the starting time for the first stage on each job is always larger or equal to 0.
Equation .
ensured that each stage's starting and completion times occurred in the same machine.
Equation .
defines the possible value of ycUyc,yc,yco , which is either 0 or 1.
Equation .
ensures that job-j stage-s is allocated in only one Equation .
Ae .
defines the non-negativity value for variables starting time, completion time of job-yc, stage-yc at machine-yco, the completion time of job-yc, and the Three assumptions are applied when dealing with the scheduling problem for this The first is that machines are assumed to be available at any time.
The second is that the setup time is included in the processing time, and the last is that material handling processes are done instantly.
2 Algorithm Development When dealing with single-stage scheduling, the LPT algorithm derives a nearoptimal solution for minimizing makespan .
It is known to have two general steps.
The first is arranging the job sequence, and the second is allocating them to machines .
The arrangement of job sequence is made by implementing the longest processing time rule, where jobs are ordered based on their processing time in non-increasing order.
Afterward, the allocation is done by prioritizing machines with the lowest load.
However, when we deal with the case of jobs with multiple stages, implementing LPT would potentially create overlaps between stages, thus leading to an infeasible solution.
To avoid this problem, we proposed a new algorithm based on modification towards the classic LPT We will mention the algorithm as Modified LPT for Multiple Identical Machine with Multi-process Capability (M-LPT MIMMPC).
The M-LPT MIMMPC is divided into three sub-algorithms.
The first and the second sub-algorithms aim to form surrogate lists for the processing times used as input for the third sub-algorithm.
Details of each step are explained in Table 1.
Table 2, and Table 3.
Given the list generated by sub-algorithm 1 (Table .
and sub-algorithm 2 (Table .
, sub-algorithm 3 (Table .
would arrange the list in non-increasing order.
The ordered Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
Jurnal Teknik Industri Vol.
No.
February 2023, pp.
ISSN: 1978-1431 print | 2527-4112 online list would be used to decide the job allocation sequence.
We also added a comparison mechanism before deciding the job starting time on the selected machine.
The starting time of a job should never be earlier than its predecessor's completion time.
There are two schedules created by sub-algorithm 3, but in the end, one was selected based on the minimum makespan.
Table 1.
M-LPT MIMMPC Sub-Algorithm A (Forward Compariso.
Input : Number of jobs .
, number of stages .
, and processing time .
eiyeU,ye.
Step 1 : Set yc = 1.
Continue to Step 2.
Step 2 : Create an initial surrogate list for processing time.
For yc = 1 to yc, set ycyc,yc ycyc,yc .
Continue to Step 3.
Step 3 : Set yc = 1.
Continue to Step 4.
Step 4 : Decide whether ycyc,yc > ycyc,.
If yes, continue to Step 5.
otherwise, continue to Step 6.
Step 5 : Check whether yc 1 = ycI.
If yes, go to Step 9.
otherwise, set yc = yc 1, then go back to Step 4.
Step 6 : Set ycyc,yc = ycyc,yc ycyc,.
that is, merging the two-processing time.
Continue to Step 7.
Step 7 : Check whether yc 1 = ycI.
If yes, go to Step 9.
otherwise, continue to Step 8.
Step 8 : Update the initial surrogate list by eliminating the .
would reduce the length of the list to .
cI Oe .
and change each value of O by ycyc,.
Go back to Step 3.
Step 9 : Check whether yc = ya.
If yes, go to Step 10.
otherwise, set yc = yc 1, then go back to Step 2.
Step 10 : Define the initial surrogate list as the final surrogate list_1.
STOP
Output : Final surrogate list_1 for Processing Time Table 2.
M-LPT MIMMPC Sub-Algorithm B (Backward Compariso.
: Number of jobs .
, number of stages .
, and processing time .
eiyeU,ye.
: Set ycn = 1.
Continue to Step 2.
: Create an initial surrogate list for processing time.
For yc = 1 to ya, set ycyc,yc ycyc,yc .
Continue to Step 3.
Step 3 : Set yc = ycI.
Continue to Step 4.
Step 4 : Decide whether ycyc,yc > ycyc.
cOe.
If yes, continue to Step 5.
otherwise, continue to Step 6.
Step 5 : Check whether yc Oe 1 = 1.
If yes, go to Step 9.
otherwise, set yc = yc Oe 1, then go back to Step 4.
Step 6 : Set ycyc,yc = ycyc,yc ycyc,.
cOe.
that is, merging the two-processing time.
Continue to Step 7.
Step 7 : Check whether yc Oe 1 = 1.
If yes, go to Step 9.
otherwise, continue to Step 8.
Step 8 : Update the initial surrogate list by eliminating the .
c Oe .
would reduce the length of the list to .
c Oe .
and change each value of O cOe.
by ycyc,.
cOe.
Go back to Step 3.
Step 9 : Check whether yc = ya If yes, go to Step 10.
otherwise, set yc = yc 1, then go back to Step 2.
Step 10 : Define the initial surrogate list as the final surrogate list_2.
STOP
Output : Final Surrogate List_2 for Processing Time Input Step 1 Step 2 Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
ISSN: 1978-1431 print | 2527-4112 online Jurnal Teknik Industri Vol.
No.
February 2023, pp.
The M-LPT MIMMPC algorithm was built into Matlab programming language.
The program is then run in the Windows OS setting.
The computer used during the experiment has the following specifications: Intel(R) Core (TM) i5-8250U CPU @ 1.
60GHz 80 GHz.
Table 3.
M-LPT MIMMPC Sub-Algorithm C (Allocating Job unto Machine.
Input : The number of surrogate lists .
the final surrogate list_ya and the final surrogate list_ya.
allocated job as an empty list.
the number of machines .
the initial load on each machine .
cyea = ya, yea = ya, ya.
A , y.
and the machine with the lowest load .
aoyayayayaya ycyea ) identified as yeaO Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 yea Set yco = 1.
Continue to Step 2.
Implement LPT rules .
on-increasing orde.
to all ycyc,yc on the Final surrogate list_yco defined it as an Ordered surrogate list_yco .
Continue to Step 3.
Set yco = 1.
Continue to Step 4.
For element-yco on the Ordered surrogate list_yco , identify the value of ycyc,yc , and O allocate element-l to machine-yco .
Continue to Step 5.
Check whether the selected ycyc,yc has a predecessor at the allocated job list.
If yes, continue to Step 6.
otherwise, continue to Step 7.
Identify the completion time of the job's predecessor .
aycNyc,.
cOe.
,yco ) Set start time .
cIycNyc,yc,ycoO ) and completion time .
aycNyc,yc,ycoO ) for element-yco and update the load on the selected machine .
aAycoO ) O ycIycNyc,yc,ycoO = yaycNyc.
cOe.
,ycoO .
yaycNyc,yc,ycoO = ycIycNyc,yc,ycoO ycyc,yc and yaAyco =yaycNyc,yc,ycoO Continue to Step 8.
Identify the load on the selected machine .
aAycoO ) Set start time .
cIycNyc,yc,ycoO ) and completion time .
aycNyc,yc,ycoO ) for element-yco and update the load on the selected machine .
aAycoO ) O ycIycNyc,yc,ycoO = yaAyco .
yaycNyc,yc,ycoO = ycIycNyc,yc,ycoO ycyc,yc and yaAyco =yaycNyc,yc,ycoO .
Continue to Step 8.
Update the identity of the machine with the lowest load argmin yaAyco or .
coO).
yco Step 9 Step 10 Step 11 Step 12 Step 13 Output Continue to Step 9.
Update the allocated job list by including ycyc,yc Continue to Step 10.
Check whether all elements in the surrogate list_yco has been allocated If yes, continue to Step 11.
otherwise, set yco = yco 1 and go back to Step 4 Determine the makespan of the schedule ycAycIyco = max .
aAyco ).
go to Step 12.
Check whether yco = 2 If yes, continue to Step 13.
otherwise, set yco = yco 1, then go back to Step 2 Find the schedule with minimum makespan and the associatedOeyco.
yaycNycoycaycu = ycoycnycu ycAycIyco .
argmin ycAycIyco yco Allocation of jobs unto machines .
and its associated makespan To ensure that the algorithm performed as intended, we created small cases and traced the solution's execution of steps and logic.
Afterward, an experiment was conducted to assess the algorithm's performance regarding solution quality and computational time.
The cases used in the experiment are designed intentionally to investigate the performance of the M-LPT MIMMPC algorithm given various situations.
The cases are explained next.
Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
Jurnal Teknik Industri Vol.
No.
February 2023, pp.
ISSN: 1978-1431 print | 2527-4112 online In case 1 .
jobs with 2 stage.
, we created two sub-cases for this setting.
The first sub-case is when ycyc,1 > ycyc,2 (See Case 1a, in Table .
and the second sub-case is when ycyc,1 < ycyc,2 .
ee Case 1b, in Table 5.
Job Processing .
Job Processing .
Table 4.
Case 1a .
jobs - 2 stage.
where ycyc,1 > ycyc,2 Stage 1 Stage 2 Table 5.
Case 1b .
jobs - 2 stage.
where ycyc,1 < ycyc,2 Stage 1 Stage 2 In case 2 .
jobs with 3 stage.
, we created three sub-cases for this setting.
The first sub-case is when ycyc,1 > ycyc,2 > ycyc,3 .
ee Case 2a, in Table .
, the second sub-case is when ycyc,1 < ycyc,2 and ycyc,2 > ycyc,3 .
ee Case 2b, in Table .
, and the third sub-case is when ycyc,2 < ycyc,3 and ycyc,1 < .
cyc,2 ycyc,3 ) .
ee Case 2c, in Table .
Job Processing .
Table 6.
Case 2a .
jobs - 3 stage.
where ycyc,1 > ycyc,2 > ycyc,3 Stage 1 Stage 2 Stage 3 Table 7.
Case 2b .
jobs - 3 stage.
where ycyc,1 < ycyc,2 and ycyc,2 > ycyc,3 Job Stage 1 Processing Stage 2 .
Stage 3 Table 8.
Case 2c .
jobs - 3 stage.
where ycyc,2 < ycyc,3 and ycyc,1 < .
cyc,2 ycyc,3 ) Job Stage 1 Processing Stage 2 .
Stage 3 In case 3 .
jobs with 4 stage.
, we created four sub-cases for this setting.
The first sub-case is when ycyc,1 > ycyc,2 > ycyc,3 > ycyc,4 .
ee Case 3a, in Table .
, the second sub-case is when ycyc,1 < ycyc,2 .
ycyc,2 > ycyc,3 and ycyc,3 > ycyc,4 .
ee Case 3b, in Table .
, the third sub-case is when ycyc,1 < ycyc,2 .
ycyc,2 > ycyc,3 .
ycyc,3 < ycyc,4 and .
cyc,1 ycyc,2 ) > .
cyc,3 ycyc,4 ), .
ee Case 3c, on Table .
, the last sub-case is when ycyc,1 > ycyc,2 > ycyc,3 and ycyc,3 < ycyc,4 .
ee Case 3d, in Table .
Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
ISSN: 1978-1431 print | 2527-4112 online Job Jurnal Teknik Industri Vol.
No.
February 2023, pp.
Table 9.
Case 3a .
jobs - 4 stage.
where ycyc,1 > ycyc,2 > ycyc,3 > ycyc,4 Stage 1 Stage 2 Stage 3 Stage 4 Table 10.
Case 3b .
jobs - 4 stage.
where ycyc,1 < ycyc,2 .
ycyc,2 > ycyc,3 and ycyc,3 > ycyc,4 Job Stage 1 Processing Stage 2 Stage 3 .
Stage 4 Processing .
Table 11.
Case 3c .
jobs - 4 stage.
where ycyc,1 < ycyc,2 .
ycyc,2 > ycyc,3 .
ycyc,3 < ycyc,4 and .
cyc,1 ycyc,2 ) > .
cyc,3 ycyc,4 ) Job Stage 1 Processing Stage 2 Stage 3 .
Stage 4 Table 12.
Case 3d .
jobs - 4 stage.
where ycyc,1 > ycyc,2 > ycyc,3 and ycyc,3 < ycyc,4 Job Stage 1 Processing Stage 2 Stage 3 .
Stage 4 When a particular optimization method or algorithm produces ycAycI O, the performance of the optimization method or algorithm can be calculated through its error.
ycAycI O The error is defined as ycAycI ycn .
As we can see, reaching an error value equal to 1 means that the algorithm can reach the ideal solution.
We use this value as a performance measure for the M-LPT MIMMPC and compare it to the error produced by the classic LPT Results and Discussion 1 Experiment Result 1 Case 1 .
jobs with two stage.
The execution of M-LPT MIMMPC sub-algorithms 1 and 2 in Case 1a would result in the separation of each ycyc,1 and ycyc,2 .
Performing the LPT rule for all processing times in Case 1a would not result in stage violation.
On the contrary, ycyc,1 and ycyc,2 for each-ycn in Case 1b would be merged and considered as one value .
urrogate valu.
during LPT Merging the processing time would translate to processing the job simultaneously for both stages.
A summary of M-LPT MIMMPC performance for Case 1 is given in Table 13.
Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
Jurnal Teknik Industri Vol.
No.
February 2023, pp.
ISSN: 1978-1431 print | 2527-4112 online Table 13.
Makespan.
Error, and Calculation Time for Case 1.
Case Number of Machines ycAycI O .
ycAycI ycn .
Error Error Bound Calculation Time (Secon.
Case 2 .
jobs with three stage.
As in Case 1a, executing sub-algorithms 1 and 2 of M-LPT MIMMPC towards Case 2a would result in the separation of ycyc,1 , ycyc,2 and ycyc,3 .
Furthermore, no surrogate value would be applied for each of them.
Case 2b would result in the merging of ycyc,1 and ycyc,2 and the separation of ycyc,3 .
Case 2c would result in the merging ycyc,1 , ycyc,2 and ycyc,3 .
The summary of MLPT MIMMPC performance for Case 2 is given in Table 14.
Table 14.
Makespan.
Error, and Calculation Time for Case 2.
Case Number of Machines ycAycI O .
ycAycI ycn .
Error Error Bound Calculation Time (Secon.
Case 3: 10 jobs with four stages Following the pattern of Case 1a and 2a.
Case 3a would result in the separation of ycyc,1 , ycyc,2 , ycyc,3 and ycyc,4 during LPT implementation.
Case 3b would result in the merging of ycyc,1 and ycyc,2 and separation of each ycyc,3 and ycyc,4 .
Case 3c would result in the merging of ycyc,1 and ycyc,2 as well as the merging of ycyc,3 and ycyc,4.
In the last case.
Case 3d, the sub-algorithms 1 and 2 of M-LPT MIMMPC would result in the merging of ycyc,1, ycyc,2 , yc, and ycyc,4 .
The summary of M-LPT MIMMPC performance for Case 3 is given in Table 15.
2 Discussions Given the three cases explained earlier, we summarize the performance of the MLPT MIMMPC algorithm.
The average error value is depicted in Fig 1, and the computational time is in Fig 2.
Each line on the graph represented a data series for each Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
ISSN: 1978-1431 print | 2527-4112 online Jurnal Teknik Industri Vol.
No.
February 2023, pp.
Table 15.
Makespan.
Error, and Calculation Time for Case 3.
Case Number of Machines ycAycI O .
ycAycI ycn .
Error Error Bound Calculation Time (Secon.
Case 1a Case 1b Case 2a Error Case 2b Case 2c Case 3a Case 3b Case 3c Case 3d Error Bound Number of Machines Fig 1.
Average error value of M-LPT MIMMPC algorithm in various cases.
Fig 1 Shows that the error value in each case is always mapped below the error When looking at this, we know that the proposed algorithm always produces a better solution than the error bound of the classical LPT algorithm.
Another interesting result is that the algorithm can match the outstanding makespan value for most of the two machines scheduling settings.
The worst performance of the algorithm was achieved primarily on the four machines scheduling settings at the error value of 1.
It is shown in the data that the higher the number of machines, the larger the error value achieved by the proposed algorithm.
These results mimic the pattern shown on the error bound derived from LPT .
It is safe to say that the proposed algorithm behaves like its preceding algorithm.
Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
Jurnal Teknik Industri Vol.
No.
February 2023, pp.
ISSN: 1978-1431 print | 2527-4112 online Calculation Time (Secon.
Case 1a Case 1b Case 2a Case 2b Case 2c Case 3a Case 3b Case 3c Case 3d Number of Machines Fig 2.
The average calculation time of the M-LPT MIMMPC algorithm in various cases.
Another critical performance measure to consider for practicality issues is computational efficiency.
Fig 2 The proposed algorithm's computational time never exceeds one second in all cases.
The general pattern found in the experiment result shows that the more stages the case considered, the higher the computational time needed.
specific stages, the computational time is determined by the number of processing times .
r surrogate processing tim.
the algorithm must sort and allocate to machines.
The less the merging process, the higher the number of jobs to be sorted and allocated, thus resulting in higher computational time.
While we only experimented on multiple-stage cases, the proposed algorithm can also be implemented in a single-stage setting.
It would lead the M-LPT MIMMPC algorithm back to the classical LPT because the result of sub-algorithm 1 and subalgorithm 2 is similar to the processing time of each job.
This general form would be beneficial in practical terms.
Conclusion and Further Research The experiment shows a promising performance of the proposed algorithm (M-LPT MIMMPC).
It is proved that the algorithm can produce a better makespan than classical LPT.
In several cases, it can even match the optimal value.
The algorithm is also efficient regarding computational time and has general applicability.
It can be used in a singlestage setting or multiple-stage setting.
Combining these qualities shows effectiveness and efficiency, which is essential in real-world applicability.
Even so, the experiment conducted in this research is still limited.
We only consider 10 jobs, 2 to 4 stages, and 2 to 4 machine settings.
Experimenting on a larger case is still needed.
Future research should explore this and try to derive the exact error value given by the algorithm analytically.
Please cite this article as: Pakpahan.
, & Sumarna.
Novel Heuristic Algorithm for Flexible Job Shop Scheduling based on the Longest Processing Time Rules to Minimize Makespan.
Jurnal Teknik Industri, 24.
, 17Ae30.
https://doi.
org/10.
22219/JTIUMM.
Vol24.
No1.
ISSN: 1978-1431 print | 2527-4112 online Jurnal Teknik Industri Vol.
No.
February 2023, pp.
Declarations Author contribution: We declare that both authors contributed equally to this paper and approved the final paper.
Funding statement: No funding was received for this work.
Conflict of interest: The authors declare no conflict of interest.
Additional information: No additional information is available for this paper.
Acknowledgment We thank Institut Teknologi Harapan Bangsa for their support in allowing this research to be conducted.
We also want to thank the anonymous reviewers for their insightful comments and suggestions to improve this paper.
References