Total views : 628

Single Machine Scheduling Model for Total Weighted Tardiness


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


Objectives: We proposed two heuristic algorithms for Total Weighted Due Date Tardiness Scheduling (TWDDTS). The main aim of this paper is to optimize the weighted tardiness based criteria. Methods/Statistical Analysis: The first one heuristic algorithm for 'TWDDTS' is based on dispatching rule (EDD-Earliest Due Date) and the second one heuristic algorithm for Modified Total Weighted Due Date Tardiness Scheduling (MTWDDTS) is based on modified weighed due dates. We equated the effectiveness of both the proposed heuristic algorithms with the help of numerical illustrations. Findings: The main aim to propose these heuristic algorithms is to obtain the optimal solution of the problem related to weighted tardiness scheduling based criteria, when processing times of the jobs are also associated with probabilities. These heuristic algorithms are justified by numerical illustrations and comparative study of both the heuristic algorithms (with the help of numerical example) show that an improved heuristic algorithm for MTWDDTS is outperform and give better results than a TWDDTS heuristic algorithm. We also found that when we measure the mean completion time of jobs by both the heuristic algorithms then we observed that the MTWDDTS heuristic algorithm gives the best result as compared to a TWDDTS heuristic algorithm. So we find that MTWDDTS gives the best result for minimization the weighted tardiness based criteria as well as makespan. Application/Improvements: The proposed MTWDDTS algorithm is more useful than the EDD dispatching rule for weighted tardiness based scheduling problems. It is easy to understand and provide an important tool for decision makers.


EDD Dispatching Rule, Modified Weighted Due Dates (MWDD), Single Machine Scheduling, Stochastic Processing Time, Weighted Tardiness.

Full Text:

 |  (PDF views: 422)


  • Tyagi N, Abedi M, Varshney RG. A preemptive scheduling and due date assignment for single-machine in batch delivery system. Proceeding of CACCS; India. 2013. p. 60–4.
  • Davis JS, Kanet JJ. Single-machine scheduling with early and tardy completion costs. Nav Res Logi. 1993; 40(1):85– 101.
  • 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. University of California at Los Angeles: Manag Sci Res Project; 1955.
  • Emmons H. One machine sequencing to minimize certain functions of job tardiness. Oper Res. 1955; 17:701–15.
  • Rinnooy Kan AHG, Lageweg BJ, Lenstra JK. Minimizing total costs in one machine scheduling. Oper Res. 1975; 23:908–27.
  • Karp RM. Reducibility among combinatorial problems. Complexity Computers Computations. New York: Plenum Press; 1972. p. 83–103.
  • Lenstra JK, Rinnooy Kan AHG, Brucker P. Complexity of machine scheduling problems. Annals of Discrete Mathematics. 1977; 1:343–62.
  • Lawler EL. A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics. 1977; 1:331–42.
  • Baker KR. Introduction to Sequencing and Scheduling. New York: Wiley; 1974.
  • Baker KR, Scudder GD. Sequencing with earliness and tardiness penalties - A review. Oper Res. 1990; 38 (1):22–36.
  • Gordon V, Proth JM, Chu CB. A survey of the state-of-theart of common due date assignment and scheduling research. Eur J of Oper Res. 2002; 139(1):1–25.
  • Wilkerson LJ, Irwin JD. An improved algorithm for scheduling independent tasks. AIIE Transactions. 1971; 3:239– 45.
  • 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.
  • Alidaee B, Rosa D. Scheduling parallel machines to minimize total weighted and unweighted tardiness. Comp and Oper Res.1997; 24:775–88.
  • Panneerselvam R. Modeling the single machine scheduling problem to minimize total tardiness and weighted total tardiness. Int J Manage Syst. 1991; 7(1):37–48.
  • Kanet J, Li X. A weighted modified due date rule for sequencing to minimize weighted tardiness. J of Scheduling. 2004; 7:261–76.
  • Franca PM, Mendes A, Moscato P. A memetic algorithm for the Total Tardiness Single Machine Scheduling Problem. Eur J of Oper Res. 2001; 132(1):224–42.
  • Vahid MD. A simulated annealing algorithm for JIT Single Machine Scheduling with Preemption and Machine Idle Time. Indian J of Sci and Tech. 2011; 4(5):502–8.
  • Maheswaran R, Ponnambalam SG, Aravindan C. A metaheuristic approach to single machine scheduling problems. The Int J of Adv Manufacturing Techn. 2005; 25:772– 6.
  • Forst FG. Bicriterion stochastic scheduling on one or more machines. Eur J of Oper Res. 1995; 80:404–9.
  • Belouadah H, Posner M, Potts C. Scheduling with release dates on a Single Machine to Minimize Total Weighted Completion Time. Discrete Appl Math. 1992; 36:213–31.


  • There are currently no refbacks.

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