This scheduling model is derived from the real problem of
scheduling looms in a textile industry. Jobs may be independently
split over several specified machines and preemption is allowed. Deadlines are
specified for each job and jobs are assumed to be available.
It is shown that minimizing maximum weighted tardiness can be done in
polynomial time. The case of uniform machines (as in the
considered application) can be modeled as a network flow and minimization of
maximum tardiness can be done in strongly polynomial time. The case of unrelated
machines can be solved either by generalized flow techniques or by Linear
Programming. Attention is also focused on the problem of finding so-called
Unordered Lexico Optima, in order to schedule non-binding jobs as early as
possible.
