Indian Journal of Science and Technology

Abstract

Objectives: In this paper, Five Dispatching Rules and a Branch & Bound algorithm is introduced for Single Machine Total Tardiness Scheduling Problem (SMTTSP) to minimize the total (average) tardiness and number of tardy jobs. Methods/ Statistical Analysis: We proposed five dispatching (priority) rules as Shortest Processing Time, Earliest Due Dates, Longest Processing Time, Minimum Slack Time and First Come First Serve for SMTTSP and compared the performance of all the proposed priority rules. Furthermore, a numerical illustrations is also provided to select the best dispatched rule of SMTTSP. Next, we developed a Branch & Bound Algorithm for SMTTSP using best selected dispatching rule. We also developed Branch Tree to understand the Lower bound process of the B& B Algorithm. Findings: The main aim to proposed these dispatching rules and a Branch and Bound Algorithm is to obtain the optimal sequence to optimize the total (average) tardiness and number of total tardy jobs. The comparative analysis of the dispatching rules shows that EDD rule is better than other dispatching rules for minimization of total tardy jobs and tardiness of the jobs while SPT rule is better for minimization of make span. But Dispatching rules do not have the guarantee to give an optimal solution. So in this study, an exact algorithm (Branch & Bound) was developed with EDD rule for finding the optimal solution for SMTTSP. The comparative study between dispatching rules and an exact (B&B) algorithm is being justified by numerical illustrations and we found that the EDD rule and B&B Algorithm give the same results. Hence it was concluded that EDD rule works as an Exact algorithm and gives the optimal solution for SMTTSP. Application/Improvements: The computational results of the proposed (B&B) algorithm and Dispatching rules show that our methodology is more useful than other optimal approach for SMTTSP and it provides an important tool for decision makers.
Keywords: Average Completion Time, (Average) Tardiness of Jobs, Branch and Bound Algorithm, Branch Tree, No of Tardy Jobs, Single Machine Scheduling