SCHEDULING JOBS ON SEVERAL MACHINES WITH THE JOB SPLITTING PROPERTY

This scheduling model is derived from the real problem of scheduling l ooms in a textile industry. Jobs may be independently split. over seve ral specified machines, and preemption is allowed. Deadlines are speci fied for each job, and jobs are assumed to be available. It is shown t hat minimizing maximum weighted tardiness can be done in polynomial ti me. The case of uniform machines (as in the considered application) ca n be modeled as a network flow, and minimization of maximum tardiness can be done in strongly polynomial time. The case of unrelated machine s can be solved either by generalized flow techniques or by Linear Pro gramming. Attention is also focused on the problem of finding so-calle d Unordered Lexico Optima, in order to schedule nonbinding jobs as ear ly as possible.