Dyeing　is　the　most　time　and　energy-consuming　process　in　textile　production.　Motivated　by　a　dyeing　overdue　problem　in　a　lace　textile　factory,　we　study　a　parallel　machine　scheduling　problem　with　different　colour　families,　sequence-dependent　setup　times,　and　machine　eligibility　restriction.　An　integer　programming　model　is　formulated　to　minimise　the　total　tardiness.　Given　that　the　dyeing　optimisation　problem　is　strongly　NP-hard,　a　hybrid　differential　evolution　(HDE)　algorithm　embedded　with　chaos　theory　and　two　local　search　algorithms　is　proposed　to　solve　real-world　instances　from　the　textile　factory.　In　our　proposed　algorithm,　a　special　encoding　and　decoding　scheme　is　designed　to　deal　with　the　machine　eligibility　constraint,　and　chaos　theory　is　adopted　to　determine　the　parameter　settings　of　the　underlying　differential　evolution　(DE)　algorithm.　To　speed　up　convergence　and　improve　search　exploitation,　two　local　search　algorithms　inspired　by　two　dominance　properties　are　developed　to　determine　the　optimal　job　sequence　for　parallel　machines,　such　that　the　decision　of　the　entire　problem　is　simplified　to　the　assignment　of　jobs　among　the　machines,　and　the　computational　time　required　is　significantly　reduced.　Comprehensive　experiments　based　on　36　synthetically　generated　small　to　large-scale　problem　instances　and　20　real-world　industrial　data　sets　confirm　the　efficacy　of　our　proposed　HDE　over　other　DE　variants.