Some Properties of the Optimal Decomposition Conditions for the Single Machine Tardiness Problem
DOI:
https://doi.org/10.33423/ajm.v24i2.7107Keywords:
management, tardiness, decomposition, optimal algorithm, machine schedulingAbstract
We consider the well-known optimal decomposition algorithm for the tardiness problem. The algorithm presents conditions which determine the positions a job could occupy in an optimal sequence. This resulted in optimal solutions for up to 100 jobs. We analyze these conditions and present simplified conditions. We then study a more recent Rule which when combined with these conditions resulted in optimal solutions for up to 500 jobs. We present several properties under which this recent rule is satisfied. We provide mathematical proofs for our properties. We believe that our study will enable more theoretical research in this field and will eventually enable optimal solutions for very large job sets.
References
Bouska, M., Sucha, P., Novak, A., & Hanzalek, Z. (2023). Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness. European Journal of Operational Research, 308, 990–1006.
Du, J., & Leung, J.Y.-T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15, 483–495.
Koulamas, C. (2010). The single-machine total tardiness problem: Review and extensions. European Journal of Operational Research, 202, 1–7.
Lawler, E.L. (1977). A ‘pseudo-polynomial’ algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342.
Naidu, J. (2003). A note on a well-known dispatching rule to minimize total tardiness. Omega - The International Journal of Management Science, 31, 137–140.
Naidu, J. (2011). A new algorithm for a special structure of the single machine tardiness problem. AIMS International Journal of Management, 5(1), 21–34.
Naidu, J.T., Gupta, J.N.D., & Alidaee, B. (2002). Insights into two solution procedures for the single machine tardiness problem. Journal of the Operational Research Society, 53, 800–806.
Potts, C.N., & Van Wassenhove, L.N. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 1, 177–181.
Szwarc, W. (1993). Single machine total tardiness problem revisited. In Y. Ijiri (Ed.), Creative and Innovative Approaches to the Science of Management (pp. 407–419). Quorum Books.
Szwarc, W., & Mukhopadhyay, S.K. (1996). Decomposition of the single machine total tardiness problem. Operations Research Letters, 19, 243–250.
