Production scheduling problems in a textile industry

In this paper scheduling problems arising in a textile industry are analysed. The maximum tardiness is taken as an objective function. Bounds on the optimal solutions are derived in the general case; the worst-case behaviour of approximate algorithms is investigated in case of uniform looms and a polynomial algorithm is presented for the case of equal looms with identical deadlines. Finally an LP-based heuristic is presented for the general case.