Scheduling Jobs on Several Machines with the Job Splitting Property
Operations Research · 1996 · Volume 44 · Issue 4
Abstract
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 nonbinding jobs as early as possible.
Keywords
industries, textiles, model for loom scheduling, network flow algorithms, application to scheduling, scheduling, sequencing multiple machines, application in textile industry
Enable JavaScript for citation tools and additional paper interactions.