This　paper　studies　a　robust　(min-max　regret)　single　machine　scheduling　problem　with　uncertain　processing　times　represented　by　interval　data.　The　objective　is　to　obtain　robust　sequences　of　jobs　that　minimize　the　absolute　deviation　of　total　tardiness　from　the　optimal　solution　under　the　worst-case　scenario.　The　problem　is　first　formulated　as　a　mixed-integer　linear　programming　(MILP)　model　and　assuming　that　the　corresponding　deterministic　NP-hard　problem　for　the　mid-point　scenario　can　be　solved　optimally,　an　optimal　schedule　under　the　mid-point　scenario　is　then　proved　to　be　a　2-approximation　solution　to　the　problem.　Next,　the　worst-case　scenarios　are　proved　to　be　not　necessarily　at　the　upper　or　lower　limits　of　the　interval　processing　times.　Utilizing　these　results,　a　2-approximation　algorithm　(2AA),　a　worst-case　scenario-based　heuristic　(WSH),　and　an　approximate　worst-case-based　heuristic　(AWH)　are　proposed　and　empirically　evaluated,　in　which　an　iterative　procedure　for　evaluating　the　maximum　regret　of　a　solution　is　integrated.　Finally,　the　paper　is　concluded　by　suggesting　some　fruitful　directions　for　future　research　in　this　area.