Total views : 562

Single Machine Scheduling Model with Total Tardiness Problem


  • Department of Mathematics, Graphic Era University, Dehradun - 248002, Uttarakhand, India
  • Department of Mathematics, Meerut College, Meerut - 250001, Uttar Pradesh, India


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.


Average Completion Time, (Average) Tardiness of Jobs, Branch and Bound Algorithm, Branch Tree, No of Tardy Jobs, Single Machine Scheduling.

Full Text:

 |  (PDF views: 332)


  • Sen T, Gupta SK. A state-of-art survey of static scheduling research involving due dates. OMEGA. The Int J of Manag Sci. 1984; 12(1):63–76.
  • Abdul-Razaq TS, Potts CN, Van WLN. A survey of algorithms for the single machine total weighted tardiness problem. Discrete Appl Math. 1990; 26:235–53
  • Koulamas C. The total tardiness problem: review and extensions. Oper Res. 1994; 42(6):1025–41.
  • Tyagi N, Abedi M, Varshney RG. 2013. A preemptive scheduling and due date assignment for single-machine in batch delivery system. Proceeding of CACCS, India. 2013; 60–4.
  • Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG. Optimization and approximating in deterministic sequencing and scheduling: A survey. Ann Discrete Math. 1979; 4:287–326.
  • Jackson JR. Scheduling a production to minimize maximum tardiness. Research Report 43, Manag Sci Res Project, University of California at Los Angeles. 1955
  • Haupt R. A Survey of Priority Rule-Based Scheduling. OR Spectgrum. 1989; 11(3):3–16.
  • Chiang TC, Fu LC. Using dispatching rules for job shop scheduling with due date-based objectives. Int J of Pro Res. 2007; 45(14):3245–62.
  • Naughton MR. Scheduling with deadlines and loss functions. Mngt Sci. 1959; 6(1): 1–12.
  • Conway RW. Priority dispatching and job lateness in a job shop. J of Ind Eng. 1965; 16(5):228–37.
  • Baker KR. Introduction to Sequencing and Scheduling. Wiley: New York. 1974.
  • Morton TE, Pentico DW. Heuristic Scheduling Systems. John Wiley and Sons. New York, NY. 1993.
  • Du J, Leung JY-T. Minimizing total tardiness on one machine is NP-hard. Math of Oper Res. 1990; 15(3):483–95.
  • Moore JM. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Mngt Sci. 1968; 15(6):102–9.
  • Emmons H. One machine sequencing to minimize certain functions of job tardiness. Oper Res. 1955; 17:701–15.
  • Land AH, Doig G. An automatic method of solving discrete programming problems. ECONOMETRICA. 1960; 28(3): 497–520.
  • Brown APG, Lomnicki ZA. Some applications of the branch and bound algorithm to the machine scheduling problem. Oper Res Quarterly. 1966; 17(2):173–80.
  • Potts CN, Wassenhove VLN. A decomposition algorithm for the single machine total tardiness problem. Oper Res Letters. 1982; 1(1):177–81.
  • Chu C. A branch-and-bound algorithm to minimize total tardiness with different due dates. Navl Res Logi. 1992; 39(9):265–83.
  • Hirakawa Y. A quick optimal algorithm for sequencing on one machine to minimize total tardiness. Int J Prod Econ. 1999; 549–55.
  • Kondakci S, Kirca O, Azizoglu M. An efficient algorithm for the single machine tardiness problem. Int J of Pro Eco. 1994; 36(2):213–9.
  • Biskup D, Piewitt W. A note on An efficient algorithm for the single machine tardiness problem. Int J of Prod Eco. 2000; 66(3):287–92.
  • Szwarc W, Croce DF, Grosso A. Solution of the single-machine total tardiness problem. J of Scheduling. 1999; 26(2-3):55–71.
  • Szwarc W, Grosso A, Croce F. Algorithmic paradoxes of the single machine total tardiness problem. J of Scheduling. 2001; 4(2):93–104.
  • Tansel BC, Kara BY, Sabuncuoglu I. An efficient algorithm for the single machine total tardiness problem. IIE Transactions. 2001; 33(8):661–74.
  • Baker KR, Scudder GD. Sequencing with earliness and tardiness penalties- A review. Oper Res. 1990; 38(1):22–36
  • Tian ZJ. On the single machine total tardiness problem. Eur J of Oper Res. 2005; 59(3):843–6.
  • Koulamas C, Kyparisis GJ. Single machine scheduling with release times, deadlines and tardiness objectives. Eur J of Oper Rese. 2001; 133(1):447–53.
  • Baptiste P. Scheduling equal-length jobs on identical parallel machines, Discrete Appl Math. 2000; 103(1): 21–32.
  • Koulamas C. The single machine total tardiness scheduling problem: Review and extensions. Eur J of Oper Res. 2010; 202(1): 1–7.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.