SINERGI Vol.
No.
June 2021: 111-118 http://publikasi.
id/index.
php/sinergi http://doi.
org/10.
22441/sinergi.
FLOW SHOP SCHEDULING BASED ON PALMER-NEH,
GUPTA-NEH AND DANNENBRING-NEH ALGORITHMS
TO MINIMIZE THE ENERGY COST
Masrikhan.
Dwi Agustina Kurniawati* Industrial Engineering Department.
Faculty of Science and Engineering.
Universitas Islam Negeri Sunan Kalijaga.
Indonesia Abstract In the manufacturing industry, the most widely used equipment is equipment that uses electricity.
Electricity cost is one of the highest operational production costs after labor cost.
So, it is very important to save and optimize the use of electrical equipment.
One of the manufacturing industries is Taru Martani.
Ltd.
This research aims to minimize the energy cost by proposing three hybrid algorithms, namely Palmer-NEH.
Gupta-NEH, and Dannenbring-NEH methods.
Some scheduling evaluation is done using the Efficiency Index (EI) and Relative Error (RE) parameters.
It is concluded that the PalmerNEH and Gupta-NEH methods are the best methods with the lowest energy cost compared with company's actual method and the Dannenbring-NEH method.
Based on the Palmer-NEH and GuptaNEH methods, both methods can save the makespan up to 399.
minutes or 6.
65 hours compared with the company's actual method.
With these methods, the company is also able to save the production cost by Rp.
818,043.
This is an open access article under the CC BY-NC license INTRODUCTION Production scheduling is defined as allocating limited resources to do several jobs .
, 2, .
Scheduling is a decision-making process related to job sequence determination used in many manufacturing and services industries.
Scheduling related to an allocation of resources .
man or machin.
to do job or task over time planning periods and its goal is to optimize one or more objectives .
, 5, 6, .
Based on the process flow pattern, scheduling can be divided into two types: flow shop scheduling and job shop Production process with flow shop means the production process with identical flow patterns from one machine to another or in other The job will be processed all flowing in the same product path.
This research's object is a company engaged in cigar and iris tobacco.
Taru Martani.
Ltd.
Taru Martani Ltd.
was first established in 1918, by a cigar producer from the Netherlands.
The company's initial location is in Bulu area, on Keywords:
Dannenbring.
Electricity.
Energy Cost.
Gupta.
NEH.
Palmer.
Scheduling.
Article History:
Received: March 23, 2020 Revised: July 7, 2020 Accepted: July 10, 2020 Published: Feb 5, 2021 Corresponding Author:
Dwi Agustina Kurniawati Industrial Engineering Department.
Faculty of Science and Engineering.
Universitas Islam Negeri Sunan Kalijaga.
Indonesia Email:
kurniawati@uin-suka.
the edge of Magelang street in Yogyakarta.
1921 the location moved on Kompol B.
Suparto 2A.
PO BOX 1167 Yogyakarta 5525.
Baciro Village.
Gondokusuman District.
There are three types of iris tobacco products made in this company: Mundi Victor.
Countryman, and Violin.
The product differentiation is based on the secret ingredients given to each type of product.
In its operation, the company has 9 .
production These are cutting machine handles, dang machines, mixing machines, the sauce I machines, chopping machines, frying machines, cooling machines, sauce II machines, and packing This company implements a make to order production system with First Come First Service (FCFS) scheduling system.
The company does not consider the dynamic job order constraints: the orders can arrive at the beginning of the month, in the middle of the month, or at the end of the The dynamic of job arriving can make a bad impact when job scheduling is done Masrikhan & D.
Kurniawati.
Flow Shop Scheduling Based on Palmer-NEH A SINERGI Vol.
No.
June 2021: 111-118 One impact is the amount of makespan in the production system can increase.
Makespan is the total work completion time, starting from the first sequence done by the machine to the last sequence on the machine .
, 9, 10, .
The makespan's size will also make the cost of electrical energy in the production machine expended to be large.
Electricity cost is one of the highest operational production costs after the cost of manpower.
In general, electricity costs that are classified as "Electric Utility Cost" cost a portion of around 7% of the total operational operating costs, so it is very important to save and optimize the use of electrical equipment .
Therefore, companies should be able to use efficient production scheduling methods in the working process to reduce the use of electrical energy in production machines.
This company's scheduling process is classified as NP-Hard (Nondeterministic Polynomial-time har.
problem since it involves more than two machines.
A heuristic algorithm can provide an optimal result in NP-Hard problems .
In the study performed by Kurniawati and Nugroho .
, they conducted a computational study of N Job M machine flow shop scheduling using Nawaz.
Enscore and Ham (NEH).
NEHEDD, modified NEH.
Shortest Processing Time (SPT), and Earliest Due Date (EDD) methods.
The study shows that the modified-NEH method has the best performance for both criteria used, which is minimizing makespan and total tardiness.
another study, based on the scheduling evaluation conducted by Mazda and Kurniawati .
, it showed that the Branch and Bound method produced a smaller makespan than the company's scheduling method applied by the company (FCFS).
The main contribution of this paper is to develop heuristics algorithms.
These are NEH algorithm combined with Gupta.
Palmer and Dannenbring methods.
So far, only a few studies have developed the NEH algorithm combine with Gupta.
Palmer and Dannenbring methods in the flow shop production process.
This study aims to minimize the cost of electrical energy in production machines to increase its profit.
METHOD
This research develops the hybrid algorithms, namely the Palmer-NEH.
Gupta-NEH Dannenbring-NEH The development is performed by combining two existing methods to obtain optimal scheduling The scheduling process is carried out in a forward approach.
The selection of allocation positions is based on the NEH algorithm with due regard to routing and precedence.
In addition, the job scheduling sequence also considers the machine set up time.
The optimization measure used in this scheduling is the minimization of energy costs.
The data that has been collected will be processed to produce a sequence of the production process with the smallest makespan.
The steps performed in this research are summarized as follows.
Collecting data of processing time from each machine.
After that, the data are calculated using the adequacy and uniformity test data .
Data sufficiency test is conducted to find out whether the observed data (N') is enough or not.
Therefore, it is necessary to determine the value of confidence level and accuracy .
egree of freedo.
in measuring work.
this study, work measurements were carried out using a confidence level of 95% and a degree of accuracy of 5%.
Processing time data that has been collected are recapitulated into Microsoft Excel and tested for the adequacy and uniformity of the data.
The data adequacy test was carried out using the Maytag Company formula .
At the same time, the data uniformity test is done through graphical data analysis.
The data that has been tested for the adequacy and uniformity tests is calculated for each machine's standard time.
The next step is determining job scheduling using the company's actual method.
NEH.
Gupta.
Palmer.
Dannenbring.
Gupta-NEH.
Palmer-NEH, and Dannenbring-NEH.
The makespan is calculated for each method.
Then it is done the performance and energy comparison between the proposed method and the company's actual method.
It is to determine the energy cost based on the existing method and the proposed methods.
Lastly, the performance test result and the energy comparisons are then analyzed to conclude which method has the smallest energy consumption.
The method that was resulting in the smallest makespan is the best method to be applied in the company.
The Proposed Algorithms As mentioned in the previous section, this paper's main contribution is to develop three hybrid algorithms by combining between NEH method with Palmer.
Gupta and Dannenbring Therefore, this section describes the proposed hybrid algorithms, namely Palmer-NEH.
Gupta-NEH, and Dannenbring-NEH algorithms.
Masrikhan & D.
Kurniawati.
Flow Shop Scheduling Based on Palmer-NEH A p-ISSN: 1410-2331 e-ISSN: 2460-1217 Palmer-NEH Algorithm Some steps are performing Palmer-NEH Algorithm.
Step 1 Determine the index value for each job, ya using the formula:ya.
= min .
cycnycoOeycycnyco .
Sorting the existing jobs by increasing index value rules.
Determine the value of makespan.
Step 2 Set k = 2 Take a job that rank first and second on the job-sorting list.
Create two alternative candidates for a new partial sequence.
Calculate each partial makespan and partial mean flow time of a new partial order candidate.
Choose a new partial sequence candidate that has the lowest partial If there is a new partial order candidate with the same lowest makespan, choose the new partial sequence candidate with a lower mean flow time.
If they are the same, they can be chosen randomly.
The new selected partial order candidate becomes the new partial order.
Cross out the jobs taken earlier from the job sort list.
Check whether k = n .
here n is the number of jobs availabl.
If yes, proceed to step 4.
If not, proceed to step 3.
Step 3 Set yco = yco 1 Take a job that rank first from the jobsorting list Generate as many k candidates for new partial sequences by entering the jobs taken in each previous partial sequence Follow the same steps in Palmer-NEH Algorithm from step 2.
4 to 2.
Step 4 The new partial order becomes the final and stops Gupta-NEH Algorithm Gupta-NEH Algorithm has some steps as The steps of Gupta-NEH algorithm are as Step 1 Permutation schedules are established using job order:
ycI1 Ou ycI2 Ou ycI3 Ou ycI4 Ou U Ou ycIycu With the slope formula:
ycA ycI1 = Oc yco=1 2yco Oe ycA Oe 1 ycycyco Where:
M = Number of machines S1 = slope index job j tjk = processing time of the jth job on kth machine Sort the jobs Perform the makespan calculation Step 2 Follow the same steps in Palmer-NEH Algorithm in Step 2 .
rom step 2.
1 to 2.
Step 3 Follow the same steps in Palmer-NEH Algorithm in Step 3 .
rom step 3.
1 to 3.
Step 4 The new partial order becomes the final and stops Dannenbring-NEH Algorithm Some steps are performing DannenbringNEH Algorithm.
The steps are as follows.
Step 1 Processing time calculation is done as ycA ycEycn1 = Oc.
cA Oe yc .
ycycnyc yc=1 ycA ycEycn2 = Oc.
ycycnyc yc=1 For i = 1,2,3 .
, n Where:
Pi1 = processing time of the job i in the first machine Pi2 = processing time of the job i in the second machine J = jth machine.
Sort the jobs.
Perform the makespan calculation Step 2 Follow the same steps in Palmer-NEH Algorithm in Step 2 .
rom step 2.
1 to 2.
Step 3 Follow the same steps in Palmer-NEH Algorithm in Step 3 .
rom step 3.
1 to 3.
Masrikhan & D.
Kurniawati.
Flow Shop Scheduling Based on Palmer-NEH A SINERGI Vol.
No.
June 2021: 111-118 Step 4 The new partial order becomes the final and stops 17 hours smaller, and when compared with Gupta alone, it saves 999.
04 minutes smaller or 65 hours.
RESULTS AND DISCUSSION
Current Scheduling in the Company The existing scheduling used by the company is FCFS.
FCFS is a scheduling system based on jobs that come first will be a top priority.
The variables such as processing time, number of units, due date, etc.
are not considered in FCFS.
The makespan obtained through scheduling with FCFS method is 22261.
46 minutes.
Scheduling Using the Dannenbring-NEH Method Scheduling using the Dannenbring-NEH method is a modification of the standard NEH method with the initial approach using the Dannenbring method.
The Dannenbring method is based on determining job sequences in Pi1 and Pi2.
After obtaining a job sequence based on the Dannenbring method, the job sequence is then iterated using the NEH method.
The makespan value obtained by scheduling using the Dannenbring-NEH method is 21872.
25 minutes.
Based on this method, when compared with the company's actual method, it saves the processing time by 389.
21 minutes or 6.
49 hours.
Meanwhile, when compared with the NEH method alone is the same, and when compared with Dannenbring alone, it saves 1063.
56 minutes smaller or 17.
Comparison between those methods is presented in Figure 1 and Table 1.
Scheduling Using the Palmer-NEH Method Scheduling using the Palmer-NEH method is a modification of the standard NEH method with the Palmer method's initial approach.
The Palmer method has a scheduling system based on the slope index value for each job.
The index values for each job are sorted from the largest to the smallest index values.
After obtaining a job sequence based on the Palmer method, the job sequence is then iterated using the NEH method.
The makespan value obtained through scheduling using the PalmerNEH method is 21862.
33 minutes.
Compared with the company's actual method, it can save the processing time by 399.
13 minutes or 6.
65 hours.
Meanwhile, when compared with the NEH method alone, it saves 9.
93 minutes or 0.
17 hours smaller, and when compared with Palmer alone, it saves 02 minutes smaller or 21.
73 hours.
Scheduling Using the Gupta-NEH Method Scheduling using the Gupta-NEH method has modified the standard NEH method with the initial approach using the Gupta method.
The Gupta method has a scheduling system based on the slack index value for each job.
The slack index values for each job are sorted from the smallest to the largest index values.
After obtaining a job sequence based on the Gupta method, the job sequence is then iterated using the NEH method.
The makespan value obtained through scheduling using the Gupta-NEH method is 33 minutes.
Based on this method when compared with the company's actual method, it can save the processing time by 399.
13 minutes 65 hours.
Meanwhile, when compared with the NEH method alone, it saves 9.
93 minutes or Scheduling Parameters In order to determine which method is better, the performance parameters used in this study are Efficiency Index (EI).
Relative Error (RE) and energy costs.
Energy costs are obtained from makespan, engine power and basic electricity EI and RE values are calculated referring to Pour .
, and the result of EI and RE can be seen in Table 2.
Based on Table 2, it appears that the method proposed by the researcher is better than the actual method applied in the company due to the value of EI> 1.
However, the Palmer-NEH and Gupta-NEH methods have the same performance (EI = .
and better than the Dannenbring-NEH method (EI <.
Based on the RE parameters, the calculation results in negative values, which means that between the two methods have a large difference in the value of makespan.
Except for the Palmer-NEH and Gupta-NEH methods, they makespan value because the RE is 0%.
The energy costs of each methods can be seen in Table 3.
Masrikhan & D.
Kurniawati.
Flow Shop Scheduling Based on Palmer-NEH A p-ISSN: 1410-2331 e-ISSN: 2460-1217 Figure 1.
Comparison of makespan Table 1.
Comparison of makespan, cost and sequence Method
FCFS
Palmer-NEH Gupta - NEH Dannenbring- NEH Make-span .
Cost
45,625,877
Sequence (R.
44,807,834 44,807,834 44,828,179 Masrikhan & D.
Kurniawati.
Flow Shop Scheduling Based on Palmer-NEH A SINERGI Vol.
No.
June 2021: 111-118 Table 2.
EI and RE values Method
(%)
FCFS - (Palmer - NEH) FCFS Ae (Gupta - NEH) FCFS Ae (Dannenbring -NEH) (Palmer Ae NEH) Ae (Dannenbring - NEH) (Gupta - NEH) Ae (Dannenbring - NEH) (Palmer Ae NEH) Ae (Gupta - NEH) Table 3.
The energy costs for each method Cost Cost Reduction (R.
(R.
Method
FCFS
45,625,877
PALMER-NEH
44,807,834
818,043
GUPTA-NEH
44,807,834
818,043
DANNENBRING-NEH
44,828,178
797,699
Based on Table 3, it can be seen that the Palmer-NEH and Gupta-NEH methods are the methods that produce the smallest energy cost worth Rp.
44,807,834.
By implementing job scheduling using the Palmer-NEH and GuptaNEH methods, the company can save the total production costs by Rp.
818,043.
So, the Palmer-NEH and Gupta-NEH methods are the best methods that can be applied by Taru Martani.
Ltd.
to minimize the energy costs of the production process, specifically the job order in August.
This research is in line with research conducted by Vallejos-Cifuentes et al.
, which is in their study.
they got an average reduction of 8% in energy consumption.
It helps to reduce peak loads and decrease the demand for applied energy sources .
Research of Huang et al.
also shows that optimizing various engine conditions under time-use rates can significantly reduce energy costs in timely delivery.
At the same time.
Zhang .
research shows that both individual and total factory electricity costs can be Mansouri and Aktas .
research on reducing energy consumption found that MOGA combined with constructive heuristics is superior to ordinary MOGA and heuristics alone.
The research provides the production managers with a new solution to make decisions by considering the energy consumption and the service goals in scheduling shop floors .
Hossain et al.
conducted research in heuristic algorithms.
are NEH.
CDS and Palmer algorithms for completing flow shop scheduling problem.
The objective is to minimize makespan.
The study found that the NEH algorithm produces more complicated results compared to Palmer and CDS Grant graphs are used to verify the effectiveness of heuristics .
CONCLUSION
There are some conclusions.
First, based on the Palmer-NEH method, the makespan value 33 minutes and the energy cost are Rp.
44,807,834.
Based on this method, when compared with the company's actual method, it saves total processing time by 399.
13 minutes or 65 hours.
The company is also able to save production costs by Rp.
818,043.
Based on the Gupta-NEH method, the makespan value is 33 minutes, and the energy cost is Rp.
44,807,834.
Based on this method, compared with the company's actual method, it can save total processing time by 399.
13 minutes 65 hours.
The company is also able to save production costs by Rp.
818,043.
Based on the Dannenbring-NEH method, the makespan value is 25 minutes and the energy cost are Rp.
44,828,178.
Based on this method, compared with the company's actual method, it can save the total processing time by 389.
minutes or 6.
49 hours.
The company is also able to save production costs by Rp.
797,699.
Finally, based on the scheduling evaluation using the parameters EI and RE, the Palmer-NEH and Gupta-NEH methods are the best methods with the smallest energy costs than the company's actual method and the Dannenbring-NEH method.
Masrikhan & D.
Kurniawati.
Flow Shop Scheduling Based on Palmer-NEH A p-ISSN: 1410-2331 e-ISSN: 2460-1217 This study still has some limitations, so there are suggestions for further research.
Firstly, it is possible to investigate another method that is more suitable for company policies such as Weight Shortest Processing Time (WSPT).
Due to certain conditions, the company is challenging to determine the job order because they have to look at several factors that may occur between the customer and the company such as the length of the partnership, prepayment, and the head's subjectivity of a production.
Secondly, it is possible for making software that can support decision making in the scheduling process.
The software can make it easier to determine the schedule, and the results will have higher accuracy.
REFERENCES