Effective heuristics for solving dynamic variant of single processor total tardiness problems

Abstract: This paper considers the dynamic variant of single processor scheduling problem of minimizing total tardiness. In practice, it occurs when minimizing tardiness penalty. The problem is NP-hard; thus two heuristics were proposed. The utility of the proposed models was demonstrated through computational experiments and comparative analyses against existing solution methods and the Branch and Bound (BB) method. The results show that the proposed models yield effi-cient solutions and in most cases perform effectively better than the existing heuristics in the lit-erature.

How to cite this paper

 Akande, S., Oluleye, A & Oyetunji, E. (2018). Effective heuristics for solving dynamic variant of single processor total tardiness problems.Journal of Project Management, 3(1), 13-22.

Refrences

Anderson, E. J., & Nyirenda, J. C. (1990). Two new rules to minimize tardiness in a job shop. The International Journal of Production Research, 28(12), 2277-2292.
Baptiste, P., Carlier, J., & Jouglet, A. (2004). A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates. European Journal of Operational Research, 158(3), 595-608.
Bean, J.C., & Hall, D.H. (1985). Accuracy of the modified due date rule. Technical Report 85-10, Department of Industrial and Production Engineering, Michigan University. 1-7.
Baker, K. R., & Bertrand, J. W. M. (1982). A dynamic priority rule for scheduling against due-dates. Journal of Operations Management, 3(1), 37-42.
Baker, K. R., & Trietsch, D. (2013). Principles of sequencing and scheduling. John Wiley & Sons.
Chu, C., & Portmann, M.C. (1992). Some new eﬃcient methods to solve the 1/ri/ ∑_(i=1)^n▒T_i (min) scheduling problem. European Journal of Operational Research, 58, 404–413.
Chu, C. (1992). A branch‐and‐bound algorithm to minimize total flow time with unequal release dates. Naval Research Logistics (NRL), 39(6), 859-875.
Du, J., & Leung, J. Y. T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of operations research, 15(3), 483-495.
Erenay, F. S., Sabuncuoglu, I., Toptal, A., & Tiwari, M. K. (2010). New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs. European Journal of Operational Research, 201(1), 89-98.
French, S. (1982). Sequencing and Scheduling, 1st ed. Ellis USA: Horwood Limited.
Hahn, B., & Valentine, D. T. (2016). Essential MATLAB for engineers and scientists. Academic Press.
Kanet, J. J., & Hayya, J. C. (1982). Priority dispatching with operation due dates in a job shop. Journal of operations Management, 2(3), 167-175.
Muhlemann, A.P., Lockett, A. G., and. Farn, C. I. (1982). Job shop scheduling heuristics and frequency of scheduling. International Journal of Production Research, 20(2), 227–241.
Oyawale, F. A. (2006). Statistical methods: An introduction.1st ed. Nigeria: International Publisher Ltd.
Oyetunji, E.O. (2009). Some common performance measures in scheduling problems. Research Journal of Applied Science, Engineering and Technology, 1(2), 6-9.
Pinedo, M.L., (2008). Scheduling – Theory, Algorithms and Systems.1st ed. New York : Springer.
Naidu, J. T. (2003). A note on a well-known dispatching rule to minimize total tardiness. Omega, 31(2), 137-140.
Süer, G. A., Yang, X., Alhawari, O. I., Santos, J., & Vazquez, R. (2012). A genetic algorithm approach for minimizing total tardiness in single machine scheduling. International Journal of Industrial Engineering and Management (IJIEM), 3(3), 163-171.