PME I J http://polipapers.upv.es/index.php/IJPME International Journal of Production Management and Engineering https://doi.org/10.4995/ijpme.2021.15217 Received: 2021-03-06 Accepted: 2021-05-02 Geometric and Harmonic means based priority dispatching rules for single machine scheduling problems Ahmad, S.a1 , Khan, Z.A.a2, Ali, M.b, Asjad, M.a3 aDepartment of Mechanical Engineering, Faculty of Engineering and Technology, Jamia Millia Islamia, New Delhi, India. bDepartment of Mechanical Engineering, Aligarh Muslim University, Aligarh, Uttar Pradesh, India. a1 shafiahmad.amu@gmail.com, a2 zakhanusm@yahoo.com, b mohdali234@rediffmail.com, a2 masjad@jmi.ac.in Abstract: This work proposes two new priority dispatching rules (PDRs) for solving single machine scheduling problems. These rules are based on the geometric mean (GM) and harmonic mean (HM) of the processing time (PT) and the due date (DD) and they are referred to as GMPD and HMPD respectively. Performance of the proposed PDRs is evaluated on the basis of five measures/criteria i.e. Total Flow Time (TFT), Total Lateness (TL), Number of Late Jobs (TNL), Total Earliness (TE) and Number of Early Parts (TNE). It is found that GMPD performs better than other PDRs in achieving optimal values of multiple performance measures. Further, effect of variation in the weight assigned to PT and DD on the combined performance of TFT and TL is also examined which reveals that for deriving optimal values of TFT and TL, weighted harmonic mean (WHMPD) rule with a weight of 0.105 outperforms other PDRs. The weighted geometric mean (WGMPD) rule with a weight of 0.37 is found to be the next after WHMPD followed by the weighted PDT i.e. WPDT rule with a weight of 0.76. Key words: job sequencing, priority dispatching rule, single machine scheduling, geometric mean of the processing time and due date (GMPD), harmonic mean of the processing time and due date (HMPD). 1. Introduction Production scheduling refers to the planning of the manufacturing process and it is an important activity as it leads to enhancement in the productivity of the system, reduction in job lateness, increased utilization of the machine etc. (Doh et  al., 2013; Geiger and Uzsoy, 2008; Pinedo, 2009). Apart from manufacturing processes, scheduling finds its application in various other areas like operating systems where it is used for memory allocation of processor, in service industries for operator allotment etc. (Baharom et al., 2015; Lee et al., 2020; Munir et al., 2008; Rafsanjani and Bardsiri, 2012). However, it is imperative in production scheduling due to its undeviating impact on the profitability of a company (Kadipasaoglu et al., 1997; Prakash et al., 2011). The effectiveness of a schedule is very much affected by the priority dispatching rule (PDR) used for job sequencing (Hussain and Ali, 2019; Krishnan et al., 2012; Waikar et al., 1995). These rules offer priority to one or more jobs over other jobs to improve certain performance measures of the system. The well-known PDRs found in the literature are as follows (Forrester, 2006; Pinedo, 2009): - First Come First Served (FCFS): A job that arrives first will be given the highest priority for processing. - Shortest Processing Time (SPT): A job having the least processing time (PT) will be processed first. - Earliest Due Date (EDD): A job with a least due date (DD) will attain the highest priority and will be processed first. To cite this article: Ahmad, S., Khan, Z.A., Ali, M., Asjad, M. (2021). Geometric and Harmonic means based priority dispatching rules for single machine scheduling problems. International Journal of Production Management and Engineering,  9(2), 93-102. https://doi.org/10.4995/ijpme.2021.15217 Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International 93 https://orcid.org/0000-0002-2193-8984 http://creativecommons.org/licenses/by-nc-nd/4.0/ - SLACK: A slack time of each job is computed which is the difference between the remaining time and the PT. Subsequently, a job with the least slack value will be processed first. - Critical Ratio (CR): A ratio of time remaining until the DD andPT is calculated which is identified as a critical ratio. Consequently, a job with the least critical ratio will be processed first. The choice of PDR has a significant effect on the overall performance of the system (Waikar et al., 1995). However, it was observed that no single PDR is capable of optimizing all the performance measures (Chan et al., 2003; Dominic et al., 2004; Ðurasević and Jakobović, 2018). Hence, the current era of research in scheduling is focused on the development of new PDRs to achieve optimal values of more than one performance measures (da Silva et al., 2019; Kanet and Li, 2004; Lu et al., 2012). Holthaus and Rajendran (1997) presented two new PDRs using additive and alternative strategies to combine process time and work content in the next queue and based on their simulation study they re- ported that this rule performed well to minimize the average flow time. Jayamohan and Rajendran (2007) proposed five new PDRs by combining different rules and showed that the proposed rules performed well for minimizing mean flow time, mean tardiness and percentage of tardy jobs. Dominic et al. (2004) examined the effectiveness of three rules developed by combining FIFO, SPT and most work remain- ing (MWK) PDRs using ARENA 4.0 simulation software and found that the combined rule provided better results as compared to other rules. Vinod and Sridharan (2008) conducted a simulation study to evaluate five new set up oriented PDRs under dif- ferent experimental conditions. The results of their study showed that the proposed rules provided bet- ter results over seven standard rules. Hamidi (2016) proposed a priority dispatching rule where in the au- thor took average of the PT and the DD of the jobs and termed this rule as PDT and suggested that the job with the least PDT value should be processed first. It is found from the literature that the PDT rule gives optimal results for multiple performance mea- sures as compared to FCFS, SPT, EDD, SLACK and CR (Hamidi, 2016). It is observed from literature that researchers have made attempt to combine two or more standard PDRs to develop new PDRs and based on the simulation studies it has been estab- lished that the combined rules perform well as com- pared to standard PDRs. Further, the presented literature demonstrated that PDRs based on combination of PT and DD have been developed by using additive strategy i.e. PDT rule. However, there is lack of studies or no study which has combined the PT and DD using geometric and harmonic means or using similar methods. With this motivation, this work attempts to combine the PT and DD using multiplicative and reciprocal strategy and proposes two new PDRs i.e. GMPD and HMPD. To the best of authors knowledge, these rules have not been proposed yet in literature. Further, researchers have used single machine scheduling problem (SMSP) and simulation based study to compare the effectiveness of the newly developed PDRs over standard rules (Cheng and Kahlbacher, 1993; Tyagi et al., 2016). Therefore, a simulation study is also conducted in this work to evaluate the effectiveness of the proposed rules over FCFS, SPT, EDD, SLACK, CR and PDT on the basis of five performance measures viz. Total Flow Time (TFT), Total Lateness (TL), Total Number of Late parts (TNL), Total Earliness (TE) and Total Number of Early parts (TNE). Hamidi (2016) also proposed weighted PT and DD total (WPDT) rule in which weights are assigned to PT and DD to obtain better performance measures. Keeping this in view, the weighted geometric mean of PT and DD (WGMPD) and weighted harmonic mean of PT and DD (WHMPD) are also proposed in this paper. It is found from the simulation study that the proposed rules give better results as compared to the standard rules as well as PDT rule. Rest of the paper is organized as follows: Section 2 describes how the proposed GMPD and HMPD rules are derived. Section 3 presents a case study in which a sample problem using the standard rules as well as the proposed rules is solved. Section 4 puts forth the simulation study in which eleven thousand randomly generated problems are solved and the results so obtained are compared for different PDRs. Section 5 illustrates the effect of weight variation in the proposed WGMPD and WHMPD on TFT and TL. Finally, section 6 presents the conclusion of the present study. To provide a better understanding of the various symbols used in this manuscript, a nomenclature is provided in Table 1. 2. Proposed rules A single machine scheduling problem (SMSP) requires effective scheduling of ‘n’ jobs say J1, J2, J3,.........., Jn on a single machine. Several PDRs can be used to schedule these jobs. Among Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102 Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Ahmad et al. 94 http://creativecommons.org/licenses/by-nc-nd/4.0/ them, the most preferable are SPT and EDD as they possess advantages over others in terms of specific performance measures. SPT rule prioritizes the jobs based on PT which results in small flow times. Whereas, in EDD rule, jobs with least DD are processed first which results in reduced lateness. As SPT rule is purely based on the PT and EDD rule is solely based on the DD of the job, priorities defined on the combined basis of PT and DD might be more effective for optimal results of multiple performance measures. In this regard, Hamidi (2016) made an attempt and proposed the PDT rule, where additive strategy was used to combine the PT and DD. Since, multiplicative and reciprocal strategy has not been examined to combine the different PDRs, this work proposes two new PDRs to solve a SMSP based on the multiplicative and reciprocal strategies. In the first rule, geometric mean of the PT and DDof the jobs is taken, and it is termed as GMPD which is based on the multiplicative strategy. According to the GMPD, top priority is given to a job for which the value of GMPD is the minimum. The second rule considers harmonic mean of the PT and DD of the jobs and it is referred to as HMPD that is based on the reciprocal strategy. A job with the least value of the HMPD is processed first according to this rule. 2.1. The geometric mean of processing time and due date (GMPD) For two numbers say ‘a’ and ‘b’ the mathematical formula used to calculate geometric mean is √(ab). Considering an SMSP of ‘n’ jobs J1, J2, J3,.........., Jn with deterministic processing time pti and due date ddi of job Ji, the priority function for GMPD rule is defined according to Equation (1). GM i pt i dd i (1) Hence, for each job, the value of priority function is calculated and the job with the least GMi value will be processed first. 2.2. The harmonic mean of processing time and due date (HMPD) The harmonic mean is related to the arithmetic mean in a manner that it is reciprocal of the arithmetic mean. PDR based on the arithmetic mean of PT and DD i.e. PDT has already been developed and established to provide better performance than other standard PDRs (Hamidi, 2016). Hence, it was supposed that PDR based on harmonic mean might be able to give better results. In this regard, the harmonic mean of PT and DD (HMPD) rule is proposed in this work. The priority function for HMPD rule is used as defined by Equation (2). HM i 2 pt i dd i pt i dd i (2) Hence, priorities to jobs are defined based on HMi value. A job with a minimum value of HMi will be most preferable for processing over other jobs. 3. Case Study In this section, a sample problem is solved using the proposed PDRs along with other rules to examine Table 1. Nomenclature. Symbol Meaning i Job number n Total number of jobs Ji Name of the job i pti Processing time of job Ji ddi Due date of job Ji Fi Flow time of job Ji Li Lateness of job Ji Ei Earliness of job Ji PDR Priority dispatching rule GM Geometric mean HM Harmonic mean PT Processing time DD Due date GMPD Geometric mean of processing time and due date HMPD Harmonic mean of processing time and due date TFT Total flow time TL Total lateness TNL Number of late jobs TE Total earliness TNE Number of early parts WGMPD Weighted geometric mean WHMPD Weighted harmonic mean FCFS First come first served SPT Shortest processing time EDD Earliest due date CR Critical ratio MWK Most work remaining Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Geometric and Harmonic means based priority dispatching rules for single machine scheduling problems 95 http://creativecommons.org/licenses/by-nc-nd/4.0/ the effectiveness of the proposed PDRs for solving SMSP. The sample problem consists of ten jobs that need to be sequenced for processing on a machine. Each job has a deterministic PT in the interval of 1 to 15 days which is determined using uniform distribution. The DD of each job is also considered to be deterministic;in the interval ranging from 3×PT of the job and 60 days, and it is determined using the same distribution (uniform distribution). The PT and the DD of each job for the sample problem considered in this work are shown in Table 2. Table 2. PT and DD of jobs. Job PT (days) DD (days) J1 9 34 J2 5 53 J3 15 50 J4 1 28 J5 8 56 J6 14 45 J7 3 15 J8 10 30 J9 9 32 J10 4 36 The effectiveness of the PDRs is examined on the basis of commonly used performance measures i.e. flow time, lateness, number of late parts, earliness and number of early parts (Oyetunji, 2009). It may be noted that either maximum or average or total values of these performance measures may be used. In the present work, total values of the performance measures are considered for the evaluation of the PDRs. The performance measures considered in this work are described as follows: - Total flow time (TFT): It represents the sum of time each job spends in the system and it is determined using Equation (3). TFT n i 1 F i (3) where, Fi=Fi-1+pti. pti and Fi indicate the PT and flow time of job Ji respectively. - Total lateness (TL): It measures the total amount of lateness to the jobs and it is computed using Equation (4). TL n i 1 L i (4) where, Li=max(0,Fi – ddi). ddi and Li represents the DD and lateness of job Ji respectively. - Total number of late parts (TNL): If a job is completed after its DD, it is said to be late. TNL is the measure that indicates the count of the late parts i.e. - Total earliness (TE): The difference between the DD and flow time when a job is completed before its DD is regarded as the earliness of a job otherwise earliness of a job is defined as 0. Total earliness is defined by Equation (5). TE n i 1 E i (5) where, Ei=max(0,ddi–Fi). ddi and Ei represent the DD and earliness of job Ji respectively. - Total number of early parts (TNE): The count of the jobs which are early is regarded as TNE i.e., where n is the number of jobs. The sample problem shown in Table 1 is solved using different PDRs viz. FCFS, SPT, EDD, SLACK, CR, PDT, GMPD and HMPD. The sequence of jobs for processing on a machine so obtained is depicted in Table 3. Table 3. Sequence of jobs using different PDRs. FCFS SPT EDD SLACK CR PDT GMPD HMPD J1 J4 J7 J7 J8 J7 J4 J4 J2 J7 J4 J8 J7 J4 J7 J7 J3 J10 J8 J9 J9 J8 J10 J10 J4 J2 J9 J1 J1 J10 J2 J2 J5 J5 J1 J4 J4 J9 J9 J5 J6 J1 J10 J6 J6 J1 J8 J9 J7 J9 J6 J10 J10 J2 J1 J1 J8 J8 J3 J3 J3 J6 J5 J8 J9 J6 J2 J2 J2 J5 J6 J6 J10 J3 J5 J5 J5 J3 J3 J3 It may be noted that for PDT rule, the jobs are sequenced based on the minimum value of the sum of PT and DD. For GMPD rule job sequence is defined based on the minimum value of priority function defined in Equation (1) and for HMPD rule Equation (2) is used to define the job sequence. Further, the values of performance measures are computed when the jobs are sequenced with these PDRs. The performance so obtained is shown in Table 4. It can be seen from Table 4 that (i) the least TFT (306 days) is obtained when the jobs are sequenced using SPT rule or HMPD rule, (ii) the minimum value of TL (47 days) is obtained when the jobs Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102 Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Ahmad et al. 96 http://creativecommons.org/licenses/by-nc-nd/4.0/ are sequenced using PDT rule, (iii) the number of late jobs is the least i.e. 4 when either of the SPT, EDD, PDT, GMPD or HMPD rule is used, (iv) maximum TE (145 days) is observed when SPT rule is used,and (v) the number of jobs which are completed before the DD i.e. TNE is maximum when either of the SPT, EDD, PDT, GMPD or HMPD is utilized. These results are in line with the results reported in the literature that no single rule is the best for all the performance measures (Dominic et al., 2004). However, an attempt has been made to identify a PDR which might be effective in achieving optimal values of all performance measures. For this purpose, the best performance value for a measure is identified among the considered PDRs. Based on the best performance value, the percentage deviation in the performance of each PDR is calculated. It is to be mentioned that for TFT, TL and TNL, maximum values whereas for TE and TNE minimum values is regarded as the best performance value. In this way, a PDR with the best value for a specific performance measure will get a percentage deviation of 0% and a PDR with least average percentage over all the performance measure will be the best PDR. The percentage deviation of each performance measure for each PDR are depicted in Table 5. Table 5. Percentage deviation of the performance measures. PDR TFT (%) TL (%) TNL (%) TE (%) TNE (%) Average % deviation FCFS 45.10 257.45 50.00 28.97 33.33 82.97 SPT 0.00 53.19 0.00 0.00 0.00 10.64 EDD 22.55 25.53 0.00 56.55 16.67 24.26 SLACK 33.99 55.32 50.00 71.03 33.33 48.73 CR 36.27 55.32 50.00 75.86 33.33 50.16 PDT 10.78 0.00 0.00 40.00 0.00 10.16 GMPD 1.63 17.02 0.00 15.17 0.00 6.77 HMPD 0.00 48.94 0.00 1.38 0.00 10.06 It is observed from Table 5 that GMPD, HMPD and PDT are the top three rules with least deviations. Hence, it can be inferred that the mean based PDRs outperform the standard PDRs. Further, among the considered PDRs, the deviation from the best is the least for GMPD rule. Hence, it can be concluded that the best PDR for deriving optimal values of the five performance measures i.e. TFT, TL, TNL, TE, and TNE is GMPD. The next in the row is found to be HMPD. Subsequently, the next best rule is observed to be the PDT rule. PDT rule has also been reported to perform better than FCFS, EDD, SLACK, and CR for obtaining optimal values of the multiple performance measures (Hamidi, 2016). Based on the values of average percentage deviation (Table 5) the importance of rest of the PDRs in decreasing order is EDD>SLACK>CR>FCFS. 4. Simulation study It is likely that results obtained for the sample problem solved in the previous section might change when the parameters of the sample problem i.e. PT and DD is changed. Therefore, it is indeed vital to examine the changes that may occur in the results when these parameters are altered. For this purpose, a simulation study was conducted in which eleven thousand problems were generated randomly and in each problem ten jobs were considered. Both PT (ranging from 1 to 10 days) and DD (in the interval of 3 x PT to 60 days) of each job was deterministically generated using uniform distribution. The performance measures were computed for each problem and the average results obtained for the eleven thousand problems were used to compare different PDRs. The average of TFT taken over eleven thousand solved problems using different PDRs is shown in Figure 1. 440,77 328,67 389,87 423,93 441,08 362,59 333,23 328,82 0 50 100 150 200 250 300 350 400 450 500 FC FS SP T ED D SL AC K CR PD T GM PD HM PD Avg_TFT Figure 1. Average TFT of eleven thousand problems. Table 4. Performance measures for different PDRs. PDR TFT (days) TL (days) TNL TE (days) TNE FCFS 444 168 6 103 4 SPT 306 72 4 145 6 EDD 375 59 4 63 5 SLACK 410 73 6 42 4 CR 417 73 6 35 4 PDT 339 47 4 87 6 GMPD 311 55 4 123 6 HMPD 306 70 4 143 6 Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Geometric and Harmonic means based priority dispatching rules for single machine scheduling problems 97 http://creativecommons.org/licenses/by-nc-nd/4.0/ It is evident from Figure 1 that the least value of TFT (328.67 days) is obtained when job sequencing is done using SPT rule and this result is in line with the result reported in literature (Lu et  al., 2012; Tyagi et al., 2016). Further, mean based PDRs i.e. GMPD, HMPD and PDT perform better than other PDRs except SPT. Among the three mean based PDRs, HMPD is found to give better results for TFT followed by GMPD and PDT. 123,76 60,50 57,81 74,79 71,05 51,25 54,00 58,01 0 20 40 60 80 100 120 140 FC FS SP T ED D SL AC K CR PD T GM PD HM PD Avg_TL Figure 2. Average TL of eleven thousand problems. Figure 2 depicts average value of TL for the eleven thousand solved problems using different PDRs and it reveals that PDT rule performs better than other PDRs as the average TL value for this rule is minimum i.e. 51.25 days. The proposed GMPD rule is next in the row as it results in average total lateness of 54 days. Performance of rest of the PDRs in descending order as observed from Figure 2 is EDD>HMPD>SPT>CR>SLACK>FCFS. 5,05 3,18 3,59 4,34 6,04 3,07 3,02 3,14 0 1 2 3 4 5 6 7 FCFS SPT EDD SLACK CR PDT GMPD HMPD Avg_No_Late Figure 3. Average TNL of eleven thousand problems. Results for the number of late parts for different PDRs are depicted in Figure 3 which clearly shows that performance of the GMPD is the best as it provides minimum number of late parts i.e. 3.02 and this rule is followed by HMPD, PDT, SPT, EDD, SLACK, FCFS, and CR. 103,31 152,15 88,26 71,17 50,28 108,97 141,08 149,50 0 20 40 60 80 100 120 140 160 FC FS SP T ED D SL AC K CR PD T GM PD HM PD Avg_TE Figure 4. Average TE of eleven thousand problems. Figure 4 depicts results of the simulation study for TE for different PDRs which clearly show that maximum TE is observed when jobs are sequenced using SPT rule. Next to SPT rule is the HMPD and then the other PDRs follow. The decreasing order of the PDRs is SPT>HMPD>GMPD>PDT>FCFS> EDD>SLACK>CR. 4,83 6,69 6,26 5,51 3,64 6,79 6,87 6,74 0 1 2 3 4 5 6 7 8 FCFS SPT EDD SLACK CR PDT GMPD HMPD Avg_No_Early Figure 5. Average TNE of eleven thousand problems. The performance measure TNE is used to examine the count over all the parts which are completed on or before the DD. Figure 5 depicts the average value of the TNE for different PDRs obtained from simulation study. It is evident from Figure 5 that GMPD rule is better than other PDRs as the average value of TNE for this rule is maximum i.e. 6.87. The other two mean based PDRs i.e. PDT and HMPD come next to GMPD. The sequence of PDRs in decreasing order is GMPD>PDT>HMPD>SPT> EDD>SLACK>FCFS>CR. Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102 Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Ahmad et al. 98 http://creativecommons.org/licenses/by-nc-nd/4.0/ The results obtained from the simulation study show that no single rule gives the best results for all the performance measures. However, it is observed that the results derived from using mean based PDRs are best for a few performance measures and for others although the results are not the best but they are close to the best one. Thus, based on the results of the simulation study it is suggested that mean based PDRs should be used to obtain optimal results for all the performance measures. To investigate the effect of PDRs on all performance measures taken together, all PDRs are ranked separately based on the results of the simulation study. The ranking results for different PDRs with respect to the performance measures are shown in Table 6. Table 6. Ranking results for PDRs. PDR Rank based on performance measures Average RankTFT TL TNL TE TNE FCFS 7 8 7 5 7 6.8 SPT 1 5 4 1 4 3 EDD 5 3 5 6 5 4.8 SLACK 6 7 6 7 6 6.4 CR 8 6 8 8 8 7.6 PDT 4 1 2 4 2 2.6 GMPD 3 2 1 3 1 2 HMPD 2 4 3 2 3 2.8 It is evident from Table 6 that average rank of the mean based PDRs i.e. GMPD, PDT, and HMPD is higher than other PDRs. Further, among the three mean based PDRs, the proposed GMPD rule is found to be the best (as its average rank is 2) followed by PDT and HMPD for achieving optimal results for multiple performance measures. Thus, the proposed GMPD rule is the most promising rule as compared to other PDRs and it should be implemented to obtain compromised or optimal results for multiple performance measures of single machine scheduling problems. Next to GMPD is the PDT and then HMPD and therefore, it is found that mean based PDRs perform better as far as scheduling of jobs on a single machine is concerned. 5. Weighted GMPD and HMPD rule It has been shown in the previous section that the PDRs based on three different strategies i.e. additive, multiplicative and reciprocal provides better results, in terms of the optimal performance measures of the system, as compared to other PDRs. It is realized that in these strategies, the weight component of both numbers is same. It is very likely that the weighted mean based PDRs where the weight components of the PT and DD of jobs are different may provide a better sequence of jobs and therefore, it is matter of investigation. Consequently, the performance of weighted form of PDT, GMPD, and HMPD is compared in this section. The weighted PT and DD (WPDT) rule has already been developed and reported in the literature (Hamidi, 2016). Hence, the weighted geometric mean of PT and DD (WGMPD) and weighted harmonic mean of PT and DD (WHMPD) rules are proposed in this work. The function used to determine the priority of the jobs using WPDT, WGMPD and WHMPD is given in Equation (6), Equation (7), and Equation (8) respectively. PDi=w · pti + (1–w)ddi (6) WGMi=ptiw · ddi1-w (7) WHM i 1 w pt i 1 w dd i (8) where, w represents weight A job with the least value of WGMi and WHMi is processed first when the priority is determined using WGMPD and WHMPD respectively. The motivation behind the development of weighted PDRs is to combine SPT and EDD rules to obtain optimal multiple performance measures. SPT and EDD rules have been considered as they possess advantage over other PDRs in terms of small flow times and reduced lateness respectively. Therefore, in this section, the weight used in WPDT, WGMPD, and WHMPS is varied from 0 to 1 with an increment of 0.1 and the values of two performance measures i.e. TFT and TL are compared. As the unit of measurement TFT and TL is different, it is necessary to normalize their values so as to bring their values on a common scale. Among the several methods of normalization, the min-max normalization method is used. The mathematical formula used in min-max normalization method is given in Equation (9). x i n x i min i x i max i x i min i x i (9) where, xi and xin represent the original and normalized value of the ith attribute. The normalized value of TFT and TL with varying weights for WPDT rule is shown in Figure 6. It Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Geometric and Harmonic means based priority dispatching rules for single machine scheduling problems 99 http://creativecommons.org/licenses/by-nc-nd/4.0/ may be noted that when the value of weight is 0, it represents EDD rule as the job sequencing is done based on DD only. When the weight is set at 1, job sequencing is done based on SPT rule and when the weight is 0.5 it represents PDT rule. It is evident from Figure 6 that for EDD rule (w = 0), the values of both performance measures i.e. TFT and TL are high which is not desirable. When w = 1 i.e.for SPT rule, value of TFT is minimum (almost zero) but the value of TL issignificantly high. Further, for PDT rule i.e. when w = 0.5, the value of TL is minimum, and also the value of TFT is smaller than that of EDD but higher than SPT. As the WPDT rule was developed with an aim to obtain optimal values of TFT and TL, the graph shown in Figure 6 supports the fact that WPDT rule can give optimal results for both the performance measures i.e. TFT and TL. It can also be observed from Figure 6 that better results can be obtained if a weight of 0.76 is considered in the WPDT as the two performance measures intersect at this point which suggests that their values are optimal. The normalized value of TFT and TL when weight is 0.76 is found to be 0.20. 0,0 0,2 0,4 0,6 0,8 1,0 1,2 ED D 0.1 0.2 0.3 0.4 PD T 0.6 0.7 0.8 0.9 SP T N or m al iz ed v al ue s TFT TL Figure 6. Variation in normalized values of TFT and TL with weight for WPDT rule. The variation of normalized values of TFT and TL for WGMPD with varying weights is shown in Figure 7. The pattern observed in this case is similar to that of the WPDT rule as shown in Figure 6. It can be seen from Figure 7 that for w = 0, TFT and TL values are high, but for SPT (w = 1), TFT value is minimum but TL value is reasonably high. For GMPD rule (w = 0.5), the values of TFT and TL are in between that of SPT and EDD. Further, intersection of TFT and TL is obtained when the weight of 0.37 is assigned. Hence, it can be concluded that for GMPD rule, the weight of 0.37 will result in optimal values of TFT and TL which is 0.16. 0,0 0,2 0,4 0,6 0,8 1,0 1,2 ED D 0.1 0.2 0.3 0.4 GM PD 0.6 0.7 0.8 0.9 SP T N or m al iz ed v al ue s TFT TL Figure 7. Variation in normalized values of TFT and TL with weight for WGMPD rule. Figure 8 shows variation in the values of TFT and TL with varying weights of WHPD rule. Once again, a similar pattern of variation as that of WPDT and WGMPD is observed in this case too. It is evident from Figure 8 that a weight of 0.105 results in the optimum values i.e. 0.135 of both TFT and TL as the two curves intersects at this point. 0,00 0,20 0,40 0,60 0,80 1,00 1,20 ED D 0.1 0.2 0.3 0.4 HM PD 0.6 0.7 0.8 0.9 SP T N or m al iz ed v al ue s TFT TL Figure 8. Variation in normalized values of TFT and TL with weight for WHMPD rule. From the analysis of the weight variation in the WPDT, WGMPD, and WHPD presented above, it is found that a weight of 0.76 used in the WPDT results in the optimum values of both TFT and TL which is 0.20. Further, a weight of 0.37 employed in the WGMPD rule and a weight of 0.105 used in the WHMPD rule leads to the optimum values of TFT and TL which are 0.16 and 0.135 respectively. Further, it is also found that among the three weighted mean based rules, WHMPD with a weight of 0.105 produces results better than WGMPD with the weight of 0.37 and WPDT with weight 0.76 as optimum values of TFT and TL are minimum i.e. 0.135. Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102 Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Ahmad et al. 100 http://creativecommons.org/licenses/by-nc-nd/4.0/ 6. Conclusion Scheduling is imperative in manufacturing systems as it directly affects the systems’ performance. For a single machine scheduling problem, priority dispatching rules are used to define the sequence of jobs to be processed as they help in enhancing the performance of the system. Among the standard PDRs i.e. FCFS, SPT, EDD, SLACK and CR, SPT performs better as far as minimum flow time is required and EDD rule is found to be promising for minimizing the lateness of the jobs. Further, it was realized that combining these rules might be able to perform better and hence, several combined rules were developed and proposed. However, it is found that most of these rules are based on the additive strategy. Therefore, an attempt was made in this study to examine the effectiveness of the combined rules based on the multiplicative and reciprocal strategy. In this regard two PDRs, first considering multiplicative strategy and second with the reciprocal strategy have been proposed in this work. The first rule named as geometric mean of PT and DD (GMPD) is based on multiplicative strategy and the other i.e. harmonic mean of PT and DD (HMPD) is based on reciprocal strategy. Five performance measures viz. Total flow time (TFT), Total Lateness (TL), Number of Late parts (TNL), Total Earliness (TE) and Number of Early parts (TNE) were used to examine the effectiveness of the proposed rules. This study demonstrates the application of heuristic and metaheuristic algorithms to deal with best PDR. The major conclusions drawn from the present work are as follows: - SPT rule is found to the best rule for minimizing the TFT of the jobs. - PDT rule performs better than other PDRs as far as minimum TL is required. - The proposed rule GMPD results in the least number of late parts compared to other PDRs. - For maximizing the total earliness, the SPT rule is found to give better results. - The maximum number of early parts is observed when the GMPD rule is used. - For optimal performance,it is found that PDRs based on different combination strategies, i.e. additive, multiplicative or reciprocal perform better than other PDRs. Further, among the three strategy based PDRs, GMPD rule performs better than others followed by PDT and HMPD. - In weighted PDRs, optimal values of multiple performance measures are found when a weight of 0.105 is used in WHMPD followed by WGMPD with a weight of 0.37 and WPDT with a weight of 0.76. The findings of this study suggest that GMPD rule is the best rule among the considered PDRs. However, there are shortcomings of this work which could be considered in future work. The comparison of the new rules has been done with six rules. However, there are various other rules which can also be compared to find the effectiveness of the proposed rules. Further, in this work the multiplicative strategy and reciprocal strategy were used to combine PT and DD which can also be used to combine process time and work content as done by Holthaus and Rajendran (1997). The results of the study are limited for a single machine scheduling problems. Hence, it can be extended further for multiple machines and flexible manufacturing systems. References Baharom, M.Z., Nazdah, W., Hussin, W. (2015). Scheduling Analysis for Job Sequencing in Veneer Lamination Line. Journal of Industrial and Intelligent Information, 3(3), 181-185. https://doi.org/10.12720/jiii.3.3.181-185 Chan, F.T.S., Chan, H.K., Lau, H.C.W., Ip, R.W.L. (2003). Analysis of dynamic dispatching rules for a flexible manufacturing system. Journal of Materials Processing Technology, 138(1), 325-331. https://doi.org/10.1016/S0924-0136(03)00093-1 Cheng, T.C.E., Kahlbacher, H.G. (1993). Single-machine scheduling to minimize earliness and number of tardy jobs. Journal of Optimization Theory and Applications, 77(3), 563-573. https://doi.org/10.1007/BF00940450 da Silva, N.C.O., Scarpin, C.T., Pécora, J.E., Ruiz, A. (2019). Online single machine scheduling with setup times depending on the jobs sequence. Computers & Industrial Engineering, 129, 251-258. https://doi.org/10.1016/j.cie.2019.01.038 Doh, H.H., Yu, J.M., Kim, J.S., Lee, D.H., Nam, S.H. (2013). A priority scheduling approach for flexible job shops with multiple process plans. International Journal of Production Research, 51(12), 3748-3764. https://doi.org/10.1080/00207543.2013.765074 Dominic, Panneer D.D., Kaliyamoorthy, S., Kumar, M.S. (2004). Efficient dispatching rules for dynamic job shop scheduling. The International Journal of Advanced Manufacturing Technology, 24(1), 70-75. https://doi.org/10.1007/s00170-002-1534-5 Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Geometric and Harmonic means based priority dispatching rules for single machine scheduling problems 101 https://doi.org/10.12720/jiii.3.3.181-185 https://doi.org/10.1016/S0924-0136(03)00093-1 https://doi.org/10.1007/BF00940450 https://doi.org/10.1016/j.cie.2019.01.038 https://doi.org/10.1080/00207543.2013.765074 https://doi.org/10.1007/s00170-002-1534-5 http://creativecommons.org/licenses/by-nc-nd/4.0/ Ðurasević, M., Jakobović, D. (2018). A survey of dispatching rules for the dynamic unrelated machines environment. Expert Systems with Applications, 113, 555-569. https://doi.org/10.1016/j.eswa.2018.06.053 Forrester, P. (2006). Operations Management: An Integrated Approach. International Journal of Operations & Production Management, 26(4), 449-450. https://doi.org/10.1108/01443570610650585 Geiger, C.D., Uzsoy, R. (2008). Learning effective dispatching rules for batch processor scheduling. International Journal of Production Research, 46(6), 1431-1454. https://doi.org/10.1080/00207540600993360 Hamidi, M. (2016). Two new sequencing rules for the non-preemptive single machine scheduling problem. The Journal of Business Inquiry, 15(2), 116-127. Holthaus, O., Rajendran, C. (1997). New dispatching rules for scheduling in a job shop —An experimental study. The International Journal of Advanced Manufacturing Technology, 13(2), 148-153. https://doi.org/10.1007/BF01225761 Hussain, M.S., Ali, M. (2019). A Multi-agent Based Dynamic Scheduling of Flexible Manufacturing Systems. Global Journal of Flexible Systems Management, 20(3), 267-290. https://doi.org/10.1007/s40171-019-00214-9 Jayamohan, M.S., Rajendran, C. (2000). New dispatching rules for shop scheduling: A step forward. International Journal of Production Research, 38(3), 563-586. https://doi.org/10.1080/002075400189301 Kadipasaoglu, S.N., Xiang, W., Khumawala, B.M. (1997). A comparison of sequencing rules in static and dynamic hybrid flow systems. International Journal of Production Research, 35(5), 1359-1384. https://doi.org/10.1080/002075497195371 Kanet, J.J., Li, X. (2004). A Weighted Modified Due Date Rule for Sequencing to Minimize Weighted Tardiness. Journal of Scheduling, 7(4), 261-276. https://doi.org/10.1023/B:JOSH.0000031421.64487.95 Lee, D.K., Shin, J.H., Lee, D.H. (2020). Operations scheduling for an advanced flexible manufacturing system with multi-fixturing pallets. Computers & Industrial Engineering, 144, 106496. https://doi.org/10.1016/j.cie.2020.106496 Lu, C.C., Lin, S.W., Ying, K.C. (2012). Robust scheduling on a single machine to minimize total flow time. Computers & Operations Research, 39(7), 1682-1691. https://doi.org/10.1016/j.cor.2011.10.003 Krishnan, M., Chinnusamy, T.R., Karthikeyan, T. (2012). Performance Study of Flexible Manufacturing System Scheduling Using Dispatching Rules in Dynamic Environment. Procedia Engineering, 38, 2793-2798. https://doi.org/10.1016/j.proeng.2012.06.327 Munir, E.U., Li, J., Shi, S., Zou, Z., Yang, D. (2008). MaxStd: A task scheduling heuristic for heterogeneous computing environment. Information Technology Journal, 7(4), 679-683. https://doi.org/10.3923/itj.2008.679.683 Oyetunji, E.O. (2009). Some common performance measures in scheduling problems. Research Journal of Applied Sciences, Engineering and Technology, 1(2), 6-9. Pinedo, M.L. (2009). Planning and Scheduling in Manufacturing and Services (2nd ed.). Springer-Verlag. https://doi.org/10.1007/978-1- 4419-0910-7 Prakash, A., Chan, F.T.S., Deshmukh, S.G. (2011). FMS scheduling with knowledge based genetic algorithm approach. Expert Systems with Applications, 38(4), 3161-3171. https://doi.org/10.1016/j.eswa.2010.09.002 Rafsanjani, M.K., Bardsiri, A.K. (2012). A New Heuristic Approach for Scheduling Independent Tasks on Heterogeneous Computing Systems. International Journal of Machine Learning and Computing, 371-376. https://doi.org/10.7763/IJMLC.2012.V2.147 Tyagi, N., Tripathi, R.P., Chandramouli, A.B. (2016). Single Machine Scheduling Model with Total Tardiness Problem. Indian Journal of Science and Technology, 9(37), 1-14. https://doi.org/10.17485/ijst/2016/v9i37/97527 Vinod, V., Sridharan, R. (2008). Dynamic job-shop scheduling with sequence-dependent setup times: Simulation modeling and analysis. The International Journal of Advanced Manufacturing Technology, 36(3), 355-372. https://doi.org/10.1007/s00170-006-0836-4 Waikar, A.M., Sarker, B.R., Lal, A.M. (1995). A comparative study of some priority dispatching rules under different shop loads. Production Planning & Control, 6(4), 301-310. https://doi.org/10.1080/09537289508930284 Int. J. Prod. Manag. Eng. (2021) 9(2), 93-102 Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International Ahmad et al. 102 https://doi.org/10.1016/j.eswa.2018.06.053 https://doi.org/10.1108/01443570610650585 https://doi.org/10.1080/00207540600993360 https://doi.org/10.1007/BF01225761 https://doi.org/10.1007/s40171-019-00214-9 https://doi.org/10.1080/002075400189301 https://doi.org/10.1080/002075497195371 https://doi.org/10.1023/B:JOSH.0000031421.64487.95 https://doi.org/10.1016/j.cie.2020.106496 https://doi.org/10.1016/j.cor.2011.10.003 https://doi.org/10.1016/j.proeng.2012.06.327 https://doi.org/10.3923/itj.2008.679.683 https://doi.org/10.1007/978-1-4419-0910-7 https://doi.org/10.1007/978-1-4419-0910-7 https://doi.org/10.1016/j.eswa.2010.09.002 https://doi.org/10.7763/IJMLC.2012.V2.147 https://doi.org/10.17485/ijst/2016/v9i37/97527 https://doi.org/10.1007/s00170-006-0836-4 https://doi.org/10.1080/09537289508930284 http://creativecommons.org/licenses/by-nc-nd/4.0/