Subscribe Now Subscribe Today
Research Article

Mixed Dispatch Rule for Single Machine Total Weighted Tardiness Problem

Aihua Yin and Jing Wang
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

The single machine total weighted tardiness scheduling problem has been discussed for many years and several effective constructive algorithms have been presented in literatures. The methods for solving this problem are applied among manufacture and logistics fields. This study proposes a quite new constructive algorithm, the Mixed Dispatch Rule (MDR) for solving the problem effectively and efficiently. What the mixed dispatch rule differs from the other dispatch rules is that it takes advantage of not only the jobs’ characters values, such as, process time, due date and the weight but also the values of the objective function for different choices of some job. In fact, in according with the process order of the jobs, at any moment, the status of the unprocessed jobs may be different, i.e., some of them are delayed but others aren’t. So, the characters of these two sorts of jobs are quite different and combining those characters with the objective function’s value can obtain effective dispatch rule. The computing experiment is based on those instances in the classic OR-Library and the computational results show that the algorithm, MDR, is effective and efficient.

Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

Aihua Yin and Jing Wang, 2013. Mixed Dispatch Rule for Single Machine Total Weighted Tardiness Problem. Journal of Applied Sciences, 13: 4616-4619.

DOI: 10.3923/jas.2013.4616.4619

Received: August 03, 2013; Accepted: November 06, 2013; Published: November 12, 2013


1:  Avci, S., M.S. Akturk and R.H. Storer, 2003. A problem space algorithm for single machine weighted tardiness problems. IIE Trans., 35: 479-486.
CrossRef  |  

2:  Bilge, U., M. Kurtulan and F. Kirac, 2007. A tabu search algorithm for the single machine total weighted tardiness problem. Eur. J. Oper. Res., 176: 1423-1435.
CrossRef  |  

3:  Ergun, O. and J.B. Orlin, 2006. Fast neighborhood search for the single machine total weighted tardiness problem. Oper. Res. Lett., 34: 41-45.
CrossRef  |  

4:  Kanet, J.J. and X. Li, 2004. A weighted modified due date rule for sequencing to minimize weighted tardiness. J. Scheduling, 7: 261-276.
CrossRef  |  

5:  Lenstra, J.K., A.H.G. Rinnooy Kan and P. Brucker, 1977. Complexity of machine scheduling problems. Ann. Discrete Math., 1: 343-362.
CrossRef  |  Direct Link  |  

6:  Maheswaran, R. and S.G. Ponnambalan, 2003. An investigation on single machine total weighted tardiness scheduling problems. Int. J. Adv. Manuf. Technol., 22: 243-248.
CrossRef  |  Direct Link  |  

7:  Mason, S.J., J.W. Fowler and W. Matthew Carlyle, 2002. A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops. J. Scheduling, 5: 247-262.
CrossRef  |  Direct Link  |  

8:  Nearchou, A.C., 2004. Solving the single machine total weighted tardiness scheduling problem using a hybrid simulated annealing algorithm. Proceedings of the 2nd IEEE International Conference on Industrial Informatics, June 26, 2004, Berlin, Germany, pp: 513-516
CrossRef  |  

9:  Potts, C.N. and L.N. Van Wassenhove, 1985. A branch and bound algorithm for the total weighted tardiness problem. Oper. Res., 33: 363-377.
CrossRef  |  Direct Link  |  

10:  Smith, W.E., 1956. Various optimizers for single-stage production. Nav. Res. Logist. Q., 3: 59-66.
CrossRef  |  

11:  Vepsalainen, A.P.J. and T.E. Morton, 1987. Priority rules for job shops with weighted tardiness costs. Manage. Sci., 33: 1035-1047.
Direct Link  |  

12:  Yoon, S.H. and I.S. Lee, 2011. New constructive heuristics for the total weighted tardiness problem. J. Oper. Res. Soc., 62: 232-237.
CrossRef  |  

©  2022 Science Alert. All Rights Reserved